Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture IV of IV

Lecture IV · Machine Learning

Clustering without an answer key

Every lecture so far has had an answer key. There was a yy, the loss was defined by the gap between the prediction and that yy, and “better” had an unambiguous meaning that no amount of arguing could move. Linear regression, the network, the tree: all three were graded.

Take the yy away and something stranger happens than the problem merely getting harder. “Better” has to come from somewhere, and in practice it comes from a model of what a cluster is. Change that model and the right answer changes with it. This lecture puts the two standard models side by side on the same points and shows them disagreeing, and then shows a dataset where the one you would call correct scores worse on the objective the algorithm is minimising.

The habit worth breaking is the assumption that unsupervised learning is supervised learning on hard mode. It is a different problem.

k-means: an objective first

Fix a number of clusters KK. A partition assigns each point xix_i to one cluster cic_i, and each cluster carries a centre μj\mu_j. The objective is the within-cluster sum of squares,

J(c,μ)=∑i=1n∥xi−μci∥2,J(c, \mu) = \sum_{i=1}^{n} \lVert x_i - \mu_{c_i}\rVert^2 ,

and k-means is nothing but a search for the cc and μ\mu that make it small. Read that formula before reading the algorithm, because every surprise later in this lecture is already visible in it. Distance is squared and Euclidean, which means a cluster is being modelled as a round ball around a point. Nothing else about the shape of the data is anywhere in the objective.

Minimising JJ jointly is NP-hard. What is easy is minimising it in each argument separately, and that is exactly what Lloyd’s algorithm does, alternating two phases.

Assign. Hold the centres fixed and choose cc to minimise JJ. The terms are independent, so each point simply goes to its nearest centre. The plane is carved into Voronoi cells, and the cell boundaries are straight lines, because the set of points equidistant from two centres is the perpendicular bisector of the segment joining them.

Update. Hold the assignment fixed and choose μ\mu to minimise JJ. Again the terms separate, one cluster at a time, and

∂∂μj∑i∈Sj∥xi−μj∥2=2∑i∈Sj(μj−xi)=0⟹μj=1∣Sj∣∑i∈Sjxi.\frac{\partial}{\partial \mu_j} \sum_{i \in S_j} \lVert x_i - \mu_j \rVert^2 = 2\sum_{i \in S_j} (\mu_j - x_i) = 0 \quad\Longrightarrow\quad \mu_j = \frac{1}{|S_j|}\sum_{i \in S_j} x_i .

The mean is not a convention. It is the unique minimiser of squared distance, and if the objective had used absolute distance instead the answer would have been the median and the algorithm would have been called k-medians.

Two consequences follow immediately. Each phase minimises JJ in one argument, so JJ never increases. And there are finitely many partitions, so the sequence of assignments cannot cycle without repeating, which means the algorithm terminates in finite time. What it does not mean is that it terminates at the global minimum, and the difference between those two statements is most of the rest of this lecture.

One iteration, in full

Five points, two starting centres, and no rounding anywhere. Take

x1=(0,0),x2=(1,0),x3=(3,1),x4=(5,0),x5=(6,0),x_1 = (0,0), \quad x_2 = (1,0), \quad x_3 = (3,1), \quad x_4 = (5,0), \quad x_5 = (6,0),

with μ1=(1,0)\mu_1 = (1,0) and μ2=(5,0)\mu_2 = (5,0). The assign phase needs squared distances and nothing else, so here they all are:

Point∥xi−μ1∥2\lVert x_i - \mu_1\rVert^2∥xi−μ2∥2\lVert x_i - \mu_2\rVert^2Goes to
x1=(0,0)x_1 = (0,0)112525cluster 1
x2=(1,0)x_2 = (1,0)001616cluster 1
x3=(3,1)x_3 = (3,1)5555cluster 1, by a tie-break
x4=(5,0)x_4 = (5,0)161600cluster 2
x5=(6,0)x_5 = (6,0)252511cluster 2

Stop on the third row. Both distances are 22+12=52^2 + 1^2 = 5, exactly, and the objective is perfectly indifferent between the two answers. Something still has to be returned, and what gets returned is whatever the inner loop does with a tie. The implementation scans centres in order and keeps only a strict improvement, so the lower index wins. That is a fact about the source file, not about JJ, and it is the first of two places in this lecture where the algorithm answers a question the objective never asked.

The objective at the moment of assignment is the sum of the winning column, 1+0+5+0+1=71 + 0 + 5 + 0 + 1 = 7. Now the update phase, which is two means:

μ1=13[(0,0)+(1,0)+(3,1)]=(43,13),μ2=12[(5,0)+(6,0)]=(112,0),\mu_1 = \tfrac{1}{3}\big[(0,0) + (1,0) + (3,1)\big] = \left(\tfrac43, \tfrac13\right), \qquad \mu_2 = \tfrac12\big[(5,0) + (6,0)\big] = \left(\tfrac{11}{2}, 0\right),

and re-measuring the same partition about its new centres gives

J=179+29+299⏟cluster 1+14+14⏟cluster 2=163+12=356≈5.8333.J = \underbrace{\tfrac{17}{9} + \tfrac{2}{9} + \tfrac{29}{9}}_{\text{cluster 1}} + \underbrace{\tfrac14 + \tfrac14}_{\text{cluster 2}} = \tfrac{16}{3} + \tfrac12 = \tfrac{35}{6} \approx 5.8333 .

One iteration bought exactly 7−356=76≈1.16677 - \tfrac{35}{6} = \tfrac76 \approx 1.1667, and every digit of that is a fraction rather than a float. Hold on to these five points. The mixture is about to be run on them from the same start, and the two answers will differ in a way that is easier to see on five points than on two hundred.

A cluster that is not a ball

The other standard answer changes the model rather than the search. A Gaussian mixture says a cluster is a normal distribution with its own mean μj\mu_j, its own mixing weight πj\pi_j, and its own full covariance matrix Σj\Sigma_j. The data is assumed drawn by picking a component with probability πj\pi_j and then sampling from it, so the density of a point is

p(x)=∑j=1Kπj N(x∣μj,Σj),p(x) = \sum_{j=1}^{K} \pi_j \, \mathcal{N}(x \mid \mu_j, \Sigma_j),

