Why Learning From Data Works At All

A model fitted to data reports a score on that data. Everyone knows not to trust it. Fewer people can say precisely what is wrong with it, how much it is wrong by, or what would have to be true for it to be trustworthy.

Those questions have exact answers, and they are more interesting than the warning. This article works through three of them, computing every figure rather than quoting it.

The number you see is a report on a search

Fix a rule before looking at the data. Its error on your sample will be close to its error on the world, because the sample points are independent draws and averages concentrate. That is ordinary statistics, and nothing is wrong yet.

Learners do not work that way. They look at the data and choose. That choice is a function of the sample, and it destroys the guarantee.

Here is the size of the damage, measured on data built so that there is nothing whatever to learn. Every candidate hypothesis is pure noise with a true error of exactly $0.5$. Draw 200 points, score them all, keep the best:

With one candidate, nothing is chosen and the score is honest to within $0.0002$. With a thousand, the reported error sits $0.1149$ below the truth - a model that looks clearly better than chance while being exactly chance.

Not one of those thousand hypotheses is better than another. They are identical in truth. What differs is luck on this particular sample, and taking the best is taking the luckiest.

This is the mechanism behind the result that will not replicate, the feature selected on the data it is then evaluated on, and "we tried several architectures and this one worked". The training score is not an estimate of future performance; it is a report on a search.

Paying for the search, in logarithms

The repair is to stop asking about the winner and ask about every candidate at once. If a guarantee holds simultaneously for all of them, it covers whichever one the data selected, however that selection happened.

That is the union bound, and combined with Hoeffding's inequality it gives a sample requirement:

$$n \;\ge\; \frac{\ln|H| + \ln(2/\delta)}{2\varepsilon^2}$$

Read it as a price list: $\varepsilon$ is the tolerance you accept, $\delta$ how often you will let the guarantee fail, and $|H|$ is what your search costs. At $\varepsilon = 0.1$ and $\delta = 0.05$:

Half a million times as many hypotheses costs 658 more samples. Not 658 times more - 658 more.

That logarithm is why machine learning is possible. If the requirement grew with the size of the class rather than with its number of digits, no useful model class would be affordable.

Both tables are in the figure below, and neither is simulated. The best of m identical hypotheses is the minimum of m binomial draws, so the flattery is a finite sum rather than an average over 200 trials - which fixes one entry: with a single candidate the expected gap is exactly 0, and the 0.0002 above is the simulation's own noise. Switch to the second panel and push the class size to a billion to watch the budget refuse to follow.

Capacity, when counting fails

The argument counts hypotheses, and almost every class worth using has infinitely many: every threshold on a line, every hyperplane in a space. Yet those classes generalise perfectly well, so counting members must be measuring the wrong thing.

The fix is to look at the data instead. Two hypotheses that assign the same labels to your points are indistinguishable on them, whatever they do elsewhere. So the quantity that matters is how many distinct labellings the class can produce - a number that stays finite even when the class does not.

A set of points is shattered when every possible labelling of it is achievable. The VC dimension is the size of the largest shattered set.

Intervals on a line make it concrete. Two points: an interval can take both, either one, or neither - all four labellings, shattered. Three points: the class achieves 7 of the 8, and the one it misses is

$$(1, 0, 1)$$

because an interval containing the outer two points must contain the middle one. Seven of eight is a failure - shattering is all-or-nothing - so the VC dimension is exactly 2, held down by one unreachable pattern.

Axis-aligned rectangles shatter four points arranged as a diamond and fail on any five, by an argument worth keeping: among five points, at most four can be extreme (leftmost, rightmost, topmost, bottommost), and the leftover point is boxed in by them. Any rectangle holding the four extremes holds it too.

Why that helps

Sauer's lemma turns a finite dimension into a polynomial count. A class of VC dimension $d$ realises at most $\sum_{i \le d} \binom{n}{i}$ labellings on $n$ points. At dimension 2:

The union bound never needed the hypotheses, only their distinct behaviours. Put the polynomial where $|H|$ stood, take the logarithm, and the price becomes about $d \log n$ - slow enough that the guarantee tightens as data accumulates. Capacity stops being a count of hypotheses and becomes a count of behaviours.

The theorem that equalises everyone

So capacity can be measured and paid for. Which algorithm is best, then?

Take a domain of five points, so there are $2^5 = 32$ possible target functions. A learner sees three labels and predicts the other two. Average its score over all 32 targets. Four deliberately different strategies - always predict 1, follow the majority seen, ignore the data and alternate, or do the opposite of the majority - each score

$$\frac{1}{2}$$

Exactly one half, computed in exact fractions over all 32 targets. Even the strategy designed to be bad.

The mechanism has nothing to do with the learners. Fix the training labels and consider any unseen point: the consistent targets come in pairs, identical except at that point, where one says 0 and the other says 1. Any prediction is right for one and wrong for its twin. The learner never enters the argument.

And the step that restores learning

Now allow only the 6 targets that switch from 0 to 1 at most once, the thresholds 00000, 00001, 00011, 00111, 01111 and 11111 - and use a learner built for that shape. Accuracy becomes $3/4$.

Nothing was learned about the world between those two calculations, and no new data arrived. What changed is which worlds were considered possible.

That is what an inductive bias is, and it is where generalisation comes from.

What the theorem is usually made to say

It gets quoted as "no algorithm is better than any other", which drops the assumption doing all the work.

The equality holds when averaging uniformly over all possible targets. Ask what that distribution contains: of all functions on a domain, the overwhelming majority have no structure at all - incompressible noise, nothing to extract. No method beats chance on those, and they dominate the average.

Real problems live in a vanishingly small, highly structured corner of that space. A uniform average over all functions is not a model of any problem anyone has.

So the theorem is not a counsel of despair and not a licence to call all methods equal. It says something sharper: you cannot get generalisation from nothing. Performance comes from assumptions, those assumptions can be wrong, and a method that appears to work everywhere has merely not met the problem it is wrong about.

Which makes the choice of model class a substantive claim about the world - worth making deliberately, and worth stating out loud.

The training path Statistical Learning Theory works through all three arguments in detail, with every computation runnable and editable in the browser.