Learning High-Dimensional Mixtures of Graphical Models

摘要

We consider unsupervised estimation of mixtures of discrete graphical models,where the class variable corresponding to the mixture components is hidden andeach mixture component over the observed variables can have a potentiallydifferent Markov graph structure and parameters. We propose a novel approachfor estimating the mixture components, and our output is a tree-mixture modelwhich serves as a good approximation to the underlying graphical model mixture.Our method is efficient when the union graph, which is the union of the Markovgraphs of the mixture components, has sparse vertex separators between any pairof observed variables. This includes tree mixtures and mixtures of boundeddegree graphs. For such models, we prove that our method correctly recovers theunion graph structure and the tree structures corresponding tomaximum-likelihood tree approximations of the mixture components. The sampleand computational complexities of our method scale as $\poly(p, r)$, for an$r$-component mixture of $p$-variate graphical models. We further extend ourresults to the case when the union graph has sparse local separators betweenany pair of observed variables, such as mixtures of locally tree-like graphs,and the mixture components are in the regime of correlation decay.