# How to compute the Kullback-Leibler divergence when the PMF contains 0s?

I have the following timeseries

obtained using the data posted below.

For a sliding window size of 10, I am trying to compute the KL-divergence between the PMF of values within the current sliding window and the PMF of the history with the final goal of plotting the value of KL-divergence across time so that I can compare two time series.

As of now, there is a conceptual problem I am facing (which I'll explain using Python):

In [228]: samples = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]

# In reality this 10 should be 20 because that is the max value I have seen in the timeseries
In [229]: bins = scipy.linspace(0, 10, 21)
In [230]: bins
Out[230]:
array([  0. ,   0.5,   1. ,   1.5,   2. ,   2.5,   3. ,   3.5,   4. ,
4.5,   5. ,   5.5,   6. ,   6.5,   7. ,   7.5,   8. ,   8.5,
9. ,   9.5,  10. ])
In [231]: scipy.histogram(samples, bins=bins, density=True)
Out[231]:
(array([ 1.63636364,  0.        ,  0.36363636,  0.        ,  0.        ,
0.        ,  0.        ,  0.        ,  0.        ,  0.        ,
0.        ,  0.        ,  0.        ,  0.        ,  0.        ,
0.        ,  0.        ,  0.        ,  0.        ,  0.        ]),
array([  0. ,   0.5,   1. ,   1.5,   2. ,   2.5,   3. ,   3.5,   4. ,
4.5,   5. ,   5.5,   6. ,   6.5,   7. ,   7.5,   8. ,   8.5,
9. ,   9.5,  10. ]))


The problem is that the resulting PMF contains 0s so that I cannot really multiple two PMFs to get the KL-divergence. Can someone tell me how to mitigate this problem?

### Data

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 2 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

-

One standard trick to deal with this problem is to use what's called a Laplace correction. In effect, you add one "count" to all bins, and renormalize. There are also good reasons to add a 0.5 count instead: this particular estimator is called the Krichevsky-Trofimov estimator.

-

One way to think about your problem is that you don't really have confidence in the PMF you have calculated from the histogram. You might need a slight prior in your model. Since if you were confident in the PMF, then the KL divergence should be infinity since you got values in one PMF that are impossible in the other PMF. If, on the other hand you had a slight, uninformative prior then there is always some small probability of seeing a certain outcome. One way of introducing this would be to add a vector of ones times some scalar to the histogram. The theoretical prior distribution you would be using is the dirichlet distribution, which is the conjugate prior of the categorical distribution. But for practical purposes you can do something like

pmf_unnorm = scipy.histogram(samples, bins=bins, density=True)[0] +  w * scipy.ones(len(bins)-1)
pmf = pmf_unnor / sum(pmf_unnorm)


where w is some positive weight, depending on how strong a prior you want to have.

-
+1 for your time and answer. Thank you. I have been reading on this for the last 8 hours and looks like I need to add a prior to work around this. However, I am unable to find a suitable reference that explains this fact. Is this something obvious in the stats community or would you happen to know a reference that points out this requirement for KL-divergence? – Legend Aug 11 '11 at 22:06

I would bin the data so you can compare the two PMFs; given two PMF estimates $\hat P$ and $\hat Q$, you can calculate the KLD simply as: $D_{KL}(\hat P \| \hat Q) \equiv \sum_i \hat P(i) \log \dfrac{\hat P(i)}{\hat Q(i)}$, where $i$ runs over the bins.

Sorry, I don't know R.

-
+1 for your time. I updated my question with the problem I am facing with this formula. I am not able to understand how to tackle this problem when the PMFs contain 0s. Would you happen to have any comments on how to mitigate this problem? – Legend Aug 11 '11 at 7:18
Does zero indicate the absence of data or is it a valid value? If the former, you would simply ignore it. If the latter, you can dedicate one of the bins to the value zero. – Emre Aug 11 '11 at 17:37
Because this is a time series, in some cases, there were zero events and in some there was missing data so I added a zero to substitute for the missing value. You bring an interesting point: Can I ignore values in a timeseries in case they are missing? Wouldn't that prove fatal? – Legend Aug 11 '11 at 22:02
I would retain the zeros selecting the elements in the moving window, but disregard them for purposes of calculating the KLD. – Emre Aug 11 '11 at 22:43
Understood. Thank You! Accepted as an answer. My last question would be regarding a related metric called "Jensen-Shannon" divergence. I came across this metric by chance but this metric does not seem to have a requirement of absolute continuity. Any suggestions? – Legend Aug 12 '11 at 1:00