Information theory - surprise, entropy, KL

Everything on this page is built from one number: how surprising a single outcome is. When an event of probability $p$ happens, we want a number that says how much it surprises us, or equally how much we learn from it. For certain events where $p = 1$ there should be no surprise and that number should be $0$. And a rarer event is more surprising, so that number should grow as $p$ shrinks.

There is an infinite number of decreasing functions that would respect these conditions, so we ideally need more requirements. That extra constraint appears when we deal with independent events: if two unrelated events happen, their collective surprise should be additive, as learning one should have no effect on the surprise of learning another.

Recall from probability that independent events have multiplicative probabilities $p(x, y) = p(x)\,p(y)$. So the function computing the surprise has the four following constraints:

• domain is probabilities, so $\mathbb{R}^+$
• $0$ at $1$
• increases as input decreases
• product-to-sum additivity, $f(xy) = f(x) + f(y)$

It will come as no surprise (forgive the dad joke) that this function is the negative logarithm (recall $\log(xy) = \log x + \log y$). That gives the information content or surprisal of an outcome of probability $p$,

$$I(x) = -\log p(x),$$

with the minus sign making it positive, since $\log p$ is negative for $p < 1$.

A different way to look at it

I highly recommend watching this 3Blue1Brown video about his approach to information content. I'll give a brief summary here as I found his explanations insightful.

Say a robot takes four instructions, up, down, left, right, with probabilities $\tfrac12, \tfrac14, \tfrac18, \tfrac18$, sent independently as a stream of bits. The naive code spends $2$ bits on each ($00, 01, 10, 11$). A better one varies the length: $0$ for up, $10$ for down, $110$ for left, $111$ for right. No codeword is the start of another one, which makes it a prefix code, so the receiver reads the stream with no dividers, taking bits until a codeword completes and then starting over. Its average length is

$$\tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 1.75 \text{ bits},$$

below the $2$ bits of the naive approach, because the rare instructions come up rarely enough that the one-bit code for up makes up for them.

Now look at the lengths it used: $1, 2, 3$ bits for probabilities $\tfrac12, \tfrac14, \tfrac18$, which is exactly $\log_2(1/p) = -\log_2 p$. Each halving of the probability adds one bit, since each extra bit doubles the number of codewords you can write. So information content is also the ideal number of bits to spend encoding an outcome of probability $p$: surprisal and optimal code length are the same number.

The entropy of a distribution is the average of $-\log p$ over draws from $p$ itself,

$$H(p) = \mathbb{E}_{x \sim p}\big[-\log p(x)\big] = -\sum_x p(x)\, \log p(x).$$

The reading I find most useful is a prediction penalty. Think of $-\log p(x)$ as a penalty you pay when outcome $x$ happens, set by the probability the distribution gave it: a lot if $x$ was unlikely, almost nothing if it was nearly certain. Entropy is that penalty averaged over outcomes drawn from $p$ itself. It measures how unpredictable $p$ is.

It is near zero when one outcome almost always happens, and it is large when the outcomes are spread out, since then even the truth can only assign small probabilities and pays a bigger penalty on average.

The information-theoretic way to see entropy is that it is the shortest average length when compressing a signal, i.e. your optimal compression floor. It can be seen as the true size of the data once all redundancies have been squeezed out.

I borrowed 3Blue1Brown's idea to interactively plot the entropy for a 1D distribution below. We give each outcome a block whose width is its probability $p_i$ and whose height is its information content $-\log_2 p_i$. Then the area of that block is exactly its contribution $p_i(-\log_2 p_i)$, and the sum of all the blocks' areas is the distribution's entropy $H(p)$.

What is interesting is that unlike probabilities it does not have to sum to a fixed number. If you add more outcomes, the total area grows as new information is available. If you skew the distribution the total entropy will also change. Play with it and try to guess, for a fixed number of events, which distribution leads to the maximum (we know the min is just when there is a single event, a.k.a. no surprise). We derive the max for both the discrete and continuous case below.

Discrete case maximum

Maximize $H(p) = -\sum_i p_i \log p_i$ over $N$ outcomes, subject to the single constraint that the probabilities sum to one, $\sum_i p_i = 1$. Formally,

$$\max_{p_1, \dots, p_N} \; -\sum_i p_i \log p_i \quad \text{subject to} \quad \sum_i p_i = 1.$$

We can solve this using the Lagrangian,

$$\mathcal{L}(p, \lambda) = -\sum_i p_i \log p_i + \lambda\Big(\sum_i p_i - 1\Big),$$

and setting $\partial \mathcal{L} / \partial p_i = -\log p_i - 1 + \lambda = 0$ gives $\log p_i = \lambda - 1$, the same value for every $i$. So all the $p_i$ are equal, which forces $p_i = 1/N$. This is the uniform distribution! Its total entropy is $\log(N)$.

Continuous case maximum

We can do the same but on the real line this time. We want to maximize the differential entropy $H(p) = -\int p \log p \, dx$ over densities with a fixed mean $\mu$ and variance $\sigma^2$. Formally,

$$\max_{p} \; -\int p \log p \, dx \quad \text{subject to} \quad \int p \, dx = 1, \;\; \int x\, p \, dx = \mu, \;\; \int (x - \mu)^2 p \, dx = \sigma^2.$$

The stationarity condition is now

$$-\log p(x) - 1 + \lambda_0 + \lambda_1 x + \lambda_2 (x - \mu)^2 = 0,$$

so $p(x) = \exp\!\big(\lambda_0 - 1 + \lambda_1 x + \lambda_2 (x - \mu)^2\big)$, the exponential of a quadratic. After matching the constraints we get $p(x) = \tfrac{1}{\sqrt{2\pi\sigma^2}}\, e^{-(x - \mu)^2 / (2\sigma^2)}$, the Gaussian distribution! So among all distributions with a given variance, the Gaussian is the maximum-entropy choice, the one that assumes the least, which is part of why it shows up everywhere. This kinda blew my mind the first time I realized.

Cross-entropy can be seen as the same prediction penalty mentioned above, except this time the penalty $-\log q(x)$ is dictated by a different distribution $q$ than the one the outcomes are actually drawn from,

$$H(p, q) = \mathbb{E}_{x \sim p}\big[-\log q(x)\big] = -\sum_x p(x)\, \log q(x).$$

In other words, it is the average penalty your model $q$ pays when it is scored against outcomes that really come from $p$. It bottoms out exactly when $q$ matches $p$, and the floor it lands on is the entropy $H(p)$ from the last section, so $H(p, q) \ge H(p)$ with equality only when $q = p$. We will accept this fact for now and see in the next section why that is the case exactly.

It is also not symmetric. The cross-entropy is largest when $q$ is not confident about high-likelihood events, $q(x_i) \ll p(x_i)$, while the opposite, $q(x_i) \gg p(x_i)$, leads to a small penalty instead. This falls out of the equation but encodes a sensible principle: since we are averaging over $p$, it is $p$ that decides what counts as a bad error. So $q$ is penalized heavily for failing to cover the outcomes $p$ produces often, but pays almost nothing for spreading probability onto outcomes $p$ rarely produces. The asymmetry also means the two orderings disagree in general,

$$H(p, q) \neq H(q, p).$$

I encourage you to take a look at the interactive plot below, it should help make all this clearer.

As a little side note related to the compression approach: building the model $q$ that minimizes cross-entropy is the same as building the best compressor for the data drawn from $p$.

We are now ready for a quantity that is ubiquitous in ML, and that the buildup so far should make easy to grasp. The Kullback-Leibler divergence is the gap between the cross-entropy and the entropy we described above,

$$D_{\mathrm{KL}}(p \,\|\, q) = H(p, q) - H(p) = \sum_x p(x)\, \log \frac{p(x)}{q(x)}.$$

Re-arranging it as $H(p,q) = H(p) + D_{\mathrm{KL}}(p \,\|\, q)$ shows clearly that the cross-entropy is the unavoidable floor $H(p)$ plus a penalty $D_{\mathrm{KL}}$ that is exactly how wrong $q$ is. Below, the dashed outline is the true $p$ and the solid bars represent the $q$ distribution. The stacked bar on the right is that same equation: a fixed teal floor $H(p)$ with the amber KL penalty stacked on top, adding up to the cross-entropy cost $H(p,q)$.

Going back to compression: $H(p)$ is the best code length for data from $p$, and $H(p,q)$ is what you pay if you code it with $q$'s code instead. So the KL is just the extra bits you waste using the wrong code.

We can bound the KL with Jensen's inequality to come up with two important characteristics. Flip the ratio inside so the log faces the right way, then use that $\log$ is concave to pull the expectation inside,

$$-D_{\mathrm{KL}}(p \,\|\, q) = \sum_x p(x)\, \log \frac{q(x)}{p(x)} = \mathbb{E}_{x \sim p}\!\left[\log \frac{q(x)}{p(x)}\right] \le \log\, \mathbb{E}_{x \sim p}\!\left[\frac{q(x)}{p(x)}\right].$$

The expectation on the right is $\sum_x p(x)\, \frac{q(x)}{p(x)} = \sum_x q(x) = 1$, and $\log 1 = 0$. So $-D_{\mathrm{KL}} \le 0$, which is $D_{\mathrm{KL}}(p \,\|\, q) \ge 0$. Jensen is tight only when the thing inside is constant, here when $q(x)/p(x)$ is the same for all $x$, which given that both sum to one means $q = p$. So as a summary,

• $D_{\mathrm{KL}}(p \,\|\, q) \ge 0$,
• $D_{\mathrm{KL}}(p \,\|\, q) = 0$ when $q = p$.

Which proves the point we made above regarding $H(p,q) \ge H(p)$, with equality when $p = q$.

The KL inherits the asymmetry of the cross-entropy it is built from, for the same reason. In practice, when $q$ is a distribution we are trying to shape, the two asymmetric orderings of the KL each get a name.

• The forward KL $D_{\mathrm{KL}}(p \,\|\, q)$ averages over the true $p$, so it penalizes $q$ for being small wherever $p$ has mass, which makes a fitted $q$ stretch to cover every mode of $p$.
• The reverse KL $D_{\mathrm{KL}}(q \,\|\, p)$ averages over $q$, so it penalizes $q$ for putting mass where $p$ has none, which makes $q$ collapse onto a single mode instead.

Which one you minimize decides whether your model spreads out or commits to one mode, and that choice comes up a lot in variational inference and in RL. This is illustrated below.

As we have seen, KL offers a lot of practical advantages but is not a proper metric. Instead, when you need a proper distance between distributions (generally for more theoretic work), the total variation distance (TV) is preferred. It is half the total disagreement in probability mass,

$$D_{\mathrm{TV}}(p, q) = \frac{1}{2} \sum_x \big| p(x) - q(x) \big|.$$

It has a second form, which is the largest gap between the probabilities the two distributions assign to any single event $A$,

$$D_{\mathrm{TV}}(p, q) = \sup_A \big| p(A) - q(A) \big|.$$

Total variation lives in $[0, 1]$, it is symmetric, and it obeys the triangle inequality, so unlike KL it is a genuine metric.

Suppose the distribution is parametrized, $p_\theta(x)$, and ask the question: if I nudge the parameters from $\theta$ to $\theta + \delta$, how much does the distribution actually move? KL is the natural way to measure that move, so look at $D_{\mathrm{KL}}(p_\theta \,\|\, p_{\theta + \delta})$ as a function of the small step $\delta$ and Taylor expand it around $\delta = 0$. This kind of local approximation is very common in optimization (trust regions, Newton and quasi-Newton methods, natural gradients), so you will often see it mentioned in optimization-based algorithms (TRPO, PPO, the natural policy gradient, and others).

Write the log-likelihood $\ell_\theta(x) = \log p_\theta(x)$ and its gradient, the score, $s_\theta(x) = \nabla_\theta \log p_\theta(x)$. Going back to the definition $D_{\mathrm{KL}}(p \,\|\, q) = \mathbb{E}_{x \sim p}\big[\log \tfrac{p(x)}{q(x)}\big]$ and splitting the log-ratio into a difference of logs, the divergence here is just an expectation of $\ell_\theta - \ell_{\theta + \delta}$ under the fixed $p_\theta$,

$$D_{\mathrm{KL}}(p_\theta \,\|\, p_{\theta + \delta}) = \mathbb{E}_{x \sim p_\theta}\big[\, \ell_\theta(x) - \ell_{\theta + \delta}(x) \,\big].$$

Now Taylor expand this in the small step $\delta$ around $\delta = 0$,

$$D_{\mathrm{KL}}(p_\theta \,\|\, p_{\theta + \delta}) = D_{\mathrm{KL}}\big|_{\delta = 0} + \big(\nabla_\delta D_{\mathrm{KL}}\big|_{\delta = 0}\big)^\top \delta + \tfrac{1}{2}\, \delta^\top \big(\nabla_\delta^2 D_{\mathrm{KL}}\big|_{\delta = 0}\big)\, \delta + O(\|\delta\|^3),$$

and read off the terms one at a time. The zeroth-order term is the value at $\delta = 0$, which is zero since KL of a distribution with itself is zero. For the first-order term, note that the expectation is taken under the fixed $p_\theta$ and $\ell_\theta(x)$ does not depend on $\delta$, so only the $-\ell_{\theta + \delta}(x)$ piece survives the derivative. Since it depends on $\delta$ only through the sum $\theta + \delta$, its $\delta$-gradient at $\delta = 0$ is just the score $\nabla_\theta \log p_\theta(x)$, giving

$$\nabla_\delta\, D_{\mathrm{KL}}\big|_{\delta = 0} = -\,\mathbb{E}_{x \sim p_\theta}\big[\nabla_\delta\, \ell_{\theta + \delta}(x)\big|_{\delta = 0}\big] = -\,\mathbb{E}_{x \sim p_\theta}\big[\nabla_\theta \log p_\theta(x)\big] = 0,$$

because the expected score is zero. The gradient vanishing makes sense: KL is non-negative with a minimum at $\delta = 0$, so it has to be flat there. The second-order term however does not vanish,

$$\nabla_\delta^2\, D_{\mathrm{KL}}\big|_{\delta = 0} = -\,\mathbb{E}_{x \sim p_\theta}\big[\nabla_\theta^2 \log p_\theta(x)\big].$$

Now rewrite that Hessian of the log in terms of the score. Starting from $\nabla^2 \log p = \nabla\!\big(\nabla p / p\big)$ and applying the quotient rule,

$$\nabla_\theta^2 \log p_\theta = \frac{\nabla_\theta^2 p_\theta}{p_\theta} - \frac{\nabla_\theta p_\theta\, \nabla_\theta p_\theta^\top}{p_\theta^2} = \frac{\nabla_\theta^2 p_\theta}{p_\theta} - s_\theta\, s_\theta^\top.$$

Take the expectation under $p_\theta$. The first piece integrates away, because the $p_\theta$ in the denominator cancels the weighting and we can pull the derivatives out of the integral,

$$\mathbb{E}_{x \sim p_\theta}\!\left[\frac{\nabla_\theta^2 p_\theta}{p_\theta}\right] = \int \nabla_\theta^2 p_\theta(x)\, dx = \nabla_\theta^2 \int p_\theta(x)\, dx = \nabla_\theta^2\, 1 = 0.$$

So the expected Hessian of the log is the negative of the score outer product, $\mathbb{E}[\nabla_\theta^2 \log p_\theta] = -\,\mathbb{E}[s_\theta s_\theta^\top]$. That outer product is the definition of the Fisher information matrix,

$$F(\theta) = \mathbb{E}_{x \sim p_\theta}\big[\nabla_\theta \log p_\theta(x)\, \nabla_\theta \log p_\theta(x)^\top\big] = -\,\mathbb{E}_{x \sim p_\theta}\big[\nabla_\theta^2 \log p_\theta(x)\big].$$

Putting the pieces back into the Taylor expansion, the second-order term is $F$ and the KL between the two nearby distributions $p_\theta$ and $p_{\theta + \delta}$ is a quadratic form in $F$,

$$D_{\mathrm{KL}}(p_\theta \,\|\, p_{\theta + \delta}) \approx \frac{1}{2}\, \delta^\top F(\theta)\, \delta.$$