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

University Of Florida, Gainesville FL

Investigators

Abstract

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.