The EM AlgorithmOpen in Colab

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 KK components, parameters θ={πk,μk,Σk}\theta = \{\pi_k, \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k\}, and observed data {xi}i=1n\{\mathbf{x}_i\}_{i=1}^n:

Step 0: Initialize μk\boldsymbol{\mu}_k, Σk=I\boldsymbol{\Sigma}_k = I, πk=1/K\pi_k = 1/K (e.g. pick KK random data points as initial means).

Step 1: E-step. Compute responsibility of component kk for point ii:

γik=πk(t) N(xi∣μk(t),Σk(t))∑j=1Kπj(t) N(xi∣μj(t),Σj(t))\gamma_{ik} = \frac{\pi_k^{(t)}\,\mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_k^{(t)}, \boldsymbol{\Sigma}_k^{(t)})}{\displaystyle\sum_{j=1}^K \pi_j^{(t)}\,\mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_j^{(t)}, \boldsymbol{\Sigma}_j^{(t)})}

This is a posterior probability — soft fractional assignment of point ii to cluster kk.

Step 2: M-step. Re-estimate every parameter using the soft assignments as weights:

Nk=∑i=1nγikN_k = \sum_{i=1}^n \gamma_{ik} μk(t+1)=1Nk∑i=1nγik xi\boldsymbol{\mu}_k^{(t+1)} = \frac{1}{N_k}\sum_{i=1}^n \gamma_{ik}\,\mathbf{x}_i Σk(t+1)=1Nk∑i=1nγik(xi−μk(t+1))(xi−μk(t+1))⊤\boldsymbol{\Sigma}_k^{(t+1)} = \frac{1}{N_k}\sum_{i=1}^n \gamma_{ik}\bigl(\mathbf{x}_i - \boldsymbol{\mu}_k^{(t+1)}\bigr)\bigl(\mathbf{x}_i - \boldsymbol{\mu}_k^{(t+1)}\bigr)^\top πk(t+1)=Nkn\pi_k^{(t+1)} = \frac{N_k}{n}

Step 3: Check convergence. Compute the log-likelihood

ℓ(θ)=∑i=1nlog⁡∑k=1Kπk N(xi∣μk,Σk)\ell(\theta) = \sum_{i=1}^n \log\sum_{k=1}^K \pi_k\,\mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)

and stop when ∣ℓ(t+1)−ℓ(t)∣<ε|\ell^{(t+1)} - \ell^{(t)}| < \varepsilon (e.g. 10−610^{-6}). 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 q(z)q(z) over the latent variable and apply Jensen's inequality (log⁡\log is concave):

log⁡p(x∣θ)=log⁡∑zq(z) p(x,z∣θ)q(z)  ≥  ∑zq(z)log⁡p(x,z∣θ)q(z)⏟ELBO(q,θ).\log p(\mathbf{x}\mid\theta) = \log \sum_z q(z)\,\frac{p(\mathbf{x},z\mid\theta)}{q(z)} \;\ge\; \underbrace{\sum_z q(z)\log\frac{p(\mathbf{x},z\mid\theta)}{q(z)}}_{\text{ELBO}(q,\theta)}.

The gap between the true log-likelihood and this lower bound is exactly a KL divergence:

log⁡p(x∣θ)−ELBO(q,θ)=KL(q(z) ∥ p(z∣x,θ))≥0.\log p(\mathbf{x}\mid\theta) - \text{ELBO}(q,\theta) = \text{KL}\bigl(q(z)\,\big\|\,p(z\mid\mathbf{x},\theta)\bigr) \ge 0.

Now both EM steps are maximizing the ELBO:

  • E-step maximizes the ELBO over qq with θ\theta fixed. The KL is minimized (to 00) by setting q(z)=p(z∣x,θ(t))q(z) = p(z\mid\mathbf{x},\theta^{(t)}) — the posterior responsibilities. The bound becomes tight: ELBO=log⁡p(x∣θ(t))\text{ELBO} = \log p(\mathbf{x}\mid\theta^{(t)}).
  • M-step maximizes the ELBO over θ\theta with qq fixed, giving θ(t+1)\theta^{(t+1)}.

Chaining these two moves proves the log-likelihood never decreases:

log⁡p(x∣θ(t+1))  ≥  ELBO(q,θ(t+1))  ≥  ELBO(q,θ(t))  =  log⁡p(x∣θ(t)).\log p(\mathbf{x}\mid\theta^{(t+1)}) \;\ge\; \text{ELBO}(q,\theta^{(t+1)}) \;\ge\; \text{ELBO}(q,\theta^{(t)}) \;=\; \log p(\mathbf{x}\mid\theta^{(t)}).

The first ≥\ge 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 X={1,2,4,5}X = \{1, 2, 4, 5\} 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

1/14

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.

