Online Learning for Latent Dirichlet Allocation
Published 6 December 2010
Matthew D. Hoffman, Francis Bach, David M. Blei
Citations1,294
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An online variational Bayes (VB) algorithm for Latent Dirichlet Allocation (LDA) based on online stochastic optimization with a natural gradient step is developed, which shows converges to a local optimum of the VB objective function.
Abstract
We develop an online variational Bayes (VB) algorithm for Latent Dirichlet Allocation (LDA). Online LDA is based on online stochastic optimization with a natural gradient step, which we show converges to a local optimum of the VB objective function. It can handily analyze massive document collections, including those arriving in a stream. We study the performance of online LDA in several ways, including by fitting a 100-topic topic model to 3.3M articles from Wikipedia in a single pass. We demonstrate that online LDA finds topic models as good or better than those found with batch VB, and in a fraction of the time. 1
Keywords
Computer Science
Journal of the Royal Statistical Society Series B (Statistical Methodology)Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
49,657 Citations1977A. P. Dempster, N. M. Laird +1 more
Journal of Machine Learning ResearchLatent dirichlet allocation
27,049 Citations2003David M. Blei, Andrew Y. Ng +1 more
The Annals of Mathematical StatisticsA Stochastic Approximation Method
9,581 Citations1951Herbert Robbins, Sutton Monro
Proceedings of the National Academy of SciencesFinding scientific topics
6,017 Citations2004Thomas L. Griffiths, Mark Steyvers
A generative model for documents is described, introduced by Blei, Ng, and Jordan, and a Markov chain Monte Carlo algorithm is presented for inference in this model, which is used to analyze abstracts from PNAS by using Bayesian model selection to establish the number of topics.
Machine LearningAn Introduction to Variational Methods for Graphical Models
3,775 Citations1999Michael I. Jordan, Zoubin Ghahramani +2 more
This paper presents a tutorial introduction to the use of variational methods for inference and learning in graphical models (Bayesian networks and Markov random fields), and describes a general framework for generating variational transformations based on convex duality.
Journal of Machine Learning ResearchOnline Learning for Matrix Factorization and Sparse Coding
2,338 Citations2010Julien Mairal, Francis Bach +2 more
A View of the Em Algorithm that Justifies Incremental, Sparse, and other Variants
2,187 Citations1998Radford M. Neal, Geoffrey E. Hinton
An incremental variant of the EM algorithm in which the distribution for only one of the unobserved variables is recalculated in each E step is shown empirically to give faster convergence in a mixture estimation problem.
Reading Tea Leaves: How Humans Interpret Topic Models
1,874 Citations2009Jonathan Chang, Sean Gerrish +3 more
New quantitative methods for measuring semantic meaning in inferred topics are presented, showing that they capture aspects of the model that are undetected by previous measures of model quality based on held-out likelihood.
The MIT Press eBooksThe Tradeoffs of Large-Scale Learning
1,185 Citations2011Léon Bottou, Olivier Bousquet
This contribution develops a theoretical framework that takes into account the effect of approximate optimization on learning algorithms and shows distinct tradeoffs for the case of small-scale and large-scale learning problems.
Neural Information Processing SystemsA Variational Baysian Framework for Graphical Models
695 Citations1999Hagai Attias
ScholarWorks@UMassAmherst (University of Massachusetts Amherst)Rethinking LDA: Why Priors Matter
563 Citations2009Hanna Wallach, David Mimno +1 more
The prior structure advocated substantially increases the robustness of topic models to variations in the number of topics and to the highly skewed word frequency distributions common in natural language.
Cambridge University Press eBooksOn-line Learning and Stochastic Approximations
546 Citations1999Léon Bottou
This framework encompasses the most common online learning algorithms in use today, as illustrated by several examples, and provides general results describing the convergence of all these learning algorithms at once.
arXiv (Cornell University)On Smoothing and Inference for Topic Models
452 Citations2012Arthur Asuncion, Max Welling +2 more
Efficient methods for topic model inference on streaming document collections
425 Citations2009Limin Yao, David Mimno +1 more
Empirical results indicate that SparseLDA can be approximately 20 times faster than traditional LDA and provide twice the speedup of previously published fast sampling methods, while also using substantially less memory.
Neural ComputationOnline Model Selection Based on the Variational Bayes
382 Citations2001Masa-aki Sato
By combining sequential model selection procedures, the online VB method provides a fully online learning method with a model selection mechanism and was able to adapt the model structure to dynamic environments.
Neural ComputationOn-line EM Algorithm for the Normalized Gaussian Network
280 Citations2000Masa-aki Sato, Shin Ishii
Online Inference of Topics with Latent Dirichlet Allocation
235 Citations2009Kevin Robert Canini, Lei Shi +1 more
Two related RaoBlackwellized online inference algorithms for the latent Dirichlet allocation (LDA) model – incremental Gibbs samplers and particle filters – are introduced and their runtime and performance are compared to that of existing algorithms.
Distributed Inference for Latent Dirichlet Allocation
220 Citations2007David Newman, Padhraic Smyth +2 more
Using five real-world text corpora, it is shown that distributed learning works very well for LDA models, i.e., perplexity and precision-recall scores for distributed learning are indistinguishable from those obtained with single-processor learning.
Online EM for unsupervised models
210 Citations2009Percy Liang, Dan Klein
It is shown that online variants provide significant speedups and can even find better solutions than those found by batch EM on four unsupervised tasks: part-of-speech tagging, document classification, word segmentation, and word alignment.
Variational methods for the Dirichlet process
181 Citations2004David M. Blei, Michael I. Jordan
A mean-field variational approach to approximate inference for the Dirichlet process, where the approximate posterior is based on the truncated stick-breaking construction (Ishwaran & James, 2001).
Journal of the American Statistical AssociationVariational Inference for Large-Scale Models of Discrete Choice
174 Citations2010Michael Braun, Jon McAuliffe
Extensive simulations, along with an analysis of real-world data, demonstrate that variational methods achieve accuracy competitive with Markov chain Monte Carlo at a small fraction of the computational cost.
Lecture notes in computer scienceVariational Extensions to EM and Multinomial PCA
163 Citations2002Wray Buntine
This paper begins with a review of the basic theory of the variational extension to the expectation-maximization algorithm, and then presents discrete component finding algorithms in that light.
Parallel Inference for Latent Dirichlet Allocation on Graphics Processing Units
104 Citations2009Feng Yan, Ningyi Xu +1 more
A novel data partitioning scheme is proposed that effectively reduces the memory cost of parallelizing two inference methods on GPUs for latent Dirichlet Allocation models, collapsed Gibbs sampling and collapsed variational Bayesian.
Modeling and predicting personal information dissemination behavior
87 Citations2005Xiaodan Song, Ching‐Yung Lin +2 more
A new way to automatically model and predict human behavior of receiving and disseminating information by analyzing the contact and content of personal communications is proposed, based on the combination of dynamic algorithms in the social network field and semantic content classification methods in the natural language processing and machine learning literatures.