and the thing being maximised is the log-likelihood ∑ilog⁡p(xi)\sum_i \log p(x_i) rather than a sum of squares.

That maximisation has no closed form, and the standard route to it, expectation maximisation, has exactly the shape of Lloyd’s algorithm.

E step. Compute each point’s responsibility to each component, which is the posterior probability that component jj generated it:

γij=πj N(xi∣μj,Σj)∑kπk N(xi∣μk,Σk).\gamma_{ij} = \frac{\pi_j \, \mathcal{N}(x_i \mid \mu_j, \Sigma_j)}{\sum_{k} \pi_k \, \mathcal{N}(x_i \mid \mu_k, \Sigma_k)} .

This is the soft version of “assign to the nearest centre”. A point squarely inside one component gets a responsibility near 11 to it; a point in the overlap gets something like 0.60.6 and 0.40.4 and genuinely belongs to both.

M step. Re-estimate every parameter as a responsibility-weighted average. Writing Nj=∑iγijN_j = \sum_i \gamma_{ij} for the effective number of points the component owns,

πj=Njn,μj=1Nj∑iγijxi,Σj=1Nj∑iγij (xi−μj)(xi−μj)T.\pi_j = \frac{N_j}{n}, \qquad \mu_j = \frac{1}{N_j}\sum_i \gamma_{ij} x_i, \qquad \Sigma_j = \frac{1}{N_j}\sum_i \gamma_{ij}\,(x_i - \mu_j)(x_i - \mu_j)^{\mathsf T}.

Compare the middle one with the k-means update. It is the same mean, with γij\gamma_{ij} where a hard zero-or-one membership used to be. That is not a coincidence: fix every covariance at σ2I\sigma^2 I and every weight at 1/K1/K, and let σ→0\sigma \to 0, and the responsibilities harden to zero and one and EM becomes Lloyd’s algorithm exactly. k-means is a Gaussian mixture with the shape argument removed.

EM has its own monotonicity guarantee, and it is stronger than it looks: the log-likelihood never decreases from one full E-M pair to the next. The argument is that the E step builds a lower bound on the log-likelihood that touches it at the current parameters, and the M step maximises that bound, so the value at the new parameters is at least the value at the old. That is a claim a reader can hold me to, and the implementation behind the plate was checked against it: over six hundred runs and twelve thousand iterations it never decreased, to a relative tolerance of 10−910^{-9}. Had it ever decreased, that would have been a bug rather than a curiosity.

The same iteration, softly

Same five points, same two starting centres. The implementation starts a mixture round, with both covariances set to σ2I\sigma^2 I for a single σ2\sigma^2 scaled to the spread of the data and both weights at 1/21/2; on these five points that scale works out to σ2=1.34\sigma^2 = 1.34 exactly. That choice is what makes the comparison fair, and it also makes the E step collapse to something you can read. When two components share a covariance and a weight, every factor in γij\gamma_{ij} cancels except the exponent, and the responsibility becomes a logistic of the difference of the two squared distances already tabulated above:

γi1=exp⁡ ⁣(−di12/2σ2)exp⁡ ⁣(−di12/2σ2)+exp⁡ ⁣(−di22/2σ2)=11+exp⁡ ⁣(−(di22−di12)/2σ2).\gamma_{i1} = \frac{\exp\!\big(-d_{i1}^2/2\sigma^2\big)}{\exp\!\big(-d_{i1}^2/2\sigma^2\big) + \exp\!\big(-d_{i2}^2/2\sigma^2\big)} = \frac{1}{1 + \exp\!\big(-(d_{i2}^2 - d_{i1}^2)/2\sigma^2\big)} .

With 2σ2=2.682\sigma^2 = 2.68 that gives, to eight places:

Pointdi22−di12d_{i2}^2 - d_{i1}^2γi1\gamma_{i1}γi2\gamma_{i2}k-means said
x1x_124240.999870960.999870960.000129040.00012904cluster 1
x2x_216160.997452650.997452650.002547350.00254735cluster 1
x3x_3000.500000000.500000000.500000000.50000000cluster 1
x4x_4−16-160.002547350.002547350.997452650.99745265cluster 2
x5x_5−24-240.000129040.000129040.999870960.99987096cluster 2

The four confident points are decided to within a thousandth, which is the useful half of the message: soft assignment is not vague. It is the third row that matters. Where Lloyd’s algorithm had to hand the whole of x3x_3 to cluster 1 on the strength of a tie-break, EM says one half and one half, and it is not hedging. Given this model, that is the posterior.

The effective counts come out at N1=N2=5/2N_1 = N_2 = 5/2 exactly, because the five points are symmetric about x=3x = 3, so the weights stay at 1/21/2 and the M step is just two weighted means:

μ1=15/2∑iγi1xi=(1.004385, 0.2),μ2=(4.995615, 0.2).\mu_1 = \frac{1}{5/2}\sum_i \gamma_{i1} x_i = (1.004385,\ 0.2), \qquad \mu_2 = (4.995615,\ 0.2).

Put those beside k-means’ (43,13)=(1.3333,0.3333)\left(\tfrac43, \tfrac13\right) = (1.3333, 0.3333) and the parting of ways is a number: 0.354943, the distance between where the two methods put the same centre after the same single iteration from the same start. All of it comes from one point, and specifically from half of one point. Lloyd’s centre was dragged toward x3x_3 by a whole membership it had to invent; EM’s was dragged half as far by a membership it computed.

Arrow keys move it by 0.05. At exactly 3.00 it is equidistant.
The σ² in the shared covariance σ²I. Sixteen rungs, 0.01 to 20, one arrow key apart. Turn it down and the mixture hardens.
The worked case
x11.00x21.00x30.50x40.00x50.00

Component 1 Component 2 Fill and number: the responsibility EM gives it +k-means mean after one update □EM mean after one update

One iteration, both ways

