Measuring surprise

Our table from the last chapter writes "Frthendd, aced. tre sedsck". Is that good? Compared with what? Looking at the output and saying "sort of English" is not enough. To improve a model (and training is nothing but improving a model over and over again) we need a single number that says how good it is. Better models should get a better number, and the number should be quick to compute.

The idea is simple. A good model is one that is rarely surprised by real text. We take a text written by a person, feed it to the model letter by letter, and each time ask: what probability did you give to the letter that actually came next? If the model keeps giving high probabilities to what really happens, it understands the language well. If it is constantly caught off guard, it doesn't.

A surprised Sprout

Let's try it before we formalise anything. Below is Sprout in its current form, the letter table from the last chapter. Type anything in English. Every letter is coloured by how much it surprised the table: a pale letter was expected, a dark one came as a shock. The needle shows the average over the whole text. Tap any letter to see what the table was expecting instead.

Play with the presets. An ordinary sentence from a story averages about 2.3 on the dial; its darkest letter is the capital L of "Lily", since names are hard to predict. "u" after "q" costs almost nothing. The pangram about the fox is noticeably harder: "q", "x" and "z" are rare. Gibberish lands at 6.4, far past the "guessing" mark: the table isn't just unsure there, it is confidently wrong. ALL CAPS is worse still, 7.8, because capitals almost never follow capitals in children's stories. Russian written in Latin letters sits in between, around 3.5: these are real letters, but the pairs are wrong for English.

The colours already tell a story. Now let's turn them into mathematics.

The probability of a whole text

The most natural way to grade a model on a text is to ask what probability it gives to the whole text. For our table that is easy to compute. The chance that a story starts with "O" is $p(\text{O} \mid \blacklozenge) = 0.253$. The chance that "n" comes next, given "O", is $0.730$. Letters come one after another, so the probabilities multiply:

$$\begin{aligned} p(\text{text}) &= p(x_1 \mid \blacklozenge) \cdot p(x_2 \mid x_1) \cdots \\ &= \prod_{t=1}^{N} p(x_t \mid x_{t-1}), \qquad x_0 = \blacklozenge \end{aligned}$$

(The big $\prod$ means "multiply everything from $t = 1$ to $N$", just as $\sum$ means "add everything".) This number is called the likelihood of the text under the model. Compare two models on the same real text, and the one that gives it the higher probability is the better one: it saw the real text coming.

Let's compute it for "Once upon a time". The sixteen probabilities are 0.253, 0.730, 0.023, 0.156, 0.313, 0.008 (the "u" of "upon": after a space, words rarely start with u)… and their product is about $8.0 \cdot 10^{-17}$. For a sixteen-letter phrase that is already a very small number. For the 45 letters of "Once upon a time, there was a dog named Spot." it is $8.0 \cdot 10^{-47}$. And a whole story?

Here is the trouble. A computer stores numbers with limited precision. An ordinary "double" (float64) cannot hold anything smaller than about $5 \cdot 10^{-324}$: below that, it becomes exactly zero. On this story that happens at letter 324. Graphics cards usually count in float32, and there the product turns into zero as early as letter 45. A zero is useless: all texts get the same grade, "impossible", and you can no longer tell a good model from a bad one.

Logarithms to the rescue

The way out is a tool from school: the logarithm. Its most useful property is that it turns multiplication into addition:

$$\log(a \cdot b) = \log a + \log b$$

So instead of the tiny product we can keep the sum of the logarithms of the probabilities:

$$\log p(\text{text}) = \sum_{t=1}^{N} \log p(x_t \mid x_{t-1})$$

The terms are ordinary moderate numbers, and so is their sum. For "Once upon a time" it is −37.1 instead of $8.0 \cdot 10^{-17}$; for the whole 706-letter story it is about −1,618 (the product itself would be about $3 \cdot 10^{-703}$), and −1,618 fits into any computer. Nothing is lost: the logarithm is an increasing function, so a larger probability always has a larger logarithm, and comparing two models by log-likelihood gives the same verdict as comparing them by likelihood. That's the pink line in the widget above: it keeps calmly walking down long after both products have hit the floor.

