Part III · Placing the Gaussians · Chapter 9

Clustering: k-means and EM

About 20 minutes. Tap Continue to move on; nothing later depends on anything you have not yet seen.

9.1 Placement is a grouping problem

Part I gave you the read-out: given where the Gaussians are, their features follow by least squares. Part II gave you the target: a grid of DINOv3 tokens. What is left is the hardest part, and the part a reviewer will press on: where do the Gaussians go?

The classical answer is clustering. Put tokens that look alike into the same group, then let one Gaussian own each group. This chapter teaches the two classical clustering algorithms, k-means and EM, and shows exactly how your project used them: as the baseline the first trained predictor lost to, and as the starting point for per-image optimisation.

By the end you can state the k-means objective and the two steps of Lloyd's algorithm, explain EM for a Gaussian mixture as Chapter 3's responsibilities plus a moment fit, and say why per-image k-means is a strong baseline for dense error.

Before reading on: you have 256 tokens, each with a 384-number feature vector and a position. How would you choose where 64 Gaussians go? One or two sentences.

9.2 k-means and Lloyd's algorithm

Take P points t1, …, tP (here, the 256 token feature vectors of one image) and a number of groups K. Each group k gets a centre μk, and each point a label c(p) saying which group it is in.

k-means. Choose labels and centres to minimise the total squared distance from every point to the centre of its own group: J = Σp ‖tp − μc(p)‖²

Minimising J exactly is hard, because there are astronomically many labellings. Lloyd's algorithm[Lloyd, 1982] alternates two easy steps instead:

  1. Assign. Hold the centres fixed; give each point the label of its nearest centre. This is the best labelling for those centres.
  2. Update. Hold the labels fixed; move each centre to the mean of its points. The mean is the point that minimises the summed squared distance to a group, so this is the best centre for those labels.

Each step can only lower J or leave it unchanged, and there are finitely many labellings, so the algorithm stops. But it stops at a local minimum: where it ends depends on where the centres start. That is why seeding matters; k-means++ picks starting centres spread out in proportion to squared distance and comes with a guarantee on the expected result[Arthur and Vassilvitskii, 2007]. Your per-image k-means baselines use this seeding (scripts/research/quick/s3_static_layouts.py, 30 Lloyd iterations).

9.3 Soft k-means

The assign step makes a hard choice: a point halfway between two centres goes wholly to one. Small moves of a centre can flip labels, so J jumps. A softer rule lets each point share itself among the groups, more to the closer ones:

rpk = exp(−β ‖tp − μk‖²) / Σj exp(−β ‖tp − μj‖²)

Here rpk is the share of point p given to group k; the shares of each point sum to one. The update step becomes a weighted mean, μk = Σp rpk tp / Σp rpk.

The number β is a stiffness. Small β: every point is shared almost equally and all centres drift to the overall mean. Large β: the nearest centre takes nearly everything, and you are back to hard k-means. In between, the assignments vary smoothly with the centres, which is exactly what a method trained by gradients will need in Chapter 10.

You have seen this formula before. It is a softmax over groups, the same shape as Chapter 3's responsibilities: rk(x) = softmax over k of (log mass + log density). The next step makes the link exact.

9.4 Gaussian mixtures and EM

Chapter 3 introduced a mixture model: K Gaussians, each with a mass πk, a centre μk and a covariance Σk, and the responsibility of each Gaussian for a point. Fitting a mixture to data means choosing those parameters so that the data are as probable as possible. The standard method is EM[Dempster et al., 1977], which has the same two-step rhythm as Lloyd's algorithm:

EM for a Gaussian mixture.
E-step: responsibilities, exactly as in Chapter 3: rpk = πk 𝒩(xp | μk, Σk) / Σj πj 𝒩(xp | μj, Σj) M-step: with Nk = Σp rpk, the weighted moments: πk = Nk / P,  μk = Σp rpk xp / Nk,
Σk = Σp rpk (xp − μk)(xp − μk)ᵀ / Nk

In words: the mass is the share of points a Gaussian owns, the centre is the weighted mean of their positions, and the covariance is their weighted spread. Each EM round never lowers the likelihood. Bishop shows that k-means is the limit of EM when every covariance is the same small multiple of the identity and that multiple shrinks to zero: responsibilities become hard, and only the centres remain[Bishop, 2006, ch. 9].

Try both below. Each tap is one half-step. Watch the k-means objective fall and stop; then switch to EM and watch the ellipses take the shape of the long group on the right, which k-means cannot describe. Tap New start twice to reach “two centres in one group”: k-means stops at an objective of about 56.8, against about 15.6 from the other starts. That is a local minimum.

9.5 What gets clustered here: features and position

Each of your tokens has two kinds of coordinates: a 384-number feature vector tp (unit length) and a position xp in [−1, 1]². Clustering on features alone groups tokens that look alike wherever they are. Clustering with position as well, using the distance

‖tp − μk‖² + m² ‖xp − νk‖²

where νk is the group's mean position and m sets the weight of position, keeps groups spatially compact. This is the idea behind SLIC superpixels, which run k-means on colour plus pixel position[Achanta et al., 2012].

Why does this matter for Gaussians? A Gaussian covers one connected, roughly elliptical region. A feature-only group can be scattered across the image (all the sky patches, left and right of a tree), and no single Gaussian can own a scattered group. Position keeps groups the shape a Gaussian can take. To turn each group into a Gaussian, the project used the M-step of 9.4 on positions: centre from the group's mean position, covariance from its spread (plus a small floor for the patch's own extent), mass from its share of tokens, then features by least squares.

Measured on the 800 holdout images at 64 groups (quick experiment, plain PyTorch, s3_static_layouts.json):