Point Squared distance to centre 1 Squared distance to centre 2 Responsibility to component 1 Lloyd says
x1 (0.00, 0) 1.0000 25.0000 0.999871 cluster 1
x2 (1.00, 0) 0.0000 16.0000 0.997453 cluster 1
x3 (3.00, 1) 5.0000 5.0000 0.500000 cluster 1
x4 (5.00, 0) 16.0000 0.0000 0.002547 cluster 2
x5 (6.00, 0) 25.0000 1.0000 0.000129 cluster 2

k-means means (1.3333, 0.3333) and (5.5000, 0.0000) · EM means (1.0044, 0.2000) and (4.9956, 0.2000) · they differ by 0.3549 · objective before 7.0000, after 5.8333 · exact ties 1

The hardening ladder, one step off the tie at x₃ = 2.75

Variance Responsibility of x₃ to component 1 Distance between the two updated means
8 0.531209 0.592622
2 0.622459 0.206513
1.34 0.678365 0.193385
0.35 0.945687 0.030266
0.05 1.000000 0 (they coincide)
0.01 1.000000 0 (they coincide)

The covariance is held at σ²I so that σ can be a dial; real EM refits it, which is what gives the mixture a shape argument in the first place. The mean update is unaffected by that freeze, because μj = Σ γij xi / Nj does not mention the covariance, so the EM means above are exactly the ones a full-covariance M step produces from the same responsibilities.

Plate I The knife edge. The five worked points, with the fill of each showing its responsibility to component 1 and the ring showing which cluster k-means gave it, so a point whose ring disagrees with its fill is a point where the two methods have parted company. Crosses mark the k-means centres after one update, open squares the EM means after one. The first dial slides x3x_3 along the line y=1y = 1: at exactly 3.00 it is equidistant from both starting centres, five either way, and only there do the two answers refuse to converge. The second dial is the shared σ2\sigma^2. Turn it down and the responsibilities saturate, the open squares walk onto the crosses, and the mixture becomes Lloyd's algorithm in front of you. Turn it down while standing on the tie and the third responsibility stays at one half forever, because the limit of a logistic at zero is a half however hard you squeeze it.

That plate is the identity claimed two paragraphs ago, made checkable rather than asserted. It is also honest about where the identity fails: the limit of EM as σ→0\sigma \to 0 is Lloyd’s algorithm everywhere except on the set of exact ties, and on that set the soft answer is 1/21/2 while the hard answer is whichever index the loop happened to visit first. The set of ties has measure zero, so nobody is wrong. But a reader who has stood on it once will never again believe that a clustering algorithm’s output is entirely determined by its objective.

Data
Initialisation
Seed
3
Iterate
k-means · hard assignment

iteration 5 · next phase update · WCSS 5.405 · reassigned 0 · centroid shift 0.005 · matches the generating labels 56% · converged

Gaussian mixture · soft assignment

iteration 28 · next phase M · log-likelihood 330.92 · change -0.000 · weights 0.50 · 0.50 · matches the generating labels 97% · converged

Cluster 1 Cluster 2 Shaded between the two: the responsibility EM assigns +Each centre, with a dashed trail of everywhere it has been

Two elongated, overlapping, differently shaped clusters. This is the shape k-means cannot see: it wants round clusters, so it cuts the pair down the middle instead of separating them. The mixture, which fits a covariance matrix per component, gets it right from almost any start.

Both components carry a full 2 × 2 covariance matrix, which is what lets the ellipses tilt; a ridge of 10−6 is added to each diagonal at every M step so a component collapsing onto a few points cannot go singular and send the likelihood to infinity. The number of clusters is fixed at two, and choosing it is a separate problem that neither algorithm solves.

Plate II The same points, clustered twice. Left: k-means, which assigns every point to exactly one centre and carves the plane into Voronoi cells. Right: a two-component Gaussian mixture fitted by EM, drawn as one- and two-sigma covariance ellipses, with each point shaded between the two colours in proportion to its responsibility, so a point in the overlap is literally drawn half one and half the other. Step advances a single phase (assign or update; E or M) in both panels at once. On Two bars, k-means converges to the partition with the lowest within-cluster sum of squares and that partition cuts across both clusters: the objective is what is wrong, not the search. On Three lobes, roughly a third of random seeds trap it in a local optimum instead; switch the initialisation to k-means++ and step through the seeds to see that rate fall by about half.

Seeds, and two different kinds of failure

The seed control is the part of that plate to spend time on, because it separates two failures that get confused with each other constantly.

A local optimum is a failure of the search. On the Three lobes dataset, about a third of random starts leave k-means genuinely stuck: it splits the near pair of lobes between its two centres and swallows the distant one whole, and no single reassignment of any point improves JJ, so the alternation has nowhere to go. Watching that happen, and then watching a different seed land somewhere sensible, is the fastest way I know to explain why k-means++ exists. Seed the first centre at random, then draw each subsequent centre with probability proportional to its squared distance from the nearest centre chosen so far. It spreads the starts out without ever hard-coding where they go.

Be careful about what that buys. On this data it roughly halves the failure rate rather than eliminating it, and the theoretical guarantee is not a guarantee of the optimum either: k-means++ has an expected objective within O(log⁡K)O(\log K) of the best possible, which is an approximation ratio and nothing more. In practice people also just restart several times and keep the run with the lowest JJ, which is honest and works. EM has the same disease, incidentally: on the same dataset some seeds converge to a visibly worse likelihood, which is what “the log-likelihood never decreases” does and does not promise.

An objective can also just be wrong, and no amount of restarting touches it. That is the Two bars dataset, and it is the picture that changed how I think about this whole family.

When the correct answer scores worse

Two bars is two long, thin, parallel clusters, 220 points, 110 in each. Run k-means on it and it does not get stuck. It converges to a partition that slices both bars in half lengthwise, and that partition is not a local optimum it failed to escape. It has the lowest within-cluster sum of squares available. Two long thin clusters have more variance along their own axes than they have between each other, so cutting across them genuinely reduces JJ more than separating them does.

The numbers that break it

That claim is the kind that deserves to be checked rather than admired, and at K=2K = 2 it can be checked exhaustively. Two centres partition the plane by the perpendicular bisector of the segment between them, so every partition k-means could possibly return is a straight split of the plane, and every straight split is a partition it could return. The feasible set is the set of lines, which is two numbers wide, and two numbers can be swept.

