一种基于共享内存的快速并行主题建模算法

摘要

随着互联网的快速发展，对非结构化数据处理的时效性要求逐渐变高，并行化的主题建模是一种能够有效的快速处理非结构化数据的方法。潜在狄利克雷分配（Latent Dirichlet Allocation，LDA）是一种常用的概率主题模型，它能够通过获取文档在主题空间的低维表示来实现文档的分析。但是并行LDA模型在处理大规模数据时面临两大问题：一是对于已有的LDA近似推理算法，都存在着相应的缺点使其难以被应用于大规模数据的处理与分析。信息传播算法虽然在收敛速度以及计算复杂度上都具有一定的优势，但其空间复杂度过大，使其无法在大数据处理上得到很好的应用；二是现有基于共享内存并未很好的解决线程之间的阻塞问题，线程阻塞大大降低了并行LDA算法效率。如何改进已有LDA算法中近似推理方法以避免其在大规模数据处理中的缺陷，以及如何有效减少共享内存并行算法中线程阻塞时间，从而实现一种更实用和高效的基于共享内存的并行LDA算法是一件非常有挑战性的工作。
　　基于传统信息传播算法的空间复杂度较大的问题，本文通过从最大化期望（Expectation Maximization，EM）的角度对信息传播算法进行重新解释，提出了一种新的参数更新方法（Expectation-maximization Belief Propagation，EBP）。这种更新方式不再需要剔除信息矩阵本身信息，能够避开统计过程中的信息存储问题，从而极大地减少信息传播算法中的空间复杂度。
　　基于传统共享内存的并行LDA算法无法有效利用线程的计算资源，经常会导致线程阻塞问题。本文提出了一种基于共享内存的动态调度并行方法，能够将算法并行的过程看成是一个为线程分配工作的过程，通过动态的为线程分配任务，实现了线程间无等待的动态调度，改善了传统共享内存并行算法中的线程等待问题。通过将改进的信息传播算法与改进的并行算法结合实现了一种基于共享内存的快速并行主题建模算法（Parallel Expectation-maximization Belief Propagation，PEBP）。
　　实验结果表明，EBP算法在混淆度与收敛速度方面的性能接近基于传统近似推理算法的LDA模型。此外，相对于一般的基于共享内存的并行方法，PEBP具有更好的加速比以及纵向扩展比，在混淆度以及收敛速度方面同样具有明显的优势。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景与意义

1.2 国内外研究现状

1.3 目前存在的主要问题

1.4 本文主要工作及创新点

1.5 本文的组织结构

第二章 主题模型及相关并行算法概述

2.1 主题模型概述

2.2 LDA近似推理算法概述

2.3 LDA并行算法概述

2.4 本章小结

第三章 基于最大期望的信息传播算法――EBP

3.1 LDA中的EM推断

3.2 EBP的推导与收敛证明

3.3 EBP与BP的比较

3.4 本章小结

第四章 快速并行LDA算法――PEBP

4.1 传统的基于共享内存的并行LDA算法

4.2 高效并行算法的实现

4.3 PEBP算法的实现

4.4 本章小结

第五章 算法综合实验

5.1 模型评价标准

5.2 实验准备

5.3 结果与分析

5.4 本章小结

第六章 总结与展望

6.1 工作总结

6.2 工作展望

参考文献

发表文章目录及参加科研项目

致谢