Why Learning Can Work at All

A machine that simply memorized last year’s messages would score perfectly on them and fail on tonight’s. What we want is for it to do well on messages it has never seen. Why should learning from some examples say anything at all about others? That question has a precise answer, and the answer is surprising.

Memorizing alone is not enough. Learning is finding a description shorter than the examples, one that also fits the examples you have not seen yet.

Two students

Two nursing students prepare for an exam by studying last year’s paper.

The first memorizes it: question 7, answer C; question 12, “call an ambulance”. On last year’s paper she would score 100%. This year the questions are reworded and the cases changed, and she is lost.

The second works out why each answer is right. A rash that does not fade under pressure means bleeding under the skin. With a fever, that can mean a dangerous infection. So any feverish child with spots that stay under a glass needs emergency care, however the question is phrased. She would also score 100% on last year’s paper. The difference shows only on new questions.

The machine of Chapter 5 faces the same choice. With enough adjustable numbers it can simply memorize last year’s messages. What we want is the second student. Doing well on new cases is called generalization, and it is the whole point of learning.

The test you didn’t study for

To find out which student a machine is, hold some examples back. Train on most of last year’s messages and test on the rest, which the machine has never seen. A memorizer scores well on the training messages and badly on the held-out ones. A real learner does well on both. Two things matter here. The score on held-out messages must be good, not merely close to the training score: a machine can do equally badly on both. And the held-out messages must be like the ones it will really face, a point Chapter 7 makes painfully clear. A machine that does much better on its training data than on new data is said to overfit.

How to read a score. This book quotes many percentages, and each one is a score on some test. Three questions decide what a score means. First, were the test cases really unseen? A model that has read much of the internet may have met the test questions, or near copies, during training; then a high score shows memory, not skill. This is called contamination, and careful studies check for it. Second, were the test cases like the real ones? A score on one hospital’s images, or on tidy exam questions, says little about another hospital or a frightened parent’s own words. Chapter 7 shows how wide that gap can be. Third, what exactly was measured? A model that picks the right condition from a description has not shown that it can get a person to the right action, a gap Chapter 18 measures directly. Keep these three questions in mind whenever a number appears.

Nothing for nothing

Here is a puzzle. A machine sees three examples:

1 → 2, 2 → 4, 3 → 6.

What comes from 4? Almost everyone says 8: the rule “double it”. But another rule, “double the first three numbers, then give 14 for the fourth”, fits everything the machine has seen just as well. In fact, infinitely many rules give 2, 4, 6 on the first three inputs and anything at all on the fourth. The examples alone cannot tell it which rule to choose.

We choose “double it” because we assume simple rules are more likely than complicated ones. That assumption is not in the data. It is something the learner brings. It is called an inductive bias.

A theorem makes this exact. The no-free-lunch theorem says that, averaged over every possible way the world could be, no learning method beats any other, including random guessing. Every method that works on some problems must do worse on others. So no learner works on everything. A learner succeeds only when its built-in assumptions match the structure of the world it is used in.

Fortunately, the real world is highly structured. Nearby things tend to be similar. Causes come before effects. The same physical laws apply everywhere. Language has grammar. Illnesses produce characteristic patterns of symptoms. This is what makes learning possible at all: generalization = data + the right assumptions.

Learning is compression

Consider the second student’s method from another angle. She replaced a long list of question-answer pairs with one short principle that generates them all. She compressed the exam.

This is more than a metaphor. In 1948 Claude Shannon showed that predicting and compressing are two faces of one thing: if you can predict the next symbol well, you can encode it in few bits, and vice versa. A learner that finds the short description behind its examples has found what they share. What they share is what tends to carry over to new cases. Compression helps a learner generalize when it captures structure that also holds in the cases it will meet. “Purple spots that stay under pressure” and “dots that don’t fade when pushed” are, underneath, one fact. A learner that discovers this has compressed two phrasings into one, and will also recognize the third phrasing it has never seen.

The memorizer compresses nothing: her description of the exam is as long as the exam. That is why she has nothing to say about new questions.

The surprise of size

Classical learning theory gave a clear warning: a machine with more adjustable numbers than examples can memorize anything, so it risks overfitting. Modern networks complicated this picture. They often have far more adjustable numbers than examples, and can memorize even completely random labels. Yet trained on real data, they generalize well.

Plot the error on new cases against the size of the network and the surprise takes a shape. Error falls, then rises near the size where the network can only just fit every example, then falls again, often to its lowest level. This is called double descent. The leading explanation: a very large network has many settings that fit the data, and gradient descent tends to find a smooth, simple one. Extra size is room to be simple, not room to memorize. The account is proven for simple models and supported by experiments on deep ones; it is not a complete theory.

At this step, the machine is a bank’s fraud detector, which flags transactions it has never seen, as long as new fraud resembles the fraud it learned from.