KL Divergence

D_ KL(P | Q) ≥ 0 — Gibbs' inequality, the engine of information theory.

The idea

The KL divergence, or relative entropy, measures the cost of modelling a true distribution $P$ by a different distribution $Q$.

Compare the two outcome by outcome through the ratio of the probabilities they assign, and average the logarithm of that ratio under $P$, the distribution actually generating the data:

$D_{\mathrm{KL}}(P \| Q) = \sum_x P(x) \ln \frac{P(x)}{Q(x)},$

measured in nats with the natural logarithm and in bits with $\log_2$ in its place. The sum is the expected log-likelihood ratio under $P$: the average evidence per observation that the data came from $P$ rather than $Q$.

Two features of the definition matter. It is not symmetric — swapping $P$ and $Q$ changes which distribution does the weighting, and in general changes the value — so it is not a distance between distributions, and the name divergence records that. And if $Q(x) = 0$ at an outcome where $P(x) > 0$, that term is infinite and the whole sum is $+\infty$: a model that assigns probability zero to an event that actually occurs is penalized without limit.

Ways to work on it

• Walkthrough. Compute D_ KL between two Bernoullis and check the key properties.
• Practice. Simplify Bernoulli KL exactly for random (p, q).
• Hardest. Relate the divergence from the uniform distribution to entropy.

Builds on

• Shannon Entropy

Leads to

• Log-Sum Inequality
• Maximum Entropy Distributions
• Method of Types & Sanov's Theorem
• Mutual Information

Not sure where to start? Take the ten-question placement test.