Entropy, cross-entropy and KL divergence

The previous note ended with a concrete task: fit the distribution we are training, $Q$, to a target distribution $P$. To do that we need a number that measures how far $Q$ is from $P$. The standard first choice is the Kullback–Leibler divergence:

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

What does this formula mean? This note builds it from the ground up: surprise → entropy → cross-entropy → KL. Along the way it explains why cross-entropy is the loss of classifiers and language models. The intermediate quantities are the entropy and the cross-entropy:

$$\begin{gathered} H(P) = -\sum_{x\in\mathcal X} P(x)\log P(x), \\ H(P, Q) = -\sum_{x\in\mathcal X} P(x)\log Q(x). \end{gathered}$$

Notation. $P$ is the real (data, target) distribution and $Q$ the believed (model) distribution. $H(P)$ is the entropy of $X \sim P$, sometimes also written $H(X)$. For continuous distributions, lowercase $p$ and $q$ denote densities and sums become integrals; what changes for densities is noted at the end of the KL section. $\log_2$ gives bits and $\ln$ gives nats; a plain $\log$ means either, as long as one base is used throughout.

Surprise#

The construction below follows the intuitive route of Josh Starmer’s StatQuest explanation of entropy (Starmer, 2021); the formal treatment is in Cover and Thomas (2006), chapter 2.

Take two boards with ten marks each. Board A has 5 noughts and 5 crosses; board B has 9 noughts and 1 cross. Draw one mark at random. On which board is getting an X more surprising?

Figure

Where is drawing an X more surprising?

Think of surprise informally as the feeling that something should not have happened. The probabilities of drawing each mark are

$$\begin{gathered} \text{A:}\quad P(\text{O}) = \tfrac12,\;\; P(\text{X}) = \tfrac12, \\ \text{B:}\quad P(\text{O}) = \tfrac{9}{10},\;\; P(\text{X}) = \tfrac{1}{10}. \end{gathered}$$

The cross is clearly more surprising on board B, so surprise must grow as the probability falls.

First attempt: $1/p$. To compare $\tfrac12$ and $\tfrac1{10}$, flip them: $1/P(\text{X})$ is $2$ on board A and $10$ on board B. This ranks the boards correctly, and as a function of $p$ it is a decreasing curve.

Problem. Take a rigged coin that always lands heads: HHHHHHHHHH. Its two outcomes give

$$\begin{aligned} P(H) = 1 &: \quad \frac{1}{P(H)} = \frac11 = 1, \\[4pt] P(T) = 0 &: \quad \frac{1}{P(T)} = \frac10 . \end{aligned}$$

Getting heads should not surprise us at all, so the first value should be $0$. The second is not even a number.

Fix: take the logarithm.

$$\begin{aligned} \log\frac{1}{P(H)} &= \log 1 = 0, \\ \log\frac{1}{P(T)} &= \log 1 - \log 0 \quad\text{is undefined}. \end{aligned}$$

The undefined case is harmless: an outcome with probability $0$ never happens, so its surprise is never needed. This gives the definition of surprise, also called self-information:

$$s(x) = \log\frac{1}{P(x)} = -\log P(x).$$

It equals $0$ when $P(x) = 1$ and grows without bound as $P(x) \to 0$.

Figure

Surprise must vanish for a certain outcome

A biased coin#

Let $P(H) = 0.9$ and $P(T) = 0.1$. Then

$$\log_2\frac{1}{0.9} \approx 0.152, \qquad \log_2\frac{1}{0.1} \approx 3.322 .$$

Tails is much rarer than heads, so its surprise is much larger.

	Heads	Tails
Probability $P(x)$	$0.9$	$0.1$
Surprise $\log_2 \frac{1}{P(x)}$	$0.152$	$3.322$

Surprise is additive#

Now flip the coin three times and observe H H T. The flips are independent, so the probability of the sequence is $0.9 \times 0.9 \times 0.1$, and

