How to interpret KL divergence quantitatively?

Question

I am comparing two distributions with KL divergence which returns me a non-standardized number that, according to what I read about this measure, is the amount of information that is required to transform one hypothesis into the other. I have two questions:

a) Is there a way to quantify a KL divergence so that it has a more meaningful interpretation, e.g. like an effect size or a R^2? Any form of standardization?

b) In R, when using KLdiv (flexmix package) one can set the 'esp' value (standard esp=1e-4) that sets all points smaller than esp to some standard in order to provide numerical stability. I have been playing with different esp values and, for my data set, I am getting an increasingly larger KL divergence the smaller a number I pick. What is going on? I would expect that the smaller the esp, the more reliable the results should be since they let more 'real values' become part of the statistic. No? I have to change the esp since it otherwise does not calculate the statistic but simply shows up as NA in the result table ...

Answer 1

Suppose you are given n IID samples generated by either p or by q. You want to identify which distribution generated them. Take as null hypothesis that they were generated by q. Let a indicate probability of Type I error, mistakenly rejecting the null hypothesis, and b indicate probability of Type II error.

Then for large n, probability of Type I error is at least

$\exp(-n \text{KL}(p,q))$

In other words, for an "optimal" decision procedure, probability of Type I falls at most by a factor of exp(KL(p,q)) with each datapoint. Type II error falls by factor of $\exp(\text{KL}(q,p))$ at most.

For arbitrary n, a and b are related as follows

$b \log \frac{b}{1-a}+(1-b)\log \frac{1-b}{a} \le n \text{KL}(p,q)$

and

$a \log \frac{a}{1-b}+(1-a)\log \frac{1-a}{b} \le n \text{KL}(q,p)$

If we express the bound above as the lower bound on a in terms of b and KL and decrease b to 0, result seems to approach the "exp(-n KL(q,p))" bound even for small n

More details on page 10 here, and pages 74-77 of Kullback's "Information Theory and Statistics" (1978).

As a side note, this interpretation can be used to motivate Fisher Information metric, since for any pair of distributions p,q at Fisher's distance k from each other (small k) you need the same number of observations to to tell them apart

Answer 2

KL has a deep meaning when you visualize a set of dentities as a manifold within the fisher metric tensor, it gives the geodesic distance between two "close" distributions. Formally:

$ds^2=2KL(p(x, \theta ),p(x,\theta + d \theta))$

The following lines are here to explain with details what is meant by this las mathematical formulae.

Definition of the Fisher metric.

Consider a parametrized family of probability distributions $D=(f(x, \theta ))$ (given by densities in $R^n$), where $x$ is a random variable and theta is a parameter in $R^p$. You may all knnow that the fisher information matrix $F=(F_{ij})$ is

$F_{ij}=E[d(\log f(x,\theta))/d \theta_i d(\log f(x,\theta))/d \theta_j]$

With this notation $D$ is a riemannian manifold and $F(\theta)$ is a Riemannian metric tensor. (The interest of this metric is given by cramer Rao lower bound theorem)

You may say ... OK mathematical abstraction but where is KL ?

It is not mathematical abstraction, if $p=1$ you can really imagine your parametrized density as a curve (instead of a subset of a space of infinite dimension) and $F_{11}$ is connected to the curvature of that curve... (see the seminal paper of Bradley Efron: Defining the Curvature of a Statistical Problem (with Applications to Second Order Efficiency))

The geometric answer to part of point a/ in your question : the squared distance $ds^2$ between two (close) distributions $p(x,\theta)$ and $p(x,\theta+d \theta)$ on the manifold (think of geodesic distance on earth of two points that are close, it is related to the curvature of the earth) is given by the quadratic form:

$ds^2= \sum F_{ij} d \theta^i d \theta^j$

and it is known to be twice the Kullback Leibler Divergence:

$ds^2=2KL(p(x, \theta ),p(x,\theta + d \theta))$

If you want to learn more about that I suggest reading the paper from Amari: Differential Geometry of Curved Exponential Families-Curvatures and Information Loss (I think there is also a book from Amari about Riemannian geometry in statistic but I don't remember the name)

Answer 3

The KL(p,q) divergence between distributions p(.) and q(.) has an intuitive information theoretic interpretation which you may find useful.

Suppose we observe data x generated by some probability distribution p(.). A lower bound on the average codelength in bits required to state the data generated by p(.) is given by the entropy of p(.).

Now, since we don't know p(.) we choose another distribution, say, q(.) to encode (or describe, state) the data. The average codelength of data generated by p(.) and encoded using q(.) will necessarily be longer than if the true distribution p(.) was used for the coding. The KL divergence tells us about the inefficiencies of this alternative code. In other words, the KL divergence between p(.) and q(.) is the average number of extra bits required to encode data generated by p(.) using coding distribution q(.). The KL divergence is non-negative and equal to zero iff the actual data generating distribution is used to encode the data.

Answer 4

For part (b) of your question, you might be running into the problem that one of of your distributions has density in a region where the other does not.

$$ D( P \Vert Q ) = \sum p_i \ln \frac{p_i}{q_i} $$

This diverges if there exists an $i$ where $p_i>0$ and $q_i=0$. The numerical epsilon in the R implementation "saves you" from this problem; but it means that the resulting value is dependent on this parameter (technically $q_i=0$ is no required, just that $q_i$ is less than the numerical epsilon).