Part III · Placing the Gaussians · Chapter 10

Learning to cluster

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

10.1 From running k-means to learning it

Chapter 9 ended with a diagnosis: a per-image k-means placed 64 Gaussians better (0.000086) than your trained predictor (0.000104). Two things were wrong with simply using k-means. It runs a separate loop for every image, and it minimises the hard objective, not the soft least-squares error you report.

The fix is to put the clustering inside the network, as a fixed number of steps whose settings are learned from the true loss on thousands of images. This chapter shows the general idea, the best-known example (slot attention), and your clustering stage line by line, with its results.

By the end you can explain what an unrolled clustering stage is, compare yours with slot attention, read every term of one iteration of free_gaussian_cluster.py, and quote what arms A, B and C measured.

Before reading on: what would you have to change in k-means so that a network could learn it by gradient descent?

10.2 Unrolling: an algorithm as layers

Lloyd's algorithm and EM repeat the same step until nothing changes. Suppose instead you run exactly T steps and write each one out as a layer of a network. Three things follow.

  • If every step is differentiable (soft assignments, not hard ones; Chapter 9.3), the whole chain is differentiable, so a loss on the final output can train it by backpropagation.
  • Numbers that were fixed choices (stiffness, how far to move, how wide to make each group) can become learned parameters, one per step if you like.
  • The cost per image is fixed and known: T steps, in one forward pass.
Unrolled iteration. A fixed number of steps of an iterative algorithm, written as network layers, with some of its settings learned end to end from a loss on the final result.

This has been done for clustering before. Neural Expectation Maximization unrolls EM as a differentiable network that learns to group[Greff et al., 2017]. Superpixel Sampling Networks make SLIC (k-means on colour plus position, Chapter 9.5) differentiable, with learned features[Jampani et al., 2018]. Chapter 11 applies the same move to an optimiser.

10.3 Slot attention

The best-known learned clustering is slot attention[Locatello et al., 2020]. It turns a set of N input vectors (for example, a CNN's feature map) into K output vectors called slots. Read its Algorithm 1 as soft k-means with learned parts:

  1. Start the slots by sampling from a learned Gaussian.
  2. Score every input against every slot with learned projections (keys from inputs, queries from slots).
  3. Take the softmax over the slots, so each input's attention sums to one across slots. This is the competition: slots compete for inputs, just as Gaussians compete for points in an E-step.
  4. Each slot takes the weighted mean of (projected) inputs, as in a soft k-means update.
  5. Update each slot from that mean with a learned recurrent cell (a GRU) and a small residual network. Repeat for a few iterations with shared weights.

So slot attention keeps the rhythm of Chapter 9 (assign softly, then average) and learns the distance and the update. What it does not have is geometry: a slot is a vector, not a region with a centre and a covariance. A decoder must learn where each slot is. Chapter 16 covers methods that run slot attention over self-supervised features.

10.4 Your clustering stage, one iteration

Your stage keeps 64 Gaussians and updates their geometry (centre, Cholesky factor, mass logit) through 8 iterations. Each Gaussian k also carries a slot vector, as in slot attention. One iteration i, as in ClusterModel.forward:

  1. Render. Responsibilities A from the current geometry (Chapter 3). In-loop features are weighted means sk (the soft centroids); least squares is used only after the last iteration.
  2. Residual. For each token p, its squared error ep under the current field. It becomes an importance ωp = 0.5 + 0.5 · min(ep/ē, 4), between 0.5 and 2.5, where ē is the image mean.
  3. Affinity of token p for Gaussian k: akp = wf[i] ⟨ŝk, tp⟩ + wg[i] (−log(1 + d²kp) + log ωp) the cosine similarity of the token to the unit centroid ŝk, plus a geometry score that falls with dkp and rises for badly fitted tokens. Here dkp is the token's distance from the Gaussian's centre measured in units of the Gaussian's own spread (the Mahalanobis distance; its square is the quantity in the exponent of Chapter 2's density).
  4. Soft assignment. Softmax over the 64 Gaussians for each token: the E-step, and the same competition axis as slot attention. Multiply by ωp, so badly fitted tokens pull harder.
  5. Moment fit. Each Gaussian's weighted mean and spread of token positions give a new centre and Cholesky factor (Chapter 9's M-step on positions). The factor is multiplied by a width w[i]; the mass logit is set to log(occupancy + 0.01), where occupancy is the Gaussian's summed share.
  6. Blend. geometry ← (1 − βi) · geometry + βi · fitted.
  7. Slot update. Each slot vector attends to the tokens (75% local, biased by the geometry score; 25% global) and to the other slots, and a linear head adds a small correction (divided by 8) to the geometry.

The residual ep is computed from a detached copy of the field, so it acts as feedback, not as a path for gradients. Everything else in the loop, including assignment → moments → geometry, is differentiated.

10.5 What is learned, and what changed from Gridless64

Here is a fact to have ready. Your earlier predictor, Gridless64, already ran this loop, with gentle fixed settings: blend 0.25, feature weight 16, geometry weight 2, width 1, and mass carried over rather than refitted. With those settings ClusterModel reproduces Gridless64 exactly; that is tested. So the clustering arms did not add a new module. They opened up its knobs:

  • Blend βi (8 numbers, through a sigmoid): how far each iteration moves toward the fitted moments. β = 1 is full clustering: the fitted geometry replaces the old.
  • Sharpness wf[i], wg[i] (through exp): the stiffness β of soft k-means, separately for features and geometry.
  • Width w[i] (through exp): how much wider or narrower than its group's spread each Gaussian is made.
  • Mass from occupancy: the M-step mass, instead of a carried-over value.