Sweeping them, over every angle to a quarter of a degree and every offset to five thousandths, then refining around the winner:

SplitObjective JJRecovers
The cheapest line there is, at 174.5°174.5°, offset −0.0400-0.04005.4046125 of 220, 56.8%
The best separation any line achieves, at 90°90°, offset −0.0200-0.02006.2977216 of 220, 98.2%
The generating partition itself, about its own two means6.3582220 of 220

So the correct answer is not merely one of several local optima. It costs 0.8931 more, which is 16.5% worse, and there is nothing below it. Being right about this dataset is a priced decision and the price is a sixth of the objective.

Two things confirm the sweep rather than repeat it. Running Lloyd’s algorithm from a thousand random seeds finds a lowest value of 5.4046 as well, by a completely different route, and 859 of those thousand runs end on a cross-cut recovering under 90%. And k-means++ makes it worse, not better: 897 of a thousand. That is not a defect in k-means++. It is a better search, it more reliably finds the global minimum, and on this data the global minimum is the wrong answer, so searching better costs you accuracy. A seeding improvement can only ever move you toward the objective, which means it can only ever help you when the objective is the thing you wanted.

Arrow keys move it one degree.
Arrow keys move it by 0.005.
Just show me

Your line · objective 5.9259 · recovers 71.8% of the generating labels · sides 94 and 126

Lowest objective you have reached
5.9259 recovering 71.8%
Best separation you have reached
71.8% costing 5.9259

No line does both. The cheapest line on this data scores 5.4046 and recovers 56.8%; the best separation available recovers 98.2% and costs 6.2977, which is 0.8931 more, or 16.5%. The generating partition itself, measured about its own two means, costs 6.3582.

Five lines, priced

Line Angle Offset Objective Recovers
The cheapest line there is 174.50° -0.0400 5.4046 56.8%
The line that separates best 90.00° -0.0200 6.2977 98.2%
Vertical, through the middle 0.00° 0.0000 5.5048 55.5%
Horizontal, through the middle 90.00° 0.0000 6.3045 96.8%
Diagonal, through the middle 45.00° 0.0000 5.9259 71.8%
The generating partition (not a line) not one not one 6.3582 100.0%

220 points, 110 in each bar. The objective is the within-cluster sum of squares about each side's own mean, which is the quantity Lloyd's algorithm decreases at every phase. Because two centres partition the plane by the perpendicular bisector between them, every partition k-means could return is one of these lines and every one of these lines is a partition k-means could return, so the cheapest line above is the global minimum rather than the best found.

Plate III The hunt, which cannot be won. Two dials set the angle and offset of a straight line across the Two bars data, and the plate prices the split it makes: the within-cluster sum of squares on one side, the fraction of the generating labels recovered on the other, and both of the reader's bests kept side by side in memory. The finding is that the two bests are never the same line. The reference numbers stay on screen throughout, so the figure is readable without being played, and the table beneath prices five named lines and the generating partition with JS off. Because a two-centre partition is exactly a half-plane split, the sweep behind the reference numbers is over the whole feasible set: 5.4046 is the global minimum of k-means on this data, not the best anyone found.

No better seeding, no restart, and no smarter optimiser repairs any of that, because there is nothing wrong with the optimiser. The assumption that clusters are round is buried in the choice of squared Euclidean distance, and it was buried there before any search began.

The mixture recovers the bars from almost any start, and the almost is measurable: 999 of a thousand random seeds converge to the same answer, recovering 214 of 220, and the one that does not (seed 994) lands at 112, which is a coin flip. One reason only: a covariance matrix can be long, thin and tilted. It is not a better search. It is a model with a parameter for the thing that mattered.

Why k-means at all, then

If the mixture is the more honest model, the obvious question is why anybody still reaches for the round one first. The answer is a count.

A KK-component mixture with full covariances in dd dimensions carries K(d+d(d+1)2+1)−1K\big(d + \tfrac{d(d+1)}{2} + 1\big) - 1 free parameters, against k-means’ KdKd. In the plane with two clusters that is 11 against 4, which is nothing. At ten clusters in fifty dimensions it is 13,259 against 500, and the gap is quadratic in dd because a covariance matrix is. Worse than the count is what the count needs: a sample covariance built from fewer than d+1d+1 points in dd dimensions is singular, so at d=50d = 50 every component needs at least 51 points just to have a matrix you can invert, and many times that to have one you would believe. The mixture does not degrade gracefully when it runs out of data. It produces a matrix with a zero determinant and stops meaning anything.

Then the cost per run, measured on Three lobes, where the round assumption is right and the mixture has nothing to buy with its extra parameters. Over 300 random seeds, k-means converges in 1.8 iterations on average and recovers 90.0%; EM takes 7.5 iterations, each of them doing strictly more arithmetic, and recovers 92.1%. Four times the work for two points, on data that suits it, and it is still stuck in a bad optimum on 71 of those 300 runs against k-means’ 91, so it does not fix the seeding problem either.

And the deepest reason, which the next section makes precise: k-means’ objective has a finite minimum, and the mixture’s likelihood has no finite maximum at all. The mixture is only usable because the search does not find its own global optimum.

The mixture wins exactly when the shape is the finding, which is a narrower condition than “when the data is not round”. If the clusters are elongated but all elongated the same way, a linear rescaling of the axes turns them round and k-means recovers. The mixture earns its parameters when different clusters have different shapes, which is precisely the Two bars case: one bar is 5.6 times longer than it is wide and tilted one way, the other is 2.7 times longer than it is wide and tilted the other, and no single rescaling of the plane fixes both.

Choosing KK, and the honesty problem

Both panels of Plate II report how much of the generating structure each method recovered, and it is worth saying plainly that they can only do that because I generated the data and kept the labels. In the wild that column does not exist. This is the whole difficulty of unsupervised learning in one sentence: the quantity you actually care about is unmeasurable, and everything you can measure is a property of your own assumptions.

It shows up first in the choice of KK. You cannot pick KK by minimising JJ, because JJ falls monotonically as KK rises and reaches zero when every point is its own cluster. The standard responses are all heuristics and should be named as such: the elbow method, which looks for the bend where extra clusters stop paying; the silhouette score, which asks whether points sit closer to their own cluster than to the next one; and for mixtures, a penalised likelihood such as BIC, which charges for parameters and therefore can be optimised over KK honestly.

