The Expectation-Maximization Algorithm
GMMs have latent variables (which component generated each point?) that we never observe. The EM algorithm handles this by iteratively guessing the latent variables and optimizing parameters. It is the optimization slot for models with hidden structure, where plain gradient descent is awkward but a guaranteed-to-improve alternating scheme works beautifully.
Real-world examples: Missing data imputation, topic modeling (LDA), hidden Markov models, clustering with partial labels.
The latent variable problem
In a GMM, we observe but not (which component generated it). If we knew , we could easily compute the MLE:
But we don't know . EM solves this by alternating between two steps.
Intuition
Imagine you're a detective. You don't know who committed the crime (latent variable), but you have suspects (components). First, you estimate the probability each suspect did it (E-step). Then you update your theory of the crime based on those probabilities (M-step). Repeat until your theory stabilizes.
The two steps
E-step (Expectation)
Compute the expected value of the latent variables given current parameters:
M-step (Maximization)
Update parameters using the responsibilities as "soft" assignments:
import numpy as np
from scipy.stats import multivariate_normal
def em_gmm(X, K, max_iter=100, tol=1e-6):
n, d = X.shape
# Initialize parameters randomly
indices = np.random.choice(n, K, replace=False)
means = X[indices].copy()
covs = [np.eye(d) for _ in range(K)]
weights = np.ones(K) / K
log_likelihoods = []
for iteration in range(max_iter):
# E-step: compute responsibilities
responsibilities = np.zeros((n, K))
for k in range(K):
responsibilities[:, k] = weights[k] * multivariate_normal.pdf(X, means[k], covs[k])
responsibilities /= responsibilities.sum(axis=1, keepdims=True)
# M-step: update parameters
N_k = responsibilities.sum(axis=0)
for k in range(K):
means[k] = (responsibilities[:, k:k+1].T @ X) / N_k[k]
diff = X - means[k]
covs[k] = (responsibilities[:, k:k+1] * diff).T @ diff / N_k[k]
covs[k] += 1e-6 * np.eye(d) # regularization
weights = N_k / n
# Compute log-likelihood
ll = 0
for k in range(K):
ll += weights[k] * multivariate_normal.pdf(X, means[k], covs[k])
log_likelihoods.append(np.log(ll + 1e-10).sum())
if iteration > 0 and abs(log_likelihoods[-1] - log_likelihoods[-2]) < tol:
print(f"Converged at iteration {iteration}")
break
labels = responsibilities.argmax(axis=1)
return labels, means, covs, weights, log_likelihoods
Why it works and worked example
The E-step and M-step are coordinate ascent on the ELBO — an evidence lower bound on the log-likelihood obtained via Jensen's inequality. Each E-step makes the bound tight (zero KL gap); each M-step pushes the bound up. Chaining these two moves proves the log-likelihood never decreases, guaranteeing convergence to a local optimum.
For the full ELBO derivation, the monotonic proof, and a complete one-iteration hand trace on with (including every responsibility calculation and parameter re-estimate), see:
Worked example: 2D GMM
import matplotlib.pyplot as plt
from sklearn.mixture import GaussianMixture
# Generate mixture data
np.random.seed(42)
X1 = np.random.multivariate_normal([0, 0], [[1, 0], [0, 1]], 200)
X2 = np.random.multivariate_normal([5, 5], [[2, 0.5], [0.5, 2]], 200)
X = np.vstack([X1, X2])
# Fit GMM
gmm = GaussianMixture(n_components=2, covariance_type='full', n_init=10)
labels = gmm.fit_predict(X)
plt.figure(figsize=(10, 5))
plt.subplot(1, 2, 1)
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='coolwarm', s=10, alpha=0.7)
plt.scatter(gmm.means_[:, 0], gmm.means_[:, 1], c='black', marker='X', s=200)
plt.title('GMM Clustering')
plt.subplot(1, 2, 2)
probs = gmm.predict_proba(X)
plt.scatter(X[:, 0], X[:, 1], c=probs[:, 1], cmap='coolwarm', s=10, alpha=0.7)
plt.colorbar(label='P(component 2)')
plt.title('Soft Assignments (probabilities)')
plt.tight_layout()
plt.show()
EM beyond GMMs
EM is a general framework for latent variable models:
| Model | Latent variables | What EM does |
|---|---|---|
| GMM | Cluster assignments | Soft clustering |
| HMM | Hidden states | Forward-backward algorithm |
| Topic models (LDA) | Topic assignments | Topic inference |
| Missing data | Missing values | Imputation |
EM is not clustering alone
EM finds maximum likelihood parameters for latent variable models. Clustering is just one application. The same framework powers speech recognition (HMMs), topic modeling (LDA), and missing data analysis.
Exercise
What guarantee does the EM algorithm provide at each iteration?
Need a hint?
Think about what EM optimizes and whether it can get worse.
Exercise
In the EM algorithm, what does the E-step compute?
Need a hint?
E stands for Expectation.
Exercise
Why is initialization important for EM?
Need a hint?
EM converges to a local optimum.
Common mistakes
- Bad initialization: Random initialization can converge to poor local optima. Use K-Means++ initialization or run multiple times.
- Singular covariances: If a component collapses to a single point, the covariance becomes singular. Add regularization: .
- Not enough data per component: EM needs sufficient data to estimate parameters. Rule of thumb: at least points per component.
- Ignoring convergence criteria: Don't just run for a fixed number of iterations. Check if the log-likelihood change is below a threshold.
Key takeaways
- EM alternates an E-step (soft responsibilities) and M-step (re-estimate parameters).
- It handles latent variables, which component generated each point is unknown.
- The log-likelihood is non-decreasing; EM finds a local optimum (use restarts).
- The same E/M pattern powers HMMs, missing-data imputation, and more.
Related concepts
- Gaussian Mixture Models: the canonical model EM fits; the interactive EM visualization there lets you step through E/M iterations and watch soft responsibilities shift in real time
- Hidden Markov Models: Baum-Welch is EM for sequences
- Factor Analysis: a latent-variable model EM fits, with per-dimension noise
- Independent Component Analysis: blind source separation via non-Gaussianity