Interactive demo · Bayesian and Probabilistic Machine Learning · Chapter 9

Why EM climbs: the lower bound L(q, θ) and the KL gap

For any distribution q(Z) over the hidden labels, ln p(X|θ) = L(q, θ) + KL(q ‖ p(Z|X, θ)), and the KL term is never negative, so L is a lower bound. The E step sets q to the posterior at the current θ: the bound (green) then touches the log likelihood (red). The M step moves θ to the top of the bound; since the bound sits below the red curve, the log likelihood rises at least as much as the bound did. Here the model is a mixture of two Gaussians on the line with a single free parameter θ, so everything can be drawn exactly.

Data and model

Free parameter θ

EM

Move θ (q stays fixed)

q = posterior at θ_q

Scoreboard

Try these

Model: p(x|θ) = (1 − π) N(x|m₁, s₁²) + π N(x|m₂, s₂²), every value known except θ, which is either m₂ or π. q(Z) gives each point a probability q_n of belonging to component 2; the E step sets q_n to the responsibility (9.13). The data are drawn with a seeded generator, so everyone sees the same points.

In the lecture notes

Chapter 9 notes: Section 9.4 (the decomposition ln p = L + KL, the E and M steps as maximisations of L, Figures 9.11 to 9.14), Section 9.3 (the expected complete-data log likelihood Q(θ, θ^old)) and Section 9.2.2 (EM for Gaussian mixtures).
EM on real data, step by step: the companion demo K-means and EM on Old Faithful.
Python code: code/ch09_mixture_em.py (the mix1d_* functions and Figure 9.14) and the checks in code/checks_ch09.py.