Entropy, Cross-Entropy, KL Divergence, and Mutual Information

KL divergence is asymmetric. It generally violates the triangle inequality. Its name encourages geometric intuitions that do not hold, and the useful question is not whether it is a metric — it is not — but which repair of it does buy one. That question has a published answer.

There is one, and it is short. Take the Jensen–Shannon divergence and take its square root. The result is symmetric, bounded, and satisfies the triangle inequality. Endres and Schindelin published it in IEEE Transactions on Information Theory in July 2003, and their abstract states the result plainly: “We introduce a metric for probability distributions, which is bounded, information-theoretically motivated, and has a natural Bayesian interpretation”. Österreicher and Vajda established the same class of metric divergences independently that year, in the Annals of the Institute of Statistical Mathematics. The Jensen–Shannon divergence is the β = 1 member of that class.

One paper puts the two square roots side by side in a single paragraph. Kazuki Okamura, writing in 2023 on metrizing powers of the Jensen–Shannon divergence, notes that “It is well-known that the square root of the JSD satisfies the triangle inequality ([11, 12, 13]),” citing Endres and Schindelin among others. The same paragraph continues: “However, the square root of the KLD is generally not a metric: it can be asymmetric and violate the triangle inequality.” Taking a square root repairs Jensen–Shannon. It does not repair KL.

So the three columns. Forward KL p‖q is the expected log ratio under p: nonnegative, zero only when the distributions agree almost everywhere, asymmetric, and infinite under support mismatch. Reverse KL q‖p weights the regions where q places mass, can settle on one mode of a multimodal target, and optimizes differently. The third column is a genuine metric — which KL is not, and √JSD is.

A source selects messages according to a probability distribution. Give the common messages short codes and the rare ones longer codes, and the average code length falls. Entropy quantifies the irreducible average uncertainty of that source under ideal coding assumptions. Cross-entropy measures the coding cost when data from one distribution are encoded using probabilities from another.

That is not only a definition. It has been measured, on a source every reader of this lesson already uses. English.

Start with a 26-letter alphabet used with no statistical structure at all: log2 26 = 4.7 bits per letter. Statistics spanning eight letters bring the figure down to roughly 2.3 bits per letter. Then give a guesser the hundred letters that came before. Shannon's 1951 prediction experiments did exactly that, and in the §6 table, "Experimental Bounds for English," the column for 100 known preceding letters reads Upper 1.3, Lower .6. He states the conclusion in his introduction: “From this analysis it appears that, in ordinary literary English, the long range statistical effects (up to 100 letters) reduce the entropy to something of the order of one bit per letter, with a corresponding redundancy of roughly 75%.”

The estimate was later checked by a different instrument. In 1978 Cover and King ran a sequential-betting experiment at 27-for-1 odds and got about 1.3 bits per symbol, which they said agreed with Shannon's estimate. Guerrero's 2009 review of the classical figures summarises the pair: “Cover and King, using gambling estimates, found a value between 1.25 and 1.35 bits per character”.

Read what that collapse from 4.7 to roughly one bit is, and what it is not. It is a statement about redundancy in the letter stream — about how much of each letter is already implied by the hundred before it. These measures concern distributions over possibilities. They do not measure truth, usefulness, causal importance, or human meaning.

With a true distribution p and model q, cross-entropy decomposes into entropy plus KL divergence: H(p,q) = H(p) + DKL(p‖q). The KL term cannot be negative. So a measured cross-entropy is an upper bound on the entropy of the source. That is what makes the decomposition an experimental instrument rather than an identity to memorise, and it is how the entropy of English has actually been bounded from above.

The experiment has been run. Brown and four colleagues built a word trigram model on 583 million words and scored it against a balanced sample: the 5.96-million-character Brown Corpus, over an alphabet of 95 printable ASCII characters. Their 1992 abstract gives the design and the result in one sentence: “We present an estimate of an upper bound of 1.75 bits for the entropy of characters in printed English, obtained by constructing a word trigram model and then computing the cross-entropy between this model and a balanced sample of English text.” The inequality that licenses the whole thing is H(P) ≤ H(P,M).

Because the bound is a property of the model, a better model lowers it. In 2018 Takahashi and Tanaka-Ishii restated the earlier figure — “They reported an estimated upper bound of 1.75 bpc for English” — and reported their own, from neural language models: “We finally obtain an estimated entropy rate value of 1.12 bpc for English characters”. Neither number is the entropy of English. Both are ceilings. The drop from 1.75 to 1.12 bits per character is a shrinking mismatch term, not a change in the language.

The four quantities in play, then. Entropy H(p) is the average surprise when outcomes follow p and coding matches p. Cross-entropy H(p,q) is the average negative log probability that q assigns to outcomes from p. KL divergence DKL(p‖q) is the extra expected coding cost of using q instead of p. And mutual information I(X;Y) is the KL divergence between the joint p(x,y) and the independent product p(x)p(y).

Suppose the true label is 1 and a model predicts q=0.9 or q=0.01. Both are wrong-or-right by the same accuracy count. The losses are not remotely the same. That asymmetry is why log loss is the training objective — and also why a falling training loss is not evidence that the reported probabilities are honest. Guo and three colleagues measured that gap directly on CIFAR-100, using expected calibration error at M = 15 bins before and after each correction.

Identify the distributions and the operational claim before computing a scalar. Define p and q, stating which distribution generates the data and which is being evaluated. Check support: find events allowed by p but assigned zero or tiny probability by q. Choose direction, and say why forward or reverse KL matches the intended approximation. Validate the estimation. Then limit the claim — do not equate information with causality, fairness, usefulness, or semantic meaning.

Step four is the one usually skipped, and it is the one with a published protocol. The trouble starts with the estimators themselves. Gao, Ver Steeg and Galstyan open their 2015 paper with the diagnosis: “We demonstrate that a popular class of non-parametric mutual information (MI) estimators based on k-nearest-neighbor graphs requires number of samples that scales exponentially with the true MI.”

A 2023 benchmark built the test bench for that claim: nine estimators, forty tasks with known ground-truth MI, N = 10,000 points per run. Its authors restate the earlier finding — “Gao et al. (2015) proves that estimation of MI between strongly interacting variables requires large sample sizes” — and then measure where the estimators break: “for Gaussian distributions, neural estimators (and the simple CCA baseline) are accurate even up to 5 nats, while after the application of the spiral diffeomorphism, the estimates become inaccurate already at 2 nats”. The diffeomorphism is a smooth change of coordinates that provably leaves the true mutual information unchanged. Nothing about the dependence moved. Only the axes did, and the accurate range fell from about 5 nats to 2.

So validating an estimator means running it on distributions whose MI you already know, in coordinates as awkward as the ones you will deploy in, and reporting the value at which it stops working. Two nats is a finding. "We used a library" is not.

Self-information assigns −log p(x) to an outcome. Rare outcomes are more surprising, and the surprises of independent events add, because logarithms turn products into sums. The log base determines the units: base two gives bits, the natural logarithm gives nats. log2 26 = 4.7 bits is the per-letter cost of a 26-letter alphabet carrying no statistical structure, and every regularity in the source pushes that number down. A zero model probability for an event that occurs under p creates infinite cross-entropy and KL divergence, because no finite code was allocated.