One cosmetic step remains. Probabilities are at most 1, so their logarithms are zero or negative. Negative numbers are awkward to talk about, so we flip the sign and give the result a name. The surprise of an event with probability $p$ is

$$s = -\log p$$

It behaves exactly the way surprise should. An event we were sure of ($p = 1$) doesn't surprise us at all: zero. The less likely the event, the bigger the surprise, and something we considered impossible ($p \to 0$) is infinitely surprising. And the surprise of two events in a row is the sum of their surprises, because the logarithm turned the product into a sum. (Information theorists call the same quantity self-information.)

Bits and nats

Which logarithm? Any will do, since they differ only by a constant factor, but two are traditional, each with its own unit of surprise.

• With base 2, surprise is measured in bits. One bit is the surprise of a fair coin landing heads: $-\log_2 \tfrac12 = 1$. Three heads in a row, with probability $\tfrac18$, cost 3 bits.
• With the natural logarithm $\ln$ (base $e \approx 2.718$), the unit is the nat. PyTorch and practically all of machine learning use natural logarithms, so losses are almost always quoted in nats.

Converting is easy: $1\ \text{nat} = 1/\ln 2 \approx 1.443$ bits, and $1\ \text{bit} \approx 0.693$ nats. The widget below lets you feel the price of a surprise: drag the point along the curve and see how many coin tosses, all heads, would surprise you just as much.

A few landmarks worth remembering. Guessing one of 97 symbols completely at random costs $\log_2 97 \approx 6.6$ bits, or $\ln 97 \approx 4.575$ nats: that's the "guessing" mark on the meter. "x" after "e" has probability 0.87%, which is 6.8 bits, about as surprising as a random guess. And "u" after "q", at 98.8% in Sprout's smoothed table, costs just 0.017 bits.

The average surprise is the loss

Now we have everything. The sum of surprises grows with the length of the text, and texts have different lengths, so we divide by the number of letters. The average surprise per letter is the grade we were looking for:

$$L = \frac{1}{N} \sum_{t=1}^{N} -\ln p(x_t \mid x_{t-1})$$

In machine learning this number is called the loss, and all of training, in this course and in every large model, is about making it smaller. Since it compares the distribution of the real text with the distribution the model believes in, it also has a more formal name: cross-entropy. We'll get to why "entropy" at the end of the chapter.

For our bigram, measured on 4.9 million letters of text it had never seen (held out from training), the loss is 2.364 nats per letter, or 3.41 bits. Here is the same calculation in a few lines of Python, on one sentence:

import json, math import numpy as np try: from pyodide.http import open_url # in the browser data = json.load(open_url('/llm/data/bigram-counts.json')) except ImportError: # on your own computer data = json.load(open('bigram-counts.json')) ALPHABET = data['alphabet'] N = np.array(data['counts'], dtype=np.float64) P = (N + 1) / (N + 1).sum(1, keepdims=True) # Sprout's bigram, with +1 def surprises(text): ids = [0] + [ALPHABET.index(c) + 1 for c in text if c in ALPHABET] return [-math.log(P[a, b]) for a, b in zip(ids, ids[1:])] # -ln p(next | previous) s = surprises('Once upon a time, there was a dog named Spot.') loss = sum(s) / len(s) print(len(s), 'letters') print('probability of the whole text:', math.prod(math.exp(-x) for x in s)) print('average surprise (loss):', round(loss, 3), 'nats =', round(loss / math.log(2), 3), 'bits') print('perplexity:', round(math.exp(loss), 2)) print('the product for 400 such letters:', math.exp(-loss) ** 400)

The last line is our old enemy: 400 letters of average probability multiply to an exact zero. And this is how the course code computes the loss of the real table. These are the last two lines of bigram() in snapshots.py, which we left unexplained in the last chapter:

nll = -np.log(probs[ids[:-1], ids[1:]]).mean() print(f'bigram: {len(ids)} letters, loss {nll:.4f} nats/letter')

