Information Theory

Entropy, cross-entropy and KL divergence in learning.

Information Theory

This note covers how to measure uncertainty and the difference between probability distributions, and why these measures show up as loss functions in machine learning.

Basic quantities

Distribution – A distribution pp assigns a probability p(x)≥0p(x) \ge 0 to each outcome xx of a random variable XX, with ∑xp(x)=1\sum_x p(x) = 1. Logs are base 2 (bits) or base ee (nats); changing the base only rescales every quantity below.

Surprisal – The information carried by observing an outcome xx. Rare outcomes are more surprising.

I(x)=−log⁡p(x)I(x) = -\log p(x)

Entropy – The expected surprisal, H(p)H(p). It measures how uncertain XX is, or equivalently the average number of bits needed to encode it.

H(p)=−∑xp(x)log⁡p(x)H(p) = -\sum_x p(x)\log p(x)

0≤H≤log⁡K0 \le H \le \log K for KK outcomes. The maximum is reached by the uniform distribution, and a fair coin has 1 bit. Among continuous distributions with variance σ2\sigma^2, the Gaussian has the largest entropy, 12log⁡(2πeσ2)\tfrac12\log(2\pi e\sigma^2).

Joint and conditional entropy – H(X,Y)H(X,Y) is the entropy of the pair. H(X∣Y)H(X \mid Y) is the uncertainty about XX that remains once YY is known.

H(X∣Y)=H(X,Y)−H(Y)≤H(X)H(X \mid Y) = H(X,Y) - H(Y) \le H(X)

Comparing distributions

Cross-entropy – The average number of bits needed to encode samples from pp using a code designed for a model qq.

H(p,q)=−∑xp(x)log⁡q(x)H(p,q) = -\sum_x p(x)\log q(x)

Kullback–Leibler (KL) divergence – The extra bits paid for using qq instead of the true pp. It is asymmetric, and zero only when q=pq = p.

KL(p ∥ q)=∑xp(x)log⁡p(x)q(x)=H(p,q)−H(p)≥0\mathrm{KL}(p\,\Vert\,q) = \sum_x p(x)\log\frac{p(x)}{q(x)} = H(p,q) - H(p) \ge 0

KL≥0\mathrm{KL} \ge 0 follows from Jensen's inequality, which says E[f(X)]≥f(EX)\mathbb{E}[f(X)] \ge f(\mathbb{E}X) for any convex function ff.

Mutual information – How much knowing YY reduces uncertainty about XX. It is zero exactly when XX and YY are independent.

I(X;Y)=H(X)−H(X∣Y)=KL(p(x,y) ∥ p(x)p(y))I(X;Y) = H(X) - H(X \mid Y) = \mathrm{KL}\big(p(x,y)\,\Vert\,p(x)p(y)\big)

Data processing inequality – If ZZ is computed from YY alone, so that X→Y→ZX \to Y \to Z, then processing cannot create information about XX: I(X;Z)≤I(X;Y)I(X;Z) \le I(X;Y).

Other divergences – The ones that come up most often:

NameDefinitionNote
Total variation12∑x∣p(x)−q(x)∣\tfrac12\sum_x \lvert p(x) - q(x)\rvertPinsker's inequality: TV≤KL/2\mathrm{TV} \le \sqrt{\mathrm{KL}/2}
Jensen–Shannon12KL(p ∥ m)+12KL(q ∥ m)\tfrac12\mathrm{KL}(p\,\Vert\,m) + \tfrac12\mathrm{KL}(q\,\Vert\,m) with m=12(p+q)m = \tfrac12(p+q)symmetric, at most log⁡2\log 2; the original GAN objective
Wassersteinthe minimum cost of moving the mass of pp onto qqstays informative even when the supports don't overlap

Maximum likelihood = minimum cross-entropy – Fitting a model qθq_\theta by maximizing the average log-likelihood of the data is the same as minimizing cross-entropy against the empirical distribution p^\hat p of the data. Since H(p^)H(\hat p) is fixed, it is also the same as minimizing KL(p^ ∥ qθ)\mathrm{KL}(\hat p\,\Vert\,q_\theta).

arg⁡max⁡θ1n∑ilog⁡qθ(xi)=arg⁡min⁡θH(p^,qθ)\arg\max_\theta \tfrac1n\sum_i \log q_\theta(x_i) = \arg\min_\theta H(\hat p, q_\theta)

Classification loss – With a one-hot target eye_y (all mass on the true class yy), the cross-entropy reduces to −log⁡q(y)-\log q(y). Label smoothing replaces the target with (1−ε)ey+ε/K(1-\varepsilon)e_y + \varepsilon/K.

Perplexity – eHe^{H} when HH is the cross-entropy in nats per token. It can be read as the effective number of choices the model is hesitating between. Dividing the loss by ln⁡2\ln 2 converts it to bits, so a language model's loss is literally a compression rate.

Forward vs reverse KL – Forward KL, KL(p ∥ q)\mathrm{KL}(p\,\Vert\,q), is mass-covering: qq is penalized wherever it misses mass that pp has. That is the objective maximum likelihood optimizes. Reverse KL, KL(q ∥ p)\mathrm{KL}(q\,\Vert\,p), is mode-seeking: qq settles on one peak of pp. It appears in variational inference and in the KL penalty of reinforcement learning from human feedback (RLHF).

Evidence lower bound (ELBO) – For a latent-variable model p(x,z)p(x,z) with hidden variable zz and any approximation q(z)q(z) to the posterior, the ELBO is a tractable lower bound on log⁡p(x)\log p(x). It is tight when qq equals the true posterior p(z∣x)p(z \mid x).

log⁡p(x)≥Eq[log⁡p(x,z)]−Eq[log⁡q(z)]=log⁡p(x)−KL(q(z) ∥ p(z∣x))\log p(x) \ge \mathbb{E}_q[\log p(x,z)] - \mathbb{E}_q[\log q(z)] = \log p(x) - \mathrm{KL}\big(q(z)\,\Vert\,p(z \mid x)\big)

KL between Gaussians – For two one-dimensional normal distributions:

KL(N(μ1,σ12) ∥ N(μ2,σ22))=log⁡σ2σ1+σ12+(μ1−μ2)22σ22−12\mathrm{KL}\big(\mathcal{N}(\mu_1,\sigma_1^2)\,\Vert\,\mathcal{N}(\mu_2,\sigma_2^2)\big) = \log\frac{\sigma_2}{\sigma_1} + \frac{\sigma_1^2 + (\mu_1-\mu_2)^2}{2\sigma_2^2} - \frac12

In a variational autoencoder (VAE) with a standard normal prior, this becomes 12(μ2+σ2−log⁡σ2−1)\tfrac12(\mu^2 + \sigma^2 - \log\sigma^2 - 1) per latent dimension.

Fisher information – The local curvature of KL around a parameter value θ\theta. For a small change δ\delta in parameters, KL(pθ ∥ pθ+δ)≈12δ⊤I(θ)δ\mathrm{KL}(p_\theta\,\Vert\,p_{\theta+\delta}) \approx \tfrac12\delta^\top I(\theta)\delta. This is the geometry the natural gradient uses.

Coding

Source coding theorem – No lossless code can average fewer than H(p)H(p) bits per symbol, and Huffman coding gets within 1 bit of that. Coding with the wrong model qq costs KL(p ∥ q)\mathrm{KL}(p\,\Vert\,q) extra bits per symbol.