Tensor decompositions for learning latent variable models
By Anima Anandkumar, Rong Ge, Daniel J. Hsu, Sham M. Kakade, Matus Telgarsky. 2012
1,214 citations recorded by the source corpus.
This work considers a computationally and statistically efficient parameter estimation method for a wide class of latent variable models--including Gaussian mixture models, hidden Markov models, and latent Dirichlet allocation--which exploits a certain tensor structure in their low-order observable moments (typically, of second- and third-order). Specifically, parameter estimation is reduced to the problem of extracting a certain (orthogonal) decomposition of a symmetric tensor derived from the moments; this decomposition can be viewed as a natural generalization of the singular value decomposition for matrices. Although tensor decompositions are generally intractable to compute, the decomposition of these specially structured tensors can be efficiently obtained by a variety of approaches, including power iterations and maximization approaches (similar to the case of matrices). A detailed analysis of a robust tensor power method is provided, establishing an analogue of Wedin's perturbation theorem for the singular vectors of matrices. This implies a robust and computationally tractable estimation approach for several popular latent variable models.
Subfields: Artificial Intelligence, Computational Mathematics, Representation & Self-Supervised Learning, Signal Processing
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
- Yoshua Bengio
- Sergey Levine
- Percy Liang
- Mohit Bansal
- Ruslan Salakhutdinov
- Quoc V. Le
- Jianfeng Gao
- Luke S. Zettlemoyer
In Computational Mathematics
- Yuanzhi Li
- Rong Ge
- Anima Anandkumar
- Zehao Dou
- Kfir Yehuda Levy
- Sham M. Kakade
- David Steurer
- Michael I. Jordan
In Representation & Self-Supervised Learning
- Bernhard Schölkopf
- Le Song
- Kenji Fukumizu
- Alex Smola
- Arthur Gretton
- Yoshua Bengio
- Michael I. Jordan
- Francis R. Bach
In Signal Processing
- Bernhard Schölkopf
- Alex Smola
- Arthur Gretton
- Francis R. Bach
- Le Song
- Anima Anandkumar
- Yuanzhi Li
- Pravesh Kothari
Citations in the corpus
- Beyond CCA: Moment Matching for Multi-View Models (2016, neutral): “However, neither JDC nor the orthogonal diagonalization-type algorithms (such as, e.g., the tensor power method by Anandkumar et al., 2014) are applicable for the problem (31).”
- Rethinking LDA: Moment Matching for Discrete ICA (2015, positive): “This structure allows to reapply the algorithms of [3, 4] for the estimation of the model parameters, with the same theoretical guarantees.”
- Causal Effect Inference with Deep Latent-Variable Models (2017, neutral): “For example, if X includes three independent views of Z [4, 22, 16, 2]; if Z is categorical and X is a Gaussian mixture model with components determined by X [5]; or if Z is comprised of binary variables and X are so-called “noisy-or” functions of Z [23, 8].”
- The Incomplete Rosetta Stone problem: Identifiability results for Multi-view Nonlinear ICA (2019, background): “[39] proves identifiability for multi-view, latent variable models, unifying previously proposed spectral techniques [2].”
- Deep Sets (2017, methodology): “Spectral methods: A consequence of the polynomial decomposition is that spectral methods (Anandkumar et al., 2012) can be viewed as a special case of the mapping ρ ◦ φ ( X ) : in that case one can compute polynomials, usually only up to a relatively low degree (such as k = 3 ), to perform inference…”
- Recovery Guarantees for One-hidden-layer Neural Networks (2017, methodology): “However, by making some assumptions, tensor decomposition method becomes efficient (Anandkumar et al., 2014; Wang et al., 2015; Wang & Anandkumar, 2016; Song et al., 2016).”
- Escaping From Saddle Points - Online Stochastic Gradient for Tensor Decomposition (2015, background): “It is possible to find all components of a tensor by iteratively finding one component, and do careful deflation, as described in Anandkumar et al. (2014) or Arora et al. (2012).”
- Efficient Exploration Through Bayesian Deep Q-Networks (2018, methodology): “1The scores of DDQN† are borrowed from original DDQN paper [11] methods [20].”
- Neural Predictive Belief Representations (2018, background): “Schmidhuber (1991); Diuk et al. (2008); Kolter & Ng (2009); Sorg et al. (2010); Anandkumar et al. (2014) and many others prescribed or tried to estimate the state transition model of the POMDP explicitly.”
- The tensor algebra compiler (2017, methodology): “Tensor algebra is a powerful tool for computing on multidimensional data and has many applications in machine learning, data analytics, engineering, and science [Abadi et al. 2016; Anandkumar et al. 2014; Bader et al. 2008; Einstein 1916; Feynman et al. 1963; Kolecki 2002].”
- Deep Models of Interactions Across Sets (2018, background): “In particular, one thread of work leverages tensor decomposition for inference in latent variable models (Anandkumar et al., 2014).”
- Structure Learning in Graphical Modeling (2016, methodology): “This fact is exploited also in methods of Anandkumar et al. (2014) and Chaganty & Liang (2014).”
- Reinforcement Learning of POMDPs using Spectral Methods (2016, methodology): “3 are based on spectral tensor decomposition methods, which have been previously used for consistent estimation of a wide class of LVMs (Anandkumar et al., 2014).”
- Learning Two Layer Rectified Neural Networks in Polynomial Time (2018, background): “(2017); Anandkumar et al. (2014); Barak et al. (2015). However, there are several technical hurdles involved in utilizing tensor decompositions to obtain estimates of V∗.”
- Making Method of Moments Great Again? -- How can GANs learn the target distribution (2020, methodology): “to learn an underlying distribution. 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 de”
- On the Expressive Power of Deep Learning: A Tensor Analysis (2015, neutral): “In Novikov et al. (2014), Anandkumar et al. (2014), Yang and Dunson (2015) and Song et al. (2013), algorithms for tensor decompositions are used to estimate parameters of different graphical models.”
- Sample-Efficient Deep RL with Generative Adversarial Tree Search (2018, methodology): “(2016a) deploys OFU in order to propose a high probability regret upper bound for Partially Observable MDPs where spectral methods (Anandkumar et al., 2014) is deployed for learning the environment model.”
- 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.”