ArmSettingsHoldout dense MSE
Gridless64blend 0.25, fixed knobs0.0001041
Ablend 1, mass from occupancy, other knobs fixed0.0000872 (−16.3%)
Ball knobs learned per iteration (blend starts at 0.5)0.0000804 (−22.8%)
Cas B, coverage penalty off0.0000806 (−22.6%)

16×16 target, 64 Gaussians, 800 holdout images, 6,000 updates, seed 20261112. Least-squares features in every arm.

10.6 What the results say

  • It is robust. B over three seeds: 0.0000804, 0.0000806, 0.0000805; mean 0.00008046, spread 0.24% of the mean, 22.9% below least-squares Gridless64's three-seed mean.
  • The layout became image-specific. The spread of each Gaussian's centre across images rose from 0.019 (Gridless64) to 0.065 (A) and 0.068 (B). The old layout was close to static; the new one moves with content.
  • The learned schedule reads like annealing. In B the blend rises from 0.59 to 0.80 over the 8 iterations, feature sharpness from 19 to 60, and width from 0.76 to about 1.2. Early iterations are soft and cautious; late ones are sharp and decisive, and make Gaussians wider than their groups, which suits least squares: overlap lets neighbouring features blend smoothly.
  • It beats per-image k-means in one pass: 0.0000804 against 0.000086, because its knobs are trained on the soft least-squares error, not on the hard k-means objective.
  • The coverage penalty does not matter (C equals B).
  • The linear probe does not move (0.868 to 0.874 across seeds). Chapter 19 explains why that probe is insensitive to placement.
  • More training is not the lever. 12,000 updates gave 0.0000787 (−2.0%), flat after step 8,000, with the training-holdout gap widening to about 9 to 11%.

10.7 Where clustering stops, and the defence

Clustering B is at 0.0000804; per-image optimisation of the same 64 Gaussians reaches about 0.000047. Why does a well-trained clustering stage stop so far short?

Because a clustering step is not a step on your objective. Each iteration moves the Gaussians toward the moments of the tokens they own. Its fixed point is a self-consistent grouping, not the minimum of the least-squares error, in which overlapping Gaussians act as a smooth basis. The error enters the loop only indirectly, through the importance weights ωp. To go further the network has to take steps on the error itself. That is Chapter 11.

When a reviewer says “this is just k-means in a network”, the precise answer has three parts:

  1. Yes, its skeleton is soft k-means / EM, and that is deliberate: Chapter 9 showed grouping by feature similarity is what the old predictor lacked.
  2. Its steps are trained end to end on the soft least-squares error, with per-iteration sharpness, blend and width, plus residual weighting and a slot update; per-image k-means does not have these, and the trained stage beats it (0.0000804 against 0.000086) in a single pass.
  3. Unlike slot attention, every slot is an explicit Gaussian with geometry fitted by moments, read out by a fixed renderer and a closed-form feature solve, not a learned decoder.

10.8 Check yourself

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

1. What does “unrolled” mean for the clustering stage?

Eight iterations, each a differentiable layer, with per-iteration settings learned from the final loss. Fixed cost, one forward pass.

2. In slot attention and in your stage, the assignment softmax runs over what?

Each token's shares sum to one across slots, as in an E-step. That competition is what makes it clustering rather than independent attention.

3. A reviewer says “this is just k-means in a network”. The key difference?

Eight iterations is fewer than k-means uses, and features drive the affinity. What k-means lacks is training of every step on the true objective, which is why B beats per-image k-means in one pass.

4. Why does clustering B still sit well above the per-image optimum?

Moment fitting converges to a self-consistent grouping. The least-squares optimum uses overlapping Gaussians as a smooth basis, which only steps on the error itself can find. Doubling training bought only 2%.

5. What did arm A change relative to Gridless64?

Gridless64 already ran the loop with blend 0.25 and carried-over mass. A set the blend to 1 and refitted mass, and gained 16.3%; both arms already used least squares.

10.9 Close the loop

Without scrolling up: describe one iteration of your clustering stage in four steps, say what is learned, and give the result. Then compare with your first answer.

A model answer

“Each of 8 iterations scores every token against every Gaussian by feature similarity to the Gaussian's centroid plus a Mahalanobis geometry score, weighted up for badly fitted tokens; takes a softmax over Gaussians, so they compete as in EM or slot attention; refits each Gaussian's centre and covariance from the moments of its tokens, scaled by a width, with mass from its occupancy; and blends that into the geometry. Blend, sharpness and width are learned per iteration from the soft least-squares loss. It reaches 0.0000804 (three seeds, spread 0.24%), 23% below the one-shot predictor and below per-image k-means, with an image-specific layout. It stops short of the per-image optimum because a clustering fixed point is not the error's minimum.”

Read next Locatello et al., “Object-Centric Learning with Slot Attention” (2020), section 2.1 and Algorithm 1. One page that you can now read as learned soft k-means; compare each line with your iteration.

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 ·