Gaussian Mixtures and the EM Algorithm

K-means gives every point one label. A Gaussian mixture gives it a distribution over labels, and that single change buys elliptical clusters, calibrated uncertainty at the boundaries, and a proper likelihood you can compare across models. The price is an optimisation problem with no closed-form solution and a likelihood function that is unbounded above.

The model says each point comes from one of \(k\) Gaussians, chosen with probability \(\pi_j\):

Maximising \(\sum_i \log p(x_i)\) directly is hard because the log of a sum does not decompose. Expectation-maximisation sidesteps this by introducing the unobserved assignment as a latent variable (Dempster, Laird and Rubin, 1977, JRSS-B 39(1)).

The two steps

E step. With parameters fixed, compute the posterior probability that point \(i\) came from component \(j\), the responsibility:

M step. With responsibilities fixed, maximise the expected complete-data log-likelihood. Each parameter has a closed form, which is the whole reason EM is attractive here. Writing \(N_j = \sum_i \gamma_{ij}\):

These are the ordinary maximum likelihood estimates with each point weighted by how much it belongs to the component. K-means is the limiting case: force every \(\gamma_{ij}\) to 0 or 1, fix all \(\Sigma_j = \sigma^2 I\), and the M step becomes "take the mean of the assigned points".

Why the likelihood never decreases

EM is coordinate ascent on a lower bound. For any distribution \(q\) over latent variables,

The E step sets \(q\) to the exact posterior, which makes the KL term zero and the bound tight. The M step maximises \(\mathcal{L}\) over \(\theta\) with \(q\) fixed. Since the bound was tight before the M step and can only rise during it, the true log-likelihood cannot decrease. That is the guarantee, and it is worth noting exactly what it is not: it says nothing about reaching a global optimum, and the convergence rate is linear, often slow near the solution.

This decomposition is the same one that underlies the ELBO in variational inference. EM is the special case where the exact posterior is available, so the bound can be made tight; variational methods restrict \(q\) to a tractable family and accept a permanent gap.

When it breaks

The likelihood is unbounded above. Place a component's mean exactly on a single data point and shrink its covariance toward zero: the density at that point diverges and the log-likelihood goes to infinity. This is not a numerical artefact, it is a genuine property of the objective, and it appears in practice as a component collapsing onto a handful of points with a near-singular covariance. Covariance regularisation, adding \(\epsilon I\), restarting from the collapse, or a Bayesian prior on \(\Sigma\) are the standard defences and one of them is always required.

Parameter count grows quadratically in dimension. A full covariance costs \(d(d+1)/2\) parameters per component. At \(d = 100\) and \(k = 10\) that is over 50,000 covariance parameters, needing far more data than most problems have. Diagonal covariances cost \(d\) per component and reintroduce the axis-aligned assumption; tied covariances share one matrix across components. The choice is a real bias-variance decision, and defaulting to full covariance in high dimensions is a common and expensive mistake.

Local optima are severe. The likelihood surface is multimodal and EM finds whichever mode its initialisation is nearest. Standard practice is to initialise from k-means and run several restarts, keeping the best final likelihood.

Label switching makes the parameters non-identifiable. Permuting component indices gives an identical likelihood, so the components have no persistent identity across runs. Any downstream use of "component 3" needs an explicit matching step.

Selecting \(k\) by likelihood does not work. More components always fit better. BIC and AIC penalise parameter count and are the usual instruments; BIC's stronger penalty makes it the more conservative choice, and both assume the mixture model is correctly specified, which is exactly what is in doubt when you are choosing \(k\).