Position weight mHard groups, group-mean featuresGaussians fitted to groups, least squares
0 (features only)0.0000857not built (groups scattered)
0.50.00008810.0000862 (best width)
10.00009500.0000876
20.0001110.0000964

A little position costs almost nothing and makes the groups usable as Gaussians; too much position forces groups to be round blobs regardless of content. The width scale was tuned on the same images, so treat the best entry as optimistic.

9.6 Why k-means is a strong baseline for dense error

Here is the fact that explains the table. Suppose the responsibilities are hard: each token belongs wholly to one group, so the matrix A of Chapter 3 has a single 1 in each row. Then the least-squares features of Chapter 4 are just the group means (ignoring the small ridge term), and the dense squared error ‖A Z − T‖² is exactly the k-means objective J on the features. Dividing by the 256 × 384 entries gives the dense MSE.

So feature k-means directly minimises the hard-assignment version of your metric. The “hard groups” column above is that number: 0.0000857. Soft, overlapping Gaussians with least-squares features can do better than hard groups, because overlaps blend neighbouring features into smooth transitions; but only if they are placed well.

This is why per-image k-means was the decisive diagnostic in the roadmap (phase 2b). At 64 Gaussians on the 16×16 target:

LayoutDense MSE
Static 8×8 grid, wide Gaussians0.000134
Trained one-shot predictor (Gridless64, least squares)0.000104
Per-image k-means, Gaussians fitted to groups0.000086
Per-image optimisation of the Gaussians (100 images)0.000047

The trained network lost to a 30-iteration clustering of each image. And entropy-driven layouts did no better than the grid (0.000136 against 0.000134). The roadmap's decision followed: build feature-similarity clustering into the predictor. Chapter 10 covers how.

9.7 Per-image k-means as a starting point, and e-means

k-means is also where per-image optimisation starts. In quick check s5 (plain PyTorch, first 100 holdout images, least squares inside the loop), gradient-based optimisation of the Gaussians' geometry (with Adam, a standard optimiser that Chapter 11 explains), started from the k-means layout at 0.0000880, reached 0.0000729 after 4 steps, 0.0000674 after 8, 0.0000606 after 16 and 0.0000483 after 200. In the 32×32 budget study (s7) every count has a “k-means”, “k-means + 16 steps” and “k-means + 200 steps” curve; Chapter 13 reads them.

A good start matters because the problem has local minima, just like k-means itself: the same 600-step optimisation ends at 0.0000465 from a grid start and at 0.0000558 from the Gridless64 layout (100 images, s4_partial_*_ls_n100.json).

A reviewer may mention e-means, a November 2026 variant of k-means. It replaces Lloyd's full passes with mini-batch updates averaged by an exponential moving average, gives scaling laws for the decay rate and batch size, reaches Lloyd's 25-epoch loss in 1.4 to 2.6 epochs, and partitions 10 billion DINO embeddings into 16 million clusters in 2.5 epochs[Bessa et al., 2026].

It does not change this project, for two reasons. First, the scale is opposite: you solve many tiny problems (256 points, 64 groups, per image), each of which fits in one batch, while e-means targets one enormous problem. Second, and more important, speed was never the bottleneck. The bottleneck is that k-means minimises the hard objective, not the true soft least-squares error, and runs per image instead of in one forward pass. A faster k-means is still k-means.

Go deeper: why EM's likelihood never falls

EM maximises a lower bound on the log-likelihood. The E-step makes the bound touch the likelihood at the current parameters; the M-step maximises the bound over the parameters. The likelihood at the new parameters is at least the bound, which is at least the old likelihood. Bishop chapter 9.4 gives the derivation in two pages.

9.8 Check yourself

Answer from memory; each question gives its reason once you choose.

1. Why is per-image feature k-means a strong baseline for dense MSE?

With one-hot responsibilities, the least-squares features are group means and the dense squared error equals the k-means objective. k-means optimises your metric under a hard-assignment restriction.

2. What does EM's M-step do for one Gaussian?

Given responsibilities, the best mass is the owned share, the best centre the weighted mean and the best covariance the weighted spread. The third option is k-means' assign step.

3. In which limit does EM become k-means?

With equal, shrinking, round covariances the nearest centre takes the whole responsibility, so the E-step becomes the hard assign step and the M-step keeps only the centres.

4. Why add position to the clustering distance?

Feature-only groups can be scattered across the image, and one Gaussian covers one compact region. A small position weight (m = 0.5) cost almost nothing in error.

5. A reviewer says: “Use e-means, it is ten times faster.” Your best answer?

e-means is unsupervised and was shown on DINO embeddings. The real limit is that any k-means minimises hard assignments per image, not the soft least-squares error in one pass.

9.9 Close the loop

Without scrolling up: explain to a reviewer why per-image k-means beat your first trained predictor, and what that told you to build next. Then compare with your first answer.

A model answer

“With hard assignments, least-squares features are group means and the dense error is exactly the k-means objective, so feature k-means directly optimises a restricted version of our metric. Adding a little position keeps groups compact, so a Gaussian fitted to each group by EM's moment step keeps the gain: 0.000086 against 0.000104 for the trained one-shot predictor. That said the predictor, not the representation, was the bottleneck, and that grouping by feature similarity is what it lacked. So we built clustering into the network. A faster k-means such as e-means would not help, because the limit is the hard objective and the per-image loop, not speed.”

Read next Bishop, “Pattern Recognition and Machine Learning” (2006), chapter 9, sections 9.1 to 9.3. k-means, mixtures of Gaussians, EM, and the k-means limit, in the vocabulary this chapter used. The free PDF is on the linked page.

Something unclear, or want to rehearse how you would say this to a reviewer? Ask your teacher in the chat.

One-page summary of this chapter ·