KL Divergence

Why This Matters

KL divergence appears everywhere in machine learning. Maximum likelihood estimation minimizes KL divergence from the data distribution to the model. Variational inference minimizes KL divergence from the approximate posterior to the true posterior. RLHF uses a KL penalty to keep the fine-tuned policy close to the base model. Understanding the asymmetry of KL divergence explains why these different objectives produce different behaviors.

Mental Model

$D_{\text{KL}}(P \| Q)$ measures the expected number of extra bits needed to encode samples from $P$ using a code optimized for $Q$. It is zero only when $P = Q$. It is not symmetric: the cost of encoding $P$-samples with a $Q$-code differs from encoding $Q$-samples with a $P$-code.

Core Definitions

Definition

KL Divergence

For discrete distributions $P$ and $Q$ on the same sample space:

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

For continuous distributions with densities $p$ and $q$:

$D_{\text{KL}}(P \| Q) = \int p(x) \log \frac{p(x)}{q(x)} \, dx$

Convention: $0 \log(0/q) = 0$ and $p \log(p/0) = +\infty$ when $p > 0$. If $Q$ does not dominate $P$ (there exists $x$ with $P(x) > 0$ but $Q(x) = 0$), then $D_{\text{KL}}(P \| Q) = +\infty$.

Definition

Cross-Entropy

The cross-entropy between $P$ and $Q$ is:

$H(P, Q) = -\sum_{x} P(x) \log Q(x) = H(P) + D_{\text{KL}}(P \| Q)$

where $H(P) = -\sum_x P(x) \log P(x)$ is the Shannon entropy. Since $H(P)$ is fixed with respect to $Q$, minimizing cross-entropy over $Q$ is equivalent to minimizing KL divergence.

Main Theorems

Theorem

Gibbs Inequality (Non-negativity of KL Divergence)

Statement

For any two probability distributions $P$ and $Q$:

$D_{\text{KL}}(P \| Q) \geq 0$

with equality if and only if $P = Q$ almost everywhere.

Intuition

The logarithm is concave. Applying Jensen's inequality to $\log(Q/P)$ under expectation with respect to $P$ gives $\mathbb{E}_P[\log(Q/P)] \leq \log(\mathbb{E}_P[Q/P]) = \log(1) = 0$. Negating both sides yields $D_{\text{KL}} \geq 0$.

Proof Sketch

By Jensen's inequality applied to the concave function $\log$:

$-D_{\text{KL}}(P \| Q) = \mathbb{E}_P\left[\log \frac{Q(X)}{P(X)}\right] \leq \log \mathbb{E}_P\left[\frac{Q(X)}{P(X)}\right] = \log \sum_x Q(x) = 0$

Equality in Jensen's holds iff $Q(X)/P(X)$ is constant $P$-a.s., which forces $P = Q$.

Why It Matters

Non-negativity of KL divergence is the foundation for many results. It implies that cross-entropy is always at least the entropy: $H(P, Q) \geq H(P)$. It guarantees that MLE is consistent (the minimizer of KL from the true distribution is the true distribution itself). It ensures the ELBO is a valid lower bound on the log-evidence.

Failure Mode

KL divergence is not a metric. It is not symmetric: $D_{\text{KL}}(P \| Q) \neq D_{\text{KL}}(Q \| P)$ in general. It does not satisfy the triangle inequality. This means you cannot use it as a distance in metric-space arguments. If you need a true metric, consider the total variation distance or Wasserstein distance.

Forward vs. Reverse KL

The two directions of KL divergence produce qualitatively different behavior when fitting an approximate distribution $Q$ to a target $P$.

Forward KL: $D_{\text{KL}}(P \| Q)$

Minimizing $D_{\text{KL}}(P \| Q)$ over $Q$ is mode-covering (also called "M-projection" or mean-seeking). The objective penalizes $Q(x) \approx 0$ wherever $P(x) > 0$, because $P(x) \log(P(x)/Q(x)) \to \infty$ as $Q(x) \to 0$. So $Q$ must spread mass to cover all modes of $P$, even if this means placing mass where $P$ is small.

This is exactly what MLE does: given data from $P$, minimize $H(P_{\text{data}}, Q_\theta) = H(P_{\text{data}}) + D_{\text{KL}}(P_{\text{data}} \| Q_\theta)$.

Reverse KL: $D_{\text{KL}}(Q \| P)$

Minimizing $D_{\text{KL}}(Q \| P)$ over $Q$ is mode-seeking (also called "I-projection"). The objective penalizes $Q(x) > 0$ wherever $P(x) \approx 0$, because $Q(x) \log(Q(x)/P(x)) \to \infty$ as $P(x) \to 0$. So $Q$ avoids placing mass where $P$ is small, and tends to concentrate on a single mode of $P$.

This is what variational inference does: minimize $D_{\text{KL}}(q_\phi(z) \| p(z | x))$ over the variational family $q_\phi$.

Connection to Variational Inference

The evidence lower bound (ELBO) arises from the decomposition:

$\log p(x) = \mathcal{L}(q) + D_{\text{KL}}(q(z) \| p(z|x))$

