Information theory · Math for AI

Information theory measures surprise. It explains why cross-entropy is the loss for every language model, what perplexity means, and why prediction and compression are the same problem.

Why it exists

Claude Shannon built it in 1948 to answer an engineering question: how few bits are needed to send a message reliably? The same quantities turned out to measure how wrong a model’s predictions are. That is why a communications theory sits at the centre of modern AI.

Core ideas

1. Surprise: why the logarithm

An unlikely event carries more information than a likely one. Define the surprise of an outcome x as −log p(x). A certain event (p = 1) has zero surprise; a rare one has a lot.

Why a logarithm, from first principles? For independent events, probabilities multiply, but total surprise should add. The logarithm is the function that turns products into sums.

With log base 2 the unit is bits; with the natural log, nats. A fair coin flip is 1 bit. A one-in-1,024 event is 10 bits.

2. Entropy: average surprise

Entropy is the expected surprise of a distribution:

H(p) = -\sum_{x} p(x) \log p(x)

It is zero when the outcome is certain and largest when all K outcomes are equally likely, where it equals log K. A uniform choice among 50,000 tokens is about 15.6 bits.

Shannon’s source coding theorem gives entropy a concrete meaning. It is the minimum average number of bits needed to encode samples from p. No compression scheme can beat it on average.

3. Cross-entropy: the cost of a wrong model

Suppose the truth is p, but you encode using a model q. The average cost is the cross-entropy:

H(p, q) = -\sum_{x} p(x) \log q(x)

It is always at least H(p), and equals it only when q = p. The extra is the price of believing the wrong distribution.

4. KL divergence: the gap between two distributions

That extra price has its own name, the Kullback–Leibler divergence:

D_{\mathrm{KL}}(p \,\|\, q) = \sum_{x} p(x) \log \frac{p(x)}{q(x)} = H(p, q) - H(p) \;\ge\; 0

It is zero only when p = q. But it is not symmetric, so it is not a true distance: D(p‖q) and D(q‖p) usually differ.

The direction changes behaviour, and this matters in practice. Minimizing D(p‖q) over q forces q to cover everywhere p has mass, so q spreads out (mode-covering). Minimizing D(q‖p) punishes q for putting mass where p has little, so q locks onto one peak (mode-seeking).

5. Why cross-entropy is the loss: three pillars meet

Training minimizes the cross-entropy between the data distribution and the model. Split it with the identity above:

H(p_{\mathrm{data}}, q_\theta) = H(p_{\mathrm{data}}) + D_{\mathrm{KL}}(p_{\mathrm{data}} \,\|\, q_\theta)

The first term does not depend on the model. So minimizing cross-entropy means minimizing the KL gap to the data, which is the same as maximum likelihood from Pillar 4. Information theory, statistics and probability all give the same loss.

It also explains a floor. H(p_data) is the irreducible entropy of language itself, so loss can approach it but never go below. That is the constant term in neural scaling laws.

6. Perplexity: cross-entropy you can feel

Perplexity is the exponential of the average cross-entropy per token (in nats):

\mathrm{PPL} = \exp\!\Big(-\frac{1}{T}\sum_{t=1}^{T} \log q_\theta(x_t \mid x_{<t})\Big)

Read it as the number of equally likely options the model is torn between at each step. A perplexity of 10 means the model is as uncertain as a fair 10-sided die. A loss of 2.0 nats per token is a perplexity of about 7.4.

One caveat: perplexity depends on the tokenizer. Two models with different vocabularies cannot be compared directly. Bits per byte of raw text normalizes this away.

7. Conditional entropy and mutual information

Conditional entropy H(X | Y) is the uncertainty left in X once you know Y. Entropies obey a chain rule, just like probabilities: H(X, Y) = H(X) + H(Y | X).

Mutual information is the uncertainty about X that Y removes:

I(X; Y) = H(X) - H(X \mid Y)

It is symmetric, never negative, and zero exactly when X and Y are independent. Unlike correlation, it catches any kind of dependence, not only linear ones. Contrastive learning objectives such as InfoNCE are built to maximize a bound on it.

8. Prediction is compression

A model that assigns probability q to the next symbol can encode it in about −log₂ q bits, using arithmetic coding. So a language model’s loss is literally its compression rate on text.

That is a deep reason why next-token prediction works as a training goal. To compress text well, a model must capture whatever structure makes the text predictable: grammar, facts, reasoning patterns.

9. The maximum entropy principle

When you must choose a distribution, choose the one with the most entropy that still matches what you know. It assumes nothing you do not know.

This principle produces familiar answers. Knowing nothing gives the uniform distribution. Knowing a mean and variance gives the Gaussian. Constraints on expected scores give the softmax form.

In AI

Training loss: every classifier and language model minimizes cross-entropy.
Evaluation: perplexity and bits per byte measure how well a model predicts held-out text.
RLHF and preference tuning: a KL penalty keeps the tuned model close to a reference model, so it improves reward without drifting into nonsense.
Distillation: a small student model learns by minimizing KL to a large teacher’s full output distribution, not only its top answer.
VAEs: the training objective includes a KL term that keeps the latent space close to a simple prior.
Uncertainty: the entropy of a model’s output distribution is a cheap signal of how unsure it is.

Questions to ask

How many bits of surprise does this outcome represent?
Which direction is this KL divergence, and what behaviour does that direction encourage?
Are these perplexities comparable: same tokenizer, same test data?
What is the irreducible entropy of this task, and how close is the loss to it?
Is low output entropy here genuine knowledge, or overconfidence?
Does this objective measure dependence in general, or only correlation?

Fluency check

Compute the entropy of a fair coin (1 bit) and a 90/10 coin (about 0.47 bits).
Prove H(p, q) = H(p) + D_KL(p‖q) from the definitions.
Compute KL in both directions for two small distributions and see they differ.
Convert a loss of 2.0 nats per token to perplexity, then to bits per token.
Estimate a text file’s entropy with a character-frequency model in Python and compare with gzip’s compressed size.