nips nips2012 nips2012-180 nips2012-180-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Anima Anandkumar, Furong Huang, Daniel J. Hsu, Sham M. Kakade
Abstract: We consider unsupervised estimation of mixtures of discrete graphical models, where the class variable is hidden and each mixture component can have a potentially different Markov graph structure and parameters over the observed variables. We propose a novel method for estimating the mixture components with provable guarantees. Our output is a tree-mixture model which serves as a good approximation to the underlying graphical model mixture. The sample and computational requirements for our method scale as poly(p, r), for an r-component mixture of pvariate graphical models, for a wide class of models which includes tree mixtures and mixtures over bounded degree graphs. Keywords: Graphical models, mixture models, spectral methods, tree approximation.
[1] A. Anandkumar, V. Y. F. Tan, F. Huang, and A. S. Willsky. High-Dimensional Structure Learning of Ising Models: Local Separation Criterion. Accepted to Annals of Statistics, Jan. 2012.
[2] A. Jalali, C. Johnson, and P. Ravikumar. On learning discrete graphical models using greedy methods. In Proc. of NIPS, 2011.
[3] P. Ravikumar, M.J. Wainwright, and J. Lafferty. High-dimensional Ising Model Selection Using l1Regularized Logistic Regression. Annals of Statistics, 2008.
[4] M. Meila and M.I. Jordan. Learning with mixtures of trees. J. of Machine Learning Research, 1:1–48, 2001.
[5] P. Spirtes and C. Meek. Learning bayesian networks with discrete variables from data. In Proc. of Intl. Conf. on Knowledge Discovery and Data Mining, pages 294–299, 1995.
[6] G. Bresler, E. Mossel, and A. Sly. Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms. In Intl. workshop APPROX Approximation, Randomization and Combinatorial Optimization, pages 343–356. Springer, 2008.
[7] J.T. Chang. Full reconstruction of markov models on evolutionary trees: identifiability and consistency. Mathematical Biosciences, 137(1):51–73, 1996.
[8] E. Mossel and S. Roch. Learning nonsingular phylogenies and hidden Markov models. The Annals of Applied Probability, 16(2):583–614, 2006.
[9] A. Anandkumar, D. Hsu, and S.M. Kakade. A Method of Moments for Mixture Models and Hidden Markov Models. In Proc. of Conf. on Learning Theory, June 2012.
[10] C. Chow and C. Liu. Approximating Discrete Probability Distributions with Dependence Trees. IEEE Tran. on Information Theory, 14(3):462–467, 1968.
[11] N. Meinshausen and P. B¨ hlmann. High Dimensional Graphs and Variable Selection With the Lasso. u Annals of Statistics, 34(3):1436–1462, 2006.
[12] M. Belkin and K. Sinha. Polynomial learning of distribution families. In IEEE Annual Symposium on Foundations of Computer Science, pages 103–112, 2010.
[13] A. Moitra and G. Valiant. Settling the polynomial learnability of mixtures of gaussians. In IEEE Annual Symposium on Foundations of Computer Science, 2010.
[14] S.L. Lauritzen. Graphical models: Clarendon Press. Clarendon Press, 1996.
[15] A. Anandkumar, D. Hsu, and S.M. Kakade. Learning High-Dimensional Mixtures of Graphical Models. Preprint. Available on ArXiv:1203.0697, Feb. 2012.
[16] V.Y.F. Tan, A. Anandkumar, and A. Willsky. A Large-Deviation Analysis for the Maximum Likelihood Learning of Tree Structures. IEEE Tran. on Information Theory, 57(3):1714–1735, March 2011. 9