Learning Theory · Chapter 1
In 1928 Ralph Hartley set out to measure information on physical rather than psychological grounds. A message is informative because of what it rules out. With N equally likely possibilities, the amount it tells you is the number of yes-or-no questions it saves. (Hartley)
Name one of 256 objects and you have conveyed 8 bits. Name one of ten and you have conveyed about 3.3. What the word means never enters; only the size of the set it was chosen from.
Twenty years later Claude Shannon extended this to outcomes that are not equally likely. He did not guess the formula. He wrote down three things any measure of uncertainty H(p1, …, pn) should do, then proved that only one function does all three. (Shannon)
The logarithm comes from the third rule. The uncertainty of two independent choices should be the sum of their uncertainties, while the number of joint outcomes is their product. Only a logarithm turns products into sums.
Shannon also drew a boundary. The meaning of a message, he wrote, is irrelevant to the engineering problem. His theory counts distinctions, not understanding. That boundary is where a theory of learning has to start. (Shannon)
Shannon’s receiver already knows the code. A learner does not. When a child sees a cat and hears the word cat, nothing is being decoded yet. The code itself is being built.
So the question changes. Not how many bits a message carries, but how many bits one observation teaches: a symbol, a sound, a picture, a few seconds of video. And where those bits end up.
For one observation there are at least three different amounts:
The signal is enormous and the lesson is small. Almost every bit of the raw input describes lighting, background or the speaker’s voice, none of which the name depends on. Most of learning is deciding which bits to throw away.
A ceiling. A labelled example cannot teach more about its label than the label contains: log2 K bits for K equally likely classes. Every number in this chapter sits under that line.
A floor. Accuracy on unseen data gives a lower bound. If a model names a new example correctly with probability 1 − Pe among K classes, Fano’s inequality (1.3) says how many bits about the true name its answers must still carry. These are the bits that survived the trip from training to something new. (Cover & Thomas)
What stays in the weights. Xu and Raginsky showed that the generalization gap is bounded by the mutual information between the training set and the learned weights, I(W; S). A model that keeps fewer bits about its particular samples generalizes better. (Xu & Raginsky)
What one observation saves. The cleanest bridge is coding. Encode a dataset one example at a time with a model that keeps learning, and the total code length is the sum of the losses along the way (1.5). Blier and Ollivier measured deep networks this way and found they compress their data well despite their many parameters. On this view, what an observation teaches is the number of bits it saves on the observations that come after it. (Blier & Ollivier)
Prime is a model we train the way you would teach a child: seeing and hearing first, then reading and writing, with 256 everyday concepts in Chinese and English. Every answer is generated, not picked from a list. All numbers below are on things it has never encountered: new photos, new voices, new fonts.
bits recovered (Fano lower bound)ceiling, log₂ K
Symbols and words come through almost whole. Pictures do not: about one bit out of eight.
The size of the input does not explain it. Two seconds of speech is about twenty times more raw data than a 32 × 32 picture, and it teaches more. What matters is how much of the input changes while the name stays the same. The character 猫 in a new font still has mostly the same strokes. A new photo of a cat shares almost no pixels with the last one.
How to read these numbers: Fano gives a floor on bits about the name only, from 300 test items per task (accuracy ±3%). It says nothing about what the model learned that is not about the name.
The clearest case came early, with ten classes. We first trained on a fixed picture book: twenty images per class, shown again and again, the way you read a favourite book to a toddler.
bits recoveredceiling
On the pictures it had seen, the model was perfect. Every one delivered its full 3.32 bits. On new pictures it recovered 0.03. The bits went in, and stayed with those twenty pictures.
Replacing repetition with variety, a different picture almost every time, raised that to 0.60. Aligning the model’s internal features with a pretrained vision model, DINOv2, added a little more. It is a stand-in for the visual system a child already has before learning words. A model twice the size, trained twice as long, reached 0.79. (DINOv2) (REPA)
Memorized bits and learned bits are different quantities. Only the second one is worth anything.
Together these suggest a working definition: an observation is worth the bits it removes from the description of future observations. Four things decide how many it can give.
And four ways an observation’s bits go to waste:
None of these pieces is new on its own. Hartley, Shannon, minimum description length and information-theoretic generalization bounds each cover part of it. The part this book wants to work out is the one a curriculum depends on: given what a learner already knows, which observation should it see next, and how many bits will it keep?
Chapter 2 turns the working definition into a precise one. It separates the surprise an observation causes from the lesson it leaves behind, and shows why the two are different quantities.