Learning Theory · Chapter 2
Chapter 1 ended with a working definition: an observation is worth the bits it removes from the description of future observations. This chapter makes it exact, and the first thing exactness does is separate two quantities that are easy to confuse.
Show a child a cat. Then show it a screen of television static. The static is far more surprising: no child could have predicted those exact dots. By Shannon’s measure it carries more information than anything else the child will see that day. It teaches nothing.
Surprise is measured against the learner’s current expectations. If the learner in state θ assigns probability pθ(x) to what it sees, its surprise is:
Static is maximally surprising because nothing about it could be predicted, and for the same reason nothing about it can be used. What a learner needs is not to be surprised now, but to be less surprised later.
Let F be the observations still to come, and LF(θ) the bits a learner in state θ needs to describe them, the sum of its surprises over F. Write θ ⊕ x for the learner after it has learned from x.
DefinitionLesson
The lesson of an observation x for a learner in state θ is the number of bits it saves on the future: ℓ(x | θ) = LF(θ) − LF(θ ⊕ x).
Three things follow at once. A lesson depends on the learner: the same picture is worth different amounts to different learners, and to the same learner at different times. A lesson can be zero, as for static or the twentieth reading of a book. And a lesson can be negative: an observation can make the future more expensive to describe, if it pushes the learner’s expectations away from the world.
Keep showing it cats. The first cat is a real lesson. After a few more, each new cat is a negative lesson: the learner now expects cats too often, and the dogs and birds it will meet become more expensive. Show it the world as it is and the lessons shrink toward zero, because there is less and less left to learn.
Suppose the world produces observations from a distribution q. The learner’s average surprise then splits exactly into two parts. This is an identity of information theory, not an approximation:
The first part, H(q), is the world’s own randomness. No learner, however good, can predict it, and no observation can teach it away. The second part, the divergence D(q ‖ pθ), is what the learner has not learned yet: its ignorance. (Cover & Thomas)
When the future is drawn from the same world, a lesson is exactly a reduction of ignorance:
This is why static teaches nothing. Its surprise is almost all entropy. A cat surprises less, but part of that surprise is ignorance, and ignorance is the only part a lesson can remove.
Add up the lessons of a sequence of observations and the middle terms cancel, so the total depends only on where the learner started and where it ended:
PropositionConservation of lessons
Over any sequence, the lessons a learner receives sum to the ignorance it lost. They can never exceed the ignorance it started with. Every negative lesson has to be paid back by a positive one before it counts.
The bound is what makes a curriculum a finite problem. A child cannot learn more about cats than it did not know about cats; what is left to decide is how fast, and in what order, that budget gets spent.
For an ideal Bayesian learner, which keeps a prior over possible worlds and updates it exactly, the average lesson of the next observation is a mutual information. It is the information the next observation shares with the future, given the past:
Bialek, Nemenman and Tishby call the information the past carries about the future predictive information, and show it is what any learner can at most extract. For a world described by k parameters, the total extra cost of learning grows only like ½ k log2 n over n observations. So the average lesson per observation falls roughly like 1 / n. (Bialek et al.) (Clarke & Barron)
That is the learning curve everyone has seen, now with a unit: early observations are worth many bits, later ones fewer, and the total converges.
Prime is not an ideal learner, and its future is not a known distribution, but the definition still gives a procedure. Fix a held-out set as the future. The lesson of a batch is the drop in the held-out code length before and after the gradient step on that batch. Summed along training, these are the bits the curriculum taught. Blier and Ollivier’s prequential code length is the same quantity measured on the training stream itself. (Blier & Ollivier)
DesignMeasurement on Prime
Per-stage lessons on Prime’s curriculum, measured this way on a fixed held-out set, are reported in chapter 32. Chapter 1’s Fano numbers are a floor on one part of them: the bits about names.
A lesson is defined relative to a learner and a future. Chapter 3 asks what can be said about it in general: six laws, from the ones that follow directly from this definition to the ones that are still bets.