$$\begin{aligned} s(\text{HHT}) &= \log_2\frac{1}{0.9\cdot 0.9\cdot 0.1} \\ &= -\log_2 0.9 - \log_2 0.9 - \log_2 0.1 \\ &\approx 0.152 + 0.152 + 3.322 \\ &= 3.626 \text{ bits}. \end{aligned}$$

The total surprise of a sequence is the sum of the surprises of the individual tosses. This is what the logarithm buys: it turns a product of probabilities into a sum. No other continuous function does this. Suppose $s(pq) = s(p) + s(q)$ for all $p, q \in (0, 1]$ and put $g(t) = s(e^{-t})$ for $t \ge 0$. Then $g(t + u) = g(t) + g(u)$, and the only continuous solutions of this equation are linear, $g(t) = ct$. Hence $s(p) = c\log\frac1p$. Requiring rare outcomes to be surprising makes $c > 0$, and the choice of $c$ is the choice of base. This is why logarithms appear in every information measure; Shannon proved the matching uniqueness result for entropy itself (Shannon, 1948, Theorem 2).

Figure

Probabilities multiply, surprises add

Entropy: expected surprise#

Now estimate the total surprise after 100 flips. We expect about $90$ heads and $10$ tails:

$$\begin{aligned} &\underbrace{(0.9\cdot 100)}_{\text{number of H}}\cdot \underbrace{0.152}_{\text{surprise of H}} \\ &\quad +\; (0.1\cdot 100)\cdot 3.322 \;\approx\; 46.9 \text{ bits}. \end{aligned}$$

Dividing by 100 gives the surprise per flip:

$$0.9 \cdot 0.152 + 0.1 \cdot 3.322 \approx 0.469 \text{ bits}.$$

This is the surprise we expect on average every time we flip the coin. Each probability multiplies its own surprise, which is exactly an expected value: if $S = s(X)$ is the surprise of a random outcome $X \sim P$, then $\mathbb E[S] = \sum_x P(x)\,s(x)$. The expected surprise is the entropy:

$$\begin{aligned} H(P) &= \sum_x P(x)\log\frac{1}{P(x)} \\ &= -\sum_x P(x)\log P(x), \end{aligned}$$

the quantity introduced by Claude Shannon in 1948 (Shannon, 1948).

Outcomes with $P(x) = 0$ never occur, so their terms are left out of the sum. Equivalently, we use the convention $0 \cdot \log\frac10 = 0$, which is the limit of $p\log\frac1p$ as $p \to 0$ (Cover and Thomas, 2006, §2.1). The rigged coin that always lands heads therefore has entropy $1 \cdot \log 1 = 0$: it holds no surprise at all.

Back to the boards#

$$\begin{aligned} H_A &= \tfrac12\log_2 2 + \tfrac12\log_2 2 = 1 \text{ bit}, \\ H_B &= \tfrac{9}{10}\log_2\frac{10}{9} + \tfrac{1}{10}\log_2 10 \approx 0.469 \text{ bits}. \end{aligned}$$

Board B has exactly the biased coin’s distribution, so it has the same entropy. The balanced board is less predictable: higher entropy means more uncertainty. For two outcomes no distribution has more than 1 bit of entropy, and only the uniform one reaches it; this follows from Gibbs’ inequality in the next section.

Cross-entropy: surprise under a wrong belief#

Take a coin that our model believes to be fair, ${Q = (0.5,\,0.5)},$ while in reality it is rigged, ${P = (0.99,\,0.01)}.$ We observe ten heads in a row:

	Probability of 10 heads	Surprise (nats)
Model $Q$	$0.5^{10} \approx 0.001$	$\ln 0.5^{-10} \approx 6.93$
Reality $P$	$0.99^{10} \approx 0.90$	$\ln 0.99^{-10} \approx 0.10$

Figure

Ten heads: surprising under the model, ordinary in reality

The outcome was ordinary. Our surprise is caused by believing in the wrong model.

Cross-entropy $H(P, Q)$ is the average surprise when the real distribution is $P$ while we believe in $Q$:

$$H(P, Q) = \sum_{x\in\mathcal X} \underbrace{P(x)}_{\substack{\text{how often } x \\ \text{is observed}}}\; \underbrace{\log\frac{1}{Q(x)}}_{\substack{\text{how surprised we} \\ \text{are to see it}}}$$

Figure

Reading the cross-entropy formula

No discrepancy. If $Q = P$, cross-entropy reduces to entropy: $H(P, P) = H(P)$.

Always (Gibbs’ inequality):

$$H(P, Q) \;\ge\; H(P),$$

with equality only when $Q = P$ (Cover and Thomas, 2006, Theorem 2.6.3). Believing in a wrong distribution can only increase the average surprise. The proof takes one line once the difference $H(P, Q) - H(P)$ has a name; it is given in the next section.

One consequence settles the question left open by the boards. Let $Q$ be uniform over the $|\mathcal X|$ outcomes. Then $\log\frac{1}{Q(x)} = \log|\mathcal X|$ for every $x$, so $H(P, Q) = \log|\mathcal X|$, and Gibbs’ inequality gives $H(P) \le \log|\mathcal X|$, with equality only for the uniform $P$ (Cover and Thomas, 2006, Theorem 2.6.4). For two outcomes the bound is $\log_2 2 = 1$ bit.

Asymmetry. In general $H(P, Q) \ne H(Q, P)$. Keep $P$ as the rigged coin and $Q$ as the fair one, and use one flip and natural logarithms. The first argument is always the distribution that generates the outcomes. With a fair belief and a rigged reality, and then with a rigged belief and a fair reality,

$$\begin{aligned} H(P, Q) &= 0.99\ln 2 + 0.01\ln 2 \\ &= \ln 2 \approx 0.69, \\ H(Q, P) &= 0.5\ln\frac{1}{0.99} + 0.5\ln\frac{1}{0.01} \\ &\approx 2.31 . \end{aligned}$$

In each sum the weights are the actual probabilities and the logarithms contain the believed ones. Believing that a fair coin is rigged is punished much harder: tails then occur half the time, and the rigged belief finds every one of them very surprising.

Kullback–Leibler divergence#

Cross-entropy mixes two sources of surprise: the surprise that the real distribution produces anyway, and the extra surprise caused by the wrong model. To isolate the second, subtract the entropy of the real distribution:

$$\begin{aligned} H(P, Q) - H(P) &= \sum_x P(x)\log\frac{1}{Q(x)} \\ &\quad - \sum_x P(x)\log\frac{1}{P(x)} \\ &= \sum_{x\in\mathcal X} P(x)\log\frac{P(x)}{Q(x)} \\ &= D_{\mathrm{KL}}(P \,\|\, Q). \end{aligned}$$

The KL divergence (Kullback and Leibler, 1951) is the extra surprise from using $Q$ as the model instead of $P$. The subtraction needs both terms to be finite; the sum on the right is the general definition. Its terms follow the same conventions as before. A term with $P(x) = 0$ contributes $0$. A term with $P(x) > 0$ but $Q(x) = 0$ is $P(x)\log\frac{P(x)}{0} = +\infty$, and then so is $D_{\mathrm{KL}}(P\,\|\,Q)$. So KL is finite only when $Q$ gives positive probability to every outcome to which $P$ does, that is, when $P$ is absolutely continuous with respect to $Q$ (Cover and Thomas, 2006, §2.3). The next note shows what this condition means in training.

So KL is non-negative and equals zero only when $Q = P$. It is not symmetric and does not satisfy the triangle inequality (Cover and Thomas, 2006, §2.3; an example follows below), so it is a divergence rather than a distance. For the two coins, in nats and with four decimals so that the parts add up,

$$\begin{aligned} D_{\mathrm{KL}}(P\,\|\,Q) &\approx 0.6931 - 0.0560 = 0.6371, \\ D_{\mathrm{KL}}(Q\,\|\,P) &\approx 2.3076 - 0.6931 = 1.6145 . \end{aligned}$$

Figure

Cross-entropy = entropy + KL divergence

The two boards from the start of the note give every mark positive probability, so they have a finite KL divergence in both directions, and its value depends on the direction:

$$\begin{aligned} D_{\mathrm{KL}}(A\,\|\,B) &= \tfrac12\log_2\frac{1/2}{9/10} + \tfrac12\log_2\frac{1/2}{1/10} \\ &\approx 0.737 \text{ bits},\\ D_{\mathrm{KL}}(B\,\|\,A) &= \tfrac{9}{10}\log_2\frac{9/10}{1/2} + \tfrac{1}{10}\log_2\frac{1/10}{1/2} \\ &\approx 0.531 \text{ bits}. \end{aligned}$$

As a check, $H(B, A) = H_B + D_{\mathrm{KL}}(B\,\|\,A) = 0.469 + 0.531 = 1$ bit: measuring surprise with the uniform board A costs exactly one bit per draw, whatever the true board is.

Figure

The two boards compared with KL

The same distributions show that KL breaks the triangle inequality. Identify O with heads and X with tails, and compare board A with the rigged coin $P = (0.99, 0.01)$, once directly and once through board B. Directly, $D_{\mathrm{KL}}(A\,\|\,P) \approx 2.329$ bits. Through B, $D_{\mathrm{KL}}(A\,\|\,B) + D_{\mathrm{KL}}(B\,\|\,P) \approx 0.737 + 0.208 = 0.945$ bits, which is less.

Why cross-entropy is the loss we minimize#

For the true data distribution $P$ and a model $Q_\theta$:

$$\underbrace{D_{\mathrm{KL}}(P \,\|\, Q_\theta)}_{\text{minimize w.r.t. } \theta} = \underbrace{H(P, Q_\theta)}_{\text{minimize w.r.t. } \theta} - \underbrace{H(P)}_{\substack{\text{constant: entropy} \\ \text{of the data}}}$$

• Changing the model’s parameters cannot change the entropy of the data, so $H(P)$ is a constant in the optimization.
• Nor do we need its value. For high-dimensional data such as images, estimating $H(P)$ from samples is itself a hard problem.
• So minimizing KL with respect to $\theta$ and minimizing cross-entropy have the same solution, and cross-entropy is the part we can estimate from samples. This is why classifiers and language models are trained with a cross-entropy loss. There the same argument is applied to the conditional distribution of the label (or of the next token) given the input. The target $P(\cdot \mid x)$ is then the true conditional law of the label, which we never see directly. Each training example supplies one observed label, a one-hot vector, and the average negative log-likelihood of the observed labels is a sample estimate of the conditional cross-entropy $\mathbb E_x\, H\big(P(\cdot \mid x), Q(\cdot \mid x)\big)$. Soft targets, such as label smoothing or a teacher model’s probabilities, replace the one-hot vector by another estimate of $P(\cdot \mid x)$.

Given samples $x_1, \dots, x_N$ from $P$, the cross-entropy is estimated by the average negative log-likelihood,

$$\begin{aligned} H(P, Q_\theta) &= \mathbb E_{x\sim P}\big[-\log Q_\theta(x)\big] \\ &\approx -\frac1N\sum_{i=1}^N \log Q_\theta(x_i). \end{aligned}$$

Minimizing it is maximum-likelihood estimation. For discrete outcomes the average negative log-likelihood is exactly the cross-entropy $H(\hat P, Q_\theta)$ between the empirical distribution $\hat P$ of the samples (probability $1/N$ on each $x_i$) and the model, so maximum likelihood minimizes $D_{\mathrm{KL}}(\hat P\,\|\,Q_\theta)$ (Goodfellow, Bengio and Courville, 2016, §5.5). As $N$ grows, the average converges to $H(P, Q_\theta)$ by the law of large numbers, and that differs from $D_{\mathrm{KL}}(P\,\|\,Q_\theta)$ only by the constant $H(P)$. So “minimize $D_{\mathrm{KL}}(P\,\|\,Q_\theta)$”, “minimize $H(P, Q_\theta)$” and “maximize likelihood” are three names for the same training objective: exactly for the empirical distribution, and in the limit of many samples for $P$ itself.

