A Method of Moments for Mixture Models and Hidden Markov Models

By Anima Anandkumar, Daniel J. Hsu, Sham M. Kakade. 2012

349 citations recorded by the source corpus.

Mixture models are a fundamental tool in applied statistics and machine learning for treating data taken from multiple subpopulations. The current practice for estimating the parameters of such models relies on local search heuristics (e.g., the EM algorithm) which are prone to failure, and existing consistent methods are unfavorable due to their high computational and sample complexity which typically scale exponentially with the number of mixture components. This work develops an efficient method of moments approach to parameter estimation for a broad class of high-dimensional mixture models with many components, including multi-view mixtures of Gaussians (such as mixtures of axis-aligned Gaussians) and hidden Markov models. The new method leads to rigorous unsupervised learning results for mixture models that were not achieved by previous works; and, because of its simplicity, it offers a viable alternative to EM for practical deployment.

Subfields: Artificial Intelligence

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

Citations in the corpus

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].”
Robust Estimators in High Dimensions without the Computational Intractability (2016, background): “…learning several fundamental classes of high-dimensional distributions: (1) a single Gaussian, (2) a product distribution on the hypercube, (3) mixtures of two product distributions (under a natural balancedness condition), and (4) mixtures of k Gaussians with identical spherical covariances.”
Tensor decompositions for learning latent variable models (2012, background): “Let wi be the probability of choosing component i ∈ [k], {µ1, µ2, . . . , µk} ⊂ Rd be the component mean vectors, and σ2I be the common covariance matrix.”
Convex Two-Layer Modeling (2013, background): “Unfortunately, none of these approaches has yet been able to accommodate a non-trivial hidden layer between an input and output layer while retaining the representational capacity of an auto-encoder or RBM (e.g. boosting strategies embed an intractable subproblem in these cases [15–17]).”
Training Gaussian Mixture Models at Scale via Coresets (2017, background): “Anandkumar et al. (2012, 2014) demonstrate that a spectral decomposition technique yields consistent parameter estimates from low-order observable moments, without additional separation assumptions.”
Reinforcement Learning of POMDPs using Spectral Methods (2016, methodology): “3 The proof builds upon previous results on HMM by Anandkumar et al. (2012), Song et al. (2013), Thm.”
Spectral Learning of Mixture of Hidden Markov Models (2014, methodology): “In every iteration, one has to perform forward-backward message passing for every sequence, resulting in a computationally expensive process, especially when dealing with large datasets.”
Long-term Forecasting using Tensor-Train RNNs (2017, methodology): “nsor methods have also been used for sequence modeling. For example, one can apply tensor decomposition as method of moments estimators for latent variable models such as Hidden Markov Models (HMMs) (Anandkumar et al., 2012). Tensor methods have also shown promises in reducing the model dimensionali”
Spectral Methods Meet EM: A Provably Optimal Algorithm for Crowdsourcing (2014, methodology): “Our method for initializing the EM algorithm in crowdsourcing is inspired by recent work using spectral methods to estimate latent variable models [3, 1, 4, 2, 5, 27, 12, 13].”
Spectral Methods for Supervised Topic Models (2014, background): “Much recent progress has been made on developing spectral decomposition [1] [2] [3] and nonnegative matrix factorization (NMF) [4] [5] [6] [7] methods to infer latent topic-word distributions.”
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.”
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.,…”
Learning mixtures of spherical gaussians: moment methods and spectral decompositions (2012, methodology): “Some previous work of the authors on moment-based estimators for the Gaussian mixture model relies on a nondegenerate multi-view assumption [3].”
Discovering Hidden Variables in Noisy-Or Networks using Quartet Tests (2013, methodology): “Recent work has used tensor methods and sparse recovery to learn linear latent variable models with graph expansion (Anandkumar et al. , 2013), and also continuous admixture models such as latent Dirichlet allocation (Anandkumar et al. , 2012a).”
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.”
A Spectral Algorithm for Latent Dirichlet Allocation (2012, methodology): “This construction bridges the gap between the single topic models (as in [22, 24]) and the independent latent factors model.”
Long-term Forecasting using Higher Order Tensor RNNs (2017, methodology): “nsor methods have also been used for sequence modeling. For example, one can apply tensor decomposition as method of moments estimators for latent variable models such as Hidden Markov Models (HMMs) (Anandkumar et al., 2012). Tensor methods have also shown promises in reducing the model dimensionali”
Estimating the accuracies of multiple classifiers without labeled data (2014, background): “For this problem, several recent works suggested spectral tensor decomposition approaches, see Anandkumar et al. [2014], Jain and Oh [2014], Zhang et al. [2014].”
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).”