Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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)$$
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
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.
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.
