EM, Step by Step

Soft assignments, monotone likelihood, and convergence to the wrong local optimum.

Ch 8 8.7

Animator

Unsupervised Learning & Text

22 mindifficulty 4/5

Controls

True clustersK*3

Fitted clustersK3

Try K ≠ K* to see mixtures merge or split truth.

Cluster separation2.600

Distance between true centers, in standard deviations.

Elongation2.500

Ratio of the long axis to the short axis of each true cluster.

Sample sizen220

Initialization

Random seed

Every result on this page is a deterministic function of the seed and the controls.

Step control

Stage 0 of 17 — initialization.

Scatter: points coloured by soft responsibility

Colour is a weighted blend of the component colours by posterior responsibility; ellipses show 1 and 2 standard-deviation contours.

component 1component 2component 3

Log-likelihood versus EM iteration

Every completed E-step can only raise (or hold) the log-likelihood — the curve never dips.

Log-likelihood

—

BIC

—

lower is better

Iterations

Converged

Δ log-likelihood < 1e-4

ARI vs. truth

0.856

1 = perfect recovery, 0 = chance

Compare seeds: EM is not a global optimizer

Same data, same fitted K, same initialization strategy — different seeds land on different local optima.

seed

seed	final log-likelihood	iterations	global best?
7	-862.445	9	yes
8	-862.445	7	yes
9	-862.445	11	yes
10	-862.445	7	yes

EM finds THE maximum-likelihood solution

EM only guarantees that each iteration does not decrease the log-likelihood; it climbs the nearest hill from wherever it starts. Different seeds — hence different random initializations — regularly land at different final log-likelihoods for the identical dataset. The "worst-case corner" initialization above is built to strand components far from the data mass, and it converges to a clearly inferior optimum compared with a k-means++ start.

Predict before you look

You run EM twice on the exact same dataset with the exact same fitted K, changing only the random seed used for initialization. What happens to the final log-likelihood?

Scenarios

Teacher-ready starting points.

Documentation

What this shows

A 2D Gaussian mixture fit by Expectation-Maximization, one E-step or M-step at a time. Points are coloured by their soft posterior responsibility (a blend of component colours), component covariance ellipses are drawn at one and two standard deviations, and a log-likelihood curve demonstrates the monotone-increase guarantee. A compare-seeds panel shows that different random initializations of the identical dataset can converge to different final log-likelihoods — EM is a local, not global, optimizer.

The EM update for a Gaussian mixture

A K-component Gaussian mixture models the density of a point x as a weighted sum of multivariate normal densities, one per component, with mixing weights that sum to one.

The E-step computes the responsibility that component c takes for point i: the posterior probability that i was generated by c, given the current parameters. This uses Bayes' rule applied component-by-component.

The M-step re-estimates each component's weight, mean, and covariance as responsibility-weighted averages over all points — exactly the same formulas as a weighted maximum-likelihood fit, with the weights being the responsibilities just computed.

Each E-step, by construction, computes the exact log-likelihood of the data under the current parameters; each M-step maximizes a lower bound that touches the true log-likelihood at the current parameters. The result is that the log-likelihood sequence is non-decreasing — but non-decreasing says nothing about which of possibly many local maxima the sequence approaches.

A small covariance floor is added after every M-step (clamping variances below a minimum and shrinking correlation until the determinant is safely positive) to prevent a component from collapsing onto a single point and producing infinite density.

p(x) = Σ_c π_c · N(x; μ_c, Σ_c)

γ_ic = π_c N(x_i; μ_c, Σ_c) / Σ_j π_j N(x_i; μ_j, Σ_j)

N_c = Σ_i γ_ic,  π_c ← N_c/n,  μ_c ← (1/N_c) Σ_i γ_ic x_i

Σ_c ← (1/N_c) Σ_i γ_ic (x_i − μ_c)(x_i − μ_c)ᵀ

ℓ(θ) = Σ_i log Σ_c π_c N(x_i; μ_c, Σ_c),  ℓ(θ^{(t+1)}) ≥ ℓ(θ^{(t)})

Try this

Set init to k-means++, run to convergence, and note the final log-likelihood and ARI. Reset EM, switch to "worst-case corner", and run to convergence again with the same data: the log-likelihood ends lower and ARI usually collapses.
Step through a single E-step then a single M-step and watch the ellipses move only after the M-step — the E-step changes only the colours (responsibilities), never the parameters.
Set elongation high (≈6) and separation low (≈1.5): watch a mixture with the correct K still struggle, since overlapping elongated ellipses are genuinely ambiguous.
Set fitted K to 2 with true K = 4: watch two true clusters get absorbed into one broad component while the log-likelihood curve still rises smoothly to its (lower) ceiling.
Open the compare-seeds panel with "random points" init and try five different seeds: read off the final log-likelihoods and see that they are not identical.

Common misconception

“EM finds the maximum likelihood solution — its guaranteed convergence means it finds the best fit.”

EM guarantees that the log-likelihood never decreases from one iteration to the next, and that the sequence converges to a stationary point. It does not guarantee that this stationary point is the global maximum. With bad initial parameters, EM converges to a local optimum with a strictly lower log-likelihood than another run from a better start on the identical data — exactly what the compare-seeds panel and the worst-case-corner initialization demonstrate.

DSPA3 §8.7 — Model-Based Clustering with EM