KL divergence

Idea: The cost of a wrong model

Sessions follow $P$: $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$, $\frac{1}{8}$. A vendor’s model $Q$ says $\frac{1}{4}$, $\frac{1}{8}$, $\frac{1}{8}$, $\frac{1}{2}$.

• A code built from $Q$ spends $2$, $3$, $3$, $1$ bits
• The best code for $P$ averages $H(P)=\frac{7}{4}$
• The wrong model costs the extra bits

Example: The extra bits per session

Using the $Q$ code on sessions that follow $P$, how many extra bits do you pay per session?

1. Cross-entropy: $\frac{1}{2}\times 2+\frac{1}{4}\times 3+\frac{1}{8}\times 4=\frac{9}{4}$
2. Extra: $\frac{9}{4}-\frac{7}{4}=\frac{1}{2}$ bit

Formula: Kullback-Leibler divergence

$D_{\mathrm{KL}}(P\parallel Q)=\sum p(x){\log }_2\left(\frac{p(x)}{q(x)}\right)$

Equals H(P, Q) − H(P): the extra bits for coding the truth with the wrong model.

Idea: Never negative

Single terms can be negative, but the total never is: $D_{\mathrm{KL}}(P\parallel Q)\ge 0$.

• Zero only when $P$ and $Q$ are the same law
• No code beats the one built for the truth

Quick check: The other direction

Now suppose $Q$ is the truth. What is $D_{\mathrm{KL}}(Q\parallel P)$ in bits?

Idea: Direction matters

$\frac{1}{2}$ one way, $\frac{5}{8}$ the other: not a distance. The weights come from the first argument.

• $q(x)=0$ where $p(x)>0$: infinite
• Where $p(x)=0$ the term drops out
• So risk models keep weight on every state ever seen

Idea: Evidence per observation

$D_{\mathrm{KL}}(P\parallel Q)$ is the expected evidence for $P$ over $Q$ from one observation, in bits.

• $8$ sessions: $8\times \frac{1}{2}=4$ bits
• A likelihood ratio near $2^4=16$
• Small divergence: a long wait to tell models apart

Common mistake: Arguments in the wrong order

$D_{\mathrm{KL}}(P\parallel Q)$ and $D_{\mathrm{KL}}(Q\parallel P)$ answer different questions; one can be infinite while the other is not.

Instead The first argument supplies the weights and sits on top of the ratio.

Idea: Say it in an interview

Extra bits per message for coding the truth with the wrong model.

• Never negative
• Not symmetric
• Infinite when the model gives zero to a real event