Measuring how much information each answer truly reveals in learning
Leveraged Learning: entropy destroyed per bit received
Information Theory
Summary
Learning involves reducing uncertainty by receiving answers to questions, but some answers can reveal more than just their own information. The authors study how much overall uncertainty is destroyed per bit of information received, a measure they call leverage. They find that if the learner's initial beliefs are smartly organized, this ratio can be much higher than if the beliefs are random. By analyzing different types of priors, including ones that prefer simpler patterns, they show how the efficiency of learning answers changes over time and can be precisely predicted.
entropysurprisalboolean mapsprior beliefleverageexchangeable priorde Finetti theoremReed-Muller codepolynomial degree over F2information theory
Authors
Daniel Chernowitz
Abstract
A learner holds a prior belief over boolean maps that answer a finite set of $Q$ questions, and receives answers one by one. Each answer costs surprisal and destroys uncertainty, not only about the question asked but every question still unasked. We call the ratio the leverage: table entropy destroyed per bit of surprisal received. It is unit for a uniform prior, but with an intelligent prior can be higher (not lower). Averaged over the truth prior and over the question order, the leverage is found exactly, and is generated by one sequence: the mean entropy $G_\ell$ of the answers to $\ell$ questions. Sending the number of input bits to infinity at fixed asked fraction $t = \ell/Q$, the increments of that sequence become a profile $γ(t)$, and initial question entropy $η_0$. The leverage closes to a thermodynamic limit. $L(t) = [η_0 - (1-t)γ(t)]/\int_0^t γ$. Exchangeable priors, by de Finetti, all give a flat $γ(t)$ and hence a hyperbolic $L(t)$, their deduction confined to a boundary layer at $t = 0$. We construct a simplicity prior that escapes this, grading Boolean maps by the degree of their polynomial over $\mathbb{F}_2$ and budgeting weight across degree shells by a CDF $F$. Reed-Muller capacity then gives $γ(t) = 1 - F(t)$ exactly, so any nonincreasing profile, and any leverage curve it generates, is realizable at macroscopic times.