Expectation-Maximization Algorithm Latent Variables Iterative Optimization
# Expectation-Maximization Algorithm: Latent Variables & Iterative Optimization
## Introduction & Motivation
EM algorithm optimizes likelihood of models with latent variables by iterating E-step (compute latent posterior) and M-step (update parameters). Guarantees monotonic likelihood increase; converges to local optimum. Foundation for GMM, HMM, mixture models, matrix factorization.
Motivation: Direct likelihood maximization intractable when latent variables exist. EM provides efficient alternating optimization. Elegant general framework for diverse models.
Applications: Clustering (GMM), sequence modeling (HMM), incomplete data imputation, missing value handling.
---
## Core Concepts & Theory
### Latent Variable Models
Data generation: \mathbf{x} observed, \mathbf{z} latent.
$$p(\mathbf{x}, \mathbf{z}|\boldsymbol{ heta}) = p(\mathbf{x}|\mathbf{z}, \boldsymbol{ heta}) p(\mathbf{z}|\boldsymbol{ heta})$$
Likelihood: L(\boldsymbol{ heta}) = \sum_{\mathbf{z}} p(\mathbf{x}, \mathbf{z}|\boldsymbol{ heta}).
### E-step
Compute posterior: Q(\mathbf{z}) = p(\mathbf{z}|\mathbf{x}, \boldsymbol{ heta}^{(t)}).
### M-step
Maximize expected log-likelihood:
$$\boldsymbol{ heta}^{(t+1)} = \arg\max_{\boldsymbol{ heta}} \mathbb{E}_Q[\log p(\mathbf{x}, \mathbf{z}|\boldsymbol{ heta})]$$
---
## Mathematical Formulation
Log-likelihood lower bound (ELBO):
$$\log p(\mathbf{x}|\boldsymbol{ heta}) \geq \mathbb{E}_Q[\log p(\mathbf{x}, \mathbf{z}|\boldsymbol{ heta})] + \mathbb{H}[Q]$$
EM maximizes ELBO; likelihood increases monotonically.
---
## Advanced Theory & Extensions
### Convergence
EM converges to local optimum; rate typically linear (geometric).
### Variational Inference
EM special case of variational inference; Q(\mathbf{z}) optimized over factorized family.
---
## Computational Considerations
Per iteration: O(n imes |\mathbf{z}|) for discrete z, O(n imes d^2) for continuous.
Convergence: Typically 10-100 iterations; varies by problem.
---
## Practical Implementation Strategies
### Initialization
Multiple random inits; select by likelihood.
### Convergence Monitoring
Track log-likelihood or parameter change; tolerance 1e-5.
### Handling Numerical Issues
Log-space computation to prevent underflow.
---
## Benchmark Datasets & Evaluation
GMM convergence: Synthetic 2D blobs; monitor likelihood.
HMM: Synthetic sequences; compare to Baum-Welch.
---
## Key Challenges & Limitations
### Local Optima
EM converges locally. Multiple inits and random restarts recommended.
### Computational Cost
E-step often expensive for large |z|; approximations (sampling) available.
---
## Hyperparameter Tuning
Initialization strategy; convergence threshold; max iterations.
---
## Real-World Applications & Case Studies
Speech Recognition: HMM-GMM via EM for acoustic modeling.
Clustering: GMM via EM for soft clustering.
---
## Integration with Other Methods
EM + Variational Inference → Approximate posterior in intractable models.
---
## Future Research Directions
Stochastic EM; online EM for streaming data; hardware acceleration.
---
## Summary & Key Takeaways
EM iteratively optimizes latent variable models by alternating between computing latent posterior (E-step) and maximizing expected likelihood (M-step), guaranteeing monotonic improvement.
Principles:
1. E-step computes latent posterior under current parameters.
2. M-step maximizes expected complete-data likelihood.
3. Likelihood increases monotonically.
4. Converges to local optimum.
5. Foundation for diverse models (GMM, HMM, etc.).
---
---
## Appendix: Practical Labs
### Lab 1: EM for GMM
from sklearn.mixture import GaussianMixture
from sklearn.datasets import make_blobs
import numpy as np
X, _ = make_blobs(n_samples=100, n_features=2, centers=3, random_state=42)
gmm = GaussianMixture(n_components=3, random_state=42, verbose=0)
gmm.fit(X)
log_likelihood = gmm.score(X) * len(X) # Convert to total likelihood
print(f"Final log-likelihood: {log_likelihood:.4f}")
assert np.isfinite(log_likelihood), "Likelihood should be finite"
assert log_likelihood < 0, "Likelihood typically negative"
print("✓ EM for GMM working")
if __name__ == "__main__":
print("Lab 1: EM for GMM - PASSED")### Lab 2: Convergence Monitoring
from sklearn.mixture import GaussianMixture
from sklearn.datasets import make_blobs
import numpy as np
X, _ = make_blobs(n_samples=150, n_features=2, centers=3, random_state=42)
gmm = GaussianMixture(n_components=3, n_init=1, random_state=42)
gmm.fit(X)
n_iter = gmm.n_iter_
print(f"Number of iterations to convergence: {n_iter}")
assert n_iter > 0 and n_iter < 1000, "Should converge in reasonable iterations"
print("✓ Convergence monitoring working")
if __name__ == "__main__":
print("Lab 2: Convergence - PASSED")### Lab 3: Multiple Initializations
from sklearn.mixture import GaussianMixture
from sklearn.datasets import make_blobs
import numpy as np
X, _ = make_blobs(n_samples=100, n_features=2, centers=3, random_state=42)
likelihoods = []
for seed in range(5):
gmm = GaussianMixture(n_components=3, random_state=seed)
gmm.fit(X)
ll = gmm.score(X)
likelihoods.append(ll)
best_ll = max(likelihoods)
print(f"Best likelihood: {best_ll:.4f}, Range: {min(likelihoods):.4f} to {max(likelihoods):.4f}")
assert len(likelihoods) == 5, "Should have 5 runs"
print("✓ Multiple initializations working")
if __name__ == "__main__":
print("Lab 3: Multiple Initializations - PASSED")### Lab 4: Posterior Computation
from sklearn.mixture import GaussianMixture
from sklearn.datasets import make_blobs
import numpy as np
X, _ = make_blobs(n_samples=50, n_features=2, centers=2, random_state=42)
gmm = GaussianMixture(n_components=2, random_state=42)
gmm.fit(X)
posteriors = gmm.predict_proba(X)
responsibilities = posteriors.sum(axis=0)
print(f"Cluster responsibilities: {responsibilities}")
assert np.allclose(posteriors.sum(axis=1), 1.0), "Should sum to 1 per sample"
assert len(responsibilities) == 2, "Should have 2 clusters"
print("✓ Posterior computation working")
if __name__ == "__main__":
print("Lab 4: Posterior Computation - PASSED")