KL Divergence

Topic 22 left a debt. The bookie's bill splits into two parts:

H(p, q) = H(p) + [extra charge]

• H(p): the irreducible cost — reality's own surprise. Nobody can pay less.
• The extra: everything you pay only because your odds q differ from the true frequencies p.

So the question becomes

You want a gap score between two distributions. Not for classification this time — for matching beliefs. This is the job KL divergence does, and it hides inside half of modern ML: VAEs, distillation, RLHF, trust regions.

The Kullback-Leibler divergence from p to q is simply

D_KL(p ‖ q) = Σₓ p(x) log( p(x) / q(x) ) = E_{x~p}[ log p(x) − log q(x) ]

Unpack the two readings — they are the same number:

• Billing view: D_KL = H(p, q) − H(p) — cross-entropy minus the irreducible entropy (Topic 22). The overcharge, nothing more, nothing less.
• Direct view: for each event, compare its true price log p with the price you'd charge log q, then average over reality.

Fundamental properties:

• Non-negative (Gibbs' inequality, from Jensen on the concave log), and zero iff p = q almost everywhere.
• Asymmetric: D_KL(p ‖ q) ≠ D_KL(q ‖ p). The transaction "reality is p, I believe q" differs from the reverse.
• Not a metric: no symmetry, and no triangle inequality. Squaring it or symmetrizing gives related distances (Jeffreys), and the Jensen-Shannon divergence fixes both defects by averaging before comparing.
• Support rule: if q(x) = 0 anywhere p(x) > 0, the divergence is infinite — you assigned zero to something real; no apology exists in log terms.

For continuous variables, replace the sum with an integral over densities; everything below carries over verbatim.

Reality is a fair coin: p = (0.5, 0.5). Your belief is a biased coin: q = (0.9, 0.1).

Walk the forward divergence term by term (natural log, so nats):

code
Copy
D_KL(p ‖ q) = 0.5·ln(0.5/0.9) + 0.5·ln(0.5/0.1)
            = 0.5·(−0.588)   + 0.5·(+1.609)
            = −0.294 + 0.805
            ≈ 0.51 nats

Notice the terms: where you overpriced (0.9 vs 0.5) you get a small credit inside the ratio, but where you underpriced (0.1 vs 0.5) the overcharge is huge — logs punish underestimating reality hardest.

Now flip the direction: score the belief q = (0.9, 0.1) against "reality" p = (0.5, 0.5):

code
Copy
D_KL(q ‖ p) = 0.9·ln(0.9/0.5) + 0.1·ln(0.1/0.5)
            ≈ 0.529 − 0.161
            ≈ 0.37 nats   ≠  0.51

Same two coins, two different scores. That asymmetry is not a bug — it is two different habits of mind (next section), and it is the reason KL is a divergence, not a distance.

Approximating a complicated p with a simple q, the choice of direction changes the geometry of failure:

• Forward KL, D(p ‖ q): penalizes regions where p has mass but q underestimates. q is forced to cover all of p and spills into the valleys between modes (mean-seeking / mass-covering). Minimizing it over a model class is exactly MLE (Topic 19): the empirical-distribution form drops to average log-likelihood, since H(p̂) is constant.
• Reverse KL, D(q ‖ p): penalizes regions where q places mass but p has little. q picks one mode and sits tightly on it (mode-seeking / zero-forcing), happily ignoring other modes. This is the direction variational inference minimizes: approximating a posterior with a tractable q means you are paying the price of missing modes rather than smearing.

Visual intuition on a bimodal target:

code
Copy
   true p:   two humps          forward KL q:      reverse KL q:
              ██      ██              ██ ██              ██
             █  █    █  █            █    █   █         █  █
   ──────────────────────────   ──────────────────────────────
   q smears over BOTH humps     q hugs ONE hump,
   and the empty valley         ignores the other

Rule of thumb:

• Forward KL when missing truth is worse than overcommitting (fitting data).
• Reverse KL when false positives are worse than missing them (compact approximations, generation with constraints).

For two univariate Gaussians, the closed form is a beautiful three-term penalty — a squared-mean gap, a variance ratio, and a log correction:

D(N(μ₀, σ₀²) ‖ N(μ₁, σ₁²)) = [ (μ₀ − μ₁)² + σ₀² ] / (2σ₁²) − ½ + log(σ₁/σ₀)

import numpy as np

def kl_gauss(m0, s0, m1, s1):
    return ((m0 - m1)**2 + s0**2) / (2 * s1**2) - 0.5 + np.log(s1 / s0)

print("KL forward:", round(kl_gauss(0.0, 1.0, 1.5, 2.0), 4))   # 0.5994
print("KL reverse:", round(kl_gauss(1.5, 2.0, 0.0, 1.0), 4))   # 1.9319 != forward

rng = np.random.default_rng(0)
x = rng.normal(0.0, 1.0, size=2_000_000)                        # sample from p
p = np.exp(-x**2 / 2) / (1 * np.sqrt(2 * np.pi))
q = np.exp(-(x - 1.5)**2 / (2 * 2.0**2)) / (2 * np.sqrt(2 * np.pi))
print("MC forward:", round(np.mean(np.log(p / q)), 4))          # matches 0.5994

Continue the bookie analogy from Topic 22 (the bookie quotes odds q; reality has true frequencies p; the bill is −log of the quoted probability).

An auditor now walks in and computes the overcharge per race: average bill minus the fair bill. That number is exactly D_KL(p ‖ q).

Read the two directions as two audits:

• Forward audit, D(p ‖ q): "For every outcome that actually happens, did you offer odds?" A bookie audited this way refuses to ignore any horse — even unlikely ones — because ignoring a horse that later wins is infinite ruin (support rule!). This is the MLE mindset.
• Reverse audit, D(q ‖ p): "For every odd you offer, is that outcome real?" This bookie is terrified of quoting longshots that never win, so they narrow down to one safe horse. This is the variational-inference mindset.

Same pair of distributions, different question asked, different fear driving behavior. That is why "which KL?" is a design decision, not a notation detail.

Once you see the overcharge, you spot it in every objective:

• Variational autoencoders / ELBO: the training objective decomposes into reconstruction + D_KL(q(z | x) ‖ p(z)) — reverse KL pulling the encoder posterior toward the standard-normal prior. The KL term is the rate-distortion knob: large weight → blurry but compressible; small weight → sharp but uncontrolled latent space.
• Knowledge distillation: students train against teacher soft labels; with teacher p and student q, standard CE is exactly forward KL + constant teacher entropy — so distillation literally minimizes KL to the teacher's distribution.
• RLHF / preference tuning: LLM fine-tuning adds β · D_KL(π_model ‖ π_reference) to the reward objective to keep the policy near the original model — the published mechanism against reward hacking and capability drift.
• Policy optimization (TRPO/PPO): the trust-region constraint is measured in KL between old and new policies; the Fisher information matrix (Topic 13) is the local second-order expansion of KL.
• Attention and interpretability: KL of an attention row against uniform flags over-concentration; KL between token distributions measures a prompt's effect on the model.
• Anomaly detection and model monitoring: KL of production score distributions against a reference detects drift and data quality failures.

KL is an expectation over p, so Monte Carlo is the workhorse:

D_KL(p ‖ q) = E_{x~p}[ log p(x) − log q(x) ]

Sample from p, evaluate log-densities of both, average. Now the caveats engineers actually hit:

1. You cannot estimate D_KL(p ‖ q) from samples of q alone (the expectation is over p) — importance sampling or density models are needed.
2. The log ratio has unbounded variance when q is small on p-support: reverse-KL estimators in VAEs with sharp posteriors are notoriously high-variance.
3. For discrete vocabularies (KL in RLHF between model and reference), compute full-vocabulary log-prob differences where possible — sampled-token single-sample estimators (the K1 estimator) are unbiased but noisy; the low-variance K3 estimator is the common practical fix.
4. Symmetrized and smoothed variants (Jeffreys, JS) trade exact interpretation for metric-like behavior when you need to compare "undirectionally."