KL Divergence

KL Divergence

D_{KL} (P ∥ Q)

measures how much one probability distribution

P

differs from a reference distribution

Q

. Key result: it is always non-negative, equals zero only when

P = Q

, but is not symmetric and is not a true distance. Applies in: information theory, statistics, machine learning, thermodynamics. Origin: Solomon Kullback and Richard Leibler, 1951.

The Kullback–Leibler divergence (also called relative entropy) quantifies the "information lost" when distribution $Q$ is used to approximate the true distribution $P$ . Concretely, it is the expected number of extra bits (or nats) you pay for encoding samples from $P$ using a code optimized for $Q$ instead of the optimal code for $P$ . It matters because it is the natural measure of distributional discrepancy that arises from coding theory, maximum-likelihood estimation, and Bayesian inference all at once. The surprising fact: although it behaves like a "squared distance" for nearby distributions, $D_{KL} (P ∥ Q) \neq = D_{KL} (Q ∥ P)$ in general, so swapping the two arguments can change the answer dramatically — even from finite to infinite.

The Core Insight

KL divergence is the expectation, under $P$ , of the log-ratio of the two densities. It answers: "On average over the true world $P$ , how surprised would I be if I believed $Q$ ?" Because $lo g \frac{p}{q}$ is positive where $P$ over-predicts and negative where it under-predicts, and because $P$ weights the average, the convexity of $- lo g$ forces the total to be non-negative. It is an asymmetric gap, not a metric.

Formal Statement

KL Divergence — Discrete Case

Let $P$ and $Q$ be probability distributions on a discrete set $X$ , with mass functions $p (x)$ and $q (x)$ . The Kullback–Leibler divergence of $Q$ from $P$ is

D_{KL} (P ∥ Q) = x \in X \sum p (x) lo g \frac{p ( x )}{q ( x )}

⟳Take the expectation under

P

of the pointwise log-ratio

lo g (p / q)

; this is the definition, not a theorem.

Here $p (x)$ is the true probability, $q (x)$ the model probability, and the logarithm base sets the units: base 2 gives bits, base $e$ gives nats. Conventions: $0 lo g \frac{0}{q} = 0$ (justified by $lim_{t \to 0^{+}} t lo g t = 0$ ), and $p lo g \frac{p}{0} = + \infty$ if any $p (x) > 0$ where $q (x) = 0$ .

KL Divergence — Continuous Case

For distributions with densities $p (x)$ and $q (x)$ on $R^{n}$ (with respect to Lebesgue measure),

D_{KL} (P ∥ Q) = \int_{R^{n}} p (x) lo g \frac{p ( x )}{q ( x )} d x

⟳Replace the sum in [1] by an integral; this requires

P

to be absolutely continuous with respect to

Q

for finiteness.

The general measure-theoretic form uses the Radon–Nikodym derivative $\frac{d P}{d Q}$ :

D_{KL} (P ∥ Q) = \int lo g (\frac{d P}{d Q}) d P

⟳When

P ≪ Q

, the density ratio

p / q

is exactly

d P / d Q

; integrating against

d P

unifies the discrete and continuous cases.

Gibbs' Inequality / Non-negativity

For any two distributions $P, Q$ on the same space,

D_{KL} (P ∥ Q) \geq 0, with equality iff P = Q (a.e.)

⟳Apply Jensen's inequality to the convex function

- lo g

with the expectation taken under

P

; strict convexity gives the equality condition.

Why It Holds / Derivation

Non-negativity via Jensen's Inequality

We prove [4].

Step 1. Write the divergence as a negative expectation:

- D_{KL} (P ∥ Q) = x \sum p (x) lo g \frac{q ( x )}{p ( x )} = E_{P} [lo g \frac{q ( X )}{p ( X )}]

⟳Flip the ratio inside the log, which negates the whole expression by

lo g (a / b) = - lo g (b / a)

Step 2. The function

lo g

is concave, so Jensen's inequality

