Information Theory
Introduction
Information theory, founded by Claude Shannon in 1948, gives us a precise, quantitative way to talk about uncertainty, surprise, and information. It answers questions like: how many bits do we need to encode a message? How “far apart” are two probability distributions? How much does knowing one variable tell us about another?
These ideas are not just elegant mathematics — they sit at the heart of modern machine learning. The loss function you minimize when training a classifier, the way decision trees choose their splits, and the objective behind variational autoencoders are all built directly from the quantities on this page.
The throughline: a model is a guessed distribution q; reality is the true distribution p. Almost everything below measures the cost — in bits — of using q when the truth is p. Training a model means shrinking that cost.
Self-Information: How Surprising Is an Event?
Start with a single outcome that occurs with probability p. Its self-information (or surprise) is:
Why this formula? It captures exactly the properties surprise should have:
- Rare events are surprising. As p → 0, −log₂ p → ∞. A one-in-a-million event carries about 20 bits of surprise.
- Certain events are unsurprising. If p = 1, then −log₂ 1 = 0 bits. Learning that the sun rose tells you nothing.
- Independent surprises add. Because log turns products into sums, the surprise of two independent events with probabilities p and r is −log₂(p·r) = −log₂ p − log₂ r. Two coin flips carry exactly 1 + 1 = 2 bits.
Using base-2 logarithms measures information in bits. One bit is the surprise of a fair coin flip (p = ½, so −log₂ ½ = 1). Using the natural log instead measures information in nats; the choice of base just rescales every quantity by a constant factor.
Intuition: self-information is the number of yes/no questions you would need (on average, with an optimal coding scheme) to pin down that this particular outcome happened.
Shannon Entropy: Average Surprise
A single outcome has surprise. A whole distribution has an expected surprise, called the Shannon entropy:
Read it literally: take each outcome's surprise −log₂ p(x), weight it by how often that outcome actually occurs, p(x), and sum. Entropy is the average number of bits of surprise per draw — equivalently, the minimum average number of bits needed to encode outcomes from this distribution (Shannon's source coding theorem).
| Distribution | Entropy | Meaning |
|---|---|---|
| One-hot (p = 1 on one outcome) | H = 0 bits | No uncertainty — the outcome is known. |
| Fair coin (½, ½) | H = 1 bit | One yes/no question settles it. |
| Uniform over n outcomes | H = log₂ n bits | Maximum possible entropy — most uncertain. |
Two extremes worth remembering: entropy is maximized by the uniform distribution (you are maximally uncertain) and is zero for a one-hot distribution (you are certain). You will verify both in the demo below by sliding the distribution around.
Cross-Entropy: The Cost of a Wrong Code
Now suppose outcomes really come from p, but you built your encoding (your model) assuming the distribution were q. The average number of bits you actually pay is the cross-entropy:
The structure mirrors entropy, but the surprise terms use the model's beliefs −log₂ q(x), while the averaging weights still come from reality p(x). If your model is perfect (q = p), cross-entropy equals the entropy H(p): you cannot do better than the true uncertainty. If q is wrong, you pay more — never less. (When q assigns zero probability to something p says can happen, the cost is infinite — a model must never be fully certain something is impossible.)
This is the loss you already use. The cross-entropy loss in classification is exactly H(p, q) where p is the true label distribution (often one-hot) and q is your model's softmax output. More on this below.
KL Divergence: Extra Bits Wasted
The Kullback–Leibler divergence isolates exactly the penalty for using the wrong distribution q instead of the true p:
That second form is the key identity: KL is the cross-entropy minus the entropy — the excess bits you pay beyond the irreducible H(p). Three properties define its behavior:
- Always non-negative: DKL(p ‖ q) ≥ 0 (Gibbs' inequality). You can never pay fewer bits with the wrong code.
- Zero iff identical: DKL(p ‖ q) = 0 if and only if q = p everywhere.
- Asymmetric: DKL(p ‖ q) ≠ DKL(q ‖ p) in general. It is not a distance — there is no triangle inequality. Which direction you minimize changes the behavior (mode-seeking vs. mass-covering).
Reading it: KL(p ‖ q) measures information lost when q is used to approximate p. Because H(p) does not depend on your model parameters, minimizing cross-entropy and minimizing KL(p ‖ q) are the same optimization — see the demo and the ML section.
Interactive: Entropy & KL Explorer
Adjust the “true” distribution p and the “model” distribution q over five outcomes. Everything is normalized to sum to 1 automatically, and every quantity is computed exactly in base-2 bits. Watch H(p), per-outcome surprise, cross-entropy, and both KL directions respond live.
Distribution p (the “truth”)
Distribution q (the “model”)
p vs q
Hit Uniform: H(p) reaches log₂(5) ≈ 2.322 bits. Spread = uncertainty.
Hit One-hot: H(p) = 0. A sure thing carries no surprise.
Hit Set q = p: KL collapses to 0 and H(p, q) = H(p).
Mutual Information: Shared Bits
One more quantity ties things together. The mutual information between two variables X and Y measures how much knowing one reduces uncertainty about the other:
Here H(X | Y) is the conditional entropy — the leftover uncertainty about X once Y is known. So I(X; Y) is literally the reduction in surprise about X that observing Y buys you. It is symmetric, always ≥ 0, and equals 0 exactly when X and Y are independent (knowing one tells you nothing about the other). Equivalently, it is the KL divergence between the joint distribution p(x, y) and the product of marginals p(x)p(y) — a measure of how far X and Y are from independence.
Where it shows up: feature selection (keep features with high mutual information with the label), and — as we will see next — decision-tree information gain is precisely the mutual information between a split and the target.
Why This Matters for Machine Learning
Cross-entropy loss
For a classifier, the true label is a one-hot distribution p and the model outputs a predicted distribution q (the softmax). The loss is the cross-entropy H(p, q) = −Σ p(x) log q(x). Because p is one-hot, this reduces to −log q(correct class) — penalize the model by the surprise it assigns to the right answer. Minimizing this pushes the model to put probability mass on the true label.
Minimizing cross-entropy = minimizing KL
Since H(p, q) = H(p) + DKL(p ‖ q) and H(p) is fixed by the data (independent of the parameters), minimizing cross-entropy over your model q is identical to minimizing DKL(p ‖ q). Training a classifier with cross-entropy loss is literally pulling the model distribution q toward the true data distribution p in KL.
Decision-tree information gain
A decision tree picks the split that most reduces uncertainty about the label. The information gain of a split is H(parent) − Σ (weighted) H(children) — the drop in entropy from splitting. This is exactly the mutual information between the split feature and the target: choose the feature that tells you the most about the label.
VAEs and the ELBO
Variational autoencoders maximize the evidence lower bound (ELBO), Eq[log p(x | z)] − DKL(q(z | x) ‖ p(z)). The first term is a reconstruction (negative cross-entropy) term; the second is a KL divergence that regularizes the encoder's latent distribution q(z | x) toward the prior p(z). The whole objective is built from the quantities on this page. (More broadly, all of variational inference minimizes a KL divergence between an approximate and a true posterior.)
Quantities at a Glance
| Quantity | Formula | What it measures |
|---|---|---|
| Self-information | I(x) = −log₂ p(x) | Surprise of one outcome |
| Entropy | H(p) = −Σ p log₂ p | Average surprise of p |
| Cross-entropy | H(p, q) = −Σ p log₂ q | Cost of code q when truth is p |
| KL divergence | Σ p log₂(p/q) = H(p,q) − H(p) | Extra bits wasted by q (≥ 0) |
| Mutual information | I(X;Y) = H(X) − H(X|Y) | Shared information between X, Y |
Common Pitfalls
Watch out
- • KL is not symmetric and not a true distance — direction matters.
- • KL(p ‖ q) is infinite if q = 0 where p > 0. Never assign exactly zero probability.
- • Entropy depends only on probabilities, not on outcome values.
- • Bits vs. nats: log₂ gives bits, ln gives nats. Be consistent.
Remember
- • H(p, q) = H(p) + KL(p ‖ q), and KL ≥ 0 always.
- • Cross-entropy ≥ entropy, with equality only when q = p.
- • Uniform = max entropy; one-hot = zero entropy.
- • Minimizing CE loss = minimizing KL to the data distribution.
Key Takeaways
- Self-information −log₂ p(x) measures the surprise of an outcome in bits; rare events are surprising, certain events carry zero information.
- Shannon entropy H(X) = −Σ p(x) log₂ p(x) is the expected surprise — the average bits per draw — maximized by the uniform distribution and zero for a one-hot distribution.
- Cross-entropy H(p, q) = −Σ p(x) log₂ q(x) is the cost of encoding data from p using a model q, and is the loss function behind softmax classifiers.
- KL divergence DKL(p ‖ q) = H(p, q) − H(p) is the extra bits wasted by q; it is always ≥ 0, zero only when q = p, and asymmetric.
- Minimizing cross-entropy is exactly minimizing KL divergence to the true distribution, because the entropy term H(p) does not depend on the model.
- Mutual information I(X; Y) = H(X) − H(X | Y) measures shared information and underlies decision-tree information gain; KL divergence also powers the VAE/ELBO objective.