The EM Algorithm
The Expectation-Maximization (EM) algorithm handles models with latent variables by iterating two steps: (1) compute soft responsibilities for the hidden variables given current parameters, and (2) re-estimate parameters as if those responsibilities were the true counts.
The EM procedure, step by step
For a Gaussian Mixture Model with components, parameters , and observed data :
Step 0: Initialize , , (e.g. pick random data points as initial means).
Step 1: E-step. Compute responsibility of component for point :
This is a posterior probability — soft fractional assignment of point to cluster .
Step 2: M-step. Re-estimate every parameter using the soft assignments as weights:
Step 3: Check convergence. Compute the log-likelihood
and stop when (e.g. ). Otherwise return to Step 1.
Why EM works: the ELBO and monotonic likelihood
The two steps look like heuristics, but they are coordinate ascent on a single objective. Introduce any distribution over the latent variable and apply Jensen's inequality ( is concave):
The gap between the true log-likelihood and this lower bound is exactly a KL divergence:
Now both EM steps are maximizing the ELBO:
- E-step maximizes the ELBO over with fixed. The KL is minimized (to ) by setting — the posterior responsibilities. The bound becomes tight: .
- M-step maximizes the ELBO over with fixed, giving .
Chaining these two moves proves the log-likelihood never decreases:
The first is Jensen; the second is the M-step's maximization; the is the E-step making the bound tight. Since the log-likelihood is bounded above, EM must converge — to a local optimum.
The key insight
Every E-step makes the ELBO bound tight (zero gap). Every M-step pushes the bound up. Since the bound lower-bounds the true likelihood, the likelihood can only go up. This is why you never need to worry about EM diverging — the monotone guarantee is built into the algebra.
Watch it run
The argument above says the likelihood can never decrease. Here it is happening, on with two components — the same data worked by hand in the next section, so every number is checkable:
EM — soft responsibilities, weighted re-estimation, monotone likelihood
Four points — 1, 2, 4, 5 — and two Gaussian components initialized at μ = (2, 4) with σ = 1.5 and equal mixing weights. Nobody has told EM which point belongs to which component; that is precisely the latent variable it has to infer. Starting log-likelihood ℓ = -7.5136.
One full EM iteration on X = {1, 2, 4, 5} with two Gaussian components, in the same numbers as the hand-worked example above, then the loop run to convergence. Watch the E-step compute a soft responsibility for every point (never a hard assignment), the M-step re-estimate each parameter as a responsibility-weighted count, and the log-likelihood rise at every single iteration — the ELBO guarantee made visible.
What to notice as you step:
- Nothing is ever assigned. is 70.9% component 1 and 29.1% component 2, and it stays fractional forever. K-Means is the hard-assignment limit of this as ; EM keeps the uncertainty and lets it decay.
- The M-step is the fully-observed estimator with as counts. Each mean is a weighted average, each variance a weighted spread — exactly the formulas you would use if the labels were known, with expected counts standing in for real ones.
- The log-likelihood bars never go down. Not once, over the whole run, with no learning rate and no line search. That monotonicity is the ELBO argument cashed out, and it is also why EM cannot tell you it has found the global optimum.
A worked EM iteration by hand
Data , . Initialize , , .
E-step: compute responsibilities
For a 1D Gaussian: .
For , component 1 ():
For , component 2 ():
Applying the same formula to all points:
| 1 | 0.855 | 0.145 |
| 2 | 0.709 | 0.291 |
| 4 | 0.291 | 0.709 |
| 5 | 0.145 | 0.855 |
By symmetry, the table is perfectly antisymmetric around the midpoint . The effective counts are and .
M-step: re-estimate parameters
The variances (using the updated means):
Verify the guarantee
The log-likelihood after one step rose from to — exactly the monotonic increase the ELBO argument promises. The means pulled slightly toward the data and the Gaussians tightened.
How the responsibilities shift after the update
Re-running the E-step with the updated parameters :
| Point | (before) | (after) |
|---|---|---|
| 1 | 0.855 | 0.902 |
| 2 | 0.709 | 0.753 |
| 4 | 0.291 | 0.247 |
| 5 | 0.145 | 0.098 |
Points 1 and 2 now assign more firmly to cluster 1 (the mean moved toward them) while points 4 and 5 shift more firmly to cluster 2, and the reduced tightened the Gaussians, amplifying the separation.
Implementing EM in code
import numpy as np
from scipy.stats import norm
def em_gmm_1d(X, K=2, max_iter=100, tol=1e-6):
n = len(X)
# Initialize
idx = np.random.choice(n, K, replace=False)
mu, sigma, pi = X[idx].copy(), np.ones(K) * X.std(), np.ones(K) / K
log_liks = []
for it in range(max_iter):
# E-step
gamma = np.array([pi[k] * norm.pdf(X, mu[k], sigma[k]) for k in range(K)]).T
gamma /= gamma.sum(axis=1, keepdims=True)
# M-step
N = gamma.sum(axis=0)
mu = (gamma * X[:, None]).sum(axis=0) / N
sigma = np.sqrt(((gamma * (X[:, None] - mu)**2).sum(axis=0)) / N)
pi = N / n
# Log-likelihood
ll = np.log(sum(pi[k] * norm.pdf(X, mu[k], sigma[k]) for k in range(K)) + 1e-300).sum()
log_liks.append(ll)
if it > 0 and abs(log_liks[-1] - log_liks[-2]) < tol:
break
return mu, sigma, pi, gamma, log_liks
Related concepts
- Gaussian Mixture Models: the model this algorithm fits; the interactive EM visualization lets you step through E/M iterations
- Hidden Markov Models: the Baum–Welch algorithm is EM applied to sequences
- The EM Algorithm lesson: source lesson with the GMM application and code