KL divergence and cross-entropy

Training a classifier means making a predicted distribution match a true one. The gap between two distributions is measured by the KL divergence, and the quantity actually minimized in practice, cross-entropy, differs from it only by a constant. Minimizing cross-entropy turns out to be exactly maximum likelihood.

Cross-entropy

The cross-entropy of a distribution $q$ relative to $p$ is the expected surprise of outcomes drawn from $p$ but scored with $q$:

It is the average number of bits to encode samples from the true $p$ using a code optimized for the model $q$. If $q = p$ it reduces to the entropy $H(p)$. Using the wrong code costs extra bits, and that excess is the KL divergence.

KL divergence

The Kullback-Leibler divergence from $p$ to $q$ is the cross-entropy minus the entropy[1, 2]:

It is the expected log-ratio under $p$. It quantifies the penalty for modeling $p$ with $q$ instead of the truth.

Nonnegativity (Gibbs' inequality)

Theorem. $D_{\mathrm{KL}}(p \,\|\, q) \ge 0$, with equality if and only if $p = q$[3].

Proof. Write the divergence with a sign flip and apply Jensen to the concave logarithm:

The expectation inside is $\sum_x p(x)\frac{q(x)}{p(x)} = \sum_x q(x) = 1$, so the bound is $\log 1 = 0$. Therefore $-D_{\mathrm{KL}} \le 0$, i.e. $D_{\mathrm{KL}} \ge 0$. Jensen is tight only when $q(X)/p(X)$ is constant, which with both summing to 1 forces $p = q$. $\qquad\blacksquare$

Asymmetry

KL is not symmetric: $D_{\mathrm{KL}}(p \,\|\, q) \neq D_{\mathrm{KL}}(q \,\|\, p)$ in general, so it is not a distance. The two directions behave differently. $D_{\mathrm{KL}}(p \,\|\, q)$ is "mean-seeking": it is huge where $p$ has mass but $q$ does not, so minimizing it forces $q$ to cover all of $p$'s support. $D_{\mathrm{KL}}(q \,\|\, p)$ is "mode-seeking": it lets $q$ concentrate on one mode. Variational inference minimizes the second; maximum likelihood, the first.

Cross-entropy loss is maximum likelihood

For classification, $p$ is the one-hot true label and $q_\theta$ the model's predicted class probabilities. The per-example cross-entropy is $H(p, q_\theta) = -\log q_\theta(\text{true class})$. Averaged over a dataset,

which is the negative average log-likelihood. Minimizing cross-entropy is maximizing likelihood. Since $H(p)$ is fixed by the data, minimizing cross-entropy also minimizes $D_{\mathrm{KL}}(p \,\|\, q_\theta)$: the model is pushed toward the true label distribution.

Check it on arrays

import numpy as np

rng = np.random.default_rng(14)

def kl(p, q):
    p, q = np.asarray(p, float), np.asarray(q, float)
    mask = p > 0
    return np.sum(p[mask] * np.log(p[mask] / q[mask]))

def cross_entropy(p, q):
    p, q = np.asarray(p, float), np.asarray(q, float)
    mask = p > 0
    return -np.sum(p[mask] * np.log(q[mask]))

def entropy(p):
    p = np.asarray(p, float)
    mask = p > 0
    return -np.sum(p[mask] * np.log(p[mask]))

p = np.array([0.5, 0.3, 0.2])
q = np.array([0.4, 0.4, 0.2])

print("KL(p||q):", round(kl(p, q), 4), " >= 0")
print("KL(p||p):", round(kl(p, p), 4), " == 0")
print("H(p,q) - H(p):", round(cross_entropy(p, q) - entropy(p), 4),
      " == KL(p||q):", round(kl(p, q), 4))
print("asymmetry: KL(q||p) =", round(kl(q, p), 4), "!= KL(p||q)")

# Cross-entropy loss == negative log-likelihood on one-hot labels
logits = rng.normal(size=(5, 3))
probs = np.exp(logits) / np.exp(logits).sum(axis=1, keepdims=True)
labels = rng.integers(0, 3, size=5)
ce = -np.log(probs[np.arange(5), labels]).mean()
print("mean cross-entropy loss:", round(ce, 4))

KL is nonnegative and zero only against itself, the cross-entropy minus entropy identity holds, the two KL directions disagree, and the classification loss is the mean negative log-likelihood.

Exercises

Exercise 1. With $p = (0.5, 0.5)$ and $q = (0.25, 0.75)$, compute $D_{\mathrm{KL}}(p \,\|\, q)$ and $D_{\mathrm{KL}}(q \,\|\, p)$ in bits by hand, and confirm they differ.

Exercise 2. Show that the cross-entropy $H(p, q)$ is minimized over $q$ exactly when $q = p$, and that its minimum value is the entropy $H(p)$.

Exercise 3 (code). Sample-estimate the cross-entropy $H(p, q)$ as the mean of $-\log q(X)$ over draws $X \sim p$, and confirm it equals $H(p) + D_{\mathrm{KL}}(p \,\|\, q)$ computed exactly.

import numpy as np

rng = np.random.default_rng(15)

p = np.array([0.5, 0.3, 0.2])
q = np.array([0.4, 0.4, 0.2])

# Monte Carlo cross-entropy: E_{X~p}[-log q(X)]
X = rng.choice(3, size=2_000_000, p=p)
ce_mc = -np.log(q[X]).mean()

H_p = -(p * np.log(p)).sum()
kl_pq = (p * np.log(p / q)).sum()
ce_exact = H_p + kl_pq

assert np.isclose(ce_mc, ce_exact, atol=2e-3)
print("cross-entropy MC:", round(ce_mc, 4), " H(p)+KL:", round(ce_exact, 4))

The next lesson uses KL to measure how much two variables tell you about each other: mutual information.