Leveraged learning measures information gained per answer bit received
Leveraged Learning: entropy destroyed per bit received
Information Theory
Summary
This work looks at how much uncertainty is reduced when a learner asks yes/no questions one by one. The authors introduce the idea of leverage, which measures how many bits of uncertainty get eliminated for each bit of surprise in an answer. They find that this leverage can be higher if the learner has an intelligent prior belief about the answers. They create mathematical models to predict how leverage behaves, showing that some prior beliefs let you learn faster and more efficiently.
What this means in practice
- •For data compression engineers: Design encoding schemes that maximize information gain per received bit by exploiting structured prior knowledge about the data.
- •For machine learning pipeline designers: Optimize question or feature selection processes by tuning learner priors to improve information efficiency in sequential decision tasks.
A theory result. No direct application yet.
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.