A Spectral Algorithm for Latent Dirichlet Allocation

Abstract

The problem of topic modeling can be seen as a generalization of the clustering problem, in that it posits that observations are generated due to multiple latent factors (e.g., the words in each document are generated as a mixture of several active topics, as opposed to just one). This increased representational power comes at the cost of a more challenging unsupervised learning problem of estimating the topic probability vectors (the distributions over words for each topic), when only the words are observed and the corresponding topics are hidden. We provide a simple and efficient learning procedure that is guaranteed to recover the parameters for a wide class of mixture models, including the popular latent Dirichlet allocation (LDA) model. For LDA, the procedure correctly recovers both the topic probability vectors and the prior over the topics, using only trigram statistics (i.e., third order moments, which may be estimated with documents containing just three words). The method, termed Excess Correlation Analysis (ECA), is based on a spectral decomposition of low order moments (third and fourth order) via two singular value decompositions (SVDs). Moreover, the algorithm is scalable since the SVD operations are carried out on $k\times k$ matrices, where $k$ is the number of latent factors (e.g. the number of topics), rather than in the $d$-dimensional observed space (typically $d\gg k$).

Changed title to match conference version, which appears in Advances in Neural Information Processing Systems 25, 2012

References in corpus (4)

• Polynomial Learning of Distribution Families
• A Spectral Algorithm for Learning Hidden Markov Models
• Learning Topic Models - Going beyond SVD
• Settling the Polynomial Learnability of Mixtures of Gaussians

Cited by in corpus (69)

• Provable Bounds for Learning Some Deep Representations
• Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcing
• On Identifiability of Nonnegative Matrix Factorization
• New Algorithms for Learning Incoherent and Overcomplete Dictionaries
• A Tensor Approach to Learning Mixed Membership Community Models
• Sequential Transfer in Multi-armed Bandit with Finite Set of Models
• Tensor Train decomposition on TensorFlow (T3F)
• A provable SVD-based algorithm for learning topics in dominant admixture corpus
• Topic Discovery through Data Dependent and Random Projections
• A New Sampling Technique for Tensors
• Outlier-robust moment-estimation via sum-of-squares
• Spectral Learning on Matrices and Tensors
• A Clustering Approach to Learn Sparsely-Used Overcomplete Dictionaries
• Author Clustering and Topic Estimation for Short Texts
• Tensor Decompositions via Two-Mode Higher-Order SVD (HOSVD)
• Pólya Urn Latent Dirichlet Allocation: a doubly sparse massively parallel sampler
• Barriers for Rank Methods in Arithmetic Complexity
• When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity
• Polynomial-time Tensor Decompositions with Sum-of-Squares
• Learning Nonlinear Mixtures: Identifiability and Algorithm
• Training Input-Output Recurrent Neural Networks through Spectral Methods
• Consistent Estimation of Low-Dimensional Latent Structure in High-Dimensional Data
• Dimension-free Concentration Bounds on Hankel Matrices for Spectral Learning
• Nonparametric Estimation of Multi-View Latent Variable Models
• Smoothed Analysis of Tensor Decompositions
• Dimension-Grouped Mixed Membership Models for Multivariate Categorical Data
• Learning Binary Latent Variable Models: A Tensor Eigenpair Approach
• Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo
• Divide-and-Conquer Learning by Anchoring a Conical Hull
• Robust Spectral Inference for Joint Stochastic Matrix Factorization
• A Sober Look at Spectral Learning
• Clustering Patients with Tensor Decomposition
• Provable benefits of representation learning
• Conic Scan-and-Cover algorithms for nonparametric topic modeling
• Learning Implicit Generative Models with the Method of Learned Moments
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Adversarial Combinatorial Bandits with General Non-linear Reward Functions
• Fourier PCA and Robust Tensor Decomposition
• Rethinking LDA: moment matching for discrete ICA
• Scalable and Robust Construction of Topical Hierarchies
• An end-to-end Differentially Private Latent Dirichlet Allocation Using a Spectral Algorithm
• Recovering Structured Probability Matrices
• Combinatorial Topic Models using Small-Variance Asymptotics
• Optimal estimation of sparse topic models
• Generalized Topic Modeling
• Learning Arbitrary Statistical Mixtures of Discrete Distributions
• Detecting approximate replicate components of a high-dimensional random vector with latent structure
• A fast algorithm with minimax optimal guarantees for topic models with an unknown number of topics
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Geometric Dirichlet Means algorithm for topic inference
• Efficient coordinate-descent for orthogonal matrices through Givens rotations
• Dirichlet Simplex Nest and Geometric Inference
• Weighted Tensor Completion for Time-Series Causal Inference
• Eigenvectors of Orthogonally Decomposable Functions
• Efficient Learning of Mixed Membership Models
• Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothing
• A model selection approach for clustering a multinomial sequence with non-negative factorization
• Compressed spectral screening for large-scale differential correlation analysis with application in selecting Glioblastoma gene modules
• A moment-matching metric for latent variable generative models
• A general method for regularizing tensor decomposition methods via pseudo-data
• Guaranteed Model Order Estimation and Sample Complexity Bounds for LDA
• Multi-Label Learning with Provable Guarantee
• The Sparse Hausdorff Moment Problem, with Application to Topic Models
• Fast moment estimation for generalized latent Dirichlet models
• Weighted Tensor Decomposition for Learning Latent Variables with Partial Data
• Spectral Learning for Supervised Topic Models
• Prior-aware Dual Decomposition: Document-specific Topic Inference for Spectral Topic Models
• Seeding K-Means using Method of Moments
• Sensing tensors with Gaussian filters