Kullback-Leibler divergence WITHOUT information theory

Question

After much trawling of Cross Validated, I still don't feel like I'm any closer to understanding KL divergence outside of the realm of information theory. It's rather odd as somebody with a Math background to find it much easier to understand the information theory explanation.

To outline my understanding from an information theory background: If we have a random variable with a finite number of outcomes, there exists an optimal encoding which allows us to communicate the outcome with somebody else with on average the shortest message (I find this easiest to picture in terms of bits). The expected length of the message one would need to communicate the outcome is given by $$ -\sum _{\alpha}p_{\alpha}\log_{2}(p_{\alpha})$$ if the optimal encoding is used. If you were to use a sub optimal encoding, then KL divergence tells us on average how much longer our message would be.

I like this explanation, because it quite intuitively deals with the asymmetry of KL divergence. If we have two different systems, i.e. two loaded coins that are differently loaded, they will have different optimal encodings. I don't somehow instinctively feel that using the second system's encoding for the first is "equally bad" to using the first system's encoding for the second. Without going through the thought process of how I convinced myself, I'm now fairly happy that $$\sum _{\alpha}p_{\alpha}( \log _{2}q_{\alpha}-\log_{2}p_{\alpha})$$ gives you this "extra expected message length", when using $q$'s encoding for $p$.

However, most definitions of KL divergence, including Wikipedia then make the statement (keeping this in discrete terms so that it can be compared to the information theory interpretation which works far better in discrete terms as bits are discrete) that if we have two discrete probability distributions, then KL provides some metric of "how different they are". I have yet to see a single explanation of how these two concepts are even related. I seem to remember in his book on inference, Dave Mackay makes points about how data compression and inference are basically the same thing, and I suspect my question is really related to this.

Regardless of whether it is or it isn't, the sort of question I have in mind is around problems of inference. (Keeping things discrete), if we have two radioactive samples, and we know that one of them is a certain material with known radioactivity (this is dubious physics but let's pretend the universe works like that) and thus we know the "true" distribution of radioactive clicks we should measure should be poissonian with known $\lambda $, is it fair to build up an empirical distribution for both samples and compare their KL divergences to the known distribution and say the lower is more likely to be that material?

Moving away from dubious physics, if I know two samples are pulled from the same distribution but I know they're not randomly selected, would comparing their KL divergences to the known, global distribution give me a feel for "how biased" the samples are, relative to one and other anyway?

And finally, if the answer to the previous questions is yes, then why? Is it possible to understand these things from a statistical point of view alone without making any (possibly tenuous) connections to information theory?

Answer 1

There is a purely statistical approach to Kullback-Leibler divergence: take a sample $X_1,\ldots,X_n$ iid from an unknown distribution $p^\star$ and consider the potential fit by a family of distributions, $$\mathfrak{F}=\{p_\theta\,,\ \theta\in\Theta\}$$The corresponding likelihood is defined as $$L(\theta|x_1,\ldots,x_n)=\prod_{i=1}^n p_\theta(x_i)$$ and its logarithm is $$\ell(\theta|x_1,\ldots,x_n)=\sum_{i=1}^n \log p_\theta(x_i)$$ Therefore, $$\frac{1}{n} \ell(\theta|x_1,\ldots,x_n) \longrightarrow \mathbb{E}[\log p_\theta(X)]=\int \log p_\theta(x)\,p^\star(x)\text{d}x$$ which is the interesting part of the Kullback-Leibler divergence between $p_\theta$ and $p^\star$ $$\mathfrak{H}(p_\theta|p^\star)\stackrel{\text{def}}{=}\int \log \{p^\star(x)/p_\theta(x)\}\,p^\star(x)\text{d}x$$the other part$$\int \log \{p^\star(x)\}\,p^\star(x)\text{d}x$$being there to have the minimum [in $\theta$] of $\mathfrak{H}(p_\theta|p^\star)$ equal to zero.

A book that connects divergence, information theory and statistical inference is Rissanen's Optimal estimation of parameters, which I reviewed here.

Answer 2

Here is a statistical interpretation of the Kullback-Leibler divergence, loosely taken from I.J. Good (Weight of evidence: A brief survey, Bayesian Statistics 2, 1985).

The weight of evidence.

Suppose you observe data points $x_1, x_2, \dots, x_n$ which you have reason to believe are independent samples from some unknown distribution having a density $f_0$. In the simplest case, you have two hypotheses $H_1$ and $H_2$ about what is $f_0$, say $H_1 = \{f_1\}$ and $H_2 = \{f_2\}$. Thus you have modelled the unknown $f_0$ as being one of $f_1$ or $f_2$.

The weight of evidence of the sample $x = (x_1, \dots, x_n)$ for $H_1$ against $H_2$ is defined as $$ W(x) = \log \frac{f_1(x)}{f_2(x)} . $$ It is an easy to interpret quantity, especially given a prior $P$ on the hypotheses $H_0$ and $H_1$. Indeed, in that case the posterior log-odds are $W$ plus the prior log-odds: $$ \log \frac{P(H_0 | x)}{P(H_1 | x)} = W(x) + \log\frac{P(H_0)}{P(H_1)}. $$ This quantity also has a number of convenient properties, such as additivity for independent samples: $$ W(x_1, \dots, x_n) = W(x_1) + \dots +W(x_n) . $$ Good provides further justification for the use of the weight of evidence, and $W(x)$ is also refered by Kullback and Leibler (in the paper that introduced the K-L divergence) as "the information in $x$ for discrimination between $H_1$ and $H_2$".

