EM & Gaussian Mixture Models
Soft clustering with latent variables: responsibilities and the EM updates.
The idea
A Gaussian mixture model is a probabilistic model for clustering. It specifies how the data was produced: pick a component $k$ with probability $\pi_{k}$, then draw the point from that component's Gaussian $\mathcal{N}(\mu_{k}, \sigma_{k}^{2})$. The label $z$ of the component picked is never observed — it is a latent variable, and clustering means inferring it.
Each half of the problem is solvable given the other. If we knew the parameters $\pi_{k}, \mu_{k}, \sigma_{k}^{2}$, Bayes' rule would give the posterior over $z$ for a point $x$: $\gamma_{k} = \mathbb{P}(z = k \mid x) = \frac{\pi_{k}\,\mathcal{N}(x \mid \mu_{k}, \sigma_{k}^{2})}{\sum_{j} \pi_{j}\,\mathcal{N}(x \mid \mu_{j}, \sigma_{j}^{2})}.$ If we knew the labels, the parameters would be ordinary averages within each group.
We know neither, so the EM algorithm alternates, holding each half fixed while improving the other. The E-step computes each $\gamma_{k}$ — called the responsibility — from the current parameters; the M-step re-estimates the parameters from the responsibilities.
Algorithm.
Algorithm: EM for a Gaussian Mixture Input: data x_1, ..., x_n, component count K, initial π_k, μ_k, σ_k² Output: fitted parameters π_k, μ_k, σ_k² and responsibilities γ_k 1. E-step: for each point x, γ_k = π_k N(x | μ_k, σ_k²) / Σ_j π_j N(x | μ_j, σ_j²) // Bayes' rule above 2. M-step: re-estimate each π_k, μ_k, σ_k² as a responsibility-weighted average 3. if the likelihood of the data stopped increasing, return the parameters 4. go to step 1
In the M-step, $\gamma_{k}$ is treated as the fraction of each point that belongs to component $k$: every sum that would count whole points weights them by responsibility instead, and the divisor $\sum_{n}\gamma_{k}$ is a fractional count. Each pass raises the likelihood of the observed data, which is why the loop makes progress.
Ways to work on it
- Walkthrough. Fit a Gaussian mixture by alternating soft assignments and parameter updates, and see the link to K-Means.
- Practice. Compute a data point's membership probability in a two-component mixture.
- Hardest. Re-estimate a mixture component's mean and variance in one full EM update.
Not sure where to start? Take the ten-question placement test.