Gaussian Mixture Models and Expectation-Maximization

In K-means Clustering every observation belonged to exactly one cluster, and the algorithm committed to that answer the moment it assigned the point. That commitment is convenient, but it hides two things we often care about. The first is doubt: a point sitting between two clusters is not really "80% cluster A and 20% cluster B" to k-means; it is entirely cluster A or entirely cluster B depending on which side of the boundary it happens to fall. The second is shape: k-means measures similarity with a plain Euclidean distance, so its nearest-centroid decision regions have straight boundaries. The squared-distance objective favours compact, roughly isotropic groups, but the regions themselves need not be spherical or equally sized.

A Gaussian mixture model (GMM) replaces that hard machinery with a probability model. We imagine that nature first picked one of $K$ hidden groups for each observation, then drew the observation from a Gaussian distribution belonging to that group. Because the group labels are never observed, they are latent variables. The model does not need to be told the labels; it infers a probability distribution over them, which is exactly the soft assignment that k-means refused to give us.

The price of that richer model is that the likelihood we want to maximize contains the log of a sum, so the general multi-component maximum likelihood equations do not yield a direct closed-form joint parameter estimate like the simpler examples in Maximum Likelihood Estimation. The Expectation-Maximization (EM) algorithm solves this by repeatedly pretending the latent labels are known, taking their expected values under the current parameters, and then re-estimating the parameters as if those expectations were counts. An exact E-step followed by an M-step that increases the auxiliary objective cannot decrease the observed-data likelihood. That guarantee requires the stated updates and valid parameters; the diagonal-addition safeguard used in our practical code does not automatically inherit it. Even exact nondecrease is weaker than finding a global maximum.

By the end of this chapter we will have derived the E-step and M-step from scratch, worked a four-point example entirely by hand, built a numerically stable implementation that handles the underflow problems a naive version would hit, and compared its soft assignments against k-means on clusters that are deliberately overlapping and elliptical.