In summary, given a sample $x$, the weight of evidence $W(x)$ is a concrete number meant to help you understand how much evidence you have at hand. Some people even use rule of thumbs such as "$W(x) > 2$ is strong evidence" (I don't encourage the blind use of such tables, mind you).

The Kullback-Leibler divergence

Now, the Kullback-Leibler divergence between $f_1$ and $f_2$ is the expected weight of evidence in a sample $x \sim f_1$. That is, $$ KL(f_1, f_2) = \mathbb{E}_{x \sim f_1} W(x) = \int f_1 \log\frac{f_1}{f_2}. $$

We should intuitively expect that a sample $x \sim f_1$ provides positive evidence in favor of $H_1 = \{f_1\}$ against $H_2$, and this is indeed reflected through the inequality $$ \mathbb{E}_{x \sim f_1} W(x) \geq 0. $$

Answer 3

I have yet to see a single explanation of how these two concepts are even related.

I don't know much about information theory, but this is how I think about it: when I hear an information theory person say "length of the message," my brain says "surprise." Surprise is 1.) random and 2.) subjective.

By 1.) I mean that "surprise" is just a transformation of your random variable $X$, using some distribution $q(X)$. Surprise is defined as $- \log q(X)$, and this is definition whether or not you have a discrete random variable.

Surprise is a random variable, so eventually we want to take an expectation to make it a single number. By 2), when I say "subjective," I mean you can use whatever distribution you want ($q$), to transform $X$. The expectation, however, will always be taken with respect to the "true" distribution, $p$. These may or may not be equal. If you transform with the true $p$, you have $E_p[-\log p(X)]$, that's entropy. If some other distribution $q$ that's not equal to $p$, you get $E_p[-\log q(X)]$, and that's cross entropy. Notice how if you use the wrong distribution, you always have a higher expected surprise.

Instead of thinking about "how different they are" I think about the "increase in expected surprise from using the wrong distribution." This is all from properties of the logarithm.

$$ E_p[\log \left( \frac{p(X)}{q(X)} \right)] = E_p[-\log q(X)] - E_p[- \log p(X)] \ge 0. $$

Edit

Response to: "Can you elaborate on how $−\log(q(x))$ is a measure of "surprise"? This quantity alone seems meaningless, as it is not even invariant under linear transforms of the sample space (I assume $q$ is a pdf)"

For one, think about what it maps values of $X$ to. If you have a $q$ that maps a certain value $x$ to $0$, then $-\log(0) = \infty$. For discrete random variables, realizations with probability $1$ have "surprise" $0$.

Second, $-\log$ is injective, so there is no way rarer values get less surprise than less rare ones.

For continuous random variables, a $q(x) > 1$ will coincide with a negative surprise. I guess this is a downside.

Olivier seems to be hinting at a property his "weight of evidence" quantity has that mine does not, which he calls an invariance under linear transformations (I'll admit I don't totally understand what he means by sample space). Presumably he is talking about if $X \sim q_X(x)$, then $Y=aX+b \sim q_x((y-b)/a)|1/a|$ as long as $X$ is continuous. Clearly $-\log q_X(X) \neq -\log q_Y(Y)$ due to the Jacobian.

I don't see how this renders the quantity "meaningless," though. In fact I have a hard time understanding why invariance is a desirable property in this case. Scale is probably important. Earlier, in a commment, I mentioned the example of variance, wherein the random variable we are taking the expectation of is $(X-EX)^2$. We could interpret this as "extremeness." This quantity suffers from lack of invariance as well, but it doesn't render meaningless peoples' intuition about what variance is.

Edit 2: looks like I'm not the only one who thinks of this as "surprise." From here:

The residual information in data $y$ conditional on $\theta$ may be defined (up to a multiplicative constant) as $-2 \log\{ p(y \mid \theta)\}$ (Kullback and Leibler, 1951; Burnham and Anderson, 1998) and can be interpreted as a measure of 'surprise' (Good, 1956), logarithmic penalty (Bernardo, 1979) or uncertainty.

Answer 4

There is (also) a purely convex analytical viewpoint on the KL divergence, which personally I find very easy to understand.

Given any convex function $F: R^k \to R$, its Bregman divergence between $p$ and $q$ ($p, q \in R$) is the quantity $$ F(p) - F(q) - \langle \nabla F(q), p - q \rangle $$ This has a very simple interpretation: it is the difference between the actual value of the function at $p$ ($F(p)$) and the value extrapolated from a linear approximation of the function computed at $q$ (that is, $F(q) + \langle \nabla F(q), p - q \rangle$). Since the function is assumed convex, this value is always nonnegative and it is zero exactly when the linear approximation yields no error.

In the case of the KL divergence, $F$ is simply the negative entropy $F(p) = \sum_i p_i \log p_i$, which is indeed convex.