# How to compute KL-divergence when PMF contains 0s?

From the Wikipedia page on Kullback-Leibler divergence, the way to compute this metric is to utilize the following formula:

The way I understand this is to compute the PMFs of two given sample sets and then use the above formula to compute the KL-divergence. I am not quite sure I am getting this though. Let us say I have the following set of values:

0 0 0 0 0 1 1 0 0 0 0 0 1 2 0 0 0 0 0 20 0 0 0


I am trying to compute the KL-divergence for a sliding window size of 7. So, I start of by choosing the bin size for my histogram as 1 and (max, min) values as (20, 0) based on the entire dataset. So that when I have the sliding window as follows:

0 0 0 0 0 1 1 0 0 0 0 0 1 2 0 0 0 0 0 20 0 0 0
|-----------|
|-----------|


I compute the PMFs across these two sliding windows as:

0 0 0 0 0 1: 0.81818182,  0.18181818 0 0 ... 0
0 0 0 0 1 2: 0.66666667,  0.16666667,  0.16666667 0 0 ... 0


Both these PMFs satisfy the first condition from the Wiki page:

The K-L divergence is only defined if P and Q both sum to 1 and if Q(i) > 0 for any i such that P(i) > 0.

but failing with the second condition. Can someone please tell me where I am going wrong?

-
I don't understand the way you are computing the PMFs. Its usual convention that $0\log\frac{0}{a}=0$ for any $a$ and $a\log\frac{a}{0}=\infty$ when $a>0$ – Ashok Aug 11 '11 at 9:44
@Ashok: Yes. You are right. It looks like KL-divergence requires that both the PMFs be absolutely continuous with respect to each other. In my case, the second case of infinity is a problem. In my calculation, the histograms contain empty bins which I am not able to understand how to handle. – Legend Aug 11 '11 at 10:08

The short answer is that the KL divergence on multinomials is defined when they have only nonzero entries. When there are zero entries, you have two choices. (1) Smooth the distributions in some way, for instance with a Bayesian prior, or (similarly) taking the convex combination of the observation with some valid (nonzero) distribution. (The standard Bayesian approach is to use a Dirichlet prior, which amounts to treating each entry as a fraction $n_i / m$ where $m=\sum_i n_i$, and $n_i$ should be integer (but with your provided data this may get messy), and replacing these fractions with for instance $(n_i + 1) / (m+|x|)$ where $|x|$ is the number of atoms in the discrete distribution; the "convex combination" smoothing choice is similar, if $x$ is your observation and $\alpha \in (0,1]$, return $\alpha U_{|x|} + (1-\alpha)x$ where $U_{|X|}$ is the uniform distribution on $|x|$ points.) (2) Employ heuristics throwing out all the values that do not make sense, as suggested above. While I acknowledge that (2) is a convention, it doesn't really fit with the nature of these distributions, as I will explain momentarily.
To summarize, the invalidity of the formula in the presence of zeros isn't just some unfortunate hack, it is a deep issue intimately tied to how these distributions behave. The smoothing/Bayesian solution is thus better motivated: it nudges the distributions into validity. But many people simply choose to throw out those values (i.e., by erasing $0\ln(0)$ or $a\ln(a/0)$ and writing $0$ in its place).