Information theory: entropy, cross-entropy and KL divergence

Surprise and entropy

How surprised should you be by an outcome with probability $p$? Shannon's answer is the information content $I(x)=-\log p(x)$: certain events carry no information, rare events carry a lot, and independent surprises add because probabilities multiply. In base 2 the unit is the bit; with natural logarithms it is the nat ($1\text{ nat}\approx1.443$ bits). The entropy of a distribution is its expected surprise,

with the convention $0\log0=0$. A fair coin has $H=1$ bit; a coin with $P(\text{heads})=0.9$ has $H=-(0.9\log_2 0.9+0.1\log_2 0.1)\approx0.469$ bits; a fair die has $\log_2 6\approx2.585$ bits. Entropy is maximized by the uniform distribution ($\log K$ for $K$ outcomes) and is zero for a certain outcome. Operationally, $H(p)$ is the minimum average number of bits needed to encode outcomes drawn from $p$ — the reason entropy and compression are the same subject.

Intuition. Entropy measures how many yes/no questions you need, on average, to pin down the outcome. A good language model asks few questions per token because it already knows a lot.

Joint and conditional entropy, mutual information

For two variables, the joint entropy $H(X,Y)=-\sum p(x,y)\log p(x,y)$ and the conditional entropy $H(Y\mid X)=H(X,Y)-H(X)$ is the surprise left in $Y$ once $X$ is known. Mutual information,

is how many bits knowing one variable saves you about the other; it is zero exactly when they are independent and, unlike correlation, captures nonlinear dependence. Decision trees split on it under the name information gain (3.8 Decision trees), and contrastive objectives such as InfoNCE are lower bounds on it (5.8 Self-supervised and contrastive learning).

Cross-entropy: coding with the wrong model

Suppose outcomes come from $p$ but you designed your code — or your model — around $q$. You pay on average

the cross-entropy, and $H(p,q)\ge H(p)$ with equality only when $q=p$. In machine learning $p$ is the data (for one labeled example it is the one-hot distribution on the true class $y$) and $q$ is the model's predicted distribution, so the per-example cross-entropy collapses to $-\log q(y)$: the negative log-probability the model gave the right answer. That is the loss of 4.3 Loss functions catalog.

KL divergence: the excess cost

The gap between coding with $q$ and coding optimally is the Kullback–Leibler divergence:

It is non-negative (Gibbs' inequality) and zero only when $p=q$; it is not symmetric and does not satisfy the triangle inequality, so it is a divergence, not a distance. The two directions mean different things. Minimizing $D_{\mathrm{KL}}(p\|q)$ over $q$ (the direction of maximum likelihood) is mass-covering: $q$ must put probability wherever $p$ does, or pay $\log(p/0)=\infty$. Minimizing $D_{\mathrm{KL}}(q\|p)$ is mode-seeking: $q$ may ignore parts of $p$ but must not put mass where $p$ is near zero — the direction used in variational inference (8.8 Generative models I: VAEs and GANs) and in the KL penalty of RLHF, which keeps the policy from drifting to text the reference model finds absurd (8.3 Alignment: RLHF, PPO, DPO, GRPO and Constitutional AI).

Math check (Gibbs' inequality). Using $\ln u\le u-1$: $-D_{\mathrm{KL}}(p\|q)=\sum_x p(x)\ln\frac{q(x)}{p(x)}\le\sum_x p(x)\Big(\frac{q(x)}{p(x)}-1\Big)=\sum_x q(x)-\sum_x p(x)=0$. ✓ Equality needs $q(x)/p(x)=1$ everywhere.

Cross-entropy minimization is maximum likelihood

Let the data come from $p_{\text{data}}$ and the model be $q_\theta$. The expected negative log-likelihood is the cross-entropy, and the cross-entropy splits as

The entropy of the data does not depend on $\theta$. Therefore minimizing cross-entropy, minimizing KL to the data distribution and maximizing likelihood (1.7 Probability II: Bayes, independence, MLE and MAP) are the same optimization. The irreducible floor $H(p_{\text{data}})$ is why a loss never reaches zero on genuinely uncertain data — and why the best possible language model still has nonzero loss.

Perplexity

Language models report perplexity, the exponentiated average negative log-likelihood per token:

A perplexity of 10 means the model is, on average, as uncertain as if it were choosing uniformly among 10 equally likely tokens — an effective branching factor. Halving perplexity is a huge improvement; a difference of 0.1 is small. Perplexity depends on the tokenizer, so only compare models that share one (6.1 Text to numbers: tokenization, 6.2 Classical NLP and n-gram language models).

Worked example

Let $p=(0.5,\,0.25,\,0.25)$ and $q=(\tfrac13,\tfrac13,\tfrac13)$, in bits.

• $H(p)=0.5\cdot1+0.25\cdot2+0.25\cdot2=1.5$ bits; $H(q)=\log_2 3=1.585$ bits.
• $H(p,q)=-\sum_x p(x)\log_2\tfrac13=\log_2 3=1.585$ bits, so $D_{\mathrm{KL}}(p\|q)=1.585-1.5=0.085$ bits.
• $D_{\mathrm{KL}}(q\|p)=\tfrac13\big[\log_2\tfrac{1/3}{0.5}+2\log_2\tfrac{1/3}{0.25}\big]=\tfrac13[-0.585+0.830]=0.082$ bits — close, but not equal: the asymmetry is real.
• Perplexity of a model that assigns $q$ to data distributed as $p$: $2^{1.585}=3$; the optimal model achieves $2^{1.5}\approx2.83$.

import numpy as np
p, q = np.array([.5, .25, .25]), np.ones(3) / 3
H  = lambda p: -(p * np.log2(p)).sum()
CE = lambda p, q: -(p * np.log2(q)).sum()
print(H(p), CE(p, q), CE(p, q) - H(p), CE(q, p) - H(q))   # 1.5 1.585 0.085 0.082

Where information theory appears in the path

Where this shows up later

• Loss functions as negative log-likelihoods — 4.3 Loss functions catalog; perplexity and n-gram models — 6.2 Classical NLP and n-gram language models; GPT's objective — 7.6 Decoder-only: GPT and autoregressive generation.
• KL in alignment and in variational autoencoders — 8.3 Alignment: RLHF, PPO, DPO, GRPO and Constitutional AI, 8.8 Generative models I: VAEs and GANs; contrastive objectives — 5.8 Self-supervised and contrastive learning; decoding temperature — 8.5 Decoding and sampling.
• Information gain in trees — 3.8 Decision trees; maximum-entropy view of the Gaussian — 1.6 Probability I: random variables and distributions.