A Spectral Algorithm for Latent Dirichlet Allocation

By Anima Anandkumar, Dean Phillips Foster, Daniel J. Hsu, Sham M. Kakade, Yi-Kai Liu. 2012

304 citations recorded by the source corpus.

Topic modeling is a generalization of clustering that posits that observations (words in a document) are generated by multiple latent factors (topics), as opposed to just one. The increased representational power comes at the cost of a more challenging unsupervised learning problem for estimating the topic-word distributions when only words are observed, and the topics are hidden. This work provides a simple and efficient learning procedure that is guaranteed to recover the parameters for a wide class of multi-view models and topic models, including latent Dirichlet allocation (LDA). For LDA, the procedure correctly recovers both the topic-word distributions and the parameters of the Dirichlet prior over the topic mixtures, using only trigram statistics (i.e., third order moments, which may be estimated with documents containing just three words). The method is based on an efficiently computable orthogonal tensor decomposition of low-order moments.

Subfields: Artificial Intelligence, Computational Mathematics

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

In Computational Mathematics

Citations in the corpus

Beyond CCA: Moment Matching for Multi-View Models (2016, neutral): “In practice, we observed that for K 0 M all models work approximately equally well, except for NMF which breaks down in high dimensions.”
Provable Bounds for Learning Some Deep Representations (2013, background): “, for which learning algorithms with provable guarantees were given (Hsu et al., 2012; Moitra & Valiant, 2010; Hsu & Kakade, 2013; Arora et al., 2012; Anandkumar et al., 2012).”
Tensor decompositions for learning latent variable models (2012, methodology): “We may derive forms similar to that of M2 and M3 from Theorem 3.1 using M4 by observing that M4(I, I, u, v) = k∑ i=1 κi(µ ⊤ i u)(µ ⊤ i v) µi ⊗ µi, M4(I, I, I, v) = k∑ i=1 κi(µ ⊤ i v) µi ⊗ µi ⊗ µi for any vectors u, v ∈ Rd.”
New Algorithms for Learning Incoherent and Overcomplete Dictionaries (2013, methodology): “Our goal is to design an algorithm for this problem with provable guarantees in the same spirit as recent work on nonnegative matrix factorization [7], topic models [8, 6] and mixtures models [43, 12].”
Applications of Topic Models (2017, background): “, 2013] or as a spectral decomposition [Anandkumar et al., 2012].”
Exact Recovery of Sparsely Used Overcomplete Dictionaries (2013, unknown): “There are various recent works providing guaranteed methods for learning topic models, e.g [1, 6, 5, 4].”
A tensor approach to learning mixed membership community models (2013, methodology): “We now compare the results of this paper to our previous work [Anandkumar et al., 2012b] on the use of tensor-based approaches for learning various latent variable models such as topic models, hidden Markov models (HMM) and Gaussian mixtures.”
Unsupervised Learning of Noisy-Or Bayesian Networks (2013, methodology): “In recent work, these have been generalized to a large class of linear latent variable models (Anandkumar et al. , 2012d).”
Making Method of Moments Great Again? -- How can GANs learn the target distribution (2020, methodology): “Method of Moments has been used in many other machine learning problems such as mixture of Gaussian distribution [71, 60], topic models [11], hidden Markov models [12], dictionary learning [17], mixture of linear regression [48] and so on, and has been used to design practical GANs [46] as well.”
Structural Topic Models for Open‐Ended Survey Responses (2014, background): “This can arise even in simple mixture models in very low dimensions (Anandkumar et al. 2012; Buot and Richards, 2006; Sontag and Roy 2009).”
Online and Differentially-Private Tensor Decomposition (2016, methodology): “1 we plot the “failure probability” (measured via 20 independent trials per setting) of the robust tensor power method with random initialization against controlled noise magnitude ‖E‖op = σ.”
Nonparametric Estimation of Multi-View Latent Variable Models (2013, methodology): “Current spectral algorithms are largely restricted to mixture of discrete or Gaussian distributions, e.g. (Anandkumar et al., 2012a; Hsu & Kakade, 2013).”
Spectral Inference Networks: Unifying Spectral Methods With Deep Learning (2018, methodology): “Spectral algorithms can also be used for asymptotically exact estimation of parametric models like hidden Markov models and latent Dirichlet allocation by computing the SVD of moment statistics [17, 1].”
Methods of Moments for Learning Stochastic Languages: Unified Presentation and Empirical Comparison (2014, methodology): “…of multipliers (ADMM) (Boyd et al., 2011) optimization algorithm; Tensor, the symmetric tensor decomposition method using the tensor-power method (Anandkumar et al., 2012b) (3.3) applied to empirical estimates f̂S ; EM, an optimized implementation6 of the BaumWelch algorithm (Dempster et al.,…”
Spectral Inference Networks: Unifying Deep and Spectral Learning (2018, methodology): “Spectral algorithms can also be used for asymptotically exact estimation of parametric models like hidden Markov models and latent Dirichlet allocation by computing the SVD of moment statistics (Hsu et al., 2012; Anandkumar et al., 2012).”
Sequential Transfer in Multi-armed Bandit with Finite Set of Models (2013, methodology): “In this paper we rely on a new variant of method-of-moments (Anandkumar et al., 2012a,c), the robust tensor power method (RTP) (Anandkumar et al., 2012b), to estimate the LVM associated with the sequential-bandit problem.”
Learning Implicit Generative Models with the Method of Learned Moments (2018, methodology): “For example, one can scale training of Latent Dirichlet Allocation to large datasets by moment estimation using the ﬁrst three order moments (Anandkumar et al., 2012a).”