Back to the on-screen lesson ·
Why a divergence is never negative, and why no model ever codes a source more cheaply than the truth.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state Gibbs' inequality and its equality case, split the average length of a code built for the wrong model into the entropy plus the divergence, assemble the argument that the true distribution is the cheapest model there is, say what values a cross-entropy can take, and recognise the same quantity when a classifier reports it as a training loss.
The divergence $D(p \| q)$ and how to compute it, and Jensen's inequality for the concave logarithm. This lesson proves the one fact about the divergence that every later bound rests on: that it is never negative.
The cross-entropy $H(p, q) = \sum p \log_2 (1/q)$ is the average length of a code built for $q$ when the data follow $p$. Gibbs' inequality is the statement $D(p \| q) \ge 0$; read through the identity $H(p, q) = H(p) + D(p \| q)$, it says the divergence is the penalty for a wrong model, and the equality case $q = p$ is the only way to avoid it.
Gibbs' inequality says $D(p \| q) \ge 0$, with equality only when $p = q$. Proof: $-D(p \| q) = \sum p \log_2 \frac{q}{p} = E_p\!\left[\log_2 \frac{q}{p}\right] \le \log_2 E_p\!\left[\frac{q}{p}\right] = \log_2 \sum q \le 0$ by Jensen on the concave logarithm, and Jensen is strict unless $q/p$ is constant, which forces $q = p$. Rewritten, it is a statement about the cross-entropy $H(p, q) = \sum p \log_2 (1/q)$, the average code length when codeword lengths are chosen for $q$ but the data follow $p$: $$H(p, q) = H(p) + D(p \| q) \ge H(p).$$ Coding for the wrong distribution costs exactly the divergence, and the true distribution is the unique cheapest model. This single inequality proves the entropy bound, subadditivity, conditioning reduces entropy, the nonnegativity of mutual information and the source coding lower bound; the log-sum inequality is its finite-sum cousin.
Another way: picture
The graph of $\log_2 x$ with the points $q(x)/p(x)$ marked along the axis and weighted by $p(x)$. Their weighted average sits at $\sum q = 1$, where the logarithm is $0$; the weighted average of the logarithms hangs below it, by concavity. That gap is $D(p \| q)$.
Another way: steps
The whole of Gibbs' inequality rests on one fact about the logarithm: $\ln x \le x - 1$ for every $x > 0$, with equality only at $x = 1$. The line $x - 1$ is the tangent to $\ln x$ at $x = 1$, and a concave curve lies below its tangents.
Apply it with $x = q(x)/p(x)$ on the support of $p$: $$-D(p \| q) \ln 2 = \sum_x p(x) \ln \frac{q(x)}{p(x)} \le \sum_x p(x)\left(\frac{q(x)}{p(x)} - 1\right) = \sum_x q(x) - \sum_x p(x) \le 1 - 1 = 0.$$ So $D(p \| q) \ge 0$. Equality needs $\ln (q/p) = q/p - 1$ at every outcome, hence $q(x) = p(x)$ wherever $p(x) > 0$, and then $\sum q = 1$ forces $q = p$ everywhere. The Jensen version in the concept is the same argument with the tangent replaced by a chord.
A code built for $q$ gives the symbol $x$ a codeword of length $\log_2 (1/q(x))$ (lesson 8 shows such codes exist, up to rounding). If the data actually follow $p$, the average length is the cross-entropy $H(p, q) = \sum_x p(x) \log_2 (1/q(x))$. Here $p = (\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{4})$ but the code was built for $q = (\tfrac{1}{4}, \tfrac{1}{2}, \tfrac{1}{4})$:
| symbol | $p$ | $q$ | length $\log_2 (1/q)$ | $p \cdot$ length |
|---|---|---|---|---|
| a | $\tfrac{1}{2}$ | $\tfrac{1}{4}$ | $2$ | $1$ |
| b | $\tfrac{1}{4}$ | $\tfrac{1}{2}$ | $1$ | $0.25$ |
| c | $\tfrac{1}{4}$ | $\tfrac{1}{4}$ | $2$ | $0.5$ |
| average | $H(p, q) = 1.75$ |
The entropy of $p$ is $1.5$ bits, so the wrong code costs $0.25$ bits per symbol more, and indeed $D(p \| q) = \tfrac{1}{2} \log_2 2 + \tfrac{1}{4} \log_2 \tfrac{1}{2} + 0 = 0.5 - 0.25 = 0.25$. The identity $H(p, q) = H(p) + D(p \| q)$ is just algebra, $\log_2 \tfrac{1}{q} = \log_2 \tfrac{1}{p} + \log_2 \tfrac{p}{q}$, and Gibbs turns it into $H(p, q) \ge H(p)$: no model beats the truth, and the penalty for a wrong model is exactly its divergence from the truth. Two special cases the practice uses: a fair bit coded for a $q$ that gives each of its values $2^{-a}$ costs $a$ bits per symbol; a coin with bias $p$ coded with the fair-coin code (one bit per flip) costs $1 = h(p) + (1 - h(p))$, an excess of $1 - h(p)$.
Common mistakes
The first error is weighting the code lengths by $q$: the data follow $p$, so $p$ weights the lengths $\log_2 (1/q)$, and the penalty that appears is $D(p \| q)$ rather than $D(q \| p)$. The second is claiming the minimum cross-entropy is $0$; it is $H(p)$, which is $0$ only when the source is certain, because even a perfect model still has to spend the entropy. The third is reading Gibbs as a statement that can be tuned away — no clever $q$ makes the divergence negative, and a model that appears to beat the entropy has been given the answers.
$H(Y) - H(Y \mid X) = \sum p(x, y) \log_2 \dfrac{p(y \mid x)}{p(y)} = \sum p(x, y) \log_2 \dfrac{p(x, y)}{p(x) p(y)}$.
Write the difference as one sum.
That is $D(p(x, y) \| p(x) p(y)) \ge 0$ by Gibbs, with equality exactly when $X$ and $Y$ are independent.
The divergence between joint and product.
Data follow $p = (\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{4})$ but the code was built for $q = (\tfrac{1}{4}, \tfrac{1}{2}, \tfrac{1}{4})$, lengths $2, 1, 2$.
Average length $H(p, q) = \tfrac{1}{2} \cdot 2 + \tfrac{1}{4} \cdot 1 + \tfrac{1}{4} \cdot 2 = 1.75$; $H(p) = 1.5$; the penalty $0.25 = D(p \| q) = \tfrac{1}{2} \log_2 2 + \tfrac{1}{4} \log_2 \tfrac{1}{2} + 0$.
Cross-entropy equals entropy plus divergence.
The fair-coin code spends $1$ bit per flip whatever happens: $H(p, q) = 1$.
The entropy of the coin is $h(0.2) = 0.722$.
Excess $= 1 - 0.722 = 0.278$ bits per flip, which is $D(p \| \text{fair})$.
$q$ gives each of the two values $2^{-3}$; the rest of $q$ sits on symbols that never occur.
Code lengths $\log_2 8 = 3$ for both values.
$H(p, q) = \tfrac{1}{2} \cdot 3 + \tfrac{1}{2} \cdot 3 = 3$ bits, against $H(p) = 1$: the divergence is $2$ bits.
Take $q$ uniform: $H(p, q) = \sum p \log_2 n = \log_2 n$.
Gibbs: $\log_2 n = H(p, u) \ge H(p)$, equality only for $p = u$.
Data follow $p = (\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \tfrac{1}{8})$, and a code is built for the model $q = (\tfrac{1}{4}, \tfrac{1}{8}, \tfrac{1}{2}, \tfrac{1}{8})$, the outcomes in the same order. Fill in the entropy of the source, the divergence of the model from it, and the average length the code actually spends.
| Bits | |
|---|---|
| $H(p)$, the entropy | |
| $D(p \| q)$, the penalty | |
| $H(p, q)$, what the code spends |
Build the argument that no model codes a source more cheaply than the truth: $H(p, q) \ge H(p)$, with equality only when $q = p$.
This task has no paper form; do it on a device.
The source is $p = (\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \tfrac{1}{8})$, with entropy $H(p) = 1.75$ bits. As the model $q$ ranges over every distribution on those outcomes, give the set of values the cross-entropy $H(p, q)$ can take, as an interval in bits.
This task has no paper form; do it on a device.
A fair bit is coded with a code designed for a distribution $q$ that gives each of its two values probability $2^{-5}$ (the rest of $q$ sits on other symbols). What is the cross-entropy $H(p, q) = \sum p \log_2 (1/q)$ in bits?
Answer:
A classifier sorts images into two labels that occur equally often. On the images whose true label is the first, it gives the correct label probability $2^{-2}$; on the images whose true label is the second, it gives the correct label probability $2^{-5}$. Its reported cross-entropy loss is the average of $\log_2 (1/q)$ over the true label. What is that loss, in bits?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Which is Gibbs' inequality, for distributions $p$ and $q$ on the same set?
You can price a wrong model in bits and say why no model beats the truth. Say in your own words which distribution weights the code lengths in a cross-entropy, and which one supplies them. Next: mutual information, the divergence between a joint distribution and the product of its marginals.
13. Your turn: why is $H(X) \le \log_2 n$ a case of Gibbs?, step 2