Questions about KL divergence?

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...

Thanks in advance, Ampleforth

-

3 Answers

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.

-

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 http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aos/1176343282)

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 http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aos/1176345779 (I think there is also a book from Amari about riemannian geometry in statistic but I don't remember the name)

-

– Rob Hyndman Jul 30 '10 at 13:10
Since I am not a mathematician nor a statistician, I would like to restate what you were saying to make sure I did not mis-understand.   So, you are saying that taking ds^2 (twice the KL) would have a similar meaning as R^2 (in a regression model) for a general distribution. And that this could actually be used to quantify  distances geometrically? Does ds^2 have a name so I can do more reading about this. Is there a paper that directly describes this metric and shows applications and examples? – Ampleforth Aug 3 '10 at 22:22
– robin girard Aug 4 '10 at 17:25
This seems to be a characterization of directional derivative of KL rather than of KL itself, and it doesn't seem possible to get KL divergence out of it because unlike the derivative, KL-divergence doesn't depend on the geometry of the manifold – Yaroslav Bulatov Aug 11 '10 at 23:37

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

-

+1 I like this interpretation! could you clarify " p below e "? why do you take small e ? you say "the probability of making the opposite mistake is" it is an upper bound  or exact probability? If I remember, this type of approach is due to Chernoff, do you have the references (I find your first reference is not clarifying the point :) ) ? – robin girard Aug 12 '10 at 11:08
Why do I take small e...hmm...that's what Balasubramanian's paper did, but now, going back to Kullback, it seems his bound holds for any e, and he also gives bound for finite n, let me update the answer – Yaroslav Bulatov Aug 12 '10 at 20:07
ok, we don't need small e (now called b, Type II error) to be small for bound to hold, but b=0 is the value for which the simplified (exp(-n KL(p,q)) bound matches the more complicated bound above. Curiously enough, lower bound for Type I error given 0 Type II error is <1, I wonder if <1 Type II error rate is actually achievable – Yaroslav Bulatov Aug 12 '10 at 22:54
Actually a much easier to understand reference for this is Cover's "Elements of Information Theory", page 309, 12.8 "Stein's Lemma" – Yaroslav Bulatov Aug 13 '10 at 21:25
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 20, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9248917698860168, "perplexity_flag": "middle"}