Kullback-Leibler Divergence — Mathematics Knowledge System

Overview

The Kullback-Leibler (KL) divergence D_KL(P||Q) measures how much probability distribution P differs from a reference distribution Q. It equals the expected extra bits needed to encode data from P using a code optimized for Q, rather than for P. KL divergence is always non-negative (Gibbs' inequality), equals zero iff P = Q, and is asymmetric (D_KL(P||Q) ≠ D_KL(Q||P) in general). It is not a true distance metric, but it is a fundamental quantity in information theory, statistics, and machine learning, appearing in the definition of mutual information, hypothesis testing, variational inference, and maximum likelihood.

Intuition

Suppose you have a true distribution P (what actually happens) and a model distribution Q (what you think happens). KL divergence D_KL(P||Q) measures the average extra bits you waste if you encode symbols from P using the optimal code for Q instead of for P. If Q = P, no bits are wasted. If Q is very wrong (assigns near-zero probability to events that are common under P), you waste many bits. The asymmetry matters: D_KL(P||Q) penalizes Q for underestimating P; D_KL(Q||P) penalizes Q for overestimating P.

Formal Definition

Definition

For discrete probability distributions P and Q on the same alphabet X, the KL divergence from Q to P (also called relative entropy of P with respect to Q) is:

D_{\mathrm{KL}}(P \| Q) = \sum_{x} P(x) \log \frac{P(x)}{Q(x)}

KL divergence (discrete)

D_{\mathrm{KL}}(P \| Q) = \mathbb{E}_P\!\left[\log\frac{P(X)}{Q(X)}\right]

Expectation form

D_{\mathrm{KL}}(P \| Q) \geq 0, \text{ with equality iff } P = Q

Gibbs inequality (non-negativity)

I(X;Y) = D_{\mathrm{KL}}(p(x,y) \| p(x)p(y))

Mutual information as KL divergence

H(X) = \log n - D_{\mathrm{KL}}(P \| U)

Entropy as divergence from uniform (n outcomes)

Notation

Notation	Meaning
$D_{\mathrm{KL}}(P \\| Q)$	KL divergence from Q to P (relative entropy)
$D(P \\| Q)$	Alternative notation for KL divergence

Theorems

Theorem 1: Gibbs Inequality (Non-Negativity of KL Divergence)

For any two probability distributions P and Q on the same alphabet, D_{\mathrm{KL}}(P \| Q) \geq 0, with equality if and only if P(x) = Q(x) for all x.

Theorem 2: Chain Rule for KL Divergence

D_{\mathrm{KL}}(P(X,Y) \| Q(X,Y)) = D_{\mathrm{KL}}(P(X) \| Q(X)) + D_{\mathrm{KL}}(P(Y|X) \| Q(Y|X)).

Theorem 3: KL Divergence and Maximum Likelihood

Minimizing D_{\mathrm{KL}}(P_{\mathrm{data}} \| P_\theta) over model parameters \theta is equivalent to maximizing the log-likelihood \mathbb{E}_{P_{\mathrm{data}}}[\log P_\theta(X)].

Worked Examples

1
Apply the formula: D_KL = ∑ P(x) log(P(x)/Q(x)).
$D_{\mathrm{KL}}(P \| Q) = \frac{1}{2}\log_2\frac{1/2}{1/4} + \frac{1}{2}\log_2\frac{1/2}{3/4}$
2
First term: 1/2 × log₂(2) = 1/2.
$\frac{1}{2}\log_2 2 = \frac{1}{2}$
3
Second term: 1/2 × log₂(2/3) = 1/2 × (1 - log₂ 3) ≈ 1/2 × (-0.585) = -0.292.
$\frac{1}{2}\log_2\frac{2}{3} \approx -0.292$
4
Total D_KL = 0.5 - 0.292 = 0.208 bits.
$D_{\mathrm{KL}}(P \| Q) \approx 0.208 \text{ bits}$

✓ Answer

D_KL(P||Q) ≈ 0.208 bits. This is the extra cost of encoding data from P using code optimal for Q.

Practice Problems

Easyfill in blank

For P = Q (identical distributions), what is D_KL(P||Q)?

Mediumapplication

Explain why D_KL(P||Q) is asymmetric and why this matters in machine learning (e.g., choosing which direction to minimize).

Common Mistakes

Common Mistake

Treating KL divergence as a distance metric (symmetric).

KL divergence is asymmetric: D_KL(P||Q) ≠ D_KL(Q||P) in general. For a symmetric version, use the Jensen-Shannon divergence (1/2)(D_KL(P||M) + D_KL(Q||M)) where M = (P+Q)/2.

Common Mistake

Assuming D_KL(P||Q) is bounded between 0 and 1.

KL divergence can be arbitrarily large or even infinite (e.g., when Q(x) = 0 for some x with P(x) > 0). It has no upper bound.

Quiz

Historical Background

The KL divergence was introduced by Solomon Kullback and Richard Leibler in 1951 as a measure of the 'information for discrimination' between two hypotheses. Kullback's book 'Information Theory and Statistics' (1959) developed the statistical perspective. The quantity also appears in the work of Turing on cryptanalysis during World War II (weight of evidence). In modern machine learning it is central to variational autoencoders, where minimizing D_KL(q||p) provides tractable approximate inference.

1951
Kullback and Leibler publish 'On Information and Sufficiency', introducing the divergence.
Solomon Kullback, Richard Leibler
1959
Kullback publishes 'Information Theory and Statistics', expanding statistical applications.
Solomon Kullback
1980s
KL divergence recognized as fundamental to maximum likelihood estimation and Bayesian statistics.
2013
KL divergence appears centrally in variational autoencoders for approximate inference.
Kingma, Welling

Summary

D_KL(P||Q) = ∑ P(x) log(P(x)/Q(x)) measures the extra bits needed to encode P using a code optimized for Q.
Gibbs inequality: D_KL(P||Q) ≥ 0, with equality iff P = Q. KL divergence is asymmetric: D_KL(P||Q) ≠ D_KL(Q||P).
Mutual information I(X;Y) = D_KL(p(x,y) || p(x)p(y)) — dependence of X and Y measured as KL divergence from independence.
Minimizing D_KL(P_data || P_theta) over model parameters is equivalent to maximum likelihood estimation.

References

PaperKullback, S. and Leibler, R.A. (1951). On Information and Sufficiency. Annals of Mathematical Statistics, 22(1), 79-86.
BookCover, T. and Thomas, J. (2006). Elements of Information Theory, 2nd ed. Wiley. Ch. 2.
WebsiteWikipedia — Kullback-Leibler divergence