Learning High-Dimensional Mixtures of Graphical Models

Details Learning High-Dimensional Mixtures of Graphical Models Learning High-Dimensional Mixtures of Graphical Models

2012-03-04

arxiv.org/abs/1203.0697v1

Statistics

Machine Learning

Scientific paper

We consider the problem of learning mixtures of discrete graphical models in high dimensions and propose a novel method for estimating the mixture components with provable guarantees. The method proceeds mainly in three stages. In the first stage, it estimates the union of the Markov graphs of the mixture components (referred to as the union graph) via a series of rank tests. It then uses this estimated union graph to compute the mixture components via a spectral decomposition method. The spectral decomposition method was originally proposed for latent class models, and we adapt this method for learning the more general class of graphical model mixtures. In the end, the method produces tree approximations of the mixture components via the Chow-Liu algorithm. Our output is thus a tree-mixture model which serves as a good approximation to the underlying graphical model mixture. When the union graph has sparse node separators, we prove that our method has sample and computational complexities scaling as poly(p, d, r), for an r-component mixture of p-variate graphical models, where d is the cardinality of the sample space of each node variable. We also extend our results to the case when the union graph has sparse local separators, which is a weaker criterion than having sparse exact separators, and when the mixture components are in the regime of correlation decay. The computational and sample complexities of our method for this class are significantly improved, since they involve an upper bound on the cardinality of local separators (as opposed to exact separators). Our results push the realm of tractable model classes for high-dimensional learning, which includes the class of tree mixtures.

Affiliated with

Also associated with

No associations

Rating

Learning High-Dimensional Mixtures of Graphical Models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Learning High-Dimensional Mixtures of Graphical Models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning High-Dimensional Mixtures of Graphical Models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-331265