where $\mathcal{L}(q) = \mathbb{E}_{q}[\log p(x, z) - \log q(z)]$ is the ELBO. Since $D_{\text{KL}} \geq 0$, we have $\mathcal{L}(q) \leq \log p(x)$. Maximizing the ELBO over $q$ is equivalent to minimizing $D_{\text{KL}}(q \| p(\cdot | x))$.

Connection to RLHF

In RLHF, the optimization objective includes a KL penalty:

$\max_\pi \mathbb{E}_{x \sim \pi}[r(x)] - \beta \, D_{\text{KL}}(\pi \| \pi_{\text{ref}})$

where $\pi_{\text{ref}}$ is the supervised fine-tuned (base) policy and $r$ is the reward model. The KL term prevents the fine-tuned policy from deviating too far from the base model, which would lead to reward hacking (exploiting errors in $r$ rather than genuinely improving quality). The coefficient $\beta$ controls the tradeoff.

Canonical Examples

Example

KL between two Gaussians

For $P = \mathcal{N}(\mu_1, \sigma_1^2)$ and $Q = \mathcal{N}(\mu_2, \sigma_2^2)$:

$D_{\text{KL}}(P \| Q) = \log \frac{\sigma_2}{\sigma_1} + \frac{\sigma_1^2 + (\mu_1 - \mu_2)^2}{2\sigma_2^2} - \frac{1}{2}$

Note: this is zero only when $\mu_1 = \mu_2$ and $\sigma_1 = \sigma_2$. The asymmetry is visible: swapping $P$ and $Q$ gives a different expression.

Example

KL between Bernoulli distributions

For $P = \text{Bern}(p)$ and $Q = \text{Bern}(q)$:

$D_{\text{KL}}(P \| Q) = p \log \frac{p}{q} + (1-p) \log \frac{1-p}{1-q}$

If $p = 0.9$ and $q = 0.5$: $D_{\text{KL}} = 0.9 \log(1.8) + 0.1 \log(0.2) \approx 0.368$ nats. If $p = 0.5$ and $q = 0.9$: $D_{\text{KL}} = 0.5 \log(5/9) + 0.5 \log(5) \approx 0.511$ nats. Different values confirm asymmetry.

Common Confusions

Watch Out

KL divergence is not a distance

$D_{\text{KL}}(P \| Q) \neq D_{\text{KL}}(Q \| P)$ and the triangle inequality fails. Calling it a "distance" is common but misleading. It is a divergence: a measure of discrepancy, not a metric.

Watch Out

Zero KL does not mean the distributions are close pointwise

$D_{\text{KL}}(P \| Q) = 0$ means $P = Q$ a.e., which is a strong statement. But $D_{\text{KL}}(P \| Q)$ being small does not imply $P$ and $Q$ are close in total variation. Pinsker's inequality gives $\text{TV}(P, Q) \leq \sqrt{D_{\text{KL}}(P \| Q)/2}$, but this bound is often loose.

Watch Out

Minimizing forward KL is not the same as minimizing reverse KL

MLE minimizes forward KL $D_{\text{KL}}(P_{\text{data}} \| Q_\theta)$, producing mode-covering fits. Variational inference minimizes reverse KL $D_{\text{KL}}(q_\phi \| p(\cdot | x))$, producing mode-seeking fits. When $P$ is multimodal and $Q$ is unimodal, forward KL places $Q$ between modes; reverse KL concentrates $Q$ on one mode. These are genuinely different objectives with different solutions.

Summary

• $D_{\text{KL}}(P \| Q) = \mathbb{E}_P[\log(P/Q)] \geq 0$, with equality iff $P = Q$
• Not symmetric, not a metric
• Forward KL ($D(P \| Q)$ over $Q$): mode-covering, equivalent to MLE
• Reverse KL ($D(Q \| P)$ over $Q$): mode-seeking, used in variational inference
• Cross-entropy = entropy + KL divergence
• KL penalty in RLHF constrains policy deviation from the base model

Exercises

ExerciseCore

Problem

Compute $D_{\text{KL}}(P \| Q)$ and $D_{\text{KL}}(Q \| P)$ for $P = \text{Bern}(0.5)$ and $Q = \text{Bern}(0.1)$. Verify that they differ.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Derive the closed-form KL divergence between two multivariate Gaussians $P = \mathcal{N}(\mu_1, \Sigma_1)$ and $Q = \mathcal{N}(\mu_2, \Sigma_2)$ in $\mathbb{R}^d$.

Hint

Reveal Solution

Related Comparisons

• KL Divergence vs. Cross-Entropy

References

Canonical:

• Cover & Thomas, Elements of Information Theory (2006), Chapter 2
• Kullback & Leibler, "On Information and Sufficiency" (1951)

Current:

• Murphy, Probabilistic Machine Learning: Advanced Topics (2023), Chapter 6
• Bishop, Pattern Recognition and Machine Learning (2006), Chapters 1.6 and 10.1
• MacKay, Information Theory, Inference, and Learning Algorithms (2003), Chapter 2
• Csiszár & Körner, Information Theory (2nd ed., 2011), Chapter 2

Next Topics

• Variational inference: using reverse KL to approximate intractable posteriors
• Mutual information: symmetric quantity built from KL divergence