Entropy, cross-entropy and KL divergence

Worked solutions

Problem 1

1. $\dfrac{d}{dp}\big[-p\log p\big] = -\log p - 1$.Product rule: $p$ differentiates to $1$, and $p\cdot\frac1p = 1$.
2. $\dfrac{d}{dp}\big[-(1 - p)\log(1 - p)\big] = \log(1 - p) + 1$.The same derivative at $1 - p$, times the inner derivative $-1$, which flips both signs.
3. $H'(p) = \log(1 - p) - \log p = \log\dfrac{1 - p}{p}$.Add steps 1 and 2; the $-1$ and $+1$ cancel.
4. $H'(p) > 0$ for $p < \tfrac12$, $H'(p) = 0$ at $p = \tfrac12$, and $H'(p) < 0$ for $p > \tfrac12$.$\log t > 0$ exactly when $t > 1$, and $(1 - p)/p > 1$ exactly when $p < \tfrac12$. So $H$ rises and then falls, and its one stationary point is the maximum.
5. $H(\tfrac12) = -\tfrac12\log\tfrac12 - \tfrac12\log\tfrac12 = \log 2$.Both terms are equal.
6. $H'(p) = \log\dfrac{1 - p}{p}$; the maximum is at $p = \tfrac12$, where $H = \ln 2 \approx 0.693$ nats $= 1$ bitDividing by $\ln 2$ converts nats to bits, because $\log_2 t = \ln t/\ln 2$. A fair coin is the most uncertain coin, and one flip carries exactly one bit.

Problem 2

1. $\mathcal{L}(p, \lambda) = -\sum_i p_i\log p_i + \lambda\big(\sum_i p_i - 1\big)$.The constraint $\sum_i p_i = 1$ enters with a multiplier. The constraints $p_i \ge 0$ can be left out: $\partial H/\partial p_i = -\log p_i - 1 \to +\infty$ as $p_i \to 0^+$, so a maximiser never sits on that boundary.
2. $\partial\mathcal{L}/\partial p_i = -\log p_i - 1 + \lambda = 0$, so $p_i = e^{\lambda - 1}$.Only the $i$-th term of each sum contains $p_i$. The right-hand side is the same for every $i$, so all the $p_i$ are equal.
3. $\sum_i p_i = Ke^{\lambda - 1} = 1$, so $p_i = 1/K$, and $H(u) = -\sum_i \tfrac1K\log\tfrac1K = \log K$.The constraint fixes the common value.
4. $\operatorname{KL}(p\,\|\,u) = \sum_i p_i\log(Kp_i) = \log K\sum_i p_i + \sum_i p_i\log p_i = \log K - H(p)$.$p_i/u_i = Kp_i$, the log of a product is a sum of logs, and $\sum_i p_i = 1$.
5. $p = u$, $p_i = 1/K$, with maximum $H(u) = \log K$; for every $p$, $H(p) = \log K - \operatorname{KL}(p\,\|\,u) \le \log K$$\operatorname{KL} \ge 0$ with equality only when the two distributions are equal (Problem 5), so step 4 bounds every entropy by $\log K$, with equality only at $p = u$. No second-derivative test is needed.

Problem 3

1. $H(p) = \tfrac12\cdot 1 + \tfrac14\cdot 2 + \tfrac18\cdot 3 + \tfrac18\cdot 3 = \tfrac74$ bits.Each probability is a power of $2$, and $-\log_2 2^{-k} = k$.
2. $H(p) = \tfrac74\ln 2 \approx 1.213$ nats.$\ln t = \ln 2\cdot\log_2 t$, so every term, and the sum, scales by $\ln 2$.
3. Perplexity $= 2^{7/4} = e^{(7/4)\ln 2} \approx 3.364$.The base of the exponential must match the unit of $H$: $2$ for bits, $e$ for nats. Both give the same number. It lies between $2$ and $4$: the distribution is as uncertain as a fair choice among about $3.4$ outcomes.
4. The mean negative log-likelihood is the cross-entropy between the test data and the model, in nats, so the perplexity is $e^{2.3}$.Problem 10 shows the mean negative log-likelihood is a cross-entropy; the unit is nats because the loss used $\ln$.
5. $H(p) = \tfrac74$ bits $= \tfrac74\ln 2 \approx 1.213$ nats; perplexity $2^{7/4} \approx 3.364$; a mean NLL of $2.3$ nats gives perplexity $e^{2.3} \approx 9.97$The model is, on average, as unsure of the next token as a uniform choice among about ten.

