Learning mixtures of Gaussians with maximum-a-posteriori oracle
Satyaki Mahalanabis; JMLR W&CP 15:489-497, 2011.
AbstractWe consider the problem of estimating the parameters of a mixture of distributions, where each component distribution is from a given parametric family e.g. exponential, Gaussian etc. We define a learning model in which the learner has access to a “maximum-a-posteriori” oracle which given any sample from a mixture of distributions, tells the learner which component distribution was the most likely to have generated it. We describe a learning algorithm in this setting which accurately estimates the parameters of a mixture of k spherical Gaussians in $R^d$ assuming the component Gaussians satisfy a mild separation condition. Our algorithm uses only polynomially many (in d, k) samples and oracle calls, and our separation condition is much weaker than those required by unsupervised learning algorithms like [Arora 01, Vempala 02].