3
$\begingroup$

Disclaimer: This question is somewhat related to: Generalized RBF Kernels. I apologize if this has too much overlap.


Say we have some distance $d(x,x')$, where $x$ is from some set $X$.

$d(x,x')$ may be a metric, that is, satisfy conditions: $$d(x,x')\geq 0$$ $$d(x,x')=d(x',x)$$ $$d(x,x')=0 \iff x=x'$$ $$d(x,x')\leq d(x,x'') + d(x'',x')$$

or a pseudo-metric (i.e., $d(x,x')$ can be zero even if $x$ and $x'$ are not identical).

And we have a kernel derived from $d(x,x')$:

$$k(x,x')= -d(x,x')^\beta ~~~\text{with}~~~ \beta \in [0,2]$$

Haasdonk and Bahlman (Learning with Distance Substitution Kernels, 2004, PDF) say in Corollary 1 that

Non-Metricity Prevents Definiteness.

That is, if $d(x,x')$ is not metric, $k(x,x')$ cannot be Conditionally Positive Semi-Definite (CPSD) (see the PDF for a definition).

My question is:

Does that imply that only actual metrics (and not pseudo-metrics) can yield CPSD $k$? Or do they just not distinguish between metric/pseudo-metric?

$\endgroup$
3
$\begingroup$

Does that imply that only actual metrics (and not pseudo-metrics) can yield CPSD $k$? Or do they just not distinguish between metric/pseudo-metric?

The latter. Here's why:

Suppose we have a pseudometric $d(x,x')$. Then $d(x,x') + \alpha ||x-x'||^2$ is a metric for all $\alpha > 0$ (here $||\cdot||$ is the Euclidean norm - we could use any other true metric as well). So the associated kernel $k_\alpha$ is CPSD for all $\alpha > 0$. The question is whether it is also CPSD for $\alpha = 0$?

The answer is yes. Following the notation in your PDF: given any $c$ we have $c^T K_\alpha c \geq 0$ for all $\alpha > 0$. It is clear that $K_\alpha$ is a continuous function of $\alpha$ by its definition in your original post. So we can take the limit $\alpha \rightarrow 0$ and the inequality will still hold. Therefore the inequality holds for all $c$ at $\alpha = 0$ and we have a CPSD kernel.

$\endgroup$

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.