Machine Learning 1 — a companion to lecture 5, §5.5
Cats are lighter than dogs, mostly. If all you are told is an animal's weight, some of the time you will get it wrong, and no amount of cleverness about where you put the cut-off will make that go away. What the cut-off does decide is how much worse than unavoidable you do. This page separates those two quantities and lets you push them around.
Each curve is a joint density p(x, C) — weight and species together, not weight given species. That is the one thing worth insisting on before anything else, because it makes the picture readable as areas: every shaded region in the figure is a probability, the two curves enclose a total area of exactly 1 between them, and the area under the cat curve alone is p(cat). Class-conditional densities would each integrate to 1 and could not be compared by eye at all.
Cats come in two groups here: a main population around 4 kg and a heavier one around 8.5 kg. Dogs are a single, wider population — centred on the same 8.5 kg. That coincidence is the whole difficulty in one number. The typical dog weighs exactly what a heavy cat weighs, so for those two groups the weight carries no information at all, and heavy therefore dog is a rule that will keep costing you. What separates the classes is not where the dog population sits but how wide it is: dogs are spread over a range no cat covers, and everything the classifier knows comes from that.
The Bayes classifier assigns x to whichever class has the largest posterior:
C(x) = argmaxk p(Ck | x)
and because p(Ck, x) = p(Ck | x) p(x), with p(x) a positive factor that does not depend on k, that is the same rule as
C(x) = argmaxk p(x, Ck)
which you can carry out by eye on this figure: at each weight, pick whichever curve is higher. The second strip under the axis is that rule drawn out. Where the curves cross, the decision flips.
Move the boundary and the total error moves with it, but it never reaches zero. The floor is the Bayes rate: the error of the rule above, which is the best any classifier can do, and is a property of the data rather than of any model.
R* = ∫ (1 − maxk p(Ck | x)) p(x) dx
The p(x) is not decoration. Without it you would be integrating a conditional probability against a bare volume element, and a region where the two classes happen to be evenly matched but no animal is ever seen would contribute full error weight. p(x) is what says that errors only count where inputs actually turn up.
Pushing it through the same identity gives two forms that read straight off the figure, and these are the ones to look at while you drag:
R* = 1 − ∫ maxk p(x, Ck) dx = ∫ min(p(x, C1), p(x, C2)) dx
The first says the achievable accuracy is the area under the upper envelope of the two curves. The second — the one that only works for two classes, where 1 − max is the same as min — says the Bayes rate is the area of the overlap. It is the region the figure shades once the boundary is in the right place, and it is why overlap and irreducible error are the same word here. For more than two classes the min form stops being true: the smallest posterior is then the least likely class, not the error.
With the default populations the Bayes rate is 13.8%, reached at a boundary of 5.8 kg. Put the boundary at 4.5 kg instead and the error is 22.3%; at 9 kg, 31.9%. All of the difference between those numbers is yours to fix. None of the 13.8% is.
One detail worth pausing on: at the optimum the two kinds of mistake are not equal. 10.6% of all animals are cats called dogs and 3.2% are dogs called cats. Minimizing the total says nothing about balancing the parts, which is the opening the loss matrix at the end of this page walks through.
Take the error as a function of where you put a single threshold:
E(x) = ∫x>x p(x, C1) dx + ∫x<x p(x, C2) dx
and differentiate, which the fundamental theorem of calculus makes a one-liner:
dE/dx = p(x, C2) − p(x, C1)
So E is stationary exactly where the two joint densities are equal — at a crossing, and nowhere else. That is the analytic version of pick the higher curve, and it also explains the shape of the right-hand panel: the error curve is flat near its minimum, because near a crossing the two integrands nearly cancel. Being a little bit wrong about the boundary is cheap. That is worth knowing, because it is the reason a crude classifier often does nearly as well as a careful one.
It also tells you what the red region is. Moving from x0 to x costs
E(x) − E(x0) = ∫x0x (p(x, C2) − p(x, C1)) dx
— the area between the two curves over the stretch you moved. The figure shades that band in red, which is why the red vanishes when the boundary reaches x0 and grows quadratically on either side of it.
Nothing above said threshold. It said pick the higher curve, and those are only the same thing when the curves cross once.
Push the heavy-cat slider up. The spike at 8.5 kg climbs until it breaks through the top of the dog curve — through the dog's own peak, since that is where it sits — the curves now cross three times, and the Bayes-optimal region for cats becomes two separate intervals: ordinary cats, and then an island of heavy cats in the middle of dog weights. The strip under the axis splits into three bands, and the sentence heavier than this means dog stops describing the optimal rule at all.
At 45% heavy cats the Bayes rate is 22.3%, while the best single threshold anywhere on the axis gives 26.7%. That 4.4-point gap is the price of the form of the classifier rather than of the noise in the problem. It is the first genuinely model-driven error on this page: every other number so far has been a property of cats and dogs, and this one is a property of the rule you insisted on using.
And a threshold is not an arbitrary thing to have insisted on. In one dimension a threshold is the linear classifier. Deciding by the sign of wx + w0 is deciding whether x falls above or below −w0/w — one cut, splitting the axis into exactly two pieces. No choice of w and w0 yields three. So the moment the optimal regions stop being two intervals, a linear classifier cannot represent the answer at all, however well it is fitted; the 4.4 points are not a training failure but a statement about what the model can express.
What is wanted instead is a rule that assigns a class per region rather than per side — one free to answer cat in two separate places. Any nonlinear decision function can do it. So can the thing the bottom strip has been doing all along: compare the two densities at each x and take the larger. That is worth holding on to, because it is exactly what a generative model hands you, and curved boundaries come with it at no extra cost.
Slide the prior. Both curves rescale — the cat curve by p(cat), the dog curve by 1 − p(cat) — and the crossing moves, because a crossing is a comparison between the two heights and the heights just changed. No shape changed; the answer did.
Take it to an extreme. At p(cat) = 0.99 the dog curve is flattened to a hundredth of its old height, the boundary has retreated to 10.0 kg, and the stretch of axis beyond it, where the rule still answers dog, holds 0.2% of all animals. The Bayes rate there is 0.8%. Meanwhile a classifier that never looks at the weight at all, and answers cat every time, gets 1.0% wrong.
So the entire value of weighing the animal is two tenths of a percentage point. Push the prior further and the dog region keeps emptying out — at p(cat) = 0.999 it holds 0.015% — and you may as well throw away the scale and call everything a cat. Note what does not happen: the threshold does not run off to infinity. It creeps to the right, slowly, while the region it cuts off stops containing anything.
This is the honest form of the warning about accuracy. A 99% figure is not a result until you know what the majority class alone would have scored. The readout carries that comparison at every prior, so it is worth watching the two numbers close on each other as you slide.
One aside, visible on the way there: somewhere between p(cat) = 0.7 and 0.95 the regions split into three again — for the same reason as the previous frame, but brought about by the prior rather than by the populations. How many decision regions there are is not a fixed property of the two shapes.
So far every mistake has counted as one mistake. That was a choice, and it is often the wrong one.
Picture the classifier running a feeding hatch with a scale on the step: it weighs whatever is standing there and decides whether to open. The two mistakes are not alike. Turn a cat away and it waits and tries again a minute later. Let a dog in and it eats the lot, and the cat goes hungry. Suppose letting a dog in is ten times as bad as turning a cat away. What you want to minimize is then not how often am I wrong but how much do my mistakes cost:
E[L] = Lcat→dog · P(cat turned away) + Ldog→cat · P(dog let in)
Put the boundary where the error rate is lowest, at 5.8 kg, and 10.6% of all animals are cats turned away while 3.2% are dogs let in. The cost is 0.106 + 10 × 0.032 = 0.43. Move the boundary down to 4.7 kg and the split becomes 18.5% and 0.9%, so the cost is 0.185 + 10 × 0.009 = 0.28.
Read that back as animals rather than as arithmetic: it is worth turning away nearly twice as many cats in order to cut the dogs getting in from one in thirty to fewer than one in a hundred. The error rate went up, from 13.8% to 19.4%, and the cost came down by a third. The classifier got worse at the thing it was asked to minimize a moment ago, and better at the thing you actually wanted.
That is all the right-hand panel is saying when it draws two curves. The dashed one is the error rate and the solid one is the cost; their lowest points are at different weights. The two vertical scales have nothing to do with each other — the only thing to read off the panel is where each minimum sits.
In general the rule becomes: assign x to the class that minimizes ∑j Ljk p(x, Cj). Its boundary is no longer where the two densities are equal, but where the cost-weighted densities are:
Lcat→dog p(x, C1) = Ldog→cat p(x, C2)
Only the ratio of the two costs matters, never their units, which is why the slider is labelled as a multiple. Medical screening has this same structure with a far larger ratio — missing a disease can be hundreds of times worse than a false alarm — and its boundary ends up somewhere no accuracy-minimizing classifier would ever have put it.
The Bayes classifier is the one built on the true posterior. It is a theoretical object — you never have p(Ck | x), and everything in the rest of the lecture is an attempt to approximate it. A rule built on an estimate p is a plug-in rule, and linear and quadratic discriminant analysis are exactly that. Keeping the names apart is what makes the Bayes rate a floor rather than just one more model's score.
And a plug-in rule only needs the argmax right, not the probabilities. A badly calibrated p that preserves the ordering hits the Bayes rate exactly. Approximation error costs nothing until it flips the winner — which is the argument for modelling the boundary directly rather than modelling both densities and dividing.
Everything here assumed the two densities were handed to you. They are not, and the rest of the lecture is about where they come from: put a Gaussian on each class, divide, and the posterior turns out to be a logistic sigmoid of a linear function of x — so the crossing you have been dragging becomes the place where wTx + w0 is zero, and fitting a classifier becomes fitting that line.