Lecture IV · Machine Learning
Clustering without an answer key
Every lecture so far has had an answer key. There was a , the loss was defined by the gap between the prediction and that , 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 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 . A partition assigns each point to one cluster , and each cluster carries a centre . The objective is the within-cluster sum of squares,
and k-means is nothing but a search for the and 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 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 to minimise . 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 to minimise . Again the terms separate, one cluster at a time, and
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 in one argument, so 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
with and . The assign phase needs squared distances and nothing else, so here they all are:
| Point | Goes to | ||
|---|---|---|---|
| cluster 1 | |||
| cluster 1 | |||
| cluster 1, by a tie-break | |||
| cluster 2 | |||
| cluster 2 |
Stop on the third row. Both distances are , 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 , 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, . Now the update phase, which is two means:
and re-measuring the same partition about its new centres gives
One iteration bought exactly , 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 , its own mixing weight , and its own full covariance matrix . The data is assumed drawn by picking a component with probability and then sampling from it, so the density of a point is
and the thing being maximised is the log-likelihood 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 generated it:
This is the soft version of “assign to the nearest centre”. A point squarely inside one component gets a responsibility near to it; a point in the overlap gets something like and and genuinely belongs to both.
M step. Re-estimate every parameter as a responsibility-weighted average. Writing for the effective number of points the component owns,
Compare the middle one with the k-means update. It is the same mean, with where a hard zero-or-one membership used to be. That is not a coincidence: fix every covariance at and every weight at , and let , 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 . 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 for a single scaled to the spread of the data and both weights at ; on these five points that scale works out to 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 cancels except the exponent, and the responsibility becomes a logistic of the difference of the two squared distances already tabulated above:
With that gives, to eight places:
| Point | k-means said | |||
|---|---|---|---|---|
| cluster 1 | ||||
| cluster 1 | ||||
| cluster 1 | ||||
| cluster 2 | ||||
| cluster 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 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 exactly, because the five points are symmetric about , so the weights stay at and the M step is just two weighted means:
Put those beside k-means’ 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 by a whole membership it had to invent; EM’s was dragged half as far by a membership it computed.
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.
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 is Lloyd’s algorithm everywhere except on the set of exact ties, and on that set the soft answer is 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.
iteration 5 · next phase update · WCSS 5.405 · reassigned 0 · centroid shift 0.005 · matches the generating labels 56% · converged
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.
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 , 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 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 , 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 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 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:
| Split | Objective | Recovers |
|---|---|---|
| The cheapest line there is, at , offset | 5.4046 | 125 of 220, 56.8% |
| The best separation any line achieves, at , offset | 6.2977 | 216 of 220, 98.2% |
| The generating partition itself, about its own two means | 6.3582 | 220 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.
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.
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 -component mixture with full covariances in dimensions carries free parameters, against k-means’ . 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 because a covariance matrix is. Worse than the count is what the count needs: a sample covariance built from fewer than points in dimensions is singular, so at 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 , 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 . You cannot pick by minimising , because falls monotonically as 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 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 . The density at that point is , so the point’s contribution to the log-likelihood grows like 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
which is a rise of exactly for every hundredfold shrink, forever. It passes the honest converged fit’s 330.92 at around . Rerun the same sequence with in place and it reads 238.92, 238.93, 238.93, 238.93, 238.93. It stops. Since the determinant can never fall below , the density at any component’s own mean is capped at , 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 points in the plane has a sample covariance of rank at most
, so at the determinant is exactly zero and at it came out
at , 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 , 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 , and that bottom-right entry is exactly before the ridge and 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)
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 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 and 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 by some rendering trick. They are , 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 directly for , takes the two half-axes as and , 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:
| Bar | Tilt, generated | Tilt, recovered | Elongation, generated | Elongation, recovered |
|---|---|---|---|---|
| The lower one | rad | |||
| The upper one | rad |
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 and , the square roots of eigenvalues and .
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 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.
Redo the iteration, off the tie. Move from to 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 and give 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.
The tie, exactly. Show that when the responsibility equals for every , so that the limit as is and not or . Conclude that the statement “k-means is the 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.
Price the correct answer. Take two bars of points each, uniformly spread along their length: bar A occupies and bar B occupies . 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 . Both are fixed points of Lloyd’s algorithm; check that too. Find the exact condition on and 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 is , and on it is . Each partition puts points in each cluster, so you never need to carry a count through the algebra: just write each cluster’s contribution as times its own mean squared deviation.
Hint two
For the crosswise partition the cluster mean sits at and the only spread is along the bar. For the lengthwise one the cluster mean sits at , and there are now two contributions, because each cluster holds half of both bars and therefore spreads in as well as in .
The solution
Crosswise: each cluster is one whole bar, mean at , spread only along , so its contribution is and the total is .
Lengthwise: each cluster is half of each bar, mean at . In the points are uniform on an interval of length , giving per point; in every point sits at distance from the mean, giving per point. Total .
The lengthwise cut is cheaper when , that is when , that is when . 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 by and by , and gives the threshold . Two bars has of and and a half-separation of , and , comfortably above . The lengthwise cut wins, which is what the sweep measured: against .
Count the parameters. A -component Gaussian mixture in dimensions with full covariances has how many free parameters? Derive it rather than quoting it, and be careful about two things: a symmetric matrix is not numbers, and the mixing weights are not free numbers. Compare with k-means’ at and at . 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 dimensions, and explain what the estimator returns just below that threshold.
Every partition is a line. Prove that if minimises with , 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 , 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 and changes nothing else, so a minimiser assigns every point to its nearer centre.
Hint two
The set of points equidistant from and is . Expand both sides. The quadratic term appears on both and cancels, which is the whole trick: what is left is linear in .
The solution
Forward: at a minimiser, every point is assigned to its nearer centre, since otherwise reassigning that one point lowers . So the two clusters are the two sides of the set where the distances are equal. Expanding gives , which rearranges to : a linear equation in , so a line, and specifically the perpendicular bisector of the segment .
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 partitions of 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 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.
Write the E step. Implement
responsibilities(points, centres, s2)for two equally weighted components sharing the covariance , andsoft_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 , that a point five hundred units away from both centres still returns a probability rather than anan, and that at , 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 kbPlate V The E step, checked against the hand arithmetic and against Lloyd's algorithm at once. Four checks pin the four confident responsibilities to ; one pins the tie to exact equality at four values of 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 with moved to 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 .Hint two
Write the logistic in two branches, exactly as Lecture II wrote its sigmoid: for return
1.0 / (1.0 + exp(-z)), and for computee = exp(z)and returne / (1.0 + e). Both branches only ever handexpa non-positive argument, andexpunderflows quietly to0.0while overflowing loudly with anOverflowError.soft_meanis then two weighted sums over one division bysum(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, is zero, the first branch runs, and
1.0 / (1.0 + math.exp(-0.0))is1.0 / 2.0, which is exactly0.5in 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_meannever 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 is whatever is doing. Freezing the covariance to make a dial costs you the shape and costs you nothing else.