Intuition on the Kullback–Leibler (KL) Divergence

Question

I have learned about the intuition behind the KL Divergence as how much a model distribution function differs from the theoretical/true distribution of the data. The source I am reading goes on to say that the intuitive understanding of 'distance' between these two distributions is helpful, but should not be taken literally because for two distributions $P$ and $Q$, the KL Divergence is not symmetric in $P$ and $Q$.

I am not sure how to understand the last statement, or is this where the intuition of 'distance' breaks down?

I would appreciate a simple, but insightful example.

Answer 1

Adding to the other excellent answers, an answer with another viewpoint which maybe can add some more intuition, which was asked for.

The Kullback-Leibler divergence is $$ \DeclareMathOperator{\KL}{KL} \KL(P || Q) = \int_{-\infty}^\infty p(x) \log \frac{p(x)}{q(x)} \; dx $$ If you have two hypothesis regarding which distribution is generating the data $X$, $P$ and $Q$, then $\frac{p(x)}{q(x)}$ is the likelihood ratio for testing $H_0 \colon Q$ against $H_1 \colon P$. We see that the Kullback-Leibler divergence above is then the expected value of the loglikelihood ratio under the alternative hypothesis. So, $\KL(P || Q)$ is a measure of the difficulty of this test problem, when $Q$ is the null hypothesis. So the asymmetry $\KL(P || Q) \not= \KL(Q || P)$ simply reflects the asymmetry between null and alternative hypothesis.

Let us look at this in a particular example. Let $P$ be the $t_\nu$-distribution and $Q$ the standard normal distribution (in the numerical exampe below $\nu=1$). The integral defining the divergence looks complicated, so let us simply use numerical integration in R:

    lLR_1  <-  function(x) {dt(x, 1, log=TRUE)-dnorm(x, 
                             log=TRUE)}  
    integrate(function(x) dt(x, 1)*lLR_1(x), lower=-Inf, 
                             upper=Inf)
    Error in integrate(function(x) dt(x, 1) * lLR_1(x), lower = 
         -Inf, upper = Inf) : 
      the integral is probably divergent
lLR_2  &lt;-  function(x) {-dt(x, 1, log=TRUE) + dnorm(x, 
                          log=TRUE)}  
integrate(function(x) dnorm(x)*lLR_2(x), lower=-Inf, 
       upper=Inf)
0.2592445 with absolute error &lt; 1e-07

In the first case the integral seems to diverge numerically, indicating the divergence is very large or infinite, in the second case it is small, summarizing: $$ \KL(P || Q) \approx \infty \\ \KL(Q || P) \approx 0.26 $$ The first case is verified by analytical symbolic integration in answer by @Xi'an here: What's the maximum value of Kullback-Leibler (KL) divergence.

What does this tell us, in practical terms? If the null model is a standard normal distribution but the data is generated from a $t_1$-distribution, then it is quite easy to reject the null! Data from a $t_1$-distribution do not look like normal distributed data. In the other case, the roles are switched. The null is the $t_1$ but data is normal. But normal distributed data could look like $t_1$ data, so this problem is much more difficult!

Here we have sample size $n=1$, and every data which might come from a normal distribution could as well have come from a $t_1$! Switching the roles, not, the difference comes mostly from the role of outliers.

Under the alternative distribution $t_1$ there is a rather large probability of obtaining a sample which have very small probability under the null (normal) model, giving a huge divergence. But when the alternative distribution is normal, practically all data we can get will have a moderate probability (really, density ...) under the null $t_1$ model, so the divergence is small.

This is related to my answer here: Why should we use t errors instead of normal errors?

Answer 2

A (metric) distance $D$ must be symmetric, i.e. $D(P,Q) = D(Q,P)$. But, from definition, $KL$ is not.

Example: $\Omega = \{A,B\}$, $P(A) = 0.2, P(B) = 0.8$, $Q(A) = Q(B) = 0.5$.

We have:

$$KL(P,Q) = P(A)\log \frac{P(A)}{Q(A)} + P(B) \log \frac{P(B)}{Q(B)} \approx 0.19$$

and

$$KL(Q,P) = Q(A)\log \frac{Q(A)}{P(A)} + Q(B) \log \frac{Q(B)}{P(B)} \approx 0.22$$

thus $KL(P,Q) \neq KL(Q,P)$ and therefore $KL$ is not a (metric) distance.

Answer 3

First of all, the violation of the symmetry condition is the smallest problem with Kullback-Leibler divergence. $D(P||Q)$ also violates triangle inequality. You can simply introduce the symmetric version as $$ SKL(P, Q) = D(P||Q) + D(Q||P) $$, but that's still not metric, because both $D(P||Q)$ and $SKL(P, Q)$ violates triangle inequality. To prove that simply take three biased coins A, B & C that produces much less heads than tails, e.g. coins with heads probability of: A = 0.1, B = 0.2 and C = 0.3. In both cases, regular KL divergence D or its symmetric version SKL, check they don't fullfil triangle inequality $$D(A||B) + D(B||C) \ngeqslant D(A||C)$$ $$SKL(A, B) + SKL(B, C) \ngeqslant SKL(A, C)$$ Simply use this formulas: $$ D(P||Q) = \sum\limits_{i}p_i \cdot \log(\frac{p_i}{q_i})$$ $$ SKL(P, Q) = \sum\limits_{i}(p_i - q_i) \cdot \log(\frac{p_i}{q_i})$$

$$D(A||B) = 0.1 \cdot \log(\frac{0.1}{0.2}) + 0.9 \cdot \log(\frac{0.9}{0.8}) \approx 0.0159$$ $$D(B||C) \approx 0.0112$$ $$D(A||C) \approx 0.0505$$ $$0.0159 + 0.0112 \ngeqslant 0.0505$$ $$SKL(A, B) \approx 0.0352$$ $$SKL(B, C) \approx 0.0234$$ $$SKL(A, C) \approx 0.1173$$ $$ 0.0352 + 0.0234 \ngeqslant 0.1173$$

