Distributed Algorithms for Topic Models with Applications to Streaming Document Data and Cancer Genomics

越来越需要分析和组织大量电子信息的方法，例如关于某些科学领域或某些医学问题的论文集，或纽约时报的新闻文章集。 传统的基于关键字的搜索速度非常快，但有重要的缺陷。 假设我们有兴趣搜索有关心脏病发作的文章。 使用关键词“心脏病发作”进行搜索不会返回使用“心肌梗死”（心脏病发作的医学术语）的文章。 一个更新和更强大的方法来分析和组织大量的电子文档和文档检索是通过使用所谓的主题模型。 这些模型的工作原理是识别集合中的隐藏主题（在纽约时报的例子中，这些主题可能是体育、世界事件、政治等）。 并且还通过识别每个文档处理的主题。 到目前为止，最常用的主题模型是所谓的潜在狄利克雷分配（LDA）模型。 不幸的是，所有精确的实现都很慢：算法按某种顺序列出所有文档中的所有单词，然后对每个单词进行计算。 这是按顺序进行的：在所有先前单词的计算完成之前，不能对给定单词进行计算。 该项目将开发一类并行工作的算法，利用现在多核平台上可用的大规模分布式计算。 因此，例如，如果有1000个处理器可用，这些算法的工作速度比现有算法快1000倍。 这些新算法将使LDA模型能够用于非常大的文档集合。 主题可用于将文档分组。然而，在其核心，LDA是一个“多会员模式”：纽约时报的一篇关于NFL足球运动员跪在国歌属于体育部分，也在政治部分。 多成员模型出现在文档检索和分类以外的领域。 例如，在癌症基因组学中，肿瘤可能被分类为几种癌症亚型的成员。 该项目将开发其他多成员模型，旨在处理非文本数据，如上面的癌症基因组学示例，并将开发并行算法来处理这些模型。 LDA和其他多成员模型本质上是贝叶斯模型，其中每个文档的主题和主题成员是未知参数。 后验分布通常由马尔可夫链蒙特卡罗估计，它已经证明了收敛保证。 该项目将开发分组吉布斯采样器，更新组中的变量，其中一个组中的所有变量可以同时更新。 该项目还将开发实用的收敛诊断和新算法收敛速度的理论结果。 理论结果将使用户能够确定马尔可夫链需要运行多长时间，以提供所需的准确度。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

There is a growing need for methods that analyze and organize large collections of electronic information, for example a collection of papers on some scientific field, or on some medical question, or a collection of news articles in the New York Times. Traditional keyword-based searches are very fast but have important deficiencies. Suppose we are interested in searching for articles that deal with heart attacks. A search using the keywords "heart attack" will not return articles that use "myocardial infarction", the medical term for "heart attack". A newer and more powerful approach to the analysis and organization of large collections of electronic documents and for document retrieval is through the use of so-called topic models. These models work by identifying the hidden topics in the collection (in the New York Times example, these might be Sports, World Events, Politics, etc.) and by also identifying the topics that each document deals with. By far the most commonly used topic model is the so-called Latent Dirichlet Allocation (LDA) model. Unfortunately, all accurate implementations are slow: the algorithms list all the words in all the documents in some order, and then carry out a calculation for each word. This is done sequentially: the calculation for a given word cannot be carried out before the calculations for all previous words have been completed. This project will develop a class of algorithms that work in parallel, taking advantage of the massive distributed computation that is now available on multi-core platforms. Thus, for example, if 1000 processors are available, these algorithms work 1000 times faster than existing algorithms. These new algorithms will enable the use of the LDA model on very large collections of documents. Topics can be used to cluster documents into groups. However, at its core, LDA is a "multi membership model": a New York Times article about NFL football players kneeling at the national anthem belongs in the Sports section, and also in the Politics section. Multi-membership models arise in areas other than document retrieval and classification. For example, in cancer genomics, tumors can be potentially classified as members of several cancer subtypes. This project will develop other multi-membership models, designed to handle non-textual data, as in the cancer genomics example above, and it will develop parallel algorithms to handle these models. The output of this project will enable researchers to handle massive collections of documents and medical data.LDA and other multi-membership models are inherently Bayesian models, in which topics and topic memberships for each document are unknown parameters. Posterior distributions are generally estimated by Markov chain Monte Carlo, which has proven convergence guarantees. This project will develop grouped Gibbs samplers which update variables in groups, where all the variables within a group can be updated simultaneously. The project will also develop practical convergence diagnostics and also theoretical results on the rates of convergence of the new algorithms. The theoretical results will enable the user to determine how long the Markov chains need to be run in order to provide a required level of accuracy.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.