KL divergence and mutual information

Last lesson ended on a decomposition: coding with wrong beliefs costs $H(p) + \mathrm{KL}(p\|q)$ — the truth’s own entropy plus a penalty for being wrong. This lesson is about the penalty. Kullback–Leibler divergence is the curriculum’s most-used and least-explained quantity: it has appeared in the MLE lesson (in disguise), t-SNE’s objective, the RLHF leash, DPO’s derivation, speculative decoding’s proof and the scaling-laws lesson — always with an IOU for a real definition. Today the IOU is paid, and the asymmetry that most treatments mumble past becomes something you have felt with a slider.

The definition, and the three readings

Three equivalent readings, each doing work somewhere in the curriculum: the coder’s (last lesson): extra bits per symbol for using code $q$ on source $p$; the gambler’s: the expected log-loss of betting with beliefs $q$ against reality $p$; the statistician’s: the expected log-likelihood-ratio between truth and model — the currency of hypothesis testing. Two properties are load-bearing everywhere: $\mathrm{KL} \ge 0$ with equality iff $p = q$ (Gibbs’ inequality — via Jensen, the same convexity trick as the EM lesson), and it is not a distance: $\mathrm{KL}(p\|q) \neq \mathrm{KL}(q\|p)$, no triangle inequality, no symmetry. That asymmetry is not a defect to apologize for — it encodes which mistakes you fear, and choosing a direction is choosing a failure mode:

The curriculum, re-read through KL

The reveal this module exists for — objectives you have already met, unmasked as divergences:

• Maximum likelihood minimizes $\mathrm{KL}(\hat p_{\text{data}} \| p_\theta)$ — the MLE lesson’s closing identity, now with its information-theoretic meaning attached: fit = compress.
• Every loss curve in the scaling-laws lesson is $H(\text{text}) + \mathrm{KL}(\text{text} \| \text{model})$ descending toward the irreducible floor.
• t-SNE minimizes $\mathrm{KL}(P\|Q)$ over layouts — mass-covering, which is why it refuses to separate points that are neighbors in the data (truth-mass must be covered) while feeling free to invent gaps.
• RLHF’s leash $\beta\,\mathrm{KL}(\pi \| \pi_{\text{ref}})$ is reverse-KL-shaped — mode-seeking: stay inside the reference’s mass, the exact philosophy the widget’s second button demonstrated. DPO’s derivation solved this objective in closed form.
• EM’s ELBO gap is exactly $\mathrm{KL}(q \| \text{posterior})$ — the bound is tight when the divergence is zero.
• Speculative decoding’s acceptance rule works because the correction distribution is built from where draft and target disagree — a KL-flavored accounting of disagreement.

One derived quantity earns its keep so often it needs its own name. Mutual information is the KL between a joint distribution and the independent world it would be if its variables ignored each other:

— the bits of uncertainty about $X$ that observing $Y$ removes. Zero iff independent, and unlike correlation it catches any dependence, not just linear (the U-shaped relationship that correlation scores at zero, MI sees plainly). It appears across the field as the honest currency of “how much does this tell me about that”: feature selection, the information bottleneck view of deep nets, decision-tree splits (information gain is exactly $I$ between split and label — the trees lesson’s Gini was a cheap cousin), and channel capacity, where Shannon defined it first.

Practical fine print, learned the hard way by everyone: KL is infinite when $q$ misses $p$‘s support — the reason label smoothing exists, why zero probabilities are clamped with $\epsilon$ everywhere in this curriculum’s code, and why the widget clamps at $10^{-12}$; estimating KL and MI from samples is genuinely hard in high dimensions (naive histogram estimators fail; the field uses variational bounds); and when you need a symmetric, bounded compromise, Jensen–Shannon divergence (the symmetrized mixture form) is the standard — it is what the original GAN objective secretly minimized.

import numpy as np

# the asymmetry, computed: bimodal truth, one-Gaussian model
xs = np.linspace(-6, 6, 4001); dx = xs[1] - xs[0]
g = lambda x, m, s: np.exp(-(x - m)**2 / (2 * s * s)) / (s * np.sqrt(2 * np.pi))
P = 0.6 * g(xs, -1.6, 0.45) + 0.4 * g(xs, 1.8, 0.55)

def kl(a, b):
    a, b = np.maximum(a, 1e-12), np.maximum(b, 1e-12)
    return float(np.sum(a * np.log(a / b) * dx))

wide  = g(xs, -0.2, 1.75)   # ~the mass-covering optimum
tight = g(xs, -1.6, 0.45)   # ~the mode-seeking optimum
print(kl(P, wide),  kl(P, tight))   # P‖Q: wide wins (tight leaves a hump uncovered)
print(kl(wide, P),  kl(tight, P))   # Q‖P: tight wins (wide bets on the empty valley)

Exercises