Entropy and KL divergence: information in bits

"It's sunny in the desert" tells you almost nothing; "it's snowing in the desert" is news. Information is surprise: the less likely an outcome, the more you learn when it happens.

In 1948 Claude Shannon turned that into a number, measured in bits. It sets the limit on how far any file can be compressed, and its cousin, cross-entropy, is the loss function that trains almost every classifier and language model.

surprise

$\log_2(1/p)$ bits for an outcome with probability $p$: 1 bit for a fair coin flip, 3 bits for a 1-in-8 event.

entropy H(P)

The average surprise of a distribution $P$: $\sum_x p(x)\log_2\frac{1}{p(x)}$.

cross-entropy H(P, Q)

The average surprise when outcomes follow $P$ but you expected $Q$.

KL divergence

$H(P, Q) - H(P)$: the extra bits you pay for believing $Q$. Never negative.

Sun (1/2) is worth 1 bit, cloud (1/4) 2 bits, rain and snow (1/8) 3 bits each. Weighted by how often each happens, the average is $0.5 \cdot 1 + 0.25 \cdot 2 + 0.125 \cdot 3 + 0.125 \cdot 3 = 1.75$ bits. The code 0, 10, 110, 111 achieves exactly that: short codes for common outcomes.

A forecaster who thinks all four are equally likely ($Q$ uniform) uses 2 bits each, so they pay $2 - 1.75 = 0.25$ extra bits per day. That gap is the KL divergence.

Drag the tops of the bars. The other bars rescale so each distribution still adds up to 1.

• Make $P$ uniform: entropy reaches its maximum, $\log_2 n$.
• Make one outcome almost certain: entropy drops towards 0.
• Pull one of $Q$'s bars down to zero while $P$'s stays up: KL shoots to infinity.

• Surprise is $\log_2(1/p)$ bits; entropy is the average surprise, at most $\log_2 n$ for $n$ outcomes.
• Cross-entropy is the average surprise under a model; KL is its excess over the entropy, never negative.
• A model that rules out something that can happen pays infinite cross-entropy.
• Machine learning minimises cross-entropy, which is the same as minimising KL from the data.