python
1def em(X, mu, sd, pi, iters):
2 for _ in range(iters):
3 # E-step: responsibility of k for x_i
4 g = [[pi[k] * N(x, mu[k], sd[k])
5 for k in range(K)] for x in X]
6 g = [[v / sum(row) for v in row]
7 for row in g]
8 # M-step: weighted counts -> parameters
9 Nk = [sum(g[i][k] for i in range(n))
10 for k in range(K)]
11 mu = [sum(g[i][k] * X[i]
12 for i in range(n)) / Nk[k]
13 for k in range(K)]
14 sd = [sqrt(sum(g[i][k] * (X[i] - mu[k])**2
15 for i in range(n)) / Nk[k])
16 for k in range(K)]
17 pi = [Nk[k] / n for k in range(K)]
18 ll = loglik(X, mu, sd, pi)
19 return mu, sd, pi
state
initial mixture
060.5501245μ1μ2x
parameters
μ1 → 2.00μ2 → 4.00σ1 → 1.500σ2 → 1.500π → (0.50, 0.50)ℓ → -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. x=2x = 2 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 σ→0\sigma \to 0; EM keeps the uncertainty and lets it decay.
  • The M-step is the fully-observed estimator with γ\gamma 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 X={1,2,4,5}X = \{1, 2, 4, 5\}, K=2K = 2. Initialize μ=(2,4)\mu = (2, 4), σ=(1.5,1.5)\sigma = (1.5, 1.5), π=(0.5,0.5)\pi = (0.5, 0.5).

E-step: compute responsibilities

For a 1D Gaussian: N(x∣μ,σ)=1σ2πexp⁡ ⁣(−(x−μ)22σ2)\mathcal{N}(x \mid \mu, \sigma) = \frac{1}{\sigma\sqrt{2\pi}}\exp\!\bigl(-\frac{(x-\mu)^2}{2\sigma^2}\bigr).

For x=1x = 1, component 1 (μ=2,σ=1.5\mu=2, \sigma=1.5):

N(1∣2,1.5)=11.52π e−12⋅2.25=0.2660×e−0.222=0.2130\mathcal{N}(1 \mid 2, 1.5) = \frac{1}{1.5\sqrt{2\pi}}\,e^{-\frac{1}{2\cdot 2.25}} = 0.2660 \times e^{-0.222} = 0.2130

For x=1x = 1, component 2 (μ=4,σ=1.5\mu=4, \sigma=1.5):

N(1∣4,1.5)=0.2660×e−94.5=0.2660×e−2.0=0.0360\mathcal{N}(1 \mid 4, 1.5) = 0.2660 \times e^{-\frac{9}{4.5}} = 0.2660 \times e^{-2.0} = 0.0360 γ1,1=0.5×0.21300.5×0.2130+0.5×0.0360=0.10650.1245=0.855\gamma_{1,1} = \frac{0.5 \times 0.2130}{0.5 \times 0.2130 + 0.5 \times 0.0360} = \frac{0.1065}{0.1245} = 0.855

Applying the same formula to all points:

xix_iγi,1\gamma_{i,1}γi,2\gamma_{i,2}
10.8550.145
20.7090.291
40.2910.709
50.1450.855

By symmetry, the table is perfectly antisymmetric around the midpoint x=3x = 3. The effective counts are N1=0.855+0.709+0.291+0.145=2.0N_1 = 0.855 + 0.709 + 0.291 + 0.145 = 2.0 and N2=2.0N_2 = 2.0.

M-step: re-estimate parameters

μ1′=0.855(1)+0.709(2)+0.291(4)+0.145(5)2.0=0.855+1.418+1.164+0.7252.0=4.1622.0=2.08\mu_1' = \frac{0.855(1)+0.709(2)+0.291(4)+0.145(5)}{2.0} = \frac{0.855+1.418+1.164+0.725}{2.0} = \frac{4.162}{2.0} = 2.08 μ2′=0.145(1)+0.291(2)+0.709(4)+0.855(5)2.0=3.92\mu_2' = \frac{0.145(1)+0.291(2)+0.709(4)+0.855(5)}{2.0} = 3.92

The variances (using the updated means):

(σ1′)2=0.855(1−2.08)2+0.709(2−2.08)2+0.291(4−2.08)2+0.145(5−2.08)22.0≈1.655(\sigma_1')^2 = \frac{0.855(1-2.08)^2 + 0.709(2-2.08)^2 + 0.291(4-2.08)^2 + 0.145(5-2.08)^2}{2.0} \approx 1.655 σ1′≈1.286,σ2′≈1.286,π′=(0.5, 0.5)\sigma_1' \approx 1.286, \quad \sigma_2' \approx 1.286, \quad \pi' = (0.5,\ 0.5)

Verify the guarantee

The log-likelihood after one step rose from −7.514-7.514 to −7.390-7.390 — 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 (μ1(1)=2.08,μ2(1)=3.92,σ(1)=1.286)(\mu_1^{(1)} = 2.08, \mu_2^{(1)} = 3.92, \sigma^{(1)} = 1.286):

Pointγi,1(0)\gamma_{i,1}^{(0)} (before)γi,1(1)\gamma_{i,1}^{(1)} (after)
10.8550.902
20.7090.753
40.2910.247
50.1450.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 σ\sigma tightened the Gaussians, amplifying the separation.

Implementing EM in code

Python
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

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
The EM AlgorithmSoftmax + Cross-Entropy G…The EM AlgorithmGaussian Mixture ModelsHidden Markov Models