Learning mixtures of Gaussians with maximum-a-posteriori oracle

Satyaki MahalanabisAISTATS 2011

Abstract

This paper explores a middle ground between fully unsupervised and supervised learning for the classic problem of estimating the parameters of a Mixture of Gaussians (MoG). By introducing a "Maximum-a-posteriori" (MAP) oracle, the author demonstrates that the parameters of overlapping Gaussians can be recovered much more efficiently and under significantly weaker separation conditions than previously thought possible. The proposed algorithm achieves polynomial-time recovery with logarithmic separation requirements, bridging the gap between spectral methods and brute-force algebraic approaches.

Introduction

Learning the parameters—means, variances, and mixing weights—of a Mixture of Gaussians is a fundamental task in statistics and machine learning. While popular algorithms like Expectation-Maximization (EM) are widely used, they lack strong theoretical guarantees for convergence to global optima.

Existing provable algorithms generally fall into two categories:

  1. Unsupervised Spectral Methods: These require significant "separation," meaning individual Gaussians must be far apart (typically by a factor of $d^{1/4}$ or $k^{1/4}$). They fail when components overlap significantly.
  2. Brute-force/Algebraic Methods: These can handle zero separation but require a number of samples that grows exponentially with the number of components ($k$), making them impractical for high-dimensional models.

This research asks whether a small amount of "side information" in the form of an expert oracle can enable the efficient learning of highly overlapping mixtures.

Methods

The core innovation is the Maximum-a-posteriori (MAP) Oracle. Given a sample $x$, the oracle identifies which Gaussian component $i$ maximizes the posterior probability $P(\text{component } i | x)$. The proposed algorithm operates in two distinct phases:

Phase 1: Initial Estimation (Oracle-Heavy)

The learner draws a set of samples and queries the MAP oracle for each. It employs a robust, median-based estimator to obtain a "ballpark" estimate of the means, variances, and weights. The use of the coordinate-wise median is critical; it provides robustness against "outlier" samples that belong to one Gaussian but are physically closer to the center of another due to overlap.

Phase 2: Refinement (Oracle-Free)

Once the initial estimates are sufficiently accurate, the learner no longer requires the oracle. It draws a larger set of samples and uses its current estimates to simulate the MAP oracle. This allows the algorithm to drive the error ($\epsilon$) down to an arbitrary level without increasing the number of expensive expert queries.

Key Results

The algorithm demonstrates a significant theoretical leap in both separation requirements and computational efficiency. Unlike previous spectral methods that required polynomial separation in terms of dimension $d$, this approach only requires logarithmic separation.

Comparison of separation conditions and computational complexity across various Mixture of Gaussians learning algorithms.

Performance Metrics

  • Sample Complexity: The algorithm requires $O(\frac{d \ln(dk)}{w_{min} \epsilon^2})$ samples to reach an error of $\epsilon$.
  • Oracle Complexity: It only requires $O(\frac{d \ln(dk)}{w_{min}})$ calls to the MAP oracle, a number independent of the final precision $\epsilon$.
  • Separation Condition: The algorithm works with a separation condition of $O(\sqrt{\ln(dk)})$, a massive improvement over the $d^{1/4}$ required by unsupervised methods.
  • Efficiency: The algorithm is strictly polynomial in the dimension ($d$) and the number of components ($k$), avoiding the exponential complexity found in non-separated unsupervised learning.

Discussion and Future Work

While this work provides a powerful new framework for MoG learning, several avenues for future research remain. The current proof is limited to spherical Gaussians, where the covariance matrix is a scaled identity matrix; extending this to arbitrary covariance matrices is a logical next step. Additionally, the model assumes a perfect MAP oracle. Real-world experts may be noisy or biased, necessitating further study into the algorithm's robustness under imperfect side information. Finally, an "active learning" approach could potentially reduce oracle complexity even further by strategically choosing which points to query.

Summary updated

BibTeX
@article{mahalanabis2011learning,
  author = {Satyaki Mahalanabis},
  title = {{Learning mixtures of Gaussians with maximum-a-posteriori oracle}},
  journal = {AISTATS},
  year = {2011},
}
Figure