Is the square root of the symmetric Kullback-Leibler divergence a metric?

Question

It is well known that the square root of the Jensen-Shannon divergence is a true metric, but how about the square root of symmetric KL: D(P||Q)+D(Q||P)? I have reasons to believe that it also is a true metric but cannot find any references on that other than anecdotal comments such as that it behaves more like a metric when used.

Update 1

Kullback-Leibler divergence: $D(P||Q) = \sum_i p_i\log(p_i/q_i)$

Jensen-Shannon divergence: $J(P,Q) = \big(D(P||(P+Q)/2)+D(Q||(P+Q)/2)\big)/2$

Symmetric KL divergence: $S(P,Q) = D(P||Q)+D(Q||P) = \sum_i (p_i-q_i)\log(p_i/q_i)$

Square root of symmetric KL: $d_{KL}(P,Q) = \sqrt{S(P,Q)}$

Is $d_{KL}$ a metric?

Update 2

I think the following upper and lower bounds hold:

$\sum_i (p_i-q_i)^2 \leq \sum_i (p_i-q_i)\log(p_i/q_i) \leq \sum_i \log(p_i/q_i)^2$

Both of the square root of the bounds are metrics, I suppose, since they are the square of the Euclidean distances in the probability space and the log-prob space respectively.

Answer 1

No, the square root of the symmetrised KL divergence is not a metric. A counterexample is as follows:

• Let $P$ be a coin that produces a head 10% of the time.
• Let $Q$ be a coin that produces a head 20% of the time.
• Let $R$ be a coin that produces a head 30% of the time.
• Then $d(P, Q) + d(Q, R) = 0.284... + 0.232... < 0.519... = d(P, R)$.

However, for $P$ and $Q$ very close together, $D(P, Q)$ and $J(P, Q)$ and $S(P, Q)$ are essentially the same (they are proportional to one another $+ O((P-Q)^3)$) and their square root is a metric (to the same order). We can take this local metric and integrate it up over the whole space of probability distributions to obtain a global metric. The result is:

$$A(P, Q) = \cos^{-1}\left(\sum_x \sqrt{P(x)Q(x)} \right)$$

I worked this out myself, so I'm afraid I do not know what it is called. I will use A for Alistair until I find out. ;-)

By construction, the triangle inequality in this metric is tight. You can actually find a unique shortest path through the space of probability distributions from $P$ to $Q$ that has the right length. In that respect it is preferable to the otherwise similar Hellinger distance:

$$H(P, Q) = 1 - \sqrt{\sum_x \sqrt{P(x)*Q(x)} }$$

Update 2013-12-05: Apparently this is called the Battacharrya arc-cos distance.

Answer 2

One case of theorem 2.2 in this paper says that if we define (for positive numbers rather than whole probability distributions) $S(p,q) = (p-q)\log(p/q)$ then $\sqrt S$ is a metric.

(I haven't looked at the paper closely enough to vouch for its correctness, but in any case you have no more reason to trust me than to trust its author :-).)

If so, then your symmetrized KL divergence is a metric on probability distributions, because of the following theorem: if you have metric spaces $(M_1,d_1)$, $(M_2,d_2)$, etc., then $(M_1 \times M_2 \times \cdots$, $\sqrt{d_1^2+d_2^2+\cdots}$ is also a metric space; see e.g. Wikipedia.

EDITED in the light of the now-accepted answer to add: So, clearly it is not true that $\sqrt S$ (as in my first paragraph above) is a metric. And indeed it isn't; specifically (taking the counterexample in that answer as inspiration) we have both $S(0.1,0.2) + S(0.2,0.3) < S(0.1,0.3)$ and $S(0.9,0.8) + S(0.8,0.7) < S(0.9,0.7)$. Unless I'm gravely misunderstanding the paper I linked to, that means its theorem 2.2 is incorrect. This theorem is concerned with a generalization of this $S$, taking the $S$ we're actually interested in here as a limit of something more tractable; it seems to be false for the more-tractable thing too, so the problem is there rather than in the passage to the limit.

Answer 3

Here is wolfram's definition of metric: http://mathworld.wolfram.com/Metric.html

They say that the properties of metrics are:

1. non-negative
2. symmetry
3. distance identity (distance between a point and itself is zero)
4. triangle inequality

The KL divergence is not non-negative. It doesn't qualify. The absolute KL-divergence is non-negative. So I am going to pull a "fog of war" and "answer the question you wish were asked". I am going to evaluate whether the absolute value of KL divergence (or its positive root) comprise a metric.

1) Because it is absolute value, the non-negative is satisfied

2) Symmetry means that $g \left( x,y\right) =g \left( y,x\right)$.

The KL divergence is not symmetric in general. The univariate cases where it is symmetric are when $p \left( x\right)=q \left( x\right)$, when the PDFs under evaluation are equal in value when evaluated at the same point $x$. Absolute value of KL divergence is symmetric.

3) IDentity (in a measurement sense) is satisfied. The natural log of one approaches zero. Neither square root nor absolute value change this.

4) Triangle inequality

In order to satisfy the requirement, the following must be true:

$ KL(a,b) + KL(b,c) \ge KL(a,c)$

or

$ abs(KL(a,b)) + abs(KL(b,c)) \ge abs(KL(a,c))$

You can see the general form of $ abs(log(x))$ where x is the ratio of likelihoods for your PDF's of interest. Are there any places where the triangle inequality is violated?

I'm not sure how to engage this right now and will come back later. At this point, without the absolute value, the KL or sqrt(KL) is broken as a metric.

EDIT: So it is now "later".

I was using a simplification of KL as $ KL = \sum_{i=1}^{N} {p(x_i) ln \left ( \frac {p(x_i)} {q(x_i)}\right )} $ being treated as $ KL_2 = \sum_{i=1}^{N} { ln \left ( \frac {p(x_i)} {q(x_i)}\right )} $ because the linear scaling isn't going to impact the nature of the metric space. The $ a_i$ is going to be (for my distributions) continuous and smooth. It could be argued that Gaussian Mixture Models (GMM's) provide a sufficient basis to represent any distribution to arbitrary precision in an analogy to Fourier Series basis for time-series signal data, but such arguments are sample size constrained.

The same sort of argument can also be made for the symmetric KL divergence.

By inspection and graphical demonstration, consider the region in the figure to the left of $ x=1$. and imagine two cases: that "a" and "b" are equal and that they are not. If they are equal, and because of the concave nature of the curve the triangle inequality holds. If they are unequal then a triangle can be drawn between the points $ (a,f(a))$, $ (b, f(b))$, and $ (a+b,f(a+b))$. The longest segment of the triangle is such that $ f(min(a,b)) \ge f(a+b) $ and the triangle inequality holds.

Now to consider when $ a = b = 1$. We get $ f(a) + f(b) = 0 + 0$ while $ f(a+b) = f(2) \gt 0$ and the triangle inequality no longer holds. In the domain where the curve is concave down for any $ f(x | x_i \ge 1)$ there are always component values for which triangle inequality is broken. For $ KL_2$ the "radius of compatibility" for the metric space is 1.

If triangle inequality is "broken" for $ KL_2$ then is it broken for $ S(P,Q)$? I will continue to think on this.