Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

enter image description here

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?

share|improve this question
2  
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
add comment

1 Answer 1

up vote 4 down vote accepted

I'll give a short answer and a long answer.

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.

The longer answer is the mathematical reason why KL divergence can't handle these zeros, which requires information about Exponential family distributions (multinomial, gaussian, etc). Every exponential family distribution is defined relative to some base measure, and it must be nonzero everywhere on that base measure: this is true with multinomials, it is true with gaussians (covariance matrix must be full rank), etc. This arises because these distributions are the solution to an optimization problem which breaks down in the presence of those zeros. Anyway, so what needs to happen is that the relative base measure is the "tightest possible": in the case of multinomials, it is the uniform distribution on the nonzero entries, and in the Gaussian case, it is Lebesgue measure restricted to the affine subspace corresponding to the eigenspace of the provided covariance, shifted by the provided mean. The KL divergence (written as an integral) only makes sense if both distributions are relative to the same "tightest fit" measure.

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

share|improve this answer
    
Very deep and insightful answer. Thank you so much. I have recently found out about the Jensen-Shannon divergence metric and am trying to understand if I could utilize that instead. The paper "Divergence Measures Based on the Shannon Entropy" explains that this metric does not face the same issues as the KL-divergence metric. If you have any suggestions on this, it would be a great addition to your already insightful answer. Thank you for your time. –  Legend Aug 17 '11 at 20:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.