KL Divergence Foundations
KL divergence compares two probability distributions. Think of $P$ as the distribution that actually generates the data, and $Q$ as the distribution predicted by a model. KL asks a direct question:
If outcomes really come from $P$, how badly surprised would a model using $Q$ be?
If $Q$ gives high probability to the outcomes that actually happen under $P$, KL is small. If $Q$ gives low probability to outcomes that often happen under $P$, KL is large.
The formula is
$$D_{KL}(P\|Q)=\sum_i p_i\log_2\frac{p_i}{q_i}.$$Read it one outcome at a time. The term $p_i$ says how often outcome $i$ happens in the real distribution. The ratio $p_i/q_i$ says whether the model underestimates or overestimates that outcome. The logarithm turns that mismatch into a surprise penalty. The sum averages that penalty over the outcomes that actually occur.
A Tiny Weather Example
Suppose the real weather distribution is $P=(0.8,0.2)$ for sun and rain. A good model should also put about $80\%$ probability on sun and $20\%$ on rain. Compare three model guesses:
| Model distribution Q | Interpretation | KL from P to Q |
|---|---|---|
| $(0.8,0.2)$ | Matches the real distribution. | $0$ bits |
| $(0.5,0.5)$ | Too uncertain. It underestimates sunny days. | about $0.278$ bits |
| $(0.2,0.8)$ | Mostly backwards. It expects rain when sun is common. | about $1.2$ bits |
The last model is punished heavily because sunny days happen often under $P$, but the model assigns them only $20\%$ probability. KL does not just ask whether the most likely class is correct. It checks the whole probability distribution.
What Do the Bits Mean?
The unit "bits" comes from the base-2 logarithm. It is a unit of surprise, not something that requires understanding prefix codes. The coding story is optional: if a model assigns low probability to common events, it pays extra surprise. That extra average surprise is KL divergence.
This is also why KL connects to entropy and cross-entropy:
$$H(P,Q)-H(P)=D_{KL}(P\|Q).$$In plain language: cross-entropy is the model's average surprise on real data, entropy is the unavoidable uncertainty in the data itself, and KL is the extra surprise caused by using the wrong probabilities.
▶ KL as Extra Surprise
The true distribution P stays fixed. Step through model distributions Q. KL shrinks as Q stops being surprised by outcomes that are common under P.
Direction Matters
The order $D_{KL}(P\|Q)$ means "judge model $Q$ using real data from $P$." It punishes $Q$ harshly when $Q$ assigns tiny probability to events that actually occur under $P$. The reversed quantity, $D_{KL}(Q\|P)$, asks a different question: if the model generates samples from $Q$, how surprising are those samples under $P$? The next post focuses on why this reversal changes behavior.
For the weather example, take $P=(0.8,0.2)$ and $Q=(0.5,0.5)$. Reversing them gives different answers:
$$\begin{aligned} D_{KL}(P\|Q)&\approx0.278\text{ bits},\\ D_{KL}(Q\|P)&\approx0.322\text{ bits}. \end{aligned}$$Both the ratio and the probabilities used to weight it change. That is why KL is not symmetric.
KL Properties for Interviews
Say “nonnegative” rather than “always positive”: KL can be zero. Here $P$ and $Q$ are valid distributions over the same finite set of outcomes, so each contains nonnegative probabilities that add up to 1.
| Question | Answer |
|---|---|
| Positive? | Always $\geq0$. It can never be negative; this is Gibbs' inequality. |
| When zero? | Exactly when $P=Q$: every outcome has the same probability in both distributions. Otherwise KL is strictly positive, possibly infinite. |
| Symmetric? | No. Swapping $P$ and $Q$ generally changes the value. Some particular pairs can give equal values; symmetry would require equality for every pair. |
| A distance? | It is a divergence, not a distance metric. It lacks symmetry and does not generally satisfy the triangle inequality. |
| Upper limit? | No finite upper bound. KL can exceed 1 by any amount; it is not itself a probability. |
| When infinite? | If some $p_i>0$ but $q_i=0$: the model declares an outcome impossible even though it can occur under $P$. |
| Zero terms? | If $p_i=0$, that outcome contributes 0, including when $q_i=0$ too. If $p_i>0$, making $q_i$ zero instead gives the infinite case above. |
| Which units? | Base-2 logs give bits; natural logs, written $\ln$, give nats. Changing between them multiplies KL by a positive constant and preserves these properties. |
The sign and equality result are covered in Stanford's information-theory notes; the failure of symmetry and the triangle inequality is discussed in CMU's notes, Section 28.2.1.
Why Can't KL Be Less Than Zero?
An individual term can be negative. If $0<p_i<q_i$, then $p_i/q_i<1$, so $p_i\log_2(p_i/q_i)<0$. But $Q$ cannot increase every probability: its probabilities must still sum to 1. The following bound proves that the complete weighted sum cannot fall below zero.
Use natural logs for this proof. Dividing the result by the positive number $\ln2$ converts it to bits, so the sign stays the same. We need one basic logarithm inequality:
$$-\ln z\geq1-z\qquad(z>0).$$Why does that inequality hold? The difference $z-1-\ln z$ has derivative $1-1/z$: negative before $z=1$ and positive after it. Its minimum is therefore its value at 1, which is 0.
For an outcome with $p_i>0$ and $q_i>0$, substitute $z=q_i/p_i$ and multiply by the positive weight $p_i$:
$$p_i\ln\frac{p_i}{q_i}\geq p_i-q_i.$$Now add these bounds over the outcomes with positive $P$ probability. Outcomes with $p_i=0$ contribute nothing:
$$\begin{aligned} \sum_{i:p_i>0}p_i\ln\frac{p_i}{q_i} &\geq\sum_{i:p_i>0}(p_i-q_i)\\ &=1-\sum_{i:p_i>0}q_i\\ &\geq0. \end{aligned}$$The $P$ probabilities in this sum add to 1. The $Q$ probabilities over those same outcomes add to at most 1, because $Q$ may also put probability elsewhere. Therefore the last expression, and hence KL, cannot be negative.
Equality requires $q_i=p_i$ for every outcome with $p_i>0$. Those probabilities already use all of $Q$'s total mass of 1, leaving zero elsewhere too. Thus KL is zero exactly when $P=Q$. If any positive $p_i$ has $q_i=0$, KL is infinite instead, which also cannot be negative.
Why Can KL Become Infinite?
Return to the weather example: $P=(0.8,0.2)$, but suppose $Q=(1,0)$. Rain occurs 20% of the time, while the model calls it impossible. As the model's rain probability $q_{\mathrm{rain}}$ approaches zero, its rain contribution grows without bound:
$$0.2\log_2\frac{0.2}{q_{\mathrm{rain}}}\longrightarrow+\infty.$$At exactly zero, we define KL as infinite; this is not an ordinary division-by-zero calculation. On a finite outcome set, keeping $q_i>0$ wherever $p_i>0$ makes KL finite. This condition is explained in Stanford's KL examples.
If asked: why isn't KL a distance metric?
Asymmetry already disqualifies it. It also fails the triangle inequality: a metric would require the direct distance from $P$ to $R$ to be no greater than the distance via $Q$.
For a counterexample, choose $P=(1,0)$, $Q=(0.5,0.5)$, and $R=(0.25,0.75)$. In bits:
$$\begin{aligned} D_{KL}(P\|R)&=2,\\ D_{KL}(P\|Q)+D_{KL}(Q\|R)&\approx1+0.208=1.208. \end{aligned}$$The direct value is larger than the sum via $Q$, so the required bound fails.