Summary · Chapter 9

Clustering: k-means and EM

k-means: minimise J = Σp ‖tp − μc(p)‖². Lloyd's algorithm: assign each point to its nearest centre; move each centre to the mean of its points; repeat. J never rises; the result is a local minimum that depends on the start (k-means++ seeding helps).

Soft k-means: shares rpk = softmax over k of −β‖tp − μk‖²; centres are weighted means. Large β gives hard k-means.

EM for a Gaussian mixture: E-step = Chapter 3's responsibilities (softmax of log mass + log density); M-step = weighted moments (mass = owned share, centre = weighted mean, covariance = weighted spread). Likelihood never falls. k-means is the limit with equal, round, shrinking covariances.

Key fact: with hard responsibilities, least-squares features are group means and the dense squared error equals the k-means objective on features. Feature k-means optimises the hard version of the metric.

64 Gaussians, 16×16 targetDense MSE
Static 8×8 grid0.000134
Trained one-shot Gridless64 (least squares)0.000104
Feature k-means, hard groups0.0000857
Feature + position k-means (m = 0.5), Gaussians fitted, least squares0.0000862
Per-image optimum (100 images, 600 Adam steps from a grid)0.0000465

Quick experiments, plain PyTorch, 800 holdout images except where stated; widths tuned on the same images. From the k-means start, Adam reaches 0.0000729 / 0.0000674 / 0.0000606 / 0.0000483 after 4 / 8 / 16 / 200 steps (100 images, s5).

Defence: “Per-image k-means beat our first predictor because it directly optimises the hard-assignment form of our metric. That showed the predictor lacked feature-similarity grouping, so we built clustering into it. Faster k-means (e-means, Bessa et al., 2026) does not help: the limit is the hard objective and the per-image loop, not speed.”

Source: Bishop, Pattern Recognition and Machine Learning (2006), chapter 9.