Fast collapsed gibbs sampling for latent dirichlet allocation

By Ian R. Porteous, David Newman, A. Ihler, Arthur U. Asuncion, Padhraic Smyth, Max Welling. Knowledge Discovery and Data Mining, 2008

627 citations recorded by the source corpus.

In this paper we introduce a novel collapsed Gibbs sampling method for the widely used latent Dirichlet allocation (LDA) model. Our new method results in significant speedups on real world text corpora. Conventional Gibbs sampling schemes for LDA require O(K) operations per sample where K is the number of topics in the model. Our proposed method draws equivalent samples but requires on average significantly less then K operations per sample. On real-word corpora FastLDA can be as much as 8 times faster than the standard collapsed Gibbs sampler for LDA. No approximations are necessary, and we show that our fast sampling scheme produces exactly the same results as the standard (but slower) sampling scheme. Experiments on four real world data sets demonstrate speedups for a wide range of collection sizes. For the PubMed collection of over 8 million documents with a required computation time of 6 CPU months for LDA, our speedup of 5.7 can save 5 CPU months of computation.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/6ae5d06fd366d44107752b903d0ec22b41321e3d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Zhiyuan Liu
2. Maosong Sun
3. Percy Liang
4. Mohit Bansal
5. Erik Cambria
6. Andrew McCallum
7. Jun Zhu
8. Tat-seng Chua

Citations in the corpus

• Towards Bayesian Deep Learning: A Survey (2016, methodology): “For example, MCMC algorithms like [42] have been proposed to learn the posterior distributions of LDA.”
• Topic Modeling Using Latent Dirichlet allocation (2021, background): “analyze the connection between Gibbs sampling [16, 41, 77, 109, 118, 181], variational inference, and maximum a posterior [4], Spherical Admixture Model for L2 normalized data [116].”
• Advances in Variational Inference (2017, neutral): “approaches rely on sampling [22], [61], [151].”
• Jumping NLP Curves: A Review of Natural Language Processing Research [Review Article] (2014, background): “…this are: (a) latent semantic analysis (Hofmann, 2001), where documents are represented as vectors in a term space; (b) latent Dirichlet allocation (Porteous et al., 2008), which involves attributing document terms to topics; (c) MapReduce (C. Liu, Qi, Wang, & Yu, 2012), a framework that has…”
• An overview of topic modeling and its current applications in bioinformatics (2016, background): “Every kind of algorithm has its own advantages: the variational approach is arguably faster computationally, but the Gibbs sampling approach is in principle more accurate (Porteous et al. 2008).”
• A Survey on Bayesian Deep Learning (2016, methodology): “For example, MCMC algorithms such as Reference [86] have been proposed to learn the posterior distributions of LDA.”
• Full-Text or Abstract? Examining Topic Coherence Scores Using Latent Dirichlet Allocation (2017, neutral): “[25], [26]) and variational-based algorithms (e.”
• Improving Topic Models with Latent Feature Word Representations (2015, background): “…are often used to learn a set of latent topics for a corpus, and predict the probabilities of each word in each document belonging to each topic (Teh et al., 2006; Newman et al., 2006; Toutanova and Johnson, 2008; Porteous et al., 2008; Johnson, 2010; Xie and Xing, 2013; Hingmire et al., 2013).”
• Memory Limited, Streaming PCA (2013, neutral): “If for any τ ≥ 0 and 0 < γ < 1, we have δτ+1 ≤ γ 2δτ 1−δτ+γ2δτ , then, δτ+1 ≤ γ2t+2δ0 1− (1− γ2t+2)δ0 .”
• Spectral Methods for Supervised Topic Models (2014, background): “Topic models are typically learned by finding maximum likelihood estimates (MLE) through local search or sampling methods [12] [18] [19], which may suffer from local optima.”
• UTOPIAN: User-Driven Topic Modeling Based on Interactive Nonnegative Matrix Factorization (2013, methodology): “In terms of the algorithm implementation, we use a widely-accepted LDA implementation called Mallet [28] the algorithm of which is based on a Gibbs sampling method [32].”
• Topical Word Embeddings (2015, methodology): “From the complexity analysis, we can see that, compared with Skip-Gram, TWE models require more parameters to record more discriminative information for word embeddings, but the computational complexity does not increase too much relatively, especially when many fast algorithms of topic models are a”
• topicmodels: An R Package for Fitting Topic Models (2011, methodology): “…allows to fit the LDA model is available through Infer.NET (Microsoft Corporation 2010) The fast collapsed Gibbs sampling method is described in Porteous, Asuncion, Newman, Ihler, Smyth, and Welling (2008) and code is also available from the first author’s web page (…”
• Style in the long tail: discovering unique interests with latent variable models in large scale social E-commerce (2014, neutral): “, [17]) from Mallet.”
• A Survey of Topic Modeling in Text Mining (2015, background): “1) Choose a topic zij ∼ Mult(θj) 2) Choose a word xij ∼ Mult(φzij ) Where the parameters of the multinomials for topics in a document θj and words in a topic φk have Dirichlet priors [12]”
• TwitterRank: finding topic-sensitive influential twitterers (2010, methodology): “Conventional Gibbs sampling is applied instead of collapsed Gibbs sampling, though collapsed Gibbs sampling is shown to achieve faster convergence and better performance [17].”