Information Theory
Entropy, cross-entropy and KL divergence in learning.
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 assigns a probability to each outcome of a random variable , with . Logs are base 2 (bits) or base (nats); changing the base only rescales every quantity below.
Surprisal – The information carried by observing an outcome . Rare outcomes are more surprising.
Entropy – The expected surprisal, . It measures how uncertain is, or equivalently the average number of bits needed to encode it.
for outcomes. The maximum is reached by the uniform distribution, and a fair coin has 1 bit. Among continuous distributions with variance , the Gaussian has the largest entropy, .
Joint and conditional entropy – is the entropy of the pair. is the uncertainty about that remains once is known.
Comparing distributions
Cross-entropy – The average number of bits needed to encode samples from using a code designed for a model .
Kullback–Leibler (KL) divergence – The extra bits paid for using instead of the true . It is asymmetric, and zero only when .
follows from Jensen's inequality, which says for any convex function .
Mutual information – How much knowing reduces uncertainty about . It is zero exactly when and are independent.
Data processing inequality – If is computed from alone, so that , then processing cannot create information about : .
Other divergences – The ones that come up most often:
| Name | Definition | Note |
|---|---|---|
| Total variation | Pinsker's inequality: | |
| Jensen–Shannon | with | symmetric, at most ; the original GAN objective |
| Wasserstein | the minimum cost of moving the mass of onto | stays informative even when the supports don't overlap |
Links to machine learning
Maximum likelihood = minimum cross-entropy – Fitting a model by maximizing the average log-likelihood of the data is the same as minimizing cross-entropy against the empirical distribution of the data. Since is fixed, it is also the same as minimizing .
Classification loss – With a one-hot target (all mass on the true class ), the cross-entropy reduces to . Label smoothing replaces the target with .
Perplexity – when 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 converts it to bits, so a language model's loss is literally a compression rate.
Forward vs reverse KL – Forward KL, , is mass-covering: is penalized wherever it misses mass that has. That is the objective maximum likelihood optimizes. Reverse KL, , is mode-seeking: settles on one peak of . 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 with hidden variable and any approximation to the posterior, the ELBO is a tractable lower bound on . It is tight when equals the true posterior .
KL between Gaussians – For two one-dimensional normal distributions:
In a variational autoencoder (VAE) with a standard normal prior, this becomes per latent dimension.
Fisher information – The local curvature of KL around a parameter value . For a small change in parameters, . This is the geometry the natural gradient uses.
Coding
Source coding theorem – No lossless code can average fewer than bits per symbol, and Huffman coding gets within 1 bit of that. Coding with the wrong model costs extra bits per symbol.