Mixtures carry one more trap worth knowing about. The likelihood is unbounded: let a component’s mean sit exactly on a single data point and shrink its covariance toward zero, and the density at that point, and so the likelihood, runs to infinity. The global maximum is that degeneracy, every time. What EM finds in practice is a well-behaved local maximum, which means the algorithm is protecting you from its own objective, and implementations quietly add a small ridge to every covariance to keep it from happening.

The ridge, measured

That last clause was doing a lot of quiet work, so here is the line it is describing, from the M step in src/lib/cluster.ts:

export const RIDGE = 1e-6;
// ...
cov: { xx: xx / nj + RIDGE, xy: xy / nj, yy: yy / nj + RIDGE },

One number, added to both diagonal entries, every M step, forever. It buys two different things, and only the first one is the one everybody names.

What it bounds. Pin a component’s mean to a single data point and let its covariance be sIsI. The density at that point is 1/(2πs)1/(2\pi s), so the point’s contribution to the log-likelihood grows like log⁡(1/s)\log(1/s) with no ceiling. Measured on Two bars, with a weight of 0.02 on the pinned component and an honest single Gaussian carrying the rest, the total log-likelihood reads

243.53  (s=10−8),248.14  (10−10),252.74  (10−12),257.35  (10−14),261.95  (10−16),243.53 \ \ (s = 10^{-8}), \quad 248.14 \ \ (10^{-10}), \quad 252.74 \ \ (10^{-12}), \quad 257.35 \ \ (10^{-14}), \quad 261.95 \ \ (10^{-16}),

which is a rise of exactly log⁡100=4.605\log 100 = 4.605 for every hundredfold shrink, forever. It passes the honest converged fit’s 330.92 at around s=10−46s = 10^{-46}. Rerun the same sequence with RIDGE=10−6\text{RIDGE} = 10^{-6} in place and it reads 238.92, 238.93, 238.93, 238.93, 238.93. It stops. Since the determinant can never fall below δ2\delta^2, the density at any component’s own mean is capped at 1/(2πδ)=159,1551/(2\pi\delta) = 159{,}155, and the objective the search is climbing has a top again.

What it actually prevents, in this implementation. No infinity ever reaches the screen, because the density routine returns zero whenever the determinant is not positive. So without the ridge you do not get a spike; you get a silence. A component owning kk points in the plane has a sample covariance of rank at most k−1k-1, so at k=1k = 1 the determinant is exactly zero and at k=2k = 2 it came out at −2.07×10−25-2.07 \times 10^{-25}, negative from rounding, which the guard also refuses. Take the ridge out and run the mixture on five collinear points: the covariance goes singular on the first M step, every density it produces is zero, the E step falls back to the mixing weights, the component’s effective count drops below 10−1210^{-12}, and the if (nj < 1e-12) continue guard freezes it there permanently. The two-component mixture is quietly a one-component mixture from that moment on, and nothing in the output says so. The same run with the ridge restored takes 17 iterations and settles at a log-likelihood of 28.545.

The ridge is visible in the worked example above, incidentally, if you look far enough right. The M step there produces Σ1=[1.2175240.3991230.3991230.160001]\Sigma_1 = \begin{bmatrix} 1.217524 & 0.399123 \\ 0.399123 & 0.160001\end{bmatrix}, and that bottom-right entry is exactly 0.160.16 before the ridge and 0.1600010.160001 after. A sixth decimal place is what stands between this figure and a component that disappears without comment.

k-means, in code

The alternation is short enough that there is no reason to take it on faith, and short enough that writing it is cheaper than reading it. Two of the four functions are below already; the other two are yours. The checks are the fractions from the worked example, so a green row is your code agreeing with the arithmetic on paper rather than with me.

The checks · run against your code

# assign sends the five points where the lecture sent them
assert assign(PTS, C0) == [0, 0, 0, 1, 1]
# the exact tie at x3 goes to the LOWER index, from your loop and not from J
assert assign([(3.0, 1.0)], C0) == [0]
# the objective at the moment of assignment is exactly 7
L = assign(PTS, C0)
assert abs(wcss(PTS, L, C0) - 7.0) < 1e-12
# the update lands the centres on (4/3, 1/3) and (11/2, 0)
M = update(PTS, L, C0)
assert abs(M[0][0] - 4.0 / 3.0) < 1e-12 and abs(M[0][1] - 1.0 / 3.0) < 1e-12
assert abs(M[1][0] - 5.5) < 1e-12 and abs(M[1][1] - 0.0) < 1e-12
# and the objective falls to 35/6, so the iteration bought exactly 7/6
assert abs(wcss(PTS, L, M) - 35.0 / 6.0) < 1e-12
assert abs(wcss(PTS, L, C0) - wcss(PTS, L, M) - 7.0 / 6.0) < 1e-12
# wcss is measured about whatever centres you hand it: the old ones cost more
assert wcss(PTS, L, C0) > wcss(PTS, L, M)
python runs in your browser · first run downloads ~240 kb
Plate IV Lloyd's algorithm, checked against the hand arithmetic. `update` is provided; `assign` and `wcss` are the exercise. The eight checks are exactly the worked example above, the five labels, the tie going to the lower index, the objective of 7 at the moment of assignment, the two updated centres as 4/34/3, 1/31/3 and 11/211/2, 00, the objective falling to 35/635/6, and the difference of the two coming to 7/67/6. They are stated to 10−1210^{-12}, which a correct implementation clears by many orders of magnitude and a plausible wrong one does not. With JS off the listing itself is the figure.
Hint one

assign needs one loop over points and, inside it, one loop over centres. Build the list of squared distances first and then take the index of the smallest; min(range(len(d)), key=lambda k: d[k]) returns the FIRST index achieving the minimum, which is exactly the tie-break the third check is testing for. Do not take a square root anywhere. It is monotone, so it cannot change which centre wins, and it costs you both time and exactness.

Hint two

