# Cancellation issue in Kullback-Leibler divergence

Per wikipedia, KL divergence is the expectation of logarithmic difference. The difference can be either positive of negative. This leads to a potential cancellation issue. E.g., -5 + 5 = 0. A total difference of 0 doesn't mean there is no difference. The differences are simply canceled. How does KL divergence make sense in this regard. The expectation of some kind of distance, say L2 norm, seems to make more sense. Since distance is non-negative, there is no cancellation issue.

Note that the fact that KL divergence is non-negative and only assumes 0 for identical distributions doesn't solve my question. Cancellation may still exist among terms in the sum. In my opinion, both negative and positive differences should be counted instead of cancelled.

## 1 Answer

Note: the OP edited their question after I answered, making my original answer less relevant. Below is this original answer, before the last paragraph of the question was added (afterwards, I included a part answering the addendum to the question):

"A total difference of 0 doesn't mean there is no difference."

Actually, it does (although it is not obvious from the expression of the Kullback—Leibler divergence). I am not sure you have fully read the Wikipedia article you cite, as this point is discussed there. I'll reproduce it below.

Essentially: while individual terms of the sum $D(p\mid\mid q) = -\sum_x p(x) \log\frac{q(x)}{p(x)}$ can be negative, i.e. one can both have $p(x) \log\frac{q(x)}{p(x)} >0$ or $p(x) \log\frac{q(x)}{p(x)} < 0$ depending on $x$, the sum itself will always be non-negative: $$\forall p,q,\qquad D(p\mid\mid q) \geq 0$$ and one has $p=q$ if, and only if, $D(p\mid\mid q)=0$. This is Gibb's inequality.

In that sense, the Kullback—Leibler divergence does make sense as some notion of distance: it is non-negative, and zero only for distributions that are equal.

To handle the added paragraph of the question:

Note that the fact that KL divergence is non-negative and only assumes 0 for identical distributions doesn't solve my question. Cancellation may still exist among terms in the sum. In my opinion, both negative and positive differences should be counted instead of cancelled.

Why do you feel this way, however? Note that if you are afraid the KL divergence "does not capture the distance" as it should, Pinsker's inequality guarantees that it will (as it is at least as big as the square of the $\ell_1$ distance, and therefore of the $\ell_2$ distance, for instance).

Note also that KL divergence does have a natural and intuitive interpretation in terms of "how much extra information is required to encode $q$ when the true unerlying distribution is $p$." In this sense, it is a well-motivated deifnition, which captures exactly what it should.

Now, nobody claimed it was the "right" notion of distance for everything (for a start, it's, again, not even a metric). You may prefer Hellinger distance for some applications, $\ell_2$ for others, or total variation/$\ell_1$ for many. Nevertheless, it is a reasonable, well-motivated notion of distance, which has a clear interpretation and satisfies many desirable properties.

• Despite the fact that the metric itself is non-negative and only assumes 0 for identical distributions, cancellation may still exist among certain terms. – Lingxi Dec 22 '17 at 5:56
• @Lingxi Yes, but how is that a problem? KL divergence is a notion of distance (careful: not a metric, by the way) between two distributions $p$ and $q$, not between a subset of their values. – Clement C. Dec 22 '17 at 5:57
• I'm thinking that maybe no cancellation at all within any subset is more desirable. – Lingxi Dec 22 '17 at 6:04
• @Lingxi Desirability is a different thing. For example, it is written in the article that the Kullback Leibler divergence is the only measure between probability measures having some property. Unfortunately, we must forgo the condition of having only positive terms, and therefore permit cancellations, to get this benefit. – астон вілла олоф мэллбэрг Dec 22 '17 at 6:06
• @Lingxi See my edit: does it answer part of your concerns? In short: what you find desirable in some notion of distance may not be suited to all applications and settings. – Clement C. Dec 22 '17 at 6:08