1.5 Entropy, cross-entropy and KL divergence
Entropy is the average surprise of a distribution, cross-entropy is the average surprise when you predict with the wrong model, and the gap between them, the KL divergence, is what classifiers, language models and variational autoencoders are trained to shrink.
01Surprise and entropy
Information theory measures how much you learn from an outcome. A likely outcome tells you little; a rare one tells you a lot. The surprise (information content) of an outcome with probability is
Why a logarithm. For independent events the probabilities multiply, , and we want the information to add: . A decreasing, continuous function that turns products into sums is up to a constant factor, and that factor is the choice of base. Base 2 measures bits; the natural log measures nats; bits. A fair coin flip carries exactly 1 bit; a fair 16-sided die carries bits.
Start with a coin. A fair coin has : each outcome costs bit, so the average is bit. Now load the coin so heads comes up 90% of the time. Heads is no news, bits; tails is a surprise, bits, but it happens only one time in ten. The average is bits: a loaded coin tells you less per flip than a fair one. Drag below: the curve peaks at and falls to 0 at both ends, where the outcome is certain.
The viewport scales this up to 16 outcomes. It builds from 16 fixed scores with a softmax, which turns any list of scores into probabilities: exponentiate each score, then divide by the total, so every is positive and they add up to 1. Here with sharpness ; the outcome numbers 1 to 16 are printed under the bars. Emerald bars in front are ; behind each one is a stack of unit-bit blocks as tall as its surprise. Outcome 3 has and costs bits; outcome 12 has and costs bits. Each stack's depth grows with , because the entropy weights every surprise by how often it occurs. The emerald plane sits at bits nats.
Watch the sampler: outcomes drawn from flash their bar, and the cyan line across the stacks is the running mean of the surprises seen so far. The side chart plots that mean against the number of draws on a log axis; by the law of large numbers it settles onto the plane. Entropy is an expectation, so it can be estimated from samples like any other mean.
Information Theory, Inference and Learning Algorithms, David J. C. MacKay, Ch. 2.4 and 4.1
Deep Learning, Goodfellow, Bengio & Courville, Ch. 3.13
02The uniform distribution has maximum entropy
With every score is multiplied by zero, is uniform, and every stack is exactly 4 blocks tall: bits, the most any distribution on 16 outcomes can have. Drag the sharpness up and concentrates on outcome 3: at it has , the likely outcome costs bits, and falls to bits even though the rarest outcome now costs bits (rose caps mark stacks truncated at 10 bits). Rare outcomes are very surprising, but they almost never happen.
Push the sharpness to .
- 1
Use nats for the algebra; the base only rescales H. The positivity constraints turn out inactive.
Entropy therefore ranges from (a certain outcome) to (no information about which outcome comes next). Adding constraints changes the answer: fixing the mean on the integers gives a geometric distribution, and fixing the mean and variance on the real line gives the Gaussian of lesson 1.3. Maximum-entropy reasoning picks the least committal distribution consistent with what you know.
Information Theory, Inference and Learning Algorithms, David J. C. MacKay, Ch. 2.4, Exercise 2.25
Mathematics for Machine Learning, Deisenroth, Faisal & Ong, Ch. 7.2
03Entropy as the length of the best code
Entropy has an operational meaning: it is the fewest bits per symbol that any lossless code can average. A prefix code assigns each outcome a codeword of bits so that no codeword starts another, and such a code exists exactly when the lengths satisfy the Kraft inequality .
A four-letter example. Let A, B, C, D have probabilities . Their surprises are 1, 2, 3 and 3 bits, whole numbers, so the codewords can be exactly that long: A = 0, B = 10, C = 110, D = 111. No codeword is the start of another, so a stream such as 0110100 decodes uniquely as A C B A. The average length is bits, exactly , and the Kraft sum is : no code space is wasted. Drag a bar away from a power of and the lengths have to round up, so pulls ahead of .
The cyan strips on the floor are those codewords, one cell per bit, bright for 1 and dim for 0. Outcome 3 gets the two-bit codeword 00; outcome 12 gets eight bits. The average length is bits against , inside the bound, and the Kraft sum is : the rounding leaves 27% of the code space unused. Each strip is the stack behind it rounded up to whole blocks. Hover to read these numbers live while you drag the sharpness.
Flatten to uniform: sharpness .
Huffman coding finds the optimal integer lengths and closes part of the gap; coding blocks of symbols at once spreads the rounding loss over symbols, so the bits per symbol approach , which is Shannon's source coding theorem. Arithmetic coding, used in modern compressors, gets within a fraction of a bit of for the whole message.
Information Theory, Inference and Learning Algorithms, David J. C. MacKay, Ch. 4.4 and 5.1 to 5.5
The rest of this lesson is in Pro
- 04Cross-entropy and maximum likelihood
- 05KL divergence: never negative, not symmetric
- 06Forward vs reverse KL: covering or seeking modes
- 07Mutual information and perplexity
- Python challenge: Entropy, KL and a stable softmax cross-entropy
- Knowledge check, 4 questions
Pro opens all 45 lessons, every graded Python challenge and the full 3D labs.
The Python challenge and knowledge check for this lesson are part of Pro.
Questions learners ask
- What is the difference between cross-entropy and KL divergence?
- Cross-entropy H(p, q) is the average number of bits needed to encode data from p using a code built for q. KL divergence is the extra part, H(p, q) minus H(p). When p is the fixed data distribution, H(p) does not depend on the model, so minimising cross-entropy and minimising KL give the same model and the same gradients; frameworks compute cross-entropy because it is cheaper and does not need H(p).
- Why is cross-entropy used for classification instead of mean squared error?
- Cross-entropy is the negative log-likelihood of a categorical model, so minimising it is maximum likelihood. Combined with softmax its gradient with respect to the logits is the prediction minus the target, which stays large when the model is confidently wrong. Mean squared error on probabilities multiplies that signal by the softmax derivative, which vanishes when the output saturates, so learning stalls exactly when the model is most wrong.
- Is KL divergence a distance metric?
- No. KL divergence is never negative and is zero only when the two distributions are equal, but it is not symmetric and does not satisfy the triangle inequality, and it is infinite when the second distribution gives zero probability to an outcome the first one allows. Symmetric alternatives include the Jensen-Shannon divergence, whose square root is a metric, and the population stability index used in drift monitoring, which adds the two KL directions.
Sources
- Information Theory, Inference and Learning Algorithms, David J. C. MacKay
- Mathematics for Machine Learning, Deisenroth, Faisal & Ong
- Maths, CS & AI Compendium, Henry Ndubuaku
- Deep Learning, Goodfellow, Bengio & Courville