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 target | Dense MSE |
|---|---|
| Static 8×8 grid | 0.000134 |
| Trained one-shot Gridless64 (least squares) | 0.000104 |
| Feature k-means, hard groups | 0.0000857 |
| Feature + position k-means (m = 0.5), Gaussians fitted, least squares | 0.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.