13
$\begingroup$

As known the Kullback-Leibler Divergence:

$$\operatorname{KL}=\sum_{i=1}^n \ln(\frac{P(i)}{Q(i)})P(i)$$

is not symmetric. I would like to know how this can be seen from the formula. I am aware that I could just try it out with exchaning Q and P for some special case, but I would like to know the mathematical reason behind it. Also, is actually here "i" the random variable?

Thanks a lot Miau

$\endgroup$
  • $\begingroup$ Note that after expanding the sum, "$P$" appear in the formula one more time than "$Q$" does. Also, "$Q$" is in the denominator while "$P$" isn't. $\endgroup$ – alancalvitti Jan 30 '13 at 0:20
  • $\begingroup$ noted, thanks ! $\endgroup$ – MiauPiau Feb 6 '13 at 20:37
16
$\begingroup$

In addition to the algebraic reason that Robert Israel gave, there's a very nice "moral reason" that the Kullback-Leibler divergence is not symmetric. Roughly speaking, it's because you should think of the two arguments of the KL divergence as different kinds of things: the first argument is empirical data, and the second argument is a model you're comparing the data to. Here's how it works.

Take a bunch of independent random variables $X_1, \ldots, X_n$ whose possible values lie in a finite set.* Say these variables are identically distributed, with $\operatorname{Pr}(X_i = x) = p_x$. Let $F_{n,x}$ be the number of variables whose values are equal to $x$. The list $F_n$ is a random variable, often called the "empirical frequency distribution" of the $X_i$. What does $F_n$ look like when $n$ is very large?

More specifically, let's try to estimate the probabilities of the possible values of $F_n$. Since the set of possible values is different for different $n$, take a sequence of frequency distributions $f_1, f_2, f_3, \ldots$ approaching a fixed frequency distribution $f$. It turns out** that $$\lim_{n \to \infty} \tfrac{1}{n} \ln \operatorname{Pr}(F_n = f_n) = -\operatorname{KL}(f, p).$$ In other words, the Kullback-Leibler divergence of $f$ from $p$ lets you estimate the probability of getting an empirical frequency distribution close to $f$ from a large number of independent random variables with distribution $p$.

You can find everything I just said, and more, in the excellent article "Information Theory, Relative Entropy and Statistics," by François Bavaud.


* You can also do this more generally, but I don't know anything about that.

** Using Stirling's approximation, $\ln k! \in k\ln k - k + O(\ln k)$.

$\endgroup$
6
$\begingroup$

$$KL(P,Q) - KL(Q,P) = \sum_{i=1}^n \ln\left(\frac{P(i)}{Q(i)}\right) (P(i) + Q(i))$$ and there is no reason for this to be $0$.

$i$ is not a random variable, it is a dummy index. However, there can be a random variable that takes value $i$ with probability $P(i)$, and another that takes the value $i$ with probability $Q(i)$.

$\endgroup$
  • $\begingroup$ Thank you a lot, what a good answer to a first question! $\endgroup$ – MiauPiau Jan 29 '13 at 18:54
0
$\begingroup$

You can just look at one term under the sum, forgetting the index $i$. So if you consider:

$$K(p,q) = \log\left(\frac{p}{q}\right)p$$

you can see there seems to be a lack of symmetry: $p$ appears two times, $q$ only once. And this matters: suppose you take a simple linear relationship between then, like $q=\alpha p$, then

$$K(p,\alpha p) = -\log\left(\alpha\right)p$$

while the symmetric is:

$$K(\alpha p, q) = \log\left(\alpha\right)p$$

which are clearly different if $p\ne 0$ or $\alpha \ne 1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.