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, JMLR Workshop and Conference Proceedings 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 = {Animashree Anandkumar and Daniel Hsu and Sham M. Kakade}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {33.1--33.34}, year = {2012}, editor = {Shie Mannor and Nathan Srebro and Robert C. Williamson}, volume = {23}, series = {Proceedings of Machine Learning Research}, address = {Edinburgh, Scotland}, month = {25--27 Jun}, publisher = {JMLR Workshop and Conference Proceedings}, pdf = {http://proceedings.mlr.press/v23/anandkumar12/anandkumar12.pdf}, url = {http://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 %J Proceedings of Machine Learning Research %P 33.1--33.34 %U http://proceedings.mlr.press %V 23 %W PMLR %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 PY - 2012/06/16 DA - 2012/06/16 ED - Shie Mannor ED - Nathan Srebro ED - Robert C. Williamson ID - pmlr-v23-anandkumar12 PB - PMLR SP - 33.1 DP - PMLR EP - 33.34 L1 - http://proceedings.mlr.press/v23/anandkumar12/anandkumar12.pdf UR - http://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 PMLR 23:33.1-33.34

Related Material