probs[ids[:-1], ids[1:]] picks, for every position, the probability of the letter that actually came next; -np.log turns each into a surprise; .mean() averages them. NLL stands for negative log-likelihood, yet another name for the same thing. On its own 41 million training letters the table scores 2.3650, and on unseen text 2.364: practically the same. A table of 9,409 numbers is far too small to memorise 41 million letters, so it cannot "cheat" on text it has seen. Bigger models can, and in chapter 5 that difference will matter a lot.

Loss in bits is also the size of a zip file

The loss in bits has a beautiful practical meaning. Given a model, a method called arithmetic coding (developed in the 1970s) can compress a text into almost exactly as many bits as the model's total surprise on it, and decompress it back using the same model. So a model with a loss of 3.41 bits per letter is a compressor that stores English in about 3.4 bits per letter instead of the 8 bits of a plain text file. Predicting well and compressing well are the same skill. That is why people say, only half jokingly, that a language model is a very clever zip program.

Perplexity: the effective number of choices

Nats are not very intuitive, so there is one more way to present the same number. Undo the logarithm, and $e^{L}$ is called perplexity. It has a lovely meaning. A model that guesses uniformly among $k$ options is surprised by $\ln k$ every time, so its perplexity is exactly $k$. Perplexity is the number of equally likely options the model is effectively choosing between at every step.

Random guessing among 97 symbols: perplexity 97. Our bigram: $e^{2.364} \approx 10.6$. Knowing just one previous letter shrinks the choice from 97 symbols to about ten and a half. That's a lot for 9,409 numbers.

A ladder of models

A number means something only in comparison. Here are three models that are easy to build, each knowing a bit more than the previous one:

• Uniform: knows nothing and gives every one of the 97 symbols $1/97$. Its loss is $\ln 97 \approx 4.575$ on any text whatsoever.
• Unigram: knows how common each letter is ("e" often, "z" rarely) but never looks back. This is our table collapsed into a single row.
• Bigram: our table, one letter of memory.

All three were measured on the same held-out text of 4.9 million letters, together with two models from later chapters:

model	loss, nats/letter	bits/letter	perplexity
uniform over 97 symbols	4.575	6.60	97
unigram (letter frequencies)	3.084	4.45	21.9
bigram (this model)	2.364	3.41	10.6
network, 3 letters of context (chapter 4)	1.479	2.13	4.4
network, 8 letters of context (chapter 5)	1.103	1.59	3.0

Every step down the ladder is a model that has understood a little more about English. Try your own text on the three models of this chapter at once, and bring in the big one too, the real Sprout. It reads text not letter by letter but in tokens, chunks of about four letters, so to put it on the same scale we add up its surprise over the whole text and divide by the number of letters. (On the held-out text there are 4.085 letters per token, so a loss per token of $L$ is about $L / 4.085$ per letter.)

Notice how the dark spots move. The uniform model is equally surprised by everything. The unigram is surprised by rare letters wherever they stand. The bigram forgives rare letters in their usual company ("u" after "q") but stumbles on the first letter of each word. A big model that remembers hundreds of tokens should, ideally, be surprised only by what nobody could predict: a name, the choice of a word, a turn of the plot. See how close Sprout gets.

On the same text, model A has a loss of 2.0 nats per letter and model B has 2.5. Which is better, and what does that mean in "effective choices"?

B: a bigger number means it has learned more A: it chooses as if among $e^{2.0} \approx 7.4$ options per letter, against $e^{2.5} \approx 12.2$ for B They are equal: 0.5 nats is within the noise

Loss is surprise, and a good model is surprised less. Half a nat per letter is a big difference: over a 1,000-letter text it adds up to 500 nats, which means B gives the real text a probability $e^{500}$ times smaller than A does.

How much surprise is unavoidable

Can the loss drop all the way to zero? Only if the text were completely predictable, and language is not. After "Once upon a" the word "time" is almost certain, but after "She picked up the" dozens of words fit. Some surprise is built into the text itself, and no model, however large, can get rid of it.

That built-in amount has a name: entropy. It is the average surprise of an ideal model, one that knows the true probabilities $p$ exactly:

$$H(p) = -\sum_i p_i \log p_i$$

A fair coin has an entropy of 1 bit. A fair six-sided die has $\log_2 6 \approx 2.58$ bits. A coin bent to land heads 90% of the time has just 0.47 bits: you are rarely surprised by it. A certain event has zero. Entropy measures how uncertain the thing itself is.

And now the most important twist. Suppose the world rolls a die with probabilities $p$, but the model believes in other probabilities $q$. Then the model's average surprise is

$$H(p, q) = -\sum_i p_i \log q_i \ \ge\ H(p),$$

and it equals $H(p)$ only when $q = p$. That is the cross-entropy, the very quantity our loss computes, with the real text playing the part of the world. The difference $H(p, q) - H(p)$ is the price of wrong beliefs. Play with it: set up the world's die, then the model's, and watch the numbers.

Our letter table holds 97 little dice, and their entropies differ a lot. After "q" the entropy is only 0.16 bits: there is nothing to guess. After a space it is 4.55 bits: a new word can start with almost anything. At the very beginning of a story it is 4.0 bits. The cell below computes this for any row you like.

def entropy(p): # in bits return -sum(x * math.log2(x) for x in p if x > 0) def cross_entropy(p, q): # the world is p, the model believes q return -sum(x * math.log2(y) for x, y in zip(p, q) if x > 0) print('coin:', entropy([0.5, 0.5]), ' die:', round(entropy([1/6] * 6), 3), ' bent coin:', round(entropy([0.9, 0.1]), 3)) world, model = [0.5, 0.25, 0.125, 0.125], [0.25, 0.25, 0.25, 0.25] print('H(p) =', entropy(world), ' H(p, q) =', cross_entropy(world, model), ' KL =', cross_entropy(world, model) - entropy(world)) for letter in ['q', ' ', 'e']: row = P[ALPHABET.index(letter) + 1] # the die after this letter print(repr(letter), round(entropy(row), 2), 'bits')

So what is the entropy of English itself, the floor under every possible model? Nobody knows exactly. In 1951 Claude Shannon estimated it by having people guess a text letter by letter, and landed somewhere between 0.6 and 1.3 bits per letter when the guesser sees a long stretch of text. Our bigram spends 3.41 bits. It's a long way down, and each of the coming chapters takes us a few steps further.

In PyTorch the whole formula is a single function, F.cross_entropy. It takes "logits" and the right answers. We'll meet logits and softmax in the next chapter; for now it's enough to know that the logits of our table are simply the logarithms of its probabilities, exactly what bigram() saved into the model file.

import json, torch import torch.nn.functional as F data = json.load(open('bigram-counts.json')) counts = torch.tensor(data['counts'], dtype=torch.float64) logits = torch.log((counts + 1) / (counts + 1).sum(1, keepdim=True)) # the bigram-char model text = 'Once upon a time, there was a dog named Spot.' ids = torch.tensor([0] + [data['alphabet'].index(c) + 1 for c in text]) print(F.cross_entropy(logits[ids[:-1]], ids[1:])) # the average surprise, in nats

2.3586: the same average surprise the runnable cell printed above (rounded there to 2.359), now computed by the function that will train every model from chapter 4 on.

A model gives probability exactly 0 to some letter, and then that letter appears in the text. What happens to the loss?

Nothing much: it's just one letter out of thousands The loss becomes zero The loss becomes infinite: the surprise −log 0 has no bound

One infinite term makes the whole average infinite. That's why Sprout's table adds one to every cell, and why real neural networks never output an exact zero: softmax, which we meet in the next chapter, always leaves every token a little probability.

Sprout right now

Sprout is the same letter table as in the last chapter, but now we can measure it: 2.364 nats of surprise per letter on text it has never seen, as if it chose each letter from ten and a half options. That's the number to beat. In the next chapter we throw the counting away, start from a table of random numbers and teach it by walking downhill on the loss, and you will watch it arrive at the very number counting gives on its training text, 2.365. Meanwhile, see how surprised Sprout is by your own sentence: