Entropy, cross-entropy and chapter summary

Suppose you must radio the winner of a horse race to a bookie, using as few bits as possible. With 8 equally likely horses there is nothing to exploit: you label them 000 to 111 and spend 3 bits per race. Now suppose the odds are skewed: one horse wins half the time, the next a quarter, then an eighth, a sixteenth, and the last four 1/64 each. Give the favorite the one-bit code 0, the second 10, and so on down to six-bit codes for the long shots. Averaged over many races you now spend exactly 2 bits per race.

The average length is 1/2(1) + 1/4(2) + 1/8(3) + 1/16(4) + 4/64(6) = 2. No code that can be decoded without ambiguity does better, and that floor has a name. The Entropy of a random variable is the average number of bits the best possible code needs per outcome:

Read the formula in two pieces. The quantity -log2 p(x) is the surprise of outcome x: a sure thing (p = 1) has surprise 0, a coin flip has surprise 1 bit, and a 1/64 long shot has surprise 6 bits, exactly its codeword length above. Entropy is then the probability-weighted average of the surprise. With base 2 the unit is bits; with the natural log the same quantity comes out in nats.

Now apply this to the 3-color language from the perplexity part, where the only words are red, blue and green. If all three are equally likely, every word carries log2 3 = 1.585 bits. If red has probability 0.8, red becomes cheap (0.322 bits) while blue and green become expensive (3.322 bits each), but because red is so common the average drops.

The last column is the bridge to the rest of the part. 2^H is the number of equally likely choices that would carry the same uncertainty: a 0.9/0.1 coin is as unpredictable as a fair die with 1.38 faces. That is exactly the weighted branching factor reading of Perplexity. Shannon used the Shannon game of guessing the next letter to estimate printed English at about 2.3 bits per letter with 8 letters of context, falling to something of the order of 1 bit per letter with about 100 letters of context. More context lowers entropy, which is the whole reason to condition on history.

In real life we never know the true distribution p of a language. We only have a model m, and we can only observe how well m codes the data that p produces. Keep the color source fixed at p = (0.8, 0.1, 0.1) and score it with several models. Coding each word with lengths -log2 m(x) but drawing words from p gives an average cost per word of

The pattern in the table is the content of slide 103. Every wrong model pays extra bits, including the overconfident one that gives red even more than its true share. The minimum, 0.922 bits, is reached only when m = p, and it equals the true Entropy. In general the Cross-entropy is an upper bound on the entropy:

The gap is the Kullback-Leibler divergence, or relative entropy: the extra bits you pay for coding with the wrong codebook. Gibbs' inequality guarantees it is never negative and is zero only when the two distributions agree. That is why a lower cross-entropy means a better model, and also why no model can push its cross-entropy below the true entropy of the source.

Reverse the roles and the punishment becomes clear. Let the test data be uniform over the three colors and score it with the model (0.8, 0.1, 0.1). Two thirds of the words are ones the model thinks are rare, each costing 3.322 bits, so H = 2.32 bits and the perplexity is 5, worse than the honest uniform model at 3. A model that is confidently wrong is punished hard, and a model that gives an observed word probability 0 pays infinitely many bits, which is the zero problem seen from the information side.

From a distribution to one long test sequence

The sum over x needs p, which we do not have. The practical estimate, SLP3 eq. 3.42, scores one long test sequence W of N words and averages the Log probability:

The Shannon-McMillan-Breiman theorem says that for a stationary, ergodic source this average converges to the cross-entropy as N grows, so a long enough sample stands in for the sum over all sequences. Natural language is neither perfectly stationary nor perfectly ergodic, which is one reason the number is an estimate, but it is the number every paper reports. Exponentiate it and you get Perplexity:

Bits, nats, and real systems

Neural language models train on the average negative log-likelihood per token in nats, and report PPL = exp(loss). Hugging Face describes this as the exponentiation of the cross-entropy between the data and the model's predictions. A test loss of 3.0 nats per token is 3.0 / ln 2 = 4.33 bits, and both e^3 and 2^4.33 give a perplexity of about 20.1. The unit changes the cross-entropy number but never the perplexity. What does change it is the vocabulary: Hugging Face notes that tokenization affects perplexity, and SLP3 says perplexities are comparable only between models with identical vocabularies. A subword model and a word model are coding different symbols, so their per-symbol costs cannot be compared directly.

The bound also gives research a tool. Brown, Della Pietra, Della Pietra, Lai and Mercer trained a word trigram model on 583 million words and measured its cross-entropy on the Brown Corpus (about 5.96 million characters). The result, 1.75 bits per character, is an upper bound on the entropy of English precisely because H(p) <= H(p, m): whatever the true entropy is, it cannot be above what a real model already achieves.

Perplexity remains an Intrinsic evaluation measure: it tells you how well a model codes text, and gains in perplexity usually, but not always, carry over to downstream tasks.

Follow one sentence, "I want Chinese food", through everything this chapter built. A Language model must give it a probability. The Chain rule of probability writes that probability exactly as a product of next-word probabilities, each conditioned on the whole history, which no corpus can estimate. The Markov assumption cuts the history to a fixed window, so P(food | I want Chinese) becomes P(food | Chinese). Maximum likelihood estimation fills in those numbers by counting and normalizing in a training corpus. Then Sparsity strikes: some perfectly good bigram in a test sentence never appeared in training, its count is 0, and the whole sentence gets probability 0.

Smoothing repairs the zero. Add-k smoothing moves a fixed amount of mass to every event, Linear interpolation mixes trigram, bigram and unigram estimates, and Backoff drops to a shorter context only when the longer one has no evidence. Backing off to raw unigram frequency exposes the next failure: "Kong" is frequent, but almost only after "Hong", so it should not be a strong guess after an unfamiliar context, while "glasses" follows many different words. Kneser-Ney smoothing replaces the unigram with a Continuation probability that counts how many contexts a word completes. A single discount still fits poorly, because counts of 1, 2 and 3 or more need different amounts removed, so Modified Kneser-Ney uses three discounts, D1, D2 and D3+.

Every step is judged the same way. Tune choices such as k or the interpolation weights on a Development set, then report Perplexity once on the Test set, which, as the previous concept showed, is 2 to the per-word cross-entropy. It is the standard Intrinsic evaluation metric, and lower is better because it means fewer bits of surprise per word. Sampling from an LM from the model shows what it learned in a way numbers cannot, including Overfitting: a 4-gram model trained on Shakespeare mostly reproduces Shakespeare.

The lecture follows Jurafsky and Martin's Speech and Language Processing, third edition, chapter 3, and slide 105 credits the manuscript dated January 6, 2026. That citation was correct when the slides were made, but SLP3 is a living draft published chapter by chapter on the authors' site, and the copy at the same address is now dated August 19, 2026.

For deeper reading on this part, go to the sources themselves: Shannon's 1948 paper defines entropy and the coding theorem behind it, his 1951 paper runs the guessing game on printed English, and Brown et al. (1992) shows how a language model becomes an upper bound on the entropy of a language. MacKay's free textbook covers relative entropy and Gibbs' inequality in chapter 2.