Problem 4

1. $\operatorname{KL}(p\,\|\,q) = \sum_i p_i\log p_i - \sum_i p_i\log q_i = -H(p) + H(p, q)$.$\log(p_i/q_i) = \log p_i - \log q_i$, and each sum is one of the definitions.
2. $H(p, q) = H(p) + \operatorname{KL}(p\,\|\,q)$.Rearrange step 1.
3. $H(p)$ does not depend on $q$, so minimising $H(p, q)$ over $q$ is minimising $\operatorname{KL}(p\,\|\,q)$, and the minimum is $H(p)$, at $q = p$.$\operatorname{KL}(p\,\|\,q) \ge 0$, with equality only at $q = p$ (Problem 5).
4. $H(p, q) = -\sum_i\big[(1 - \varepsilon)y_i + \tfrac{\varepsilon}{K}\big]\log q_i = -(1 - \varepsilon)\log q_c - \tfrac{\varepsilon}{K}\sum_i\log q_i$.Cross-entropy is linear in its first argument, and the one-hot $y$ picks out the term $i = c$.
5. $H(p, q) = H(p) + \operatorname{KL}(p\,\|\,q)$; with label smoothing $H(p, q) = -(1 - \varepsilon)\log q_c - \tfrac{\varepsilon}{K}\sum_i\log q_i$, minimised at $q = p$ with value $H(p) > 0$The second term penalises any class whose probability goes to $0$, which is how smoothing stops the logits growing without bound. Because $p$ is not one-hot, $H(p) > 0$: the loss has a floor above zero (the last mistake below).

Problem 5

1. $\log t \le t - 1$ for every $t > 0$, with equality only at $t = 1$.$f(t) = t - 1 - \log t$ has $f'(t) = 1 - 1/t$, negative for $t < 1$ and positive for $t > 1$, so its minimum is $f(1) = 0$.
2. Let $S = \{i : p_i > 0\}$. If $q_i = 0$ for some $i \in S$, then $\operatorname{KL}(p\,\|\,q) = +\infty > 0$. Otherwise $-\operatorname{KL}(p\,\|\,q) = \sum_{i \in S} p_i\log\dfrac{q_i}{p_i}$.Terms with $p_i = 0$ are $0$ by convention, and $-\log(p_i/q_i) = \log(q_i/p_i)$.
3. $\sum_{i \in S} p_i\log\dfrac{q_i}{p_i} \le \sum_{i \in S} p_i\Big(\dfrac{q_i}{p_i} - 1\Big) = \sum_{i \in S} q_i - 1$.Step 1 with $t = q_i/p_i > 0$, multiplied by the positive weight $p_i$; then $\sum_{i \in S} p_i = 1$.
4. $\sum_{i \in S} q_i \le \sum_i q_i = 1$, so $-\operatorname{KL}(p\,\|\,q) \le 0$.Leaving out terms of a sum of non-negative numbers can only make it smaller.
5. Equality needs $q_i/p_i = 1$ for every $i \in S$ (step 3) and $\sum_{i \in S} q_i = 1$ (step 4), so $q_i = p_i$ on $S$ and $q_i = 0 = p_i$ off it.The equality case of step 1 applies term by term, because every weight $p_i$ in step 3 is positive.
6. $\operatorname{KL}(p\,\|\,q) \ge 0$ for all $p, q$, with equality if and only if $q = p$This is Gibbs' inequality. It is what makes $H(p)$ the floor of the cross-entropy (Problem 4), $\log K$ the ceiling of the entropy (Problem 2) and the empirical distribution the maximum-likelihood fit (Problem 10).

Problem 6

