Back to the on-screen lesson ·
The divergence $D(p \| q)$, what it costs to believe a wrong model, and why it is not a distance.
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 define the relative entropy $D(p \| q)$, compute it exactly for dyadic distributions and against the uniform distribution, compute the same pair both ways round and see that the two answers differ, say which outcomes contribute and which make it infinite, sort the true statements about it from the false ones, and use it to rank competing models by the bits their errors cost.
Entropy as the average surprise under one distribution, and Jensen's inequality for the concave logarithm. This lesson asks a different question: what it costs to believe the wrong distribution, measured in bits, against the truth.
The relative entropy or Kullback-Leibler divergence $D(p \| q)$ measures how far the model $q$ is from the truth $p$. The support of $p$ is the set of outcomes it gives positive probability; only those contribute. It is called a divergence rather than a distance because it is asymmetric: $D(p \| q)$ and $D(q \| p)$ are different numbers.
The relative entropy or Kullback-Leibler divergence of $p$ from $q$ is $$D(p \| q) = \sum_x p(x) \log_2 \frac{p(x)}{q(x)},$$ with $0 \log \frac{0}{q} = 0$ and $p \log \frac{p}{0} = +\infty$. It measures how far a model $q$ is from the truth $p$, in bits: it is the expected extra surprise when you believe $q$ but $p$ is generating the data. Against the uniform $u$ on $n$ outcomes it is $\log_2 n - H(p)$, so the entropy bound is a divergence in disguise. It is not symmetric and violates the triangle inequality, so it is not a distance, but it is nonnegative and zero only for $p = q$ (Gibbs' inequality, next lesson), it is convex in the pair $(p, q)$, and it obeys a chain rule. Mutual information will be the divergence between a joint distribution and the product of its marginals.
Another way: story
A weather forecaster who believes $q$ prices each day's surprise at $\log_2 (1/q)$. The true climate is $p$. The forecaster's average surprise exceeds the best possible, $H(p)$, by exactly $D(p \| q)$: the divergence is the cost of a wrong belief, paid in bits every day.
Another way: steps
Lay the two distributions side by side, form the ratio $p/q$, take its logarithm, weight by $p$ and add. Negative terms are normal: where $q$ overestimates $p$ the surprise under $q$ is smaller than under $p$. Only the total is guaranteed to be nonnegative. For $p = (0.9, 0.1)$ against the fair coin $q = (0.5, 0.5)$:
| $x$ | $p(x)$ | $q(x)$ | $p/q$ | $\log_2 (p/q)$ | $p \log_2 (p/q)$ |
|---|---|---|---|---|---|
| heads | $0.9$ | $0.5$ | $1.8$ | $0.848$ | $0.763$ |
| tails | $0.1$ | $0.5$ | $0.2$ | $-2.322$ | $-0.232$ |
| sum | $1$ | $1$ | $D(p \| q) = 0.531$ |
Swap the roles and the answer changes:
| $x$ | $q(x)$ | $p(x)$ | $q/p$ | $\log_2 (q/p)$ | $q \log_2 (q/p)$ |
|---|---|---|---|---|---|
| heads | $0.5$ | $0.9$ | $0.556$ | $-0.848$ | $-0.424$ |
| tails | $0.5$ | $0.1$ | $5$ | $2.322$ | $1.161$ |
| sum | $1$ | $1$ | $D(q \| p) = 0.737$ |
Against the fair coin there is a shortcut: $D(p \| \text{fair}) = \sum p \log_2 p + \sum p \log_2 2 = 1 - h(p)$. The graph is a U: zero at $p = \tfrac{1}{2}$ and one full bit at the ends, where a certain outcome is maximally far from a fair coin.
When $q = u$ is uniform on $n$ outcomes, $\log_2 (p/u) = \log_2 p + \log_2 n$, so $D(p \| u) = \log_2 n - H(p)$: the divergence from the uniform is the entropy deficit. If $p$ is itself uniform on a subset of $2^m$ of the $n = 2^k$ outcomes, $H(p) = m$ and the divergence is simply $k - m$ bits, the number of bits the uniform model wastes on outcomes that never happen.
| $p$ uniform on $2^m$ of $2^k$ outcomes | $H(p)$ | $\log_2 n$ | $D(p \| u) = k - m$ |
|---|---|---|---|
| $2$ of $16$ | $1$ | $4$ | $3$ |
| $4$ of $16$ | $2$ | $4$ | $2$ |
| $8$ of $64$ | $3$ | $6$ | $3$ |
| $1$ of $2^k$ | $0$ | $k$ | $k$ |
The last row is the extreme: $p$ certain of one outcome $x_0$. Then only one term survives, $D(p \| q) = 1 \cdot \log_2 \dfrac{1}{q(x_0)}$, the surprise $q$ assigns to the thing that always happens. If $q(x_0) = 2^{-a}$ the divergence is $a$ bits; if $q(x_0) = 0$ it is $+\infty$, and no amount of data can rescue a model that called the truth impossible.
| Property | Holds for $D(p \| q)$? | Why |
|---|---|---|
| nonnegative | yes | Gibbs' inequality |
| zero only when $p = q$ | yes | equality case of Jensen |
| symmetric | no | $0.531 \ne 0.737$ |
| triangle inequality | no | so it is not a metric |
| finite | not always | $+\infty$ if $q = 0$ where $p > 0$ |
| convex in $(p, q)$ | yes | log-sum inequality |
Common mistakes
The first error is weighting by $q$ instead of $p$: the first distribution in $D(p \| q)$ is the truth, and it does the weighting, so the same pair gives two different answers depending on which way round you write it. The second is dropping the negative terms because 'a divergence is positive'; only the total is, and an outcome the model overrates really does contribute a negative term. The third is treating $D$ as a distance and expecting symmetry or a triangle inequality, neither of which holds. And an outcome with $p(x) = 0$ contributes nothing however wrong $q$ is about it, while an outcome with $q(x) = 0$ and $p(x) > 0$ makes the whole divergence infinite.
$p = (0.9, 0.1)$, $q = (0.5, 0.5)$: $D(p \| q) = 0.9 \log_2 1.8 + 0.1 \log_2 0.2 = 0.763 - 0.232 = 0.531$ bits.
Equals $1 - h(0.1)$.
The other way: $D(q \| p) = 0.5 \log_2 \frac{0.5}{0.9} + 0.5 \log_2 \frac{0.5}{0.1} = -0.424 + 1.161 = 0.737$ bits: not symmetric.
Individual terms may be negative; the sum never is.
$p = (\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \tfrac{1}{8})$ and $u$ uniform on four outcomes: $H(p) = 1.75$.
$D(p \| u) = \log_2 4 - H(p) = 2 - 1.75 = 0.25$ bits.
The shortfall from maximum entropy.
Shortcut: $D(p \| \text{fair}) = 1 - h(0.25)$.
$h(0.25) = 0.811$, so $D = 0.189$ bits.
Term by term: $0.25 \log_2 0.5 + 0.75 \log_2 1.5 = -0.25 + 0.439 = 0.189$. Same answer.
$\log_2 1.5 = \log_2 3 - 1 = 0.585$.
$p(x) = \tfrac{1}{4}$ on four outcomes, $u(x) = \tfrac{1}{16}$ on all sixteen.
Each surviving term: $\tfrac{1}{4} \log_2 \dfrac{1/4}{1/16} = \tfrac{1}{4} \log_2 4 = \tfrac{1}{2}$.
The twelve outcomes with $p = 0$ contribute nothing.
$D = 4 \cdot \tfrac{1}{2} = 2$ bits $= \log_2 16 - \log_2 4 = k - m$.
Only the first term survives: $1 \cdot \log_2 (1 / \tfrac{1}{4})$.
$D(p \| q) = 2$ bits; and $D(q \| p) = +\infty$ because $p$ gives the second outcome probability $0$.
The true distribution is $p = (\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \tfrac{1}{8})$ and a model proposes $q = (\tfrac{1}{4}, \tfrac{1}{8}, \tfrac{1}{2}, \tfrac{1}{8})$, the outcomes taken in the same order. Fill in $D(p \| q)$ and $D(q \| p)$, in bits.
| Bits | |
|---|---|
| $D(p \| q)$ | |
| $D(q \| p)$ |
Match each pair of distributions to the value of $D(p \| q)$.
| $0$ bits | $8$ bits | $1$ bit | infinite | |
|---|---|---|---|---|
| $q = p$ | ||||
| $p$ is certain of one outcome, to which $q$ gives probability $2^{-8}$ | ||||
| $p$ is uniform on two of four outcomes; $q$ is uniform on all four | ||||
| $q$ gives probability $0$ to an outcome $p$ gives positive probability |
Select every statement that is true of the relative entropy $D(p \| q)$ for all distributions $p$ and $q$ on the same set.
This task has no paper form; do it on a device.
$p$ is uniform on $8$ of the $32$ outcomes and zero elsewhere; $u$ is uniform on all $32$. Compute $D(p \| u)$ in bits.
Answer:
Tomorrow's weather is one of four kinds, and the true distribution is $p = (\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \tfrac{1}{8})$. Three forecasters publish the distributions below. Put them in order, the best model first, by the extra bits per day their forecast costs.
Number the steps in order (write the number in the box):
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Which statement about $D(p \| q)$ is correct?
You can compute a divergence either way round, and say why it is not a distance. Say in your own words which of the two distributions does the weighting in $D(p \| q)$, and what goes wrong if you swap them. Next: Gibbs' inequality, which proves the divergence is never negative, and cross-entropy, which prices a wrong model in code length.
13. Your turn: $p = (1, 0)$ and $q = (\tfrac{1}{4}, \tfrac{3}{4})$, step 2