wcss is one line if you zip the points against their labels: for each pair, the squared distance from the point to centres[label]. The reason it takes the centres as a separate argument is that the last two checks measure the same labelling about two different sets of centres, which is how the update phase gets priced.

The solution

Two loops and a sum:

def assign(points, centres):
  labels = []
  for p in points:
      d = [(p[0] - c[0]) ** 2 + (p[1] - c[1]) ** 2 for c in centres]
      labels.append(min(range(len(centres)), key=lambda k: d[k]))
  return labels

def wcss(points, labels, centres):
  return sum((p[0] - centres[l][0]) ** 2 + (p[1] - centres[l][1]) ** 2
             for p, l in zip(points, labels))

Note what is missing from assign: any tie-breaking logic at all. The lower index wins because min over a range returns the first minimiser, which means the answer to the knife-edge question in Plate I is a documented property of a builtin and not a decision anybody made about clustering. Swap min(...) for a manual loop that keeps the last improvement instead of the first and the third check turns red, with nothing about the objective having changed.

Wrap those two around the provided update and the loop is finished:

def lloyd(points, centres, max_iter=300):
    labels = None
    for _ in range(max_iter):
        new = assign(points, centres)
        if new == labels:                # nothing moved, so nothing ever will
            return labels, centres
        labels = new
        centres = update(points, labels, centres)
    return labels, centres

Twenty-five lines in total, and the stopping test is the interesting one. Convergence is declared when the assignment stops changing, not when the centres stop moving by some tolerance, because the assignment is what the objective depends on and it takes only finitely many values. EM cannot use that test, since responsibilities are real numbers that keep creeping, so it has to watch the log-likelihood and stop when it stops moving.

The if not owned branch is not defensive padding. A cluster really can lose every one of its points, most often when two centres are seeded almost on top of each other. Leaving the centre where it was, as above, is the least surprising response; the alternatives are to drop the cluster and return K−1K - 1 of them, or to reseed it at the point currently furthest from any centre. All three are defensible and none of them is in the objective, which is worth noticing: the formula at the top of this lecture does not say what to do when a cluster disappears. That is the second of the two places promised earlier where the algorithm answers a question the objective never asked, and the tie-break is the first. Between them they are a fair summary of what a clustering “method” is: an objective, plus a search, plus a handful of decisions neither of them makes.

A distance that was not one

One story, because it is the reason the implementation behind this plate has a test suite at all.

When I ported an older k-means of my own into the library, its distance function computed sqrt((sum(a - b)) ** 2): it summed the coordinate differences before squaring them, rather than squaring each and then summing. Under that function the points (1,−1)(1, -1) and (0,0)(0, 0) sit at distance zero. It had been clustering plausibly for months.

That is the precise danger of untested numerical code. It does not crash, it does not warn, and the pictures it draws look approximately right, because a wrong distance still groups nearby points more often than distant ones. The fix ships with a regression test named after the bug, and the general rule it taught me is the same one Lecture I applied to gradients: anything you derived should be checked against something computed a completely different way, even when, and especially when, the output looks reasonable.

The ellipse is its eigenvectors

One loose end, and it is the one worth pulling, because it is where this lecture touches the other course on the shelf.

The ellipses in Plate II are not drawn from Σj\Sigma_j by some rendering trick. They are Σj\Sigma_j, read in the only basis where a covariance matrix is simple. The drawing routine computes the trace and the determinant, solves the characteristic polynomial of the 2×22 \times 2 directly for λ=tr⁡2±tr⁡24−det⁡\lambda = \tfrac{\operatorname{tr}}{2} \pm \sqrt{\tfrac{\operatorname{tr}^2}{4} - \det}, takes the two half-axes as λ1\sqrt{\lambda_1} and λ2\sqrt{\lambda_2}, and takes the tilt as the direction of the eigenvector belonging to the larger eigenvalue. That is the whole of it. An ellipse is a pair of eigenvalues wearing a pair of eigenvectors, and that identification is Linear Algebra, Lecture VI, where the same decomposition is developed for its own sake.

Which is worth doing because it says what the mixture actually recovered. The Two bars data was generated by drawing along one axis with one standard deviation and across it with another, then rotating; the whole cloud is then scaled by a single uniform factor, which is a similarity transform and therefore leaves every angle and every axis ratio exactly where it was. So the generating tilt and elongation survive into the data, and EM either finds them or it does not. Fitted from seed 3, converging in 28 iterations to a log-likelihood of 330.92 and recovering 214 of 220 points:

BarTilt, generatedTilt, recoveredElongation, generatedElongation, recovered
The lower one0.20.2 rad =11.46°= 11.46°12.69°12.69°0.25/0.045=5.560.25 / 0.045 = 5.565.755.75
The upper one−0.14-0.14 rad =−8.02°= -8.02°−7.81°-7.81°0.19/0.07=2.710.19 / 0.07 = 2.712.572.57

Both recovered columns are eigen-decompositions of a matrix EM estimated from unlabelled points, and both land within a degree and a fifth of a ratio of numbers it was never told. The half-axes for the lower bar come out at 0.18190.1819 and 0.03160.0316, the square roots of eigenvalues 0.033110.03311 and 0.001000.00100.

k-means has no such table, and not because it estimates the numbers badly. It has nowhere to put them. Its entire parameter set is KK points, and a point has no tilt.

Where this ends

The two algorithms in this lecture are the same algorithm with different commitments, and the commitments are what you are actually choosing between. That choice cannot be made by measurement, because the thing that would settle it is the labels you do not have. It is made by looking at your data and deciding what you believe a cluster is, which makes it an act of judgement, and being explicit about that is more useful than any amount of tuning.

Which is the note the course so far ends on. Lecture I derived a loss and descended it, Lecture II broke the model and kept the method, Lecture III threw away the gradient entirely, and this lecture threw away the labels. Four different answers to “what does it mean to be right”, and none of them was supplied by the data.

Problems

