# Calculate the Kullback-Leibler Divergence in practice?

I am using KL Divergence as a measure of dissimilarity between 2 $p.m.f.$ $P$ and $Q$.

$$D_{KL}(P||Q) = \sum_{i=1}^N \ln \left( \frac{P_i}{Q_i} \right) P_i$$ $$=-\sum P(X_i)ln\left(Q(X_i)\right) + \sum P(X_i)ln\left(P(X_i)\right)$$

If $$P(X_i)=0$$ then we can easily calculate that $$P(X_i)ln\left(Q(X_i)\right)=0$$ $$P(X_i)ln\left(P(X_i)\right)=0$$

But if $$P(X_i)\ne0$$ and $$Q(X_i)=0$$ how to calculate the $$P(X_i)ln\left(Q(X_i)\right)$$

-
To save everyone else some time staring at what you meant you might want to change $P(X_i)!=0$ to $P(X_i) \ne 0$ with the "\ne" token –  Matthew May 16 at 2:12
In addition, do you mean that $Q(X_i) = 0$ for all $X_i$? In this case the KL divergence is not defined, since $Q$ is not a probability function (those must sum to 1 over the support). –  Matthew May 16 at 2:19
@Matthew Thanks, corrected. I followed my coding habit accidentally. –  smwikipedia May 16 at 2:34
@Matthew $Q(X_i)=0$ for some $X_i$, not all. I am considering a workaround to base $P$ and $Q$ on the same set of outcomes and add a small pseudo count, say 0.001, for the not-show-up outcomes. It can avoid the zero-valued probabilities. But I am not sure if there's any side-effects. –  smwikipedia May 16 at 2:35

You can't and you don't. Imagine that you have an random variable of probability distribution Q. But your friend Bob thinks that the outcome comes from the probability distribution P. He has constructed an optimal encoding, that minimizes the number of expected bits he will need to use to tell you the outcome. But, since he constructed the encoding from P and not from Q, his codes will be longer than necessary. KL-divergence measure how much longer the codes will be.

Now lets say he has a coin and he wants to tell you the sequence of outcomes he gets. Because head and tail are equally likely he gives them both 1-bit codes. 0 for head, 1 for tail. If he gets tail tail head tail, he can send 1 1 0 1. Now, if his coin lands on the edge he cannot possibly tell you! No code he sends you would work. At this point KL-divergence breaks down.

Since KL-divergence breaks down you will either have to use another measure or other probability distributions. What you should do really depends on what you want. Why are you comparing probability distributions? Where do your probability distributions come from, are they estimated from data?

You say your probability distributions come from natural language documents somehow, and you want to compare pairs of categories.

First, I'd recommend a symmetric relatedness measure. For this application it sounds like A to be as similar to B as B is similar to A.

Have you tried the cosine similarity measure? It is quite common in NLP.

If you want to stick with KL, one thing you could do is estimate a probability function from both documents and then see how how many extra bits you'd need on average for either document. That is (P||(P+Q)/2 + Q||(P+Q)/2)/2

-
Great explanation but slightly confusing: the way you describe the first paragraph, isn't that KL(Q||P)? –  Jurgen May 26 at 22:01

In practice, I have run into this issue as well. In this case, I've found that substituting the value of 0 for some very small number can cause problems. Depending upon the value that you use, you will introduce a "bias" in the KL value. If you are using the KL value for hypothesis testing or some other use that involves a threshold, then this small value can bias your results. I have found that the most effective way to deal with this is to only consider computing the KL over a consistent hypothesis space X_i where BOTH P and Q are non-zero. Essentially, this limits the domain of the KL to a domain where both are defined and keeps you out of trouble when using the KL to perform hypothesis tests.

-
Thanks. It's an interesting suggestion. Basically, it is also trying to base P and Q on the same set of outcomes. I will try that. –  smwikipedia May 16 at 3:51
If I calculate KL over the data subset where both P and Q are non zero, do I need to re-normalize P and Q over that subset? Or just use the original probability value? I think I should. Otherwise, P and Q are still not on the same base. –  smwikipedia May 20 at 3:11
I just tried with your suggestion. P distributes over 10K outcomes, and Q distributes over 10K outcomes, too. But P and Q only have 3K outcomes in common. If I only use the common 3K outcomes to estimate the difference between P and Q, I don't think it's reasonable. Because we are ignoring to many things. And btw, the result with this approach is quite different from what I get by adding a small number (or pseudo count). –  smwikipedia May 20 at 5:42
Add some context, I am working on a NLP experiment. I have several categories of documents and I want to tell how close each pair of categories are related to each other. –  smwikipedia May 20 at 5:46

Having a probability distribution where $Q_i=0$ for any $i$ means that you are certain that $Q_i$ can not occur. Therefore if a $Q_i$ were ever obeserved it would represent infinite surprise/information, which is what Shannon information represents. KL diveregence represents the amount of additional surprise (ie information lost) per observation if the distribution $Q$ is used as an approximation for the distribution $P$. If the approximation predicts 0 probability for an event that has a postive probability in reality, then you will experience infinite surprise some percentage of the time and thus infinite surprise on average.

The solution is to never allow 0 or 1 probabilities in estimated distributions. This is usually achieved by some form of smoothing like Good-Turing smoothing, Dirichlet smoothing or Laplace smoothing.

-