Later families of generative models differ mostly in how they deal with the fact that $\log Q_\theta(x)$ is hard to compute: VAEs bound it, normalizing flows compute it exactly, GANs avoid it altogether, and diffusion models bound it again, with a fixed noising process in place of a learned encoder.

Jensen–Shannon divergence#

The Jensen–Shannon divergence (Lin, 1991) uses the same building block, but it is symmetric and bounded. It compares both distributions with their mixture $M = \tfrac12(P + Q)$:

$$\begin{aligned} D_{\mathrm{JS}}(P \,\|\, Q) &= \tfrac12 D_{\mathrm{KL}}(P \,\|\, M) \\ &\quad + \tfrac12 D_{\mathrm{KL}}(Q \,\|\, M). \end{aligned}$$

Because $M(x) > 0$ wherever $P(x) > 0$ or $Q(x) > 0$, both terms are always finite. Both are non-negative, so $D_{\mathrm{JS}} \ge 0$, with equality only when $P = M = Q$. For the upper bound, note that $P(x) \le P(x) + Q(x) = 2M(x)$. Every term of $D_{\mathrm{KL}}(P\,\|\,M)$ therefore has $\log\frac{P(x)}{M(x)} \le \log 2$, so $D_{\mathrm{KL}}(P\,\|\,M) \le \log 2$, with equality only if $P(x) = 2M(x)$, that is $Q(x) = 0$, wherever $P(x) > 0$. The same holds for the second term. Hence

$$0 \;\le\; D_{\mathrm{JS}}(P \,\|\, Q) \;\le\; \ln 2 \text{ nats} = 1 \text{ bit},$$

and the maximum is reached exactly when $P$ and $Q$ do not overlap. For the two coins, $D_{\mathrm{JS}} \approx 0.193$ nats ($0.279$ bits).

JS will matter twice. In the next note it is one of the losses compared on a two-mode target. In the GAN note, the original GAN objective with an optimal discriminator turns out to equal $2\,D_{\mathrm{JS}}(P\,\|\,Q) - 2\ln 2$, with $P$ the data distribution and $Q$ the generator’s (Goodfellow et al., 2014). The saturation of JS at $\ln 2$ for non-overlapping distributions then explains why GAN training can stall (Arjovsky and Bottou, 2017).

Next#

We now have a number for how far a model $Q$ is from the data $P$, and we know that minimizing $D_{\mathrm{KL}}(P\,\|\,Q_\theta)$ is maximum likelihood. The next note puts this to work on the Gaussian model from the previous note. It trains a Gaussian $Q$ by minimizing a sample estimate of the KL, asks what the formula assumes (common support, direction), and compares what forward KL, reverse KL and JS do when one Gaussian must fit two modes. Its Notebook section describes the code, where KL and JS are estimated from samples.

References#

• C. E. Shannon. A Mathematical Theory of Communication. Bell System Technical Journal, 27(3), 379–423 and 27(4), 623–656, 1948. Theorem 2: uniqueness of the entropy formula.
• S. Kullback, R. A. Leibler. On Information and Sufficiency. Annals of Mathematical Statistics, 22(1), 1951.
• J. Lin. Divergence measures based on the Shannon entropy. IEEE Transactions on Information Theory, 37(1), 1991.
• T. M. Cover, J. A. Thomas. Elements of Information Theory, 2nd ed. Wiley, 2006. §2.1 (entropy, the convention $0\log 0 = 0$), §2.3 (relative entropy), Theorems 2.6.3 (information inequality) and 2.6.4 (maximum entropy); §8.1 and §8.5–8.6 (differential entropy and relative entropy for densities).
• I. Goodfellow, Y. Bengio, A. Courville. Deep Learning. MIT Press, 2016. §3.13 (information theory) and §5.5 (maximum likelihood and cross-entropy).
• I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, Y. Bengio. Generative adversarial nets. NeurIPS, 2014.
• M. Arjovsky, L. Bottou. Towards principled methods for training generative adversarial networks. ICLR, 2017.
• J. Starmer. Entropy (for data science) Clearly Explained!!! StatQuest, YouTube, 2021. The surprise-based route to entropy used above.