TL;DR
The Expectation-Maximization (EM) algorithm is a workhorse for learning parameters in models with hidden variables, but it can be notoriously slow. This paper empirically investigates various acceleration techniques for EM, particularly in the context of Gaussian mixture models, to understand which methods offer the best speed-up across different problem complexities. They find that while some accelerations consistently improve performance, others can be detrimental in "easy" cases, highlighting the problem-dependent nature of choosing the right acceleration strategy.
What Problem Does This Paper Address?
Many real-world problems in machine learning and statistics involve learning the parameters of probabilistic models where some variables are not directly observed (hidden variables). The Expectation-Maximization (EM) algorithm is a widely used iterative method to find the maximum likelihood estimates for such models. However, EM is known for its slow convergence, especially when the model's parameters are close to each other or the likelihood surface is "elongated." While several methods have been proposed to speed up EM, there's a lack of comprehensive empirical comparisons to guide practitioners on which acceleration technique to use in different scenarios. This paper aims to fill that gap by empirically comparing several EM acceleration methods on a well-understood problem: density estimation with Gaussian mixtures.
Methods
The paper focuses on comparing EM with several acceleration strategies. The core idea behind most accelerations is to leverage information from previous EM iterations or to combine EM with gradient-based optimization methods.
- EM (Baseline): The standard Expectation-Maximization algorithm.
- Gradient Ascent: A basic local search method that moves in the direction of the gradient of the log-likelihood. This method, however, doesn't inherently handle parameter constraints.
- Projected Gradient Ascent: A modification of gradient ascent to respect parameter constraints (e.g., probabilities summing to 1).
- Optimized-Step-Size Gradient Ascent: Gradient ascent where the step size is optimized at each iteration using a line search. This can lead to "zig-zagging" behavior.
- Conjugate Gradient (CG): An optimization method that aims to eliminate zig-zagging by optimizing along conjugate directions, generally leading to faster convergence than simple gradient ascent.
- Parameterized EM (PEM): This method uses the change in parameters from an EM iteration to take a step in that direction. It can be used with fixed step sizes or optimized step sizes (PEM(opt)).
- Conjugate Gradient with EM Information (CG+EM): This approach uses the EM update to find better conjugate directions for the gradient descent. It can also be applied in a reparameterized space (CG+EM(rp)).
The authors emphasize that the computational cost of computing the gradient and the EM update is often similar, allowing them to compare methods based on "EM-equivalent iterations" rather than raw CPU time.
Datasets
The experiments were conducted on synthetic datasets generated from Gaussian mixture models with varying degrees of separation between the Gaussian components. Specifically, they used:
- Data Set 1: Two Gaussians with means at (0,0) and (3,3).
- Data Set 2: Two Gaussians with means at (0,0) and (2,2).
- Data Set 3: Two Gaussians with means at (0,0) and (1,1) (harder to distinguish).
- Data Set 4: A more complex scenario with M=5 components and d=2 dimensions (easy).
- Data Set 5: A more complex scenario with M=5 components and d=2 dimensions (harder to distinguish).
- Data Set 6: A higher dimensional scenario with M=5 components and d=5 dimensions.
- IRAS data set: A real-world dataset with N=5420 data points and d=93 dimensions, used for MAP estimation.
Key Insights and Ideas
- Problem Dependency is Crucial: No single acceleration method is universally superior. The effectiveness of an acceleration technique heavily depends on the "difficulty" of the problem, particularly how close the underlying components (e.g., Gaussian means) are.
- "Easy" vs. "Hard" Cases: Methods like CG+EM and CG+EM(rp) show significant speed-ups in "hard" cases where components are close. However, in "easy" cases, these methods can sometimes slow down convergence due to premature activation of the acceleration step.
- Fixed-Step-Size PEM Consistency: Parameterized EM with fixed step sizes (PEM(1.5), PEM(1.9)) demonstrated consistent behavior across different data sets, though their speed-up was less dramatic than CG+EM in hard cases.
- Line Search Pitfalls: While line searches can optimize step sizes, they can be problematic and lead to failures or slow downs, especially in complex or noisy likelihood surfaces. Some methods that rely heavily on line searches (like CG+EM(rp) and PEM(opt)) sometimes failed or performed poorly.
- EM's Robustness: Despite its slowness, EM is praised for its impressive performance away from the solution, its global convergence properties, and its monotonicity, making it a reliable default choice.
Key Results
- CG+EM and CG+EM(rp) Dominance in Hard Cases: These methods achieved the highest speed-ups (e.g., ~12.8x for CG+EM on Data Set 3) in scenarios where Gaussian components were close and difficult to distinguish.
- PEM(1.5) and PEM(1.9) Offer Moderate Speed-ups: These fixed-step-size PEM variants provided consistent speed-ups (e.g., ~1.7x on Data Set 3) across various difficulties, without the significant slow-downs seen in CG+EM on easy cases.
- CG and PEM(opt) Generally Underperform: Standard Conjugate Gradient and optimized-step-size Parameterized EM did not consistently outperform EM or other accelerated methods.
- IRAS Data Insights: On the high-dimensional IRAS data, fixed-step-size PEM showed the best performance, suggesting that simpler accelerations can be effective when the problem is not "smooth" enough for conjugate gradient methods.
Limitations and Future Work
- Stopping Rule Sensitivity: The paper acknowledges that their simple stopping rule (change in log-likelihood < 10^-5) might not be optimal and could be improved with scaled or adaptive rules. A better stopping rule could potentially reduce the need for some accelerations.
- Generalization to Other Models: The study is primarily focused on Gaussian mixture models. The authors suggest that similar comparative analyses are needed for other model classes like Bayesian networks and HMMs to verify if the observed "easy" vs. "hard" case characterizations hold.
- High Dimensionality and Parameter-to-Sample Ratio: The behavior on the IRAS dataset, and some unusual runs on synthetic data, suggest that the ratio of parameters to samples, and high dimensionality, can introduce complexities that affect acceleration performance. Further investigation into these factors is warranted.
- Numerical Instability: The authors note that numerical instability can be a reason for poor performance in some cases, especially when dealing with very small variances or probabilities.
Summary updated