KL Divergence

⚡ Key Takeaways

KL Divergence $D_{\mathrm{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 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 $\log\frac{p}{q}$ is positive where $P$ over-predicts and negative where it under-predicts, and because $P$ weights the average, the convexity of $-\log$ forces the total to be non-negative. It is an asymmetric gap, not a metric.

DefinitionKL Divergence — Discrete Case

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

1

\quad D_{\mathrm{KL}}(P\|Q)=\sum_{x\in\mathcal{X}} p(x)\,\log\frac{p(x)}{q(x)}

Derivation hint: Take the expectation under $P$ of the pointwise log-ratio $\log(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\log\frac{0}{q}=0$ (justified by $\lim_{t\to0^+}t\log t=0$ ), and $p\log\frac{p}{0}=+\infty$ if any $p(x)>0$ where $q(x)=0$ .

DefinitionKL Divergence — Continuous Case

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

2

\quad D_{\mathrm{KL}}(P\|Q)=\int_{\mathbb{R}^n} p(x)\,\log\frac{p(x)}{q(x)}\,dx

Derivation hint: 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{dP}{dQ}$ :

3

\quad D_{\mathrm{KL}}(P\|Q)=\int \log\!\left(\frac{dP}{dQ}\right) dP

Derivation hint: When $P\ll Q$ , the density ratio $p/q$ is exactly $dP/dQ$ ; integrating against $dP$ unifies the discrete and continuous cases.

TheoremGibbs' Inequality / Non-negativity

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

4

\quad D_{\mathrm{KL}}(P\|Q)\ge 0,\qquad\text{with equality iff } P=Q \text{ (a.e.)}

Derivation hint: Apply Jensen's inequality to the convex function $-\log$ with the expectation taken under $P$ ; strict convexity gives the equality condition.

ProofNon-negativity via Jensen's Inequality

We prove [4].

Step 1. Write the divergence as a negative expectation:

5

\quad -D_{\mathrm{KL}}(P\|Q)=\sum_x p(x)\log\frac{q(x)}{p(x)}=\mathbb{E}_{P}\!\left[\log\frac{q(X)}{p(X)}\right]

Derivation hint: Flip the ratio inside the log, which negates the whole expression by $\log(a/b)=-\log(b/a)$ .

Step 2. The function $\log$ is concave, so Jensen's inequality $\mathbb{E}[\log Z]\le \log \mathbb{E}[Z]$ applies with $Z=q(X)/p(X)$ :

6

\quad \mathbb{E}_{P}\!\left[\log\frac{q(X)}{p(X)}\right]\le \log \mathbb{E}_{P}\!\left[\frac{q(X)}{p(X)}\right]

Derivation hint: Jensen for a concave $\varphi$ states $\mathbb{E}[\varphi(Z)]\le \varphi(\mathbb{E}[Z])$ .

Step 3. Evaluate the inner expectation (the $p$ 's cancel):

7

\quad \mathbb{E}_{P}\!\left[\frac{q(X)}{p(X)}\right]=\sum_x p(x)\frac{q(x)}{p(x)}=\sum_x q(x)\le 1

Derivation hint: 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_{\mathrm{KL}}(P\|Q)\le \log 1 = 0$ , i.e. $D_{\mathrm{KL}}(P\|Q)\ge 0$ .

Step 5 (equality). Since $\log$ 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. $\blacksquare$

∎

mathematician · 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.

🧠 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 $-\log_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)\,(-\log_2 q(x))$ , the cross-entropy $H(P,Q)$ . The unavoidable minimum is the entropy $H(P)=\sum_x p(x)(-\log_2 p(x))$ . KL divergence is exactly the excess:

8

\quad D_{\mathrm{KL}}(P\|Q)=H(P,Q)-H(P)

Derivation hint: Expand $\log(p/q)=\log p-\log 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.

Figure

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

ExampleTwo Coins — Discrete KL in Bits

Given: True coin $P=(p_{\text{H}},p_{\text{T}})=(0.5,0.5)$ . Model coin $Q=(0.25,0.75)$ . Compute $D_{\mathrm{KL}}(P\|Q)$ in bits (base-2 log).

Step 1. Apply [1]:

D_{\mathrm{KL}}(P\|Q)=0.5\log_2\frac{0.5}{0.25}+0.5\log_2\frac{0.5}{0.75}

Step 2. Evaluate each term: $\log_2(0.5/0.25)=\log_2 2 = 1$ , so first term $=0.5\times 1=0.5$ . $\log_2(0.5/0.75)=\log_2(0.6667)=-0.585$ , so second term $=0.5\times(-0.585)=-0.2925$ .

Step 3. Sum: $0.5-0.2925=0.2075$ .

\boxed{D_{\mathrm{KL}}(P\|Q)\approx 0.2075\ \text{bits}}

Asymmetry check: Reversing, $D_{\mathrm{KL}}(Q\|P)=0.25\log_2\frac{0.25}{0.5}+0.75\log_2\frac{0.75}{0.5}=0.25(-1)+0.75(0.585)=-0.25+0.4387=\boxed{0.1887\ \text{bits}}$ . Different value — confirming asymmetry.

ExampleTwo Gaussians — Continuous KL in Nats

Given: $P=\mathcal{N}(\mu_1,\sigma_1^2)$ and $Q=\mathcal{N}(\mu_2,\sigma_2^2)$ . The closed-form result is

9

\quad D_{\mathrm{KL}}(P\|Q)=\log\frac{\sigma_2}{\sigma_1}+\frac{\sigma_1^2+(\mu_1-\mu_2)^2}{2\sigma_2^2}-\frac12

Derivation hint: Plug the two Gaussian densities into [2], expand the log into quadratic terms, and use $\mathbb{E}_P[(X-\mu_1)^2]=\sigma_1^2$ and $\mathbb{E}_P[X]=\mu_1$ .

Numbers: Let $\mu_1=0,\sigma_1=1$ (standard normal) and $\mu_2=1,\sigma_2=2$ .

Step 1. $\log(\sigma_2/\sigma_1)=\log 2=0.6931$ nats.

Step 2. Numerator $\sigma_1^2+(\mu_1-\mu_2)^2=1+(0-1)^2=2$ . Denominator $2\sigma_2^2=2(4)=8$ . Ratio $=2/8=0.25$ .

Step 3. Subtract $\tfrac12$ : total $=0.6931+0.25-0.5$ .

\boxed{D_{\mathrm{KL}}(P\|Q)\approx 0.4431\ \text{nats}}

(Multiply by $1/\ln 2\approx1.4427$ to convert to bits: $\approx0.639$ bits.)

⚠️ Common mistake

KL divergence is NOT a distance metric. It fails two of the three metric axioms: 1. Asymmetry: $D_{\mathrm{KL}}(P\|Q)\neq D_{\mathrm{KL}}(Q\|P)$ in general (see Example 1). 2. Triangle inequality fails: there is no general $D_{\mathrm{KL}}(P\|R)\le D_{\mathrm{KL}}(P\|Q)+D_{\mathrm{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_{\mathrm{KL}}(P\|Q)+D_{\mathrm{KL}}(Q\|P)$ (still not a metric).

CounterexampleInfinite 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)=\tfrac13>0$ , so the term $\tfrac13\log\frac{1/3}{0}=+\infty$ . Hence

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

Yet $D_{\mathrm{KL}}(Q\|P)$ is finite: $Q$ assigns no mass to $\{3\}$ , so no division-by-zero occurs, and $D_{\mathrm{KL}}(Q\|P)=\tfrac12\log\frac{1/2}{1/3}+\tfrac12\log\frac{1/2}{1/3}=\log\frac{3}{2}\approx0.405$ nats. This dramatic asymmetry shows why the direction of KL matters: $D_{\mathrm{KL}}(P\|Q)$ harshly punishes $Q$ for placing zero mass where $P$ has support, while the reverse is forgiving.

connection

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_{\mathrm{KL}}(P_{XY}\|P_X P_Y)$ . Cross-Entropy equals $H(P)+D_{\mathrm{KL}}(P\|Q)$ , which is why minimizing cross-entropy loss is exactly minimizing KL to the data distribution. Minimizing $D_{\mathrm{KL}}(P_{\text{data}}\|P_\theta)$ 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.

TheoremKL and Fisher Information — Local Structure

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

10

\quad D_{\mathrm{KL}}(P_\theta\|P_{\theta+d\theta})=\tfrac12\, d\theta^{\top} \mathcal{I}(\theta)\, d\theta + O(\|d\theta\|^3)

Derivation hint: Taylor-expand $\log\frac{p_\theta}{p_{\theta+d\theta}}$ to second order; the first-order term vanishes (score has zero mean) and the second-order term is the Fisher information matrix $\mathcal{I}(\theta)=\mathbb{E}[\nabla_\theta\log p\,\nabla_\theta\log p^{\top}]$ . This shows KL is locally a (Riemannian) squared distance, even though it is globally asymmetric.

🔬 Where this appears

⏳ History

- 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.

open-problem

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_{\mathrm{KL}}$ from finite samples in general. The choice of forward ( $D_{\mathrm{KL}}(P\|Q)$ , "mean-seeking," covers all modes of $P$ ) versus reverse ( $D_{\mathrm{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.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also