20
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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$ $\endgroup$
    – Ashok
    Aug 11, 2011 at 9:44
  • $\begingroup$ @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. $\endgroup$
    – Legend
    Aug 11, 2011 at 10:08
  • $\begingroup$ @Legend KL divergence does not require absolute continuity in both directions. $\endgroup$
    – dvitek
    Jan 27, 2022 at 4:36

1 Answer 1

25
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Legend
    Aug 17, 2011 at 20:44
  • $\begingroup$ @Legend JSD is simply a symmetric and smoothed version of the KL divergence. It is canonically defined as $JSD(P || Q) = \frac{1}{2}(KL(P || M) + KL(Q || M))$, where $M$ is a mixture of $P$ and $Q$ with equal weights. Therefore, the zero-problem should be inherited from KL-divergence. $\endgroup$ Oct 30, 2018 at 22:08
  • $\begingroup$ The Bayesian smoothing as you have described, if I understand it, is simply if your data is a series of counts of events, just add 1 to each count before normalizing the data to change from counts into probabilities? $\endgroup$
    – WolfLink
    Feb 23, 2020 at 3:50
  • 2
    $\begingroup$ JSD is a valid solution. It generates a mixture distribution as an intermediary and you can remove zero values when calculating KL-divergence. $\endgroup$
    – Hao Zhang
    Feb 1, 2021 at 12:06
  • $\begingroup$ @EliKorvigo This is false; Jensen-Shannon divergence (with the usual conventions in Ashok's comment on the main post) has no absolute-continuity requirements, because both $P$ and $Q$ will be absolutely continuous with respect to $M$ regardless of zero values. $\endgroup$
    – dvitek
    Jan 27, 2022 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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