Big Learning Expectation Maximization

Yulai Cong, Sijia LiAAAI 2024 · DOI

Abstract

Mixture models trained via the Expectation-Maximization (EM) algorithm frequently converge to suboptimal local minima, particularly as the number of components increases. We present Big Learning Expectation Maximization (BigLearn-EM), a framework that leverages the "big learning" principle by simultaneously optimizing joint, marginal, and randomly transformed distributions. This multi-perspective approach allows the model to escape local optima that trap standard EM. Empirical evaluations on synthetic 25-component mixtures, real-world clustering benchmarks, and deep clustering tasks demonstrate that BigLearn-EM consistently achieves near-optimal performance and robustness to initialization, outperforming standard EM and several modern alternatives.

Introduction

Mixture models, particularly Gaussian Mixture Models (GMMs), are fundamental tools in statistical machine learning for tasks such as clustering and density estimation. However, their reliance on the Expectation-Maximization (EM) algorithm presents a significant challenge: extreme sensitivity to parameter initialization. For models with more than three components, the probability of EM becoming trapped in a "bad local optimum"—a solution that is locally stable but globally inferior—is exponentially high. While techniques like k-means++ provide better starting points, the underlying optimization remains brittle. BigLearn-EM addresses this by reformulating the training process to incorporate multiple diverse learning objectives simultaneously.

Methods: The Big Learning Principle

BigLearn-EM is inspired by the success of foundation models that learn from diverse tasks. Instead of a single joint matching objective, BigLearn-EM decomposes training into three distinct types of updates:

  1. Joint Matching: The standard EM update considering all features simultaneously.
  2. Marginal Matching: Updates focusing on random subsets of features.
  3. Transformed Marginal Matching: Updates performed in randomly rotated coordinate spaces using orthogonal matrices.
Figure 1b: Test KL Divergence over training steps, illustrating the transition between stages where marginal matching helps escape local optima.

The core insight is that a local optimum for the joint distribution is often not an optimum for a marginal or transformed distribution. By alternating between these perspectives, the algorithm provides a "gradient nudge" that pulls parameters out of traps. These updates are derived as analytical EM-type formulas, maintaining the computational efficiency of the original algorithm without requiring the complex hyperparameter tuning associated with gradient-based deep learning.

Key Insights

  • The Power of Inconsistency: Inconsistency between matching tasks is leveraged as a feature. When Joint-EM stalls, the Marginal-EM task provides the necessary signal to move toward a globally consistent solution.
  • Data Augmentation via Rotation: Random orthogonal transformations ($y = Ax$) allow the model to view data from infinite perspectives, acting as a powerful regularizer against over-focusing on specific feature correlations.
  • Component Preservation: To prevent mixture weights from dropping to zero (a common failure mode known as "dying components"), BigLearn-EM employs a Maximum a Posteriori (MAP) update to keep all $K$ components active.

Experimental Results

Simulated 25-Component GMM

In a 2D simulation designed with numerous local optima traps, standard EM failed almost universally. In contrast, BigLearn-EM reached the global optimum with high probability from random initializations.

Figure 6: Comparison of Joint-EM and BigLearn-EM on a 25-component grid. (a) Visual fit comparison; (b) Boxplot of Test Joint KL Divergence; (c) Example of Joint-EM failure.

Real-World and Deep Clustering Benchmarks

Across nine diverse real-world datasets (e.g., Pendigits, Covtype), BigLearn-EM consistently outperformed standard EM and advanced variants like Sliced-Wasserstein GMMs. On the Pendigits dataset, it achieved an Adjusted Rand Index (ARI) of 0.724, significantly higher than the 0.626 achieved by standard EM. Furthermore, on the FashionMNIST deep clustering benchmark, BigLearn-EM achieved an NMI of 0.681, surpassing several dedicated deep learning architectures like DEC and IDEC without requiring a neural network.

Conclusion and Future Work

BigLearn-EM provides a robust upgrade to a classic algorithm, significantly improving its global convergence properties. While empirical results are strong, providing a formal mathematical proof for global convergence with $K \ge 3$ components remains an open theoretical challenge. Future research will also focus on refining stopping criteria and exploring the algorithm's performance in even higher-dimensional latent spaces.

Summary updated

BibTeX
@inproceedings{cong2024big,
  author = {Yulai Cong and Sijia Li},
  title = {{Big Learning Expectation Maximization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i10.29050},
}
Figure