Measuring surprise

In July 1948 an engineer at Bell Labs, Claude Shannon, published “A Mathematical Theory of Communication”. On its second page he brushed meaning aside: “these semantic aspects of communication are irrelevant to the engineering problem”. What he cared about was how much information a message contains and how to transmit it efficiently. His answer founded an entire discipline and, seventy years later, gives the best description of what a language model does.

§Information is surprise

If someone tells you the sun will rise tomorrow, you learn nothing: you already knew. If they tell you it will snow in Seville tomorrow, you learn a lot. Shannon formalized this intuition: the information an event carries depends only on how improbable it was.

A certain event ($p=1$) carries 0 bits. A fair coin carries $-{\log }_2\frac{1}{2}=1$ bit. An event with probability $\frac{1}{1024}$ carries 10 bits. The logarithm is there for a reason: we want the information of two independent events to add up, while their joint probability multiplies: $-\log (pq)=-\log p-\log q$.

§Entropy: the average surprise

Before learning the outcome we do not know how much surprise awaits us, but we can compute its average value. That average is the entropy, the central quantity of the whole theory.

Shannon did not choose the formula for its looks: he proved it is the only reasonable measure of uncertainty.

Go back to the example on the home page. For “The cat is sitting on the…”, a distribution spread over mat, sofa and floor has high entropy: there is a lot of uncertainty about the next word. After “Once upon a…”, almost all the probability falls on time and the entropy is almost zero. Drag the bars in the figure to see how it changes.

§To compress is to predict

Entropy has a very concrete operational meaning: it is the limit of lossless compression.

Sketch of the proof

The lengths $\ell (x)$ of a prefix-free code satisfy Kraft's inequality, $\sum _x{2}^{-\ell (x)}\le 1$, so $q(x)=2^{-\ell (x)}$ behaves like a distribution. Then $L-H=\sum _{x}p(x){\log }_2\frac{p(x)}{q(x)}\ge 0$ by Gibbs' inequality (below). For the upper bound, choose $\ell (x)=\lceil -{\log }_{2}p(x)\rceil$, which satisfies Kraft and gives $L<H+1$.

In 1952 David Huffman, then a PhD student at MIT, found a simple algorithm that builds the optimal code: repeatedly merge the two least probable symbols. The consequence is the key to everything that follows: to compress well you must predict well. Whoever knows the distribution can give short codes to what is likely. The converse also holds: a good compressor contains a good model of the data.

§Cross-entropy: the price of being wrong

Suppose the data follow the true distribution $p$ and your model believes they follow $q$. If you design the code with $q$, each symbol $x$ costs you $-{\log }_{2}q(x)$ bits, and on average you pay the cross-entropy:

The first term is the inherent uncertainty of the data, which no model can remove. The second, the Kullback–Leibler divergence (1951), measures the bits wasted by using $q$ instead of $p$:

Proof

Use $\ln y\le y-1$, with equality only at $y=1$. Summing over the $x$ with $p(x)>0$:

$$-D_{\mathrm{KL}}(p\Vert q)=\sum _{x}p(x)\ln \frac{q(x)}{p(x)}\le \sum _{x}p(x)(\frac{q(x)}{p(x)}-1)=\sum _{x}q(x)-1\le 0.$$

(Changing the base of the logarithm only multiplies by a positive constant.)

This is the point of the site where everything clicks into place. If $p$ is the empirical distribution of the training data, minimizing $H(p,q_{\theta })$ with respect to the parameters $\theta$ is the same as minimizing the negative log-likelihood from the previous chapter. Maximum likelihood, minimum cross-entropy and maximum compression are the same objective, and that objective is the loss function every LLM is trained with:

Its exponential is called perplexity, $\mathrm{PPL}=2^{ℒ}$ (with $ℒ$ in bits): it is as if the model were hesitating, at each step, between $\mathrm{PPL}$ equally likely words.

§Shannon's approximations to English

In the same 1948 paper Shannon ran an experiment that seems prophetic today. He generated random text with increasingly informed models: equiprobable letters, letters with their real frequency, letters that depend on the previous one (digrams), on the previous two… and then the same with words. At each level the text looked more like English. It was the first statistical language model, built by hand from frequency tables taken from books.

In 1951 Shannon estimated the entropy of English by asking people to guess texts letter by letter, and obtained between 0.6 and 1.3 bits per letter, far below the ${\log }_{2}27\approx 4.75$ bits of equiprobable letters. That redundancy is what a language model exploits. An $n$-gram model cannot go much further: the number of contexts grows exponentially with $n$, and almost all of them appear once or never. To generalize to unseen contexts, words must be represented so that “cat” and “feline” end up close together. For that we need vectors and linear algebra.

§References

1. C. E. Shannon (1948). “A Mathematical Theory of Communication”. Bell System Technical Journal, 27(3–4).
2. S. Kullback and R. A. Leibler (1951). “On Information and Sufficiency”. Annals of Mathematical Statistics, 22(1).
3. C. E. Shannon (1951). “Prediction and Entropy of Printed English”. Bell System Technical Journal, 30(1).
4. D. A. Huffman (1952). “A Method for the Construction of Minimum-Redundancy Codes”. Proceedings of the IRE, 40(9).
5. T. M. Cover and J. A. Thomas (2006). Elements of Information Theory, 2nd ed. Wiley.
6. G. Delétang et al. (2024). “Language Modeling Is Compression”. ICLR 2024.