E [lo g Z] \leq lo g E [Z]

applies with

Z = q (X) / p (X)

E_{P} [lo g \frac{q ( X )}{p ( X )}] \leq lo g E_{P} [\frac{q ( X )}{p ( X )}]

⟳Jensen for a concave

φ

states

E [φ (Z)] \leq φ (E [Z])

Step 3. Evaluate the inner expectation (the

p

's cancel):

E_{P} [\frac{q ( X )}{p ( X )}] = x \sum p (x) \frac{q ( x )}{p ( x )} = x \sum q (x) \leq 1

⟳Each

q (x)

summand survives; the total mass of

Q

is at most 1 (exactly 1 if

Q

is a genuine distribution over the same support).

Step 4. Therefore

- D_{KL} (P ∥ Q) \leq lo g 1 = 0

, i.e.

D_{KL} (P ∥ Q) \geq 0

. Step 5 (equality). Since

lo g

is strictly concave, Jensen is an equality only if

Z = q (X) / p (X)

is constant

P

-almost-surely. Combined with

\sum q = 1

, this constant must be 1, forcing

p (x) = q (x)

everywhere

P

has mass.

■

Solomon Kullback & Richard Leibler | 1907–1994, 1914–2003

Kullback and Leibler, both cryptanalysts and statisticians, introduced the quantity in their 1951 paper "On Information and Sufficiency" while working on statistical decision theory and the discrimination between hypotheses. Kullback was a chief scientist at the U.S. National Security Agency and authored the influential 1959 monograph Information Theory and Statistics. Their original motivation was the discrimination information between two statistical hypotheses — how decisively data favors $P$ over $Q$ — which links directly to the Neyman–Pearson Lemma and the theory of Sufficient Statistics.

Building Intuition

Imagine you must design a code to compress messages whose letters truly follow distribution $P$ . The optimal code (Shannon's source coding) assigns roughly $- lo g_{2} q (x)$ bits to letter $x$ if you believe the distribution is $Q$ . The true expected code length is then $\sum_{x} p (x) (- lo g_{2} q (x))$ , the cross-entropy $H (P, Q)$ . The unavoidable minimum is the entropy $H (P) = \sum_{x} p (x) (- lo g_{2} p (x))$ . KL divergence is exactly the excess:

D_{KL} (P ∥ Q) = H (P, Q) - H (P)

⟳Expand

lo g (p / q) = lo g p - lo g q

inside the sum and recognize the two entropy expressions.

So KL divergence = wasted bits from using the wrong codebook. It cannot be negative (you can never beat the optimal code) and is zero only when your codebook matches reality. The asymmetry now makes sense: paying with the wrong codebook in one direction is a different penalty than the other.

KL divergence as the gap between cross-entropy and entropy, and a mismatched density pair

Worked Examples

Two Coins — Discrete KL in Bits

Given: True coin

P = (p_{H}, p_{T}) = (0.5, 0.5)

. Model coin

Q = (0.25, 0.75)

. Compute

D_{KL} (P ∥ Q)

in bits (base-2 log). Step 1. Apply [1]:

D_{KL} (P ∥ Q) = 0.5 lo g_{2} \frac{0.5}{0.25} + 0.5 lo g_{2} \frac{0.5}{0.75}

Step 2. Evaluate each term:

lo g_{2} (0.5/0.25) = lo g_{2} 2 = 1

, so first term

= 0.5 \times 1 = 0.5

lo g_{2} (0.5/0.75) = lo g_{2} (0.6667) = - 0.585

, so second term

= 0.5 \times (- 0.585) = - 0.2925

. Step 3. Sum:

0.5 - 0.2925 = 0.2075

D_{KL} (P ∥ Q) \approx 0.2075 bits

Asymmetry check: Reversing,

D_{KL} (Q ∥ P) = 0.25 lo g_{2} \frac{0.25}{0.5} + 0.75 lo g_{2} \frac{0.75}{0.5} = 0.25 (- 1) + 0.75 (0.585) = - 0.25 + 0.4387 = 0.1887 bits

. Different value — confirming asymmetry.

Two Gaussians — Continuous KL in Nats

Given:

P = N (μ_{1}, σ_{1}^{2})

and

Q = N (μ_{2}, σ_{2}^{2})

. The closed-form result is

D_{KL} (P ∥ Q) = lo g \frac{σ _{2}}{σ _{1}} + \frac{σ _{1}^{2} + ( μ _{1} - μ _{2} ) ^{2}}{2 σ _{2}^{2}} - \frac{1}{2}

⟳Plug the two Gaussian densities into [2], expand the log into quadratic terms, and use

E_{P} [(X - μ_{1})^{2}] = σ_{1}^{2}

and

E_{P} [X] = μ_{1}

Numbers: Let

μ_{1} = 0, σ_{1} = 1

(standard normal) and

μ_{2} = 1, σ_{2} = 2

. Step 1.

lo g (σ_{2} / σ_{1}) = lo g 2 = 0.6931

nats. Step 2. Numerator

σ_{1}^{2} + (μ_{1} - μ_{2})^{2} = 1 + (0 - 1)^{2} = 2

. Denominator

2 σ_{2}^{2} = 2 (4) = 8

. Ratio

= 2/8 = 0.25

. Step 3. Subtract

\frac{1}{2}

: total

= 0.6931 + 0.25 - 0.5

D_{KL} (P ∥ Q) \approx 0.4431 nats

(Multiply by $1/ ln 2 \approx 1.4427$ to convert to bits: $\approx 0.639$ bits.)

Common Misconceptions

KL divergence is NOT a distance metric. It fails two of the three metric axioms:

Asymmetry: $D_{KL} (P ∥ Q) \neq = D_{KL} (Q ∥ P)$ in general (see Example 1).
Triangle inequality fails: there is no general $D_{KL} (P ∥ R) \leq D_{KL} (P ∥ Q) + D_{KL} (Q ∥ R)$ .

It does satisfy non-negativity and the identity-of-indiscernibles. To get a symmetric, metric-like quantity, use the Jensen–Shannon Divergence (whose square root is a metric) or symmetrize as

D_{KL} (P ∥ Q) + D_{KL} (Q ∥ P)

(still not a metric).

Infinite Divergence from Support Mismatch

Let $P$ be uniform on ${1, 2, 3}$ and $Q$ uniform on ${1, 2}$ . Then $q (3) = 0$ but $p (3) = \frac{1}{3} > 0$ , so the term $\frac{1}{3} lo g \frac{1/3}{0} = + \infty$ . Hence

D_{KL} (P ∥ Q) = + \infty.

Yet

D_{KL} (Q ∥ P)

is finite:

Q

assigns no mass to

{3}

, so no division-by-zero occurs, and

D_{KL} (Q ∥ P) = \frac{1}{2} lo g \frac{1/2}{1/3} + \frac{1}{2} lo g \frac{1/2}{1/3} = lo g \frac{3}{2} \approx 0.405

nats. This dramatic asymmetry shows why the direction of KL matters:

D_{KL} (P ∥ Q)

harshly punishes

Q

for placing zero mass where

P

has support, while the reverse is forgiving.

Connections

KL divergence is the hub of a web of information-theoretic quantities. Mutual Information is the KL divergence between a joint distribution and the product of its marginals: $I (X; Y) = D_{KL} (P_{X Y} ∥ P_{X} P_{Y})$ . Cross-Entropy equals $H (P) + D_{KL} (P ∥ Q)$ , which is why minimizing cross-entropy loss is exactly minimizing KL to the data distribution. Minimizing $D_{KL} (P_{data} ∥ P_{θ})$ over a parametric family is equivalent to Maximum Likelihood Estimation. The local quadratic approximation of KL recovers the Fisher Information Matrix as its Hessian — the foundation of information geometry. Finally, Shannon Entropy is the self-reference baseline that KL measures excess against.

KL and Fisher Information — Local Structure

For a smooth parametric family ${P_{θ}}$ , the KL divergence between nearby parameters is, to second order,

D_{KL} (P_{θ} ∥ P_{θ + d θ}) = \frac{1}{2} d θ^{⊤} I (θ) d θ + O (∥ d θ ∥^{3})

⟳Taylor-expand

lo g \frac{p _{θ}}{p _{θ + d θ}}

to second order; the first-order term vanishes (score has zero mean) and the second-order term is the Fisher information matrix

I (θ) = E [\nabla_{θ} lo g p \nabla_{θ} lo g p^{⊤}]

This shows KL is locally a (Riemannian) squared distance, even though it is globally asymmetric.

Real-World Applications

Machine learning loss functions — Cross-entropy/KL loss trains nearly all classification networks; minimizing it is minimizing $D_{KL} (P_{data} ∥ P_{model})$ .
Variational inference & VAEs — The Evidence Lower Bound (ELBO) contains a KL term $D_{KL} (q_{ϕ} (z ∣ x) ∥ p (z))$ regularizing the approximate posterior toward the prior; this is the core of variational autoencoders.
Reinforcement learning — Trust Region Policy Optimization (TRPO) and PPO constrain policy updates by bounding $D_{KL}$ between old and new policies to ensure stable improvement.
Model selection — The Akaike Information Criterion (AIC) is derived as an estimator of expected KL divergence between the true and fitted models.
Hypothesis testing & cryptanalysis — The original Kullback–Leibler use: the divergence equals the expected log-likelihood-ratio, governing the error exponents of Neyman–Pearson tests (Stein's lemma).
Statistical physics — Relative entropy bounds free-energy differences; the non-negativity underpins the second law and the Jarzynski/Crooks fluctuation theorems.
Anomaly & drift detection — Monitoring $D_{KL}$ between a reference data distribution and live streaming data flags distribution shift in deployed ML systems.

Historical Development

1948 — Claude Shannon introduces entropy and source coding in A Mathematical Theory of Communication, providing the bit-counting framework KL later exploits.
1951 — Solomon Kullback and Richard Leibler publish "On Information and Sufficiency" (Annals of Mathematical Statistics), defining the divergence as discrimination information between hypotheses.
1959 — Kullback's monograph Information Theory and Statistics systematizes relative entropy in statistical inference.
1957 — E. T. Jaynes formulates the Maximum Entropy Principle, in which minimizing KL to a prior generalizes entropy maximization.
1960s — Stein's lemma connects KL to the optimal error exponent of hypothesis tests, formalizing the cryptanalytic origin.
1973 — Hirotugu Akaike derives AIC, showing model selection approximates minimizing expected KL divergence.
1985–1990s — Shun'ichi Amari develops information geometry, treating KL as a dual-flat divergence with the Fisher metric, unifying it with differential geometry.
2013–2014 — Kingma & Welling (VAEs) and Schulman et al. (TRPO) embed KL divergence at the heart of modern deep learning objectives.

Subtleties & Limits

Unboundedness and estimation. KL divergence can be infinite under support mismatch, which destabilizes training of generative models (motivating Wasserstein distances in GANs, which remain finite). Estimating KL from samples in high dimensions is notoriously hard: nonparametric estimators suffer the curse of dimensionality and have high variance, and there is no unbiased estimator of

D_{KL}

from finite samples in general. The choice of forward (

D_{KL} (P ∥ Q)

, "mean-seeking," covers all modes of

P

) versus reverse (

D_{KL} (Q ∥ P)

, "mode-seeking," collapses onto one mode) divergence remains an active design question in variational inference, with no universally optimal answer. Generalizations such as

f

-divergences, Rényi divergences, and integral probability metrics each repair different shortcomings, but no single divergence is simultaneously symmetric, metric, finite, and easily estimable.