M7.5 · LESSON 5 OF 6

Cross-entropy and KL

Connect likelihood, estimation and uncertainty to entropy, cross-entropy, KL divergence and perplexity.

THE IDEA

Coding with the wrong distribution

Entropy measures the best average code length (or surprise) if you know the true distribution p. Now suppose outcomes really come from p, but your model q believes something else. You pay surprise according to q, while outcomes arrive according to p: H(p, q) = −Σ p·log q, the cross-entropy. It is never below the entropy H(p). The extra cost is the KL divergence:

The identity

H(p, q) = H(p) + KL(p || q)
KL(p || q) = sum p * log(p / q)  >= 0,   and = 0 exactly when q = p

Example: truth p = [0.5, 0.5], model q = [0.25, 0.75]. In nats: H(p) = 0.6931, H(p, q) = 0.837, KL = 0.1438. The model costs an extra 0.144 nats per outcome.

Green: the truth p. Orange: your model q.

model weight A5model weight B5model weight C5model weight D5

entropy H(p) = 1.75 bits

cross-entropy H(p, q) = 2 bits

KL(p || q) = 0.25 bits

H(p) + KL(p || q) = 2

KL(q || p) = 0.25 bits

True distribution p is fixed (green, entropy 1.75 bits). Reshape the model q (orange) and watch cross-entropy never drop below 1.75, and equal it only when q matches p.

Predict first. A model q = uniform (0.25 each) is scored against the true distribution 1/2, 1/4, 1/8, 1/8. What is the cross-entropy in bits?

KL is not symmetric, and zeros are dangerous

KL(p || q) and KL(q || p) are different quantities. They ask different questions: who is the truth, and who is the model. Try the model with weights 1, 20, 20, 20 above: KL(p || q) = 2.02 bits but KL(q || p) = 0.96 bits. So KL is not a distance. Also, if q gives probability 0 to an outcome that p can produce, the cross-entropy and KL are infinite: a model that calls something impossible is punished without limit when it happens.

The training loss for classification

In classification the true distribution is the label: all probability on the correct class (a one-hot vector). Then cross-entropy collapses to −log q(correct class), the log-loss. The entropy of a one-hot label is 0, so the loss is the KL divergence from the label to the model. Minimising it pushes probability on the right class towards 1.

probability given to the true class, percent0.7

label (one-hot) p = [0, 1, 0], model q has q₂ = 0.7

loss = -ln(0.7) = 0.357 nats

= 0.515 bits

The loss for one example as a function of the probability the model gave to the correct class. Confident and right is cheap, confident and wrong is expensive.

Chapter context

Statistics estimates properties of a population from observations. Information measures describe how surprising those observations are under a probability model. Keep the true or empirical distribution distinct from the model used to describe it.

TRY IT YOURSELF

Part 1. Tune it by hand

The truth is fixed at 1/2, 1/4, 1/8, 1/8. You design the model by setting weights; they are normalised. Tasks tick from the computed cross-entropy and KL.

Green: the truth p. Orange: your model q.

model weight A5model weight B5model weight C5model weight D5

entropy H(p) = 1.75 bits

cross-entropy H(p, q) = 2 bits

KL(p || q) = 0.25 bits

H(p) + KL(p || q) = 2

KL(q || p) = 0.25 bits

To do: Adjust the model so the cross-entropy is at most 1.80 bits (the true distribution is fixed at 1/2, 1/4, 1/8, 1/8)
To do: Make the model match the truth exactly, so the KL divergence is 0 and cross-entropy equals the entropy
To do: Give an outcome that really happens a model probability of exactly 0 and watch the loss become infinite
To do: Find a model where KL(p||q) and KL(q||p) are both finite but differ by at least 0.5 bits

Part 2. Do it in code

Write cross_entropy(p, q, base=2) and kl(p, q, base=2) for two lists over the same outcomes. p is the true distribution, q the model.
Terms where p = 0 contribute 0 whatever q is. If q = 0 where p > 0, the answer is float("inf").
Both must raise ValueError for different lengths or for an input that is not a distribution. kl must equal cross_entropy minus the entropy of p.

import math

def entropy(p, base=2):
    return -sum(x * math.log(x, base) for x in p if x > 0)

def cross_entropy(p, q, base=2):
    # -sum p_i log q_i ; inf if q_i = 0 where p_i > 0 ; validate inputs
    pass

def kl(p, q, base=2):
    # sum p_i log(p_i / q_i) ; same rules as above
    pass

print(cross_entropy([0.5, 0.5], [0.25, 0.75]))

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Is KL(p||q) necessarily equal to KL(q||p)?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

H(p)=-\sum_i p_i\log p_i,\quad H(p,q)=-\sum_i p_i\log q_i.

D_{KL}(p\Vert q)=H(p,q)-H(p),\quad \operatorname{PPL}=e^{H(p,q)}.

These expressions use natural logarithms. If q assigns zero probability where p is positive, cross-entropy and KL are infinite.

For n Bernoulli observations with s successes, the maximum-likelihood probability estimate is s/n. For a sample with mean x-bar, the variance estimate dividing squared deviations by n is a different quantity from the usual unbiased sample-variance estimator dividing by n-1. State which one is being used.

Worked example

Use p=[0.5,0.5] and q=[0.25,0.75]. Source entropy is ln 2≈0.693147 nats. Cross-entropy is −0.5ln(0.25)−0.5ln(0.75)≈0.836988. KL≈0.143841 nats. Perplexity is exp(0.836988)≈2.309401, larger than the source's effective uncertainty of 2.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import log, exp, isclose
p, q = [.5,.5], [.25,.75]
h = -sum(a*log(a) for a in p)
ce = -sum(a*log(b) for a,b in zip(p,q))
assert isclose(h, 0.6931471805599453)
assert isclose(ce, 0.8369882167858358)
assert isclose(ce-h, 0.1438410362258905)
assert isclose(exp(ce), 2.309401076758503)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Likelihood is not the posterior probability of a model. Lower perplexity across different tokenizers is not a clean model comparison. Bias is not removed merely by computing more decimal places.