Settling the Polynomial Learnability of Mixtures of Gaussians

Details Settling the Polynomial Learnability of Mixtures of Gaussians Settling the Polynomial Learnability of Mixtures of Gaussians

2010-04-23

arxiv.org/abs/1004.4223v1

Computer Science

Learning

43 pages, 2 figures

Scientific paper

Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. We give an algorithm for this problem that has a running time, and data requirement polynomial in the dimension and the inverse of the desired accuracy, with provably minimal assumptions on the Gaussians. As simple consequences of our learning algorithm, we can perform near-optimal clustering of the sample points and density estimation for mixtures of k Gaussians, efficiently. The building blocks of our algorithm are based on the work Kalai et al. [STOC 2010] that gives an efficient algorithm for learning mixtures of two Gaussians by considering a series of projections down to one dimension, and applying the method of moments to each univariate projection. A major technical hurdle in Kalai et al. is showing that one can efficiently learn univariate mixtures of two Gaussians. In contrast, because pathological scenarios can arise when considering univariate projections of mixtures of more than two Gaussians, the bulk of the work in this paper concerns how to leverage an algorithm for learning univariate mixtures (of many Gaussians) to yield an efficient algorithm for learning in high dimensions. Our algorithm employs hierarchical clustering and rescaling, together with delicate methods for backtracking and recovering from failures that can occur in our univariate algorithm. Finally, while the running time and data requirements of our algorithm depend exponentially on the number of Gaussians in the mixture, we prove that such a dependence is necessary.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-386653