I introduced this example in purpose. Let's imagine that you're tossing some coins, e.g. 100 times. As long as this coins are unbiased, you would simply encode tossing results with sequence of 0-1 bits, (1-head, 0-tail). In such situation when probability of head is the same as probability of tail and equal to 0.5, that's a quite effective encoding. Now, we have some biased coins, so we would rather encode more likely results with shorter code, e.g. merge groups of heads and tails and represent sequences of k heads with longer code than sequence of k tails (they are more probable). And here Kullback-Leibler divergence $D(P||Q)$ occures. If P represents the true distribution of results, and Q is only an approximation of P, then $D(P||Q)$ denotes the penalty you pay when you encode results that actually come from P distrib with encoding intended for Q (penalty in the sense of the extra bits you need to use).

If you simply need metric, use Bhattacharyya distance (of course the modified version $\sqrt{1 - [\sum\limits_{x} \sqrt{p(x)q(x)}]}$ )

Answer 4

I am tempted here to give a purely intuitive answer to your question. Rephrasing what you say, the KL divergence is a way to measure to the distance between two distributions as you would compute the distance between two data sets in a Hilbert space, but some caution should be taken.

Why? The KL divergence is not a distance as that you may use usually, such as for instance the $L_2$ norm. Indeed, it is positive and equal to zero if and only if the two distributions are equal (as in the axioms for defining a distance). But as mentioned, it is not symmetric. There are ways to circumvent this, but it makes sense for it to not be symmetric.

Indeed, the KL divergence defines the distance between a model distribution $Q$ (that you actually know) and a theoretical one $P$ such that it makes sense to handle differently $KL(P, Q)$ (the "theoretical" distance of $P$ to $Q$ assuming the model $P$) and $KL(Q, P)$ (the "empirical" distance of $P$ to $Q$ assuming the data $Q$) as they mean quite different measures.

Answer 5

The textbook Elements of Information Theory gives us an example:

For example, if we knew the true distribution p of the random variable, we could construct a code with average description length H(p). If, instead, we used the code for a distribution q, we would need H(p) + D(p||q) bits on the average to describe the random variable.

To paraphrase the above statement, we can say that if we change the information distribution(from q to p) we need D(p||q) extra bits on average to code the new distribution.

An illustration

Let me illustrate this using one application of it in natural language processing.

Consider that a large group of people, labelled B, are mediators and each of them is assigned a task to choose a noun from turkey, animal and book and transmit it to C. There is a guy name A who may send each of them an email to give them some hints. If no one in the group received the email they may raise their eyebrows and hesitate for a while considering what C needs. And the probability of each option being chosen is 1/3. Toally uniform distribution(if not, it may relate to their own preference and we just ignore such cases).

But if they are given a verb, like baste, 3/4 of them may choose turkey and 3/16 choose animal and 1/16 choose book. Then how much information in bits each of the mediators on average has obtained once they know the verb? It is:

\begin{align*} D(p(nouns|baste)||p(nouns)) &= \sum_{x\in\{turkey, animal, book\}} p(x|baste) \log_2 \frac{p(x|baste)}{p(x)} \\ &= \frac{3}{4} * \log_2 \frac{\frac{3}{4}}{\frac{1}{3}} + \frac{3}{16} * \log_2\frac{\frac{3}{16}}{\frac{1}{3}} + \frac{1}{16} * \log_2\frac{\frac{1}{16}}{\frac{1}{3}}\\ &= 0.5709 \space \space bits\\ \end{align*}

But what if the verb given is read? We may imagine that all of them would choose book with no hesitatation, then the average information gain for each mediator from the verb read is:

\begin{align*} D(p(nouns|read)||p(nouns)) &= \sum_{x\in\{book\}} p(x|read) \log_2 \frac{p(x|read)}{p(x)} \\ &= 1 * \log_2 \frac{1}{\frac{1}{3}} \\ & =1.5849 \space \space bits \\ \end{align*} We can see that the verb read can give the mediators more information. And that's what relative entropy can measure.

Let's continue our story. If C suspects that the noun may be wrong because A told him that he might have made a mistake by sending the wrong verb to the mediators. Then how much information in bits can such a piece of bad news give C?

1) if the verb given by A was baste:
\begin{align*} D(p(nouns)||p(nouns|baste)) &= \sum_{x\in\{turkey, animal, book\}} p(x) \log_2 \frac{p(x)}{p(x|baste)} \\ &= \frac{1}{3} * \log_2 \frac{\frac{1}{3}}{\frac{3}{4}} + \frac{1}{3} * \log_2\frac{\frac{1}{3}}{\frac{3}{16}} + \frac{1}{3} * \log_2\frac{\frac{1}{3}}{\frac{1}{16}}\\ &= 0.69172 \space \space bits\\ \end{align*}

2) but what if the verb was read? \begin{align*} D(p(nouns)||p(nouns|baste)) &= \sum_{x\in\{book, *, *\}} p(x) \log_2 \frac{p(x)}{p(x|baste)} \\ &= \frac{1}{3} * \log_2 \frac{\frac{1}{3}}{1} + \frac{1}{3} * \log_2\frac{\frac{1}{3}}{0} + \frac{1}{3} * \log_2\frac{\frac{1}{3}}{0}\\ &= \infty \space \space bits\\ \end{align*}

Since C never know what would the other two nouns be and any word in the vocabulary would be possible.

We can see that the KL divergence is asymmetric.

I hope I am right, and if not please comment and help correct me. Thanks in advance.