Skip to content
LearnMLByDoing
Free

1.5 Entropy, cross-entropy and KL divergence

30 minProintermediateMacKayMMLCompendiumDL

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 xx with probability p(x)p(x) is

h(x)=−log⁡2p(x),H(p)=Ex∼p[h(x)]=−∑xp(x)log⁡2p(x)h(x)=\tok{surprise}{-\log_2 p(x)},\qquad \tok{entropy}{H(p)}=\mathbb{E}_{x\sim p}\big[h(x)\big]=-\sum_x \tok{prob}{p(x)}\log_2 \tok{prob}{p(x)}
Surprise of one outcome, and its average: the entropy. By convention 0 log 0 = 0, the limit of t log t as t → 0.

Why a logarithm. For independent events the probabilities multiply, p(x,y)=p(x) p(y)p(x,y)=p(x)\,p(y), and we want the information to add: h(x,y)=h(x)+h(y)h(x,y)=h(x)+h(y). A decreasing, continuous function that turns products into sums is −log⁡-\log up to a constant factor, and that factor is the choice of base. Base 2 measures bits; the natural log measures nats; 1 nat=1/ln⁡2=1.4431\text{ nat}=1/\ln 2=1.443 bits. A fair coin flip carries exactly 1 bit; a fair 16-sided die carries log⁡216=4\log_2 16=4 bits.

Start with a coin. A fair coin has p(heads)=0.5p(\text{heads})=0.5: each outcome costs −log⁡20.5=1-\log_2 0.5=1 bit, so the average is H=1H=1 bit. Now load the coin so heads comes up 90% of the time. Heads is no news, −log⁡20.9=0.15-\log_2 0.9=0.15 bits; tails is a surprise, −log⁡20.1=3.32-\log_2 0.1=3.32 bits, but it happens only one time in ten. The average is H=0.9×0.15+0.1×3.32=0.47H=0.9\times0.15+0.1\times3.32=0.47 bits: a loaded coin tells you less per flip than a fair one. Drag pp below: the curve peaks at p=0.5p=0.5 and falls to 0 at both ends, where the outcome is certain.

Loading figure
The lower panel is the whole definition of entropy in one picture: each bar's width is how often the outcome happens, its height is how surprising it is, and the shaded area is HH. Perplexity 2H2^{H} is the number of equally likely outcomes with the same uncertainty: 1.381.38 for this coin, 22 for a fair one.

The viewport scales this up to 16 outcomes. It builds pp from 16 fixed scores zz with a softmax, which turns any list of scores into probabilities: exponentiate each score, then divide by the total, so every p(x)p(x) is positive and they add up to 1. Here p=softmax⁡(s z)p=\operatorname{softmax}(s\,z) with sharpness s=1s=1; the outcome numbers 1 to 16 are printed under the bars. Emerald bars in front are p(x)p(x); behind each one is a stack of unit-bit blocks as tall as its surprise. Outcome 3 has p=0.356p=0.356 and costs 1.491.49 bits; outcome 12 has p=0.0072p=0.0072 and costs 7.127.12 bits. Each stack's depth grows with p(x)p(x), because the entropy weights every surprise by how often it occurs. The emerald plane sits at H(p)=3.160H(p)=3.160 bits =2.190=2.190 nats.

Watch the sampler: outcomes drawn from pp 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 s=0s=0 every score is multiplied by zero, pp is uniform, and every stack is exactly 4 blocks tall: H=log⁡216=4H=\log_2 16=4 bits, the most any distribution on 16 outcomes can have. Drag the sharpness up and pp concentrates on outcome 3: at s=4s=4 it has p=0.970p=0.970, the likely outcome costs 0.0440.044 bits, and H(p)H(p) falls to 0.2410.241 bits even though the rarest outcome now costs 22.622.6 bits (rose caps mark stacks truncated at 10 bits). Rare outcomes are very surprising, but they almost never happen.

Push the sharpness to s=4s=4.

Optional: maximising H(p) on the simplex (Lagrange multipliers, lesson 1.4)1/4
  1. 1
    max⁡p  −∑k=1Kpkln⁡pks.t.∑k=1Kpk=1\max_{p}\;-\sum_{k=1}^{K}p_k\ln p_k\quad\text{s.t.}\quad \sum_{k=1}^{K}p_k=1

    Use nats for the algebra; the base only rescales H. The positivity constraints turn out inactive.

Entropy therefore ranges from 00 (a certain outcome) to log⁡2K\log_2 K (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 ℓ(x)\ell(x) bits so that no codeword starts another, and such a code exists exactly when the lengths satisfy the Kraft inequality ∑x2−ℓ(x)≤1\sum_x 2^{-\ell(x)}\le1.

H(p)  ≤  Ep[ℓ(x)]  <  H(p)+1,ℓ(x)=⌈−log⁡2p(x)⌉\tok{entropy}{H(p)}\;\le\;\mathbb{E}_{p}\big[\tok{code_length}{\ell(x)}\big]\;<\;\tok{entropy}{H(p)}+1,\qquad \tok{code_length}{\ell(x)}=\big\lceil\tok{surprise}{-\log_2 p(x)}\big\rceil
Shannon's source coding bound for symbol codes. Rounding each surprise up to whole bits satisfies Kraft and loses less than one bit per symbol.

A four-letter example. Let A, B, C, D have probabilities 12,14,18,18\tfrac12,\tfrac14,\tfrac18,\tfrac18. 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 12⋅1+14⋅2+18⋅3+18⋅3=1.75\tfrac12\cdot1+\tfrac14\cdot2+\tfrac18\cdot3+\tfrac18\cdot3=1.75 bits, exactly HH, and the Kraft sum is 12+14+18+18=1\tfrac12+\tfrac14+\tfrac18+\tfrac18=1: no code space is wasted. Drag a bar away from a power of 12\tfrac12 and the lengths have to round up, so E[ℓ]\mathbb{E}[\ell] pulls ahead of HH.

Loading figure
Each codeword is the surprise rounded up to whole bits; the codes are assigned shortest first, so they always form a prefix code (the Kraft sum stays at most 1).

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 E[ℓ]=3.636\mathbb{E}[\ell]=3.636 bits against H=3.160H=3.160, inside the bound, and the Kraft sum is 0.7300.730: the rounding leaves 27% of the code space unused. Each strip is the stack behind it rounded up to whole blocks. Hover ℓ(x)\tok{code_length}{\ell(x)} to read these numbers live while you drag the sharpness.

Flatten pp to uniform: sharpness s=0s=0.

Huffman coding finds the optimal integer lengths and closes part of the gap; coding blocks of nn symbols at once spreads the rounding loss over nn symbols, so the bits per symbol approach HH, which is Shannon's source coding theorem. Arithmetic coding, used in modern compressors, gets within a fraction of a bit of −log⁡2p-\log_2 p 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.

Compiling scene

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