Learning mixtures of separated nonspherical Gaussians

Mathematics – Probability

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Published at http://dx.doi.org/10.1214/105051604000000512 in the Annals of Applied Probability (http://www.imstat.org/aap/) by

Scientific paper

10.1214/105051604000000512

Mixtures of Gaussian (or normal) distributions arise in a variety of application areas. Many heuristics have been proposed for the task of finding the component Gaussians given samples from the mixture, such as the EM algorithm, a local-search heuristic from Dempster, Laird and Rubin [J. Roy. Statist. Soc. Ser. B 39 (1977) 1-38]. These do not provably run in polynomial time. We present the first algorithm that provably learns the component Gaussians in time that is polynomial in the dimension. The Gaussians may have arbitrary shape, but they must satisfy a ``separation condition'' which places a lower bound on the distance between the centers of any two component Gaussians. The mathematical results at the heart of our proof are ``distance concentration'' results--proved using isoperimetric inequalities--which establish bounds on the probability distribution of the distance between a pair of points generated according to the mixture. We also formalize the more general problem of max-likelihood fit of a Gaussian mixture to unstructured data.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Learning mixtures of separated nonspherical Gaussians 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 mixtures of separated nonspherical Gaussians, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning mixtures of separated nonspherical Gaussians will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-684546

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.