What is the KL divergence KL(P||Q), and why is it not a distance metric?
answer
- expectation is taken under the first argument
- extra bits from using the wrong distribution
- zero only when the two agree
- two of the four metric axioms fail
- swap the arguments, get a different number
basics
~20 sKL(P||Q) = sum P(x) log(P(x)/Q(x)) is the cost of describing draws from P as if they came from Q. It is never negative and zero only when P equals Q, but it is asymmetric, so it is a divergence, not a metric.
solid answer
~50 sFor discrete distributions, `KL(P||Q) = sum_x P(x) * log(P(x) / Q(x))`, with expectations taken under `P`. Read it as the expected extra cost, in bits if the log is base 2, of describing draws from `P` while believing they came from `Q`. Two properties always hold: `KL(P||Q) >= 0` (Gibbs' inequality, a consequence of Jensen applied to the concave log), and it equals 0 exactly when `P = Q`. Two metric properties fail. It is not symmetric: with `P = (0.5, 0.5)` and `Q = (0.9, 0.1)`, `KL(P||Q) ≈ 0.74` bits while `KL(Q||P) ≈ 0.53` bits. And it does not satisfy the triangle inequality. It is also unbounded — infinite as soon as some outcome has `P(x) > 0` but `Q(x) = 0`. So call it a divergence and always say which argument is which.
go deeper
Be ready to state the formula, say it is zero only when the two distributions match, and know that swapping the arguments changes the answer.
Explain that the expectation is under the first argument, sketch why Gibbs' inequality makes it non-negative, and give a worked asymmetric example with actual numbers.
Show you handle the failure modes: infinite values from zero support, sensitivity to how you bin a continuous variable, and when to reach for a bounded symmetric alternative instead.
Own the reporting standard: an unbounded, direction-dependent number makes a poor dashboard threshold, so decide as a team what direction, binning and smoothing are used before anyone alerts on it.
## Definition For discrete distributions `P` and `Q` on the same outcome space, ``` KL(P||Q) = sum_x P(x) * log( P(x) / Q(x) ) ``` and for densities the sum becomes an integral. Two conventions matter: a term with `P(x) = 0` contributes 0 regardless of `Q(x)`, and a term with `P(x) > 0` and `Q(x) = 0` makes the whole thing `+infinity`. The log base sets the unit — base 2 gives bits, natural log gives nats. The expectation is taken **under P**, which is the key to reading the formula: `KL(P||Q) = E_P[ log(P(X)/Q(X)) ]`. Only regions where `P` puts mass contribute at all. If `Q` wastes probability on outcomes `P` never produces, that costs nothing directly; if `P` produces outcomes `Q` thinks are near-impossible, that costs a great deal. ## The interpretation that makes it stick Suppose data really comes from `P`, but you build your description (your code, your model, your expectations) around `Q`. Coding draws from `P` optimally would cost `H(P)` bits per draw; coding them with a scheme tuned for `Q` costs more, and the excess is exactly `KL(P||Q)`. So KL is a *regret*: the price of using the wrong distribution, measured in the same units as entropy. Zero regret means `Q` is exactly right. ## Non-negativity `KL(P||Q) >= 0` for all `P, Q`, with equality if and only if `P = Q` (everywhere `P` has mass). This is Gibbs' inequality. One route: write `-KL(P||Q) = sum_x P(x) log(Q(x)/P(x))`, and apply Jensen's inequality to the concave function `log`, giving `-KL <= log( sum_x P(x) * Q(x)/P(x) ) = log( sum_x Q(x) ) = log 1 = 0`. Strict concavity of the log gives the equality case. The practical upshot: a KL of 0 is the only "they match" value, and there is no negative side of the scale to mistake for a good fit. ## Why it is not a metric A metric `d` must satisfy four things: non-negativity, identity of indiscernibles, symmetry, and the triangle inequality. KL passes the first two and fails the last two. **Asymmetry.** `KL(P||Q) != KL(Q||P)` in general. Concretely, take a fair coin `P = (0.5, 0.5)` and a biased one `Q = (0.9, 0.1)`. Then `KL(P||Q) ≈ 0.737` bits and `KL(Q||P) ≈ 0.531` bits. The two numbers answer different questions: the first is the cost of expecting a biased coin and getting a fair one, the second is the cost of expecting a fair coin and getting a biased one. In the first direction, `P` regularly produces the outcome that `Q` calls rare (probability 0.1), and each such event is expensive; in the second, `Q`'s draws are mostly the outcome `P` considers merely ordinary. Different question, different answer. **No triangle inequality.** There exist `P, Q, R` with `KL(P||R) > KL(P||Q) + KL(Q||R)`, so you cannot chain KL values the way you chain distances, and "P is close to Q and Q is close to R" implies nothing quantitative about P and R. Because of this, the correct vocabulary is *divergence*, and the correct habit is to always say the direction out loud: "KL of the data distribution from the model", not "the KL between them". ## Unboundedness and the support condition KL is not bounded above. If there is any outcome with `P(x) > 0` and `Q(x) = 0`, the divergence is infinite: `Q` claims something impossible that `P` actually produces, and no finite amount of evidence rescues that. This is why KL needs `P` to be **absolutely continuous with respect to** `Q` — every event `P` gives positive probability, `Q` must too. The reverse is fine: `Q` may put mass where `P` has none without penalty, in that direction. ## Relatives worth naming - **Jensen-Shannon divergence**: `JS(P,Q) = 0.5*KL(P||M) + 0.5*KL(Q||M)` with `M = (P+Q)/2`. It is symmetric by construction, always finite (because `M` has support wherever either does), and bounded by 1 bit in base 2. Its square root is a genuine metric. - **Mutual information**: `I(X;Y) = KL( P(X,Y) || P(X)P(Y) )`, which is just KL applied to the joint versus the independent product. ## What interviewers listen for A weak answer says "KL is the distance between two distributions". A strong one gives the formula, names the unit, says whose expectation it is (P's), states non-negativity with equality only at `P = Q`, gives a concrete asymmetric pair of numbers, and names the infinite-KL support trap. Mentioning Jensen-Shannon as the symmetric, bounded alternative is the natural closer.
- Which of the metric axioms does KL divergence actually satisfy?Two of four. It is non-negative, and it is zero exactly when the two distributions agree — that is Gibbs' inequality with its equality case. It fails symmetry, since `KL(P||Q)` and `KL(Q||P)` are generally different numbers, and it fails the triangle inequality, so KL values cannot be chained. That is why it is called a divergence rather than a distance.
- When is KL(P||Q) infinite, and what does that mean practically?Whenever some outcome has `P(x) > 0` but `Q(x) = 0` — `P` produces something `Q` calls impossible, and the log blows up. Practically it means `Q` lacks support where the data lives. The usual responses are to widen `Q`'s support, add a small smoothing mass to every outcome, or switch to a bounded symmetric alternative such as Jensen-Shannon.
- What is the Jensen-Shannon divergence and how does it fix KL's shortcomings?`JS(P,Q) = 0.5*KL(P||M) + 0.5*KL(Q||M)` where `M = (P+Q)/2` is the mixture. Because the mixture has support wherever either distribution does, no term can be infinite, so JS is always finite and bounded by 1 bit in base 2. It is symmetric by construction, and its square root satisfies the triangle inequality, making that a true metric.
It is the surcharge for packing for the wrong climate: what it costs you depends on which climate you actually land in, so swapping the two changes the bill.
saying these in an interview costs you the question
- Calls KL the distance between two distributions
- Claims KL is symmetric or obeys the triangle inequality
- Thinks KL can be negative for a bad fit
- Ignores which argument the expectation is taken under
- Does not know KL is infinite when the second distribution lacks support