Source-linked AI summary
Sparse Stochastic Inference for Latent Dirichlet allocation
David Mimno, Matt Hoffman, David Blei
TL;DR
Large-scale topic modeling needs inference that handles both enormous corpora and many topics while limiting variational bias. The paper combines online stochastic updates with sparse Gibbs sampling, applies the method to 1.2 million books, and reports improved model quality and scalable computation. The approach also generalizes to a broad class of Bayesian hidden-variable models.
Problem
Large topic-modeling applications require methods that scale across large document collections and many topics while addressing limitations of variational inference.
Method
The algorithm combines online stochastic inference with sparse Gibbs sampling, using Monte Carlo estimates within stochastic natural-gradient updates.
Results
Sampled online inference produced fewer very poor topics and greater held-out probability than Online LDA, while processing time remained similar for K = 1000 and 2000.
Takeaways & Limitations
The hybrid method supports training topic models on vast corpora with many topics without requiring vast computer clusters and generalizes to broad Bayesian models.
Takeaways & Limitations
The comparison gives SMC an advantage because SMC documents see results from all previous documents, unlike independently sampled documents within a mini-batch.
Abstract
from arXiv · showhide
We present a hybrid algorithm for Bayesian topic models that combines the efficiency of sparse Gibbs sampling with the scalability of online stochastic inference. We used our algorithm to analyze a corpus of 1.2 million books (33 billion words) with thousands of topics. Our approach reduces the bias of variational inference and generalizes to many Bayesian hidden-variable models.
1. Introduction
Topic models infer hidden topic distributions and document-topic proportions to organize, search, and explore large document collections. The paper introduces a hybrid method combining online stochastic inference with sparse sampling for models with many topics.
- Topic models represent each topic as a vocabulary distribution and each document as proportions over topics.
- Inferring the hidden topics and document-topic proportions given observed documents is the central computational problem.
- A 2000-topic model was trained on a library of 1.2 million out-of-copyright books.
- Online LDA reduces memory use and updates topics frequently by repeatedly subsampling documents, but does not scale to large topic counts.
- The proposed algorithm adds sampling as a second stochasticity source, enabling sparse computation that scales sublinearly with the number of topics.
2. Hybrid stochastic-MCMC inference
The method combines variational inference, stochastic minibatch updates, and Gibbs sampling over document topic assignments. Monte Carlo estimates make the updates sparse while avoiding explicit document-topic proportions, although they add noise to the gradient.
- The model separates global topic-word distributions from document-level topic proportions and token-topic indicators.
- The variational family treats each document’s topic-indicator sequence as one unit rather than factorizing over individual tokens.
- The algorithm updates global variational parameters with stochastic natural gradients estimated from minibatches of documents.
- Gibbs sampling from document-level topic configurations supplies empirical estimates for the expectations required by the gradient.
- MCMC estimates add gradient noise but enable a collapsed objective without document-topic proportions and yield sparse sufficient-statistic estimates.
- The online algorithm preserves sparsity in topic-word parameters, making updates and Gibbs sampling more efficient for large vocabularies.
3. Related Work
The paper combines data subsampling with Monte Carlo inference, integrating two stochastic ingredients that earlier methods used separately. Relative to related approaches, it also uses a distinct global representation and a less factorized treatment of topic assignments.
- The method combines data subsampling and Monte Carlo inference as two sources of zero-mean noise in approximate variational gradients.
- Earlier stochastic EM variants used Monte Carlo estimates without data subsampling, whereas online EM subsampled data while retaining standard local inference.
- Standard collapsed Gibbs sampling represents topic-word distributions through assignments across the entire corpus and is theoretically sequential.
- Unlike fully factorized collapsed variational inference, this method does not factorize topic assignments by token, reducing one source of bias while potentially adding initialization bias from Gibbs chains.
4. Empirical Results
The sampled online algorithm combines sparse computation with online inference, improving scalability with topic count while producing stronger topic-quality and held-out-probability results than comparable online baselines. Its evaluations also show advantages over sequential Monte Carlo and sensitivity to corpus size, smoothing, and sweep settings.
- Comparison to Online VB: Sampled online inference grows more slowly with K than standard online inference, whose wallclock time is linear in K.The comparison used minibatches of 100 documents and evaluated K up to 1000.
- Comparison to Online VB: At K = 200, sampled online inference produces fewer very poor topics and greater held-out probability than Online LDA.The coherence difference is significant at p < 0.001, and the held-out-probability advantage holds for every test document.
- Comparison to Sequential Monte Carlo: At K = 200, sampled online inference has consistently better per-topic coherence and per-document held-out log probability than one pass of sequential Monte Carlo.The sampled online method gives more weight to recently sampled documents through learning-rate decay, unlike SMC's equal weighting of documents.
- Effect of parameter settings: Increasing η from 0.1 through 0.4 significantly improves average coherence, with no significant difference among η = 0.4, 0.5, and 0.6.At η = 0.1, many topics are visibly nonsensical; smoothing pushes parameters away from an unstable near-zero region.
- Effect of parameter settings: For the smallest corpus, using t0 = 300000 significantly worsens average topic coherence, while other settings show no significant difference.The corpus-size experiment used subsets containing one half, one quarter, and one eighth of the full corpus; the effect occurred at 12.5% of the data with p < 0.001.
- Scalability: On 44 million book-section documents, fewer than 1% of topic-word parameters are non-zero at K = 2000, while processing time is similar for K = 1000 and K = 2000.The book corpus uses a vocabulary of 216 words and models with K ∈{100, 500, 1000, 2000}.
5. Conclusions
The paper combines stochastic online inference with sparse Gibbs sampling to scale topic modeling across both large document collections and large topic sets. It also reduces one source of variational-inference bias and extends beyond text analysis to broader Bayesian hidden-variable models.
- Stochastic online inference scales topic modeling to large document sets, while sparse Gibbs sampling scales it to large numbers of topics.
- Combining these methods enables training on vast, open-ended corpora without requiring vast computer clusters.
- Computation within each mini-batch can be trivially parallelized when parallel architectures are available.
- Using MCMC within stochastic variational inference reduces one source of bias in estimating local variables, and the hybrid method generalizes to a broad class of Bayesian models.
A. Sparse computation
The method achieves sparse computation by exploiting sparsity in topic-word parameters and document-word counts. Its updates avoid work over zero entries, while incremental normalization and parameter resets support efficient and stable processing.
- Sparse topic-word parameters make the normalizing constant computable in much less than O(k) when λ_kw is represented sparsely.
- The nonzero portion of the normalizer depends only on topics with nonzero ˜N_kw, while the remaining term can be updated incrementally as N_dk changes.
- Sparse updates modify only elements with non-zero n_dw, avoiding updates for words absent from the current mini-batch.
- The scale factor π_t is periodically reset after becoming small to avoid numerical instability.