publication . Preprint . Conference object . 2010

Settling the Polynomial Learnability of Mixtures of Gaussians

Ankur Moitra; Gregory Valiant;
Open Access English
  • Published: 23 Apr 2010
Abstract
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 consi...
Subjects
free text keywords: Computer Science - Learning, Computer Science - Data Structures and Algorithms, 68Q32, Algorithm, Polynomial, Mathematical optimization, Mixture model, Univariate, Backtracking, Computational complexity theory, Time complexity, Gaussian process, symbols.namesake, symbols, Mathematics, Discrete mathematics, Density estimation
35 references, page 1 of 3

[1] D. Achlioptas and F. McSherry. On spectral learning of mixtures of distributions. In COLT, pages 458{469, 2005.

[2] S. Arora and R. Kannan. Learning mixtures of arbitrary Gaussians. In STOC, pages 247{257, 2001.

[3] M. Belkin and K. Sinha. Learning Gaussian mixtures with arbitrary separation. CoRR, 2009.

[4] S. C. Brubaker and S. Vempala. Isotropic PCA and a ne-invariant clustering. In FOCS, pages 551{560, 2008. [OpenAIRE]

[5] K. Chaudhuri and S. Rao. Learning mixtures of product distributions using correlations and independence. In COLT, pages 9{20, 2008.

[6] K. Chaudhuri and S. Rao. Beyond Gaussians: Spectral methods for learning mixtures of heavy-tailed distributions. In COLT, pages 21{32, 2008.

[7] A. Dasgupta, J. Hopcroft, J. Kleinberg, and M. Sandler. On learning mixtures of heavy-tailed distributions. In FOCS, pages 491{500, 2005. [OpenAIRE]

[8] S. Dasgupta. Learning mixtures of Gaussians. In FOCS, pages 634{644, 1999.

[9] S. Dasgupta, A. T. Kalai, and C. Monteleoni. Analysis of perceptron-based active learning. In COLT, pages 249{263, 2005.

[10] S. Dasgupta and L. J. Schulman. A two-round variant of EM for Gaussian mixtures. In UAI, pages 152{159, 2000.

[11] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM Algorithm. J. Roy. Statist. Soc. Ser. B, 39:1{38, 1977.

[12] A. Dinghas. Uber eine klasse superadditiver mengenfunktionale von brunn{minkowski{lusternik-schem typus. Math. Zeitschr., 68:111{125, 1957.

[13] J. Feldman, R. A. Servedio, and R. O'Donnell. PAC learning axis-aligned mixtures of Gaussians with no separation assumption. In COLT, pages 20{34, 2006. [OpenAIRE]

[14] A. A. Giannopoulos and V. D. Milman. Concentration property on probability spaces. Adv. Math., 156:77{106, 2000. [OpenAIRE]

[15] P. J. Huber. Projection pursuit. Ann. Statist. 13:435{475, 1985.

35 references, page 1 of 3
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue