Measuring surprise

Our table can already write something like “Frthendd, aced. tre sedsck”. Now we need to tell whether the next version is any better. An impression such as “looks like English” will not do for training: the program needs a score it can compute after each step. This chapter develops that score and explains what it measures.

Take a text the model did not use during training and reveal it one character at a time. Before each reveal, ask what probability the model assigned to the actual continuation. The higher those probabilities tend to be, the better it predicts this text. We will say it is less surprised. That is a mathematical metaphor: we are measuring prediction quality, not feelings or the factual reliability of generated answers.

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?

Computer numbers have a limited range. The smallest positive float64 value is about $5 \cdot 10^{-324}$; a sufficiently small result rounds to zero. In this example, that happens at character 324. Float32 has a narrower range, and here the product reaches zero at character 45. Modern models use several numerical formats, but the problem remains: products that have rounded to zero can no longer distinguish the probabilities of long texts.

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})$$

This is our loss function: the quantity training will try to reduce. Here it is the average negative logarithm of the probability assigned to observed characters. It is also called empirical cross-entropy, because it measures how the model’s predictions compare with the data. Other tasks can use other loss functions. We will examine the connection to 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:]] selects the probability of the actual next character at each position; -np.log turns it into surprise, and .mean() takes the average. The sum of these surprises is the NLL, or negative log-likelihood; our loss is the NLL divided by the number of predictions. The table scores 2.3650 nats per character on training text and 2.364 on held-out text. Their closeness tells us that it predicts these two sets about equally well. It does not prove that small models cannot overfit: the amount and similarity of the data matter too.

What loss tells us about compression

Loss in bits has a practical interpretation. An arithmetic coder can use the model’s probabilities to encode a text in a length close to its total surprise. At an average loss of 3.41 bits per character, a long text from the same source can be encoded at roughly that rate rather than the 8 bits of an ASCII character. This estimates the encoded text, though, not an entire archive: the receiver also needs the model. For short texts, storing that model can cost more than the compression saves.

Perplexity: the effective number of choices

Nats are hard to relate to everyday quantities, so we often report $e^L$, called perplexity. A model that always guesses uniformly among $k$ options has a loss of $\ln k$ and a perplexity of exactly $k$. For non-uniform predictions, perplexity is the equivalent number of equally likely options with the same average loss. It is not a literal count of candidates left in the vocabulary: probability may still be spread across every token.

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 loss reach zero? A model can approach zero on a finite set it has memorised, but new text still contains uncertainty: after “She picked up the”, dozens of continuations fit. The lower bound on expected loss depends on the source distribution and the context available. To understand that bound, we will first look at a simpler source: a coin or a die.

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')

There is no single known constant for the entropy of English that applies to every experiment. Estimates depend on the texts, alphabet and amount of context. In his 1951 paper, Claude Shannon studied people guessing letters from preceding text and estimated roughly 0.6–1.3 bits per letter for literary English. That is a useful historical reference, but not a direct benchmark for our 3.41 bits: our texts and character set differ. To compare our models fairly, we will keep using the same held-out corpus.

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. Smoothing protects our table against zero probabilities. With finite logits, softmax also gives strictly positive probabilities in exact arithmetic, but a computer can round a tiny value down to zero. Library cross-entropy functions therefore work from logits using a numerically stable calculation, rather than first computing tiny probabilities and then taking their logarithms.

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: