3
$\begingroup$

There is the notion of Generalized RBF Kernels, for example in "Towards Optimal Bag-of-Features for Object Categorization and Semantic Video Retrieval" from Jiang (1) or in formula (2.72) in http://agbs.kyb.tuebingen.mpg.de/lwk/sections/section23.pdf (2).

They define: Gen. RBF Kernel: $e^{-pd(x,y)}$, where (1) says d can be any distance function and (2) requires it to be a metric.

I now have been wondering for a long time: Is a function defined by $e^{-pd(x,y)}$ where d is a metric always a Mercer's Kernel? I think in (2) it sounds like it, but if it were true, not many people know of it, since they are still looking to prove that $e^{-EMD(x,y)}$ is a kernel, where EMD = Earth Mover's Distance, which is a metric.

If its not a Mercer's Kernel - do you know of any counter example?

$\endgroup$

1 Answer 1

3
$\begingroup$

Haasdonk and Bahlmann, Learning with distance substitution kernels (2004; doi, pdf) give us the following result, as a subset of their Proposition 1:

Let $d$ be a pseudosemimetric (i.e. $d$ is symmetric, nonnegative, and $d(x, x) = 0$ for all $x$). Then the kernel $\exp\left( - \gamma d^2(x, y) \right)$ is positive definite for all $\gamma > 0$ iff $d$ is isometrically embeddable in $L_2$.

(Incidentally, this is what I've usually seen called the generalized RBF kernel, with the squared distance. Hat-tip to this related answer for the pointer.)

Thus if $\sqrt d$ is a pseudosemimetric, the kernel $\exp\left( - \gamma d(x, y) \right)$ is positive definite for all $\gamma > 0$ iff $\sqrt d$ is isometrically embeddable in $L_2$. (Of course, if $d$ is a pseudosemimetric, so is $\sqrt d$.)


Two facts about $L_2$ embeddability:

  1. A metric $d$ is $L_2$-embeddable iff $-d^2$ is conditionally positive definite. (Schoenberg, Metric spaces and positive definite functions, 1938, Trans. Am. Math. Soc. 44.3 pp 522–536; pdf)

  2. $-d^\beta$ is conditionally positive definite for all $\beta \in [0, 2]$ iff $d$ is $L_2$-embeddable. (Haasdonk and Bahlmann, Proposition 1)

So:

  • If $d$ is $L_2$-embeddable, by fact 2 $-d$ is cpd, so by fact 1 $\sqrt d$ is $L_2$-embeddable.

If $d$ is not $L_2$-embeddable, however, fact 2 does not imply that $-d$ is not cpd – only that there is some $\beta$ such that $-d^\beta$ is not cpd. I don't know a nice condition on $d$ that shows $\sqrt d$ is not $L_2$-embeddable.

$\endgroup$

Your Answer

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

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