15
$\begingroup$

I am clustering probability distributions using the Affinity Propagation algorithm, and I plan to use Jensen-Shannon Divergence as my distance metric.

Is it correct to use JSD itself as the distance, or JSD squared? Why? What differences would result from choosing one or the other?

$\endgroup$
19
$\begingroup$

I think it depends on how it is to be used.

Just for reference for other readers, if $P$ and $Q$ are probability measures, then the Jensen-Shannon Divergence is $$ J(P,Q) = \frac{1}{2} \big( D(P \mid\mid R) + D(Q\mid\mid R) \big) $$ where $R = \frac{1}{2} (P + Q)$ is the mid-point measure and $D(\cdot\mid\mid\cdot)$ is the Kullback-Leibler divergence.

Now, I would be tempted to use the square root of the Jensen-Shannon Divergence since it is a metric, i.e. it satisfies all the "intuitive" properties of a distance measure.

For more details on this, see

Endres and Schindelin, A new metric for probability distributions, IEEE Trans. on Info. Thy., vol. 49, no. 3, Jul. 2003, pp. 1858-1860.

Of course, in some sense, it depends on what you need it for. If all you are using it for is to evaluate some pairwise measure, then any monotonic transformation of JSD would work. If you're looking for something that's closest to a "squared-distance", then the JSD itself is the analogous quantity.

Incidentally, you might also be interested in this previous question and the associated answers and discussions.

$\endgroup$
  • $\begingroup$ Cool, I will read "a new metric for probability distribution" as soon as possible. Txh $\endgroup$ – ocram Feb 27 '11 at 7:04
  • $\begingroup$ Thanks! I didn't realize that JSD itself is already analogous to dist**2 $\endgroup$ – AlcubierreDrive Feb 27 '11 at 10:53
  • $\begingroup$ Thanks for the great explanation! Just a quick question. I know J-Divergence is symmetric in that J(P,Q) = J(Q,P). I read that JS divergence is symmetric in P and Q. Does this mean JS(P,Q) = JS(Q,P)? I am asking this because I am using the KLdiv function from the flexmix package in R. For my two distributions, the matrix output from KLdiv is not symmetric. I was expecting JS to correct this but the output from JS (computed using KL) is not symmetric. $\endgroup$ – Legend Jan 16 '13 at 20:33
  • 1
    $\begingroup$ @Legend: Yes, the JS divergence is symmetric. Hopefully that is easy to see from the equation given in the answer. Make sure that you are taking the KL divergence between $P$ and the midpoint measure and $Q$ and the midpoint measure for each of the two terms. Separately, neither will be symmetric, necessarily. $\endgroup$ – cardinal Jan 18 '13 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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