Work these in order. The first five are paper; the last one runs its own checks, and every number it asks for has already appeared in this lecture, so a red row is a disagreement with arithmetic you can redo by hand.

  1. Redo the iteration, off the tie. Move x3x_3 from (3,1)(3,1) to (2.75,1)(2.75, 1) and recompute the whole of the worked example: the five squared distances to each starting centre, the assignment, the objective at the moment of assignment, both updated centres, and the objective afterwards. Then do the E step for the same five points at σ2=1.34\sigma^2 = 1.34 and give γ31\gamma_{31} to four places. Check every one of those against Plate I by dragging the first dial to 2.75. Finally, say in one sentence what changed about the relationship between the two methods’ answers, as opposed to the answers themselves.

  2. The tie, exactly. Show that when di12=di22d_{i1}^2 = d_{i2}^2 the responsibility γi1\gamma_{i1} equals 1/21/2 for every σ2>0\sigma^2 > 0, so that the limit as σ→0\sigma \to 0 is 1/21/2 and not 00 or 11. Conclude that the statement “k-means is the σ→0\sigma \to 0 limit of a Gaussian mixture” is true off the set of exact ties and false on it. Then argue that this does not matter for any dataset drawn from a continuous distribution, and say precisely what property of such a distribution you used.

  3. Price the correct answer. Take two bars of nn points each, uniformly spread along their length: bar A occupies [−L,L]×{−h}[-L, L] \times \lbrace -h\rbrace and bar B occupies [−L,L]×{h}[-L, L] \times \lbrace h \rbrace. Compute the within-cluster sum of squares of (i) the crosswise partition that separates the two bars, and (ii) the lengthwise partition that cuts both bars at x=0x = 0. Both are fixed points of Lloyd’s algorithm; check that too. Find the exact condition on LL and hh under which the lengthwise cut, the wrong one, is the cheaper. Then say what that condition means in one sentence of English.

    Hint one

    The variance of a uniform distribution on [−L,L][-L, L] is L2/3L^2/3, and on [−L,0][-L, 0] it is L2/12L^2/12. Each partition puts nn points in each cluster, so you never need to carry a count through the algebra: just write each cluster’s contribution as nn times its own mean squared deviation.

    Hint two

    For the crosswise partition the cluster mean sits at (0,∓h)(0, \mp h) and the only spread is along the bar. For the lengthwise one the cluster mean sits at (∓L/2,0)(\mp L/2, 0), and there are now two contributions, because each cluster holds half of both bars and therefore spreads in yy as well as in xx.

    The solution

    Crosswise: each cluster is one whole bar, mean at (0,∓h)(0, \mp h), spread only along xx, so its contribution is nL2/3n L^2 / 3 and the total is 2nL2/32nL^2/3.

    Lengthwise: each cluster is half of each bar, mean at (∓L/2,0)(\mp L/2, 0). In xx the points are uniform on an interval of length LL, giving L2/12L^2/12 per point; in yy every point sits at distance hh from the mean, giving h2h^2 per point. Total 2n(L2/12+h2)=nL2/6+2nh22n\left(L^2/12 + h^2\right) = nL^2/6 + 2nh^2.

    The lengthwise cut is cheaper when nL2/6+2nh2<2nL2/3nL^2/6 + 2nh^2 \lt 2nL^2/3, that is when 2h2<L2/22h^2 \lt L^2/2, that is when L>2hL \gt 2h. In English: the wrong answer wins as soon as each bar is longer than twice the gap between the bars, and it wins by more the longer they get. Nothing about the optimiser appears anywhere in that derivation.

    The Gaussian version of the same calculation, which is what the shipped dataset actually is, replaces L2/3L^2/3 by σℓ2\sigma_\ell^2 and L2/12L^2/12 by σℓ2(1−2/π)\sigma_\ell^2(1 - 2/\pi), and gives the threshold h<σℓ2/π≈0.798 σℓh \lt \sigma_\ell \sqrt{2/\pi} \approx 0.798\,\sigma_\ell. Two bars has σℓ\sigma_\ell of 0.250.25 and 0.190.19 and a half-separation hh of 0.140.14, and 0.798×0.22=0.1750.798 \times 0.22 = 0.175, comfortably above 0.140.14. The lengthwise cut wins, which is what the sweep measured: 5.40465.4046 against 6.29776.2977.

  4. Count the parameters. A KK-component Gaussian mixture in dd dimensions with full covariances has how many free parameters? Derive it rather than quoting it, and be careful about two things: a symmetric d×dd \times d matrix is not d2d^2 numbers, and the mixing weights are not KK free numbers. Compare with k-means’ KdKd at (K,d)=(2,2)(K, d) = (2, 2) and at (10,50)(10, 50). Then the part that is not a count: state the smallest number of points a component can own and still have an invertible sample covariance in dd dimensions, and explain what the estimator returns just below that threshold.

  5. Every partition is a line. Prove that if (c,μ)(c, \mu) minimises JJ with K=2K = 2, then the two clusters are separated by a straight line, and conversely that every straight split of the plane is the assignment phase of some pair of centres. Then explain why that turns the search over partitions, of which there are 2n−12^{n-1}, into a search over two real numbers, and why that in turn makes the figure 5.4046 in this lecture a global minimum rather than a best effort.

    Hint one

    For the forward direction, argue by contradiction on a single point: if a point is assigned to the further centre, moving it to the nearer one strictly decreases JJ and changes nothing else, so a minimiser assigns every point to its nearer centre.

    Hint two

    The set of points equidistant from μ1\mu_1 and μ2\mu_2 is ∥x−μ1∥2=∥x−μ2∥2\lVert x - \mu_1 \rVert^2 = \lVert x - \mu_2\rVert^2. Expand both sides. The quadratic term ∥x∥2\lVert x \rVert^2 appears on both and cancels, which is the whole trick: what is left is linear in xx.

    The solution

    Forward: at a minimiser, every point is assigned to its nearer centre, since otherwise reassigning that one point lowers JJ. So the two clusters are the two sides of the set where the distances are equal. Expanding ∥x−μ1∥2=∥x−μ2∥2\lVert x - \mu_1\rVert^2 = \lVert x - \mu_2 \rVert^2 gives −2x⋅μ1+∥μ1∥2=−2x⋅μ2+∥μ2∥2-2 x \cdot \mu_1 + \lVert \mu_1\rVert^2 = -2 x \cdot \mu_2 + \lVert \mu_2 \rVert^2, which rearranges to 2x⋅(μ2−μ1)=∥μ2∥2−∥μ1∥22 x \cdot (\mu_2 - \mu_1) = \lVert \mu_2\rVert^2 - \lVert\mu_1\rVert^2: a linear equation in xx, so a line, and specifically the perpendicular bisector of the segment μ1μ2\mu_1\mu_2.

    Converse: given any line, take any two points reflections of each other across it. Their perpendicular bisector is that line, so the assignment phase for those two centres reproduces the split.

    So the 2n−12^{n-1} partitions of nn points into two non-empty labelled groups are not all reachable; the reachable ones are indexed by an angle and an offset. That is why sweeping two dials finely is not a heuristic here. It covers the feasible set, which is why 5.40465.4046 is the lowest objective k-means can attain on Two bars and not the lowest anyone happened to find. Lloyd’s algorithm from a thousand random seeds independently agreeing on the same value is a check on the sweep, not the source of the claim.

  6. Write the E step. Implement responsibilities(points, centres, s2) for two equally weighted components sharing the covariance σ2I\sigma^2 I, and soft_mean(points, gammas) for the M step’s mean. The checks are the eight numbers from the worked example plus three properties: that the tie is exactly one half at every σ2\sigma^2, that a point five hundred units away from both centres still returns a probability rather than a nan, and that at σ2=10−6\sigma^2 = 10^{-6}, one step off the tie, hardening the responsibilities reproduces Lloyd’s assignment exactly. That last row is the identity of this lecture, run as a test.

    The checks · run against your code

    # the five responsibilities are the ones the lecture computed
    g = responsibilities(PTS, C0, 1.34)
    assert abs(g[0] - 0.99987096) < 1e-8
    assert abs(g[1] - 0.99745265) < 1e-8
    assert abs(g[3] - 0.00254735) < 1e-8
    assert abs(g[4] - 0.00012904) < 1e-8
    # the tie is exactly one half, at every sigma, and not approximately
    for s2 in (20.0, 1.34, 1e-3, 1e-9):
        assert responsibilities(PTS, C0, s2)[2] == 0.5
    # every value is a probability
    assert all(0.0 <= v <= 1.0 for v in g)
    # a point far from both centres must not underflow into 0/0
    far = responsibilities([(500.0, 0.0)], C0, 1e-6)
    assert far[0] == far[0] and 0.0 <= far[0] <= 1.0
    # the soft mean is the lecture's (1.004385, 0.2)
    m = soft_mean(PTS, g)
    assert abs(m[0] - 1.004385) < 1e-6 and abs(m[1] - 0.2) < 1e-12
    # and off the tie, hardening reproduces Lloyd exactly: move x3 to 2.75 and
    # the sigma -> 0 limit of the responsibilities IS the k-means assignment
    Q = [(0.0, 0.0), (1.0, 0.0), (2.75, 1.0), (5.0, 0.0), (6.0, 0.0)]
    hard = [0 if v > 0.5 else 1 for v in responsibilities(Q, C0, 1e-6)]
    assert hard == [0, 0, 0, 1, 1]
    python runs in your browser · first run downloads ~240 kb
    Plate V The E step, checked against the hand arithmetic and against Lloyd's algorithm at once. Four checks pin the four confident responsibilities to 10−810^{-8}; one pins the tie to exact equality at four values of σ2\sigma^2 spanning ten orders of magnitude; one requires a point at distance five hundred to come back a probability, which is what forces the two-branch logistic rather than a ratio of exponentials; and the last hardens the responsibilities at σ2=10−6\sigma^2 = 10^{-6} with x3x_3 moved to 2.752.75 and requires the result to be the k-means labelling. A green board is your E step agreeing with the fractions on paper and with the assign phase in Plate IV.
    Hint one

    Do not compute two densities and divide. Both of them contain the same normalising constant and the same mixing weight, and both underflow to zero for a point far from either centre, which turns the division into 0.0 / 0.0. Subtract the exponents instead: the whole posterior is 1/(1+exp⁡(−(d22−d12)/2σ2))1 / (1 + \exp(-(d_2^2 - d_1^2)/2\sigma^2)).

    Hint two

    Write the logistic in two branches, exactly as Lecture II wrote its sigmoid: for z≥0z \geq 0 return 1.0 / (1.0 + exp(-z)), and for z<0z \lt 0 compute e = exp(z) and return e / (1.0 + e). Both branches only ever hand exp a non-positive argument, and exp underflows quietly to 0.0 while overflowing loudly with an OverflowError. soft_mean is then two weighted sums over one division by sum(gammas).

    The solution

    Eleven lines, and the branch is the only interesting one:

    import math
    
    def logistic(z):
      if z >= 0.0:
          return 1.0 / (1.0 + math.exp(-z))
      e = math.exp(z)
      return e / (1.0 + e)
    
    def responsibilities(points, centres, s2):
      out = []
      for p in points:
          d1 = (p[0] - centres[0][0]) ** 2 + (p[1] - centres[0][1]) ** 2
          d2 = (p[0] - centres[1][0]) ** 2 + (p[1] - centres[1][1]) ** 2
          out.append(logistic((d2 - d1) / (2.0 * s2)))
      return out
    
    def soft_mean(points, gammas):
      n = sum(gammas)
      return (sum(g * p[0] for g, p in zip(gammas, points)) / n,
              sum(g * p[1] for g, p in zip(gammas, points)) / n)

    At the tie, d2−d1d_2 - d_1 is zero, the first branch runs, and 1.0 / (1.0 + math.exp(-0.0)) is 1.0 / 2.0, which is exactly 0.5 in binary floating point with no rounding anywhere. That is why the check can demand equality rather than a tolerance, and it is the cleanest available demonstration that the half is a fact about the model and not an artefact of the arithmetic.

    soft_mean never mentions the covariance, which is the reason the means it returns are the real EM means and not an approximation to them: the M step for μj\mu_j is ∑iγijxi/Nj\sum_i \gamma_{ij} x_i / N_j whatever Σj\Sigma_j is doing. Freezing the covariance to make σ\sigma a dial costs you the shape and costs you nothing else.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.