1. $\operatorname{KL}(p\,\|\,q) = \tfrac12\log\dfrac{1/2}{9/10} + \tfrac12\log\dfrac{1/2}{1/10} = \tfrac12\log\tfrac59 + \tfrac12\log 5 = \tfrac12\log\tfrac{25}{9} = \log\tfrac53$.The definition, then $\tfrac12(\log a + \log b) = \tfrac12\log ab$ and $\tfrac12\log(25/9) = \log(5/3)$.
2. $\operatorname{KL}(q\,\|\,p) = \tfrac{9}{10}\log\dfrac{9/10}{1/2} + \tfrac{1}{10}\log\dfrac{1/10}{1/2} = 0.9\log 1.8 - 0.1\log 5$.The weights now come from $q$, and $\log(1/5) = -\log 5$.
3. $\operatorname{KL}(p\,\|\,q) = \ln\tfrac53 \approx 0.511$; $\operatorname{KL}(q\,\|\,p) = 0.9\ln 1.8 - 0.1\ln 5 \approx 0.368$The two differ, so KL is not symmetric and not a distance. The larger one weights by $p$, which puts half its mass on an outcome $q$ gives only $\tfrac1{10}$: KL is large when the first distribution is often surprised by the second.

Problem 7

1. $\operatorname{KL}(p\,\|\,q_A) = +\infty$.Outcome $3$ has $p_3 = \tfrac12 > 0$ and $q_{A,3} = 0$, so its term is $\tfrac12\log(\tfrac12/0) = +\infty$.
2. $\operatorname{KL}(p\,\|\,q_B) = \tfrac12\log\tfrac{1/2}{1/3} + 0 + \tfrac12\log\tfrac{1/2}{1/3} = \log\tfrac32 \approx 0.405$.The middle term has $p_2 = 0$ and is $0$ by convention.
3. $\operatorname{KL}(q_A\,\|\,p) = 1\cdot\log\dfrac{1}{1/2} = \log 2 \approx 0.693$.Now the weights are $q_A$'s; the terms with $q_{A,i} = 0$ vanish.
4. $\operatorname{KL}(q_B\,\|\,p) = +\infty$.Outcome $2$ has $q_{B,2} = \tfrac13 > 0$ and $p_2 = 0$.
5. $\operatorname{KL}(p\,\|\,q_A) = \infty$, $\operatorname{KL}(p\,\|\,q_B) = \ln\tfrac32$; $\operatorname{KL}(q_A\,\|\,p) = \ln 2$, $\operatorname{KL}(q_B\,\|\,p) = \infty$: the forward KL prefers the covering $q_B$, the reverse KL the single-mode $q_A$$\operatorname{KL}(p\,\|\,q)$ is infinite when $q$ misses mass that $p$ has, so minimising it over $q$ spreads $q$ out (mass-covering). $\operatorname{KL}(q\,\|\,p)$ is infinite when $q$ puts mass where $p$ has none, so minimising it shrinks $q$ onto one mode (mode-seeking). Maximum likelihood minimises the forward direction (Problem 10); variational inference, including the VAE, minimises the reverse.

Problem 8

1. $\log p(x) = -\tfrac12\log(2\pi\sigma_1^2) - \dfrac{(x - \mu_1)^2}{2\sigma_1^2}$, and likewise for $q$.The log of the density in the definitions.
2. $\log p(x) - \log q(x) = \log\dfrac{\sigma_2}{\sigma_1} - \dfrac{(x - \mu_1)^2}{2\sigma_1^2} + \dfrac{(x - \mu_2)^2}{2\sigma_2^2}$.The $2\pi$ cancels, and $-\tfrac12\log\sigma_1^2 + \tfrac12\log\sigma_2^2 = \log(\sigma_2/\sigma_1)$.
3. $\mathbb{E}_p\big[(x - \mu_1)^2\big] = \sigma_1^2$.The definition of the variance of $p$.
4. $\mathbb{E}_p\big[(x - \mu_2)^2\big] = \sigma_1^2 + (\mu_1 - \mu_2)^2$.Write $x - \mu_2 = (x - \mu_1) + (\mu_1 - \mu_2)$ and expand: the cross term is $2(\mu_1 - \mu_2)\,\mathbb{E}_p[x - \mu_1] = 0$.
5. $\operatorname{KL}(p\,\|\,q) = \mathbb{E}_p[\log p(x) - \log q(x)] = \log\dfrac{\sigma_2}{\sigma_1} - \dfrac{\sigma_1^2}{2\sigma_1^2} + \dfrac{\sigma_1^2 + (\mu_1 - \mu_2)^2}{2\sigma_2^2}$.KL is the expectation under $p$ of the log-ratio; expectation is linear, so steps 3 and 4 apply term by term.
6. $\operatorname{KL}(p\,\|\,q) = \ln\dfrac{\sigma_2}{\sigma_1} + \dfrac{\sigma_1^2 + (\mu_1 - \mu_2)^2}{2\sigma_2^2} - \dfrac12$Sanity check: with $\mu_1 = \mu_2$ and $\sigma_1 = \sigma_2$ it is $0 + \tfrac12 - \tfrac12 = 0$. The mean difference is measured in units of $q$'s spread, $\sigma_2$, which is again not symmetric.

Problem 9

1. Both densities are products over coordinates, so $\log q(x) - \log p_0(x) = \sum_j\big[\log q_j(x_j) - \log p_{0}(x_j)\big]$, and the KL is $\sum_j \operatorname{KL}\big(\mathcal{N}(\mu_j, \sigma_j^2)\,\|\,\mathcal{N}(0, 1)\big)$.A diagonal covariance makes the coordinates independent, the log of a product is a sum, and the expectation of each term involves only $x_j$, whose distribution under $q$ is $\mathcal{N}(\mu_j, \sigma_j^2)$.
2. Each term is $-\log\sigma_j + \tfrac12(\sigma_j^2 + \mu_j^2) - \tfrac12$.Problem 8 with $\mu_1 = \mu_j$, $\sigma_1 = \sigma_j$, $\mu_2 = 0$, $\sigma_2 = 1$.
3. $-\log\sigma_j = -\tfrac12\log\sigma_j^2 = -\tfrac12 s_j$, and $\sigma_j^2 = e^{s_j}$.Rewrite in the variable the encoder outputs.
4. $\operatorname{KL} = \tfrac12\sum_j\big(\mu_j^2 + e^{s_j} - s_j - 1\big)$.Steps 2 and 3, summed over $j$.
5. $\partial\operatorname{KL}/\partial\mu_j = \mu_j$ and $\partial\operatorname{KL}/\partial s_j = \tfrac12(e^{s_j} - 1)$.Only the $j$-th term contains $\mu_j$ or $s_j$; $\tfrac12\mu_j^2$ differentiates to $\mu_j$, and $\tfrac12(e^{s_j} - s_j)$ to $\tfrac12(e^{s_j} - 1)$.
6. $\operatorname{KL} = \tfrac12\sum_j(\mu_j^2 + e^{s_j} - s_j - 1)$; $\nabla_\mu\operatorname{KL} = \mu$ and $\partial\operatorname{KL}/\partial s_j = \tfrac12(e^{s_j} - 1) = \tfrac12(\sigma_j^2 - 1)$Both gradients vanish exactly at $\mu = 0$, $\sigma^2 = \mathbf{1}$, the prior. Outputting $s = \log\sigma^2$ rather than $\sigma^2$ keeps the variance positive with no constraint on the network.

Problem 10

1. $\dfrac1N\sum_{n=1}^{N} -\log q_{x_n} = \sum_{i=1}^{K}\dfrac{n_i}{N}\,(-\log q_i)$.Group the terms by outcome: the term $-\log q_i$ appears once for each of the $n_i$ data points equal to $i$.
2. $= H(\hat p, q) = H(\hat p) + \operatorname{KL}(\hat p\,\|\,q)$.The definition of cross-entropy with $\hat p_i = n_i/N$, then Problem 4.
3. $H(\hat p)$ does not depend on $q$, and $\operatorname{KL}(\hat p\,\|\,q) \ge 0$ with equality only at $q = \hat p$.Problem 5. Maximising the likelihood is minimising the mean negative log-likelihood, because $\log$ is increasing and $1/N > 0$.
4. Mean NLL $= H(\hat p, q) = H(\hat p) + \operatorname{KL}(\hat p\,\|\,q)$; it is minimised at $q_i = n_i/N$, where it equals $H(\hat p)$The maximum-likelihood page reaches the same estimate with a Lagrange multiplier. For a model family $q_\theta$ that cannot reach $\hat p$, step 2 still holds: maximum likelihood picks the $\theta$ minimising the forward divergence $\operatorname{KL}(\hat p\,\|\,q_\theta)$.