Algorithms for Mixture Models

Mixture models form one of the most fundamental classes of generative models for clustered data. Specific application examples include text classification problems, image segmentation and motion detection, collaborative filtering and many others. However, quite surprisingly, very little had been known about algorithms which have provable performance guarantees within the framework of mixture models. This is the topic we study in this work. Our contribution is twofold. First, for the canonical problem of separating mixtures of continuous distributions in the high-dimensional Euclidean space, we provide the first algorithm that can learn distributions with heavy tails, including those with infinite variance and expectation. We formulate necessary conditions and provide an algorithm which guarantees that the underlying mixture model can be learned by observing only polynomially many samples. We also show that for many classes of distributions, our separation conditions are necessary for {\em any} algorithm which guarantees accurate reconstruction. Second for the case of \emph{discrete mixture models} we give an efficient polynomial time algorithm with provable performance guarantees. Recasting of our algorithm for the text classification problem immediately results in a very fast unsupervised learning method, with an excellent classification accuracy.

Author dc:creator

• Sandler, Mark Moiseevich

• Mixture Models
• Collaborative Filtering
• Theoretical Computer Science

Language dc:language.iso

en_US

Handle dc:identifier.uri

https://hdl.handle.net/1813/3386

OAI identifier oai:identifier

oai:ecommons.cornell.edu:1813/3386