A Method of Moments for Mixture Models and Hidden Markov Models

Animashree Anandkumar, Daniel Hsu, Sham M. Kakade
Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:33.1-33.34, 2012.

Abstract

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 (\emphe.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 \emphmethod 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v23-anandkumar12, title = {A Method of Moments for Mixture Models and Hidden Markov Models}, author = {Anandkumar, Animashree and Hsu, Daniel and Kakade, Sham M.}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {33.1--33.34}, year = {2012}, editor = {Mannor, Shie and Srebro, Nathan and Williamson, Robert C.}, volume = {23}, series = {Proceedings of Machine Learning Research}, address = {Edinburgh, Scotland}, month = {25--27 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v23/anandkumar12/anandkumar12.pdf}, url = {https://proceedings.mlr.press/v23/anandkumar12.html}, abstract = {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 (\emphe.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 \emphmethod 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.} }
Endnote
%0 Conference Paper %T A Method of Moments for Mixture Models and Hidden Markov Models %A Animashree Anandkumar %A Daniel Hsu %A Sham M. Kakade %B Proceedings of the 25th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2012 %E Shie Mannor %E Nathan Srebro %E Robert C. Williamson %F pmlr-v23-anandkumar12 %I PMLR %P 33.1--33.34 %U https://proceedings.mlr.press/v23/anandkumar12.html %V 23 %X 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 (\emphe.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 \emphmethod 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.
RIS
TY - CPAPER TI - A Method of Moments for Mixture Models and Hidden Markov Models AU - Animashree Anandkumar AU - Daniel Hsu AU - Sham M. Kakade BT - Proceedings of the 25th Annual Conference on Learning Theory DA - 2012/06/16 ED - Shie Mannor ED - Nathan Srebro ED - Robert C. Williamson ID - pmlr-v23-anandkumar12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 23 SP - 33.1 EP - 33.34 L1 - http://proceedings.mlr.press/v23/anandkumar12/anandkumar12.pdf UR - https://proceedings.mlr.press/v23/anandkumar12.html AB - 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 (\emphe.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 \emphmethod 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. ER -
APA
Anandkumar, A., Hsu, D. & Kakade, S.M.. (2012). A Method of Moments for Mixture Models and Hidden Markov Models. Proceedings of the 25th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 23:33.1-33.34 Available from https://proceedings.mlr.press/v23/anandkumar12.html.

Related Material