Learning Mixtures of Tree Graphical Models

Part of Advances in Neural Information Processing Systems 25 (NIPS 2012)

Bibtex Metadata Paper


Anima Anandkumar, Daniel J. Hsu, Furong Huang, Sham M. Kakade


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 $p$-variate graphical models, for a wide class of models which includes tree mixtures and mixtures over bounded degree graphs.