Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Fix a domain $X$: Let $d : X \times X \rightarrow \mathbb{R}$ be a distance function on $X$, with the properties

  • $d(x,y) = 0 \iff x = y$ for all $x,y$
  • $d(x,y) = d(y,x)$ for all $x,y$

Optionally, $d$ might satisfy the triangle inequality (making it a metric), but this is not necessarily the case.

In machine learning, a kernel is a function $K : X \times X \rightarrow \mathbb{R}$ with the properties

  • $K(x,y) = 1 \iff x = y$
  • $K(x,y) = K(y,x)$
  • for all $n$ and all sequences $x_1, \ldots, x_n$, the Gram matrix $\mathbf{K}$ with $\mathbf{K}_{ij} = K(x_i, x_j)$ is positive definite.

A space that admits a kernel is handy in ML, and often if all you have is a distance function, you can compute a kernel-like object in the form

$$ \kappa_d(x, y) = \exp(- \gamma d^2(x,y)) $$

The question:

Under what conditions on $d$ is the resulting function $\kappa_d$ a kernel ?

share|improve this question
    
note: as pointed out by both commenters, my original kernel condition was wrong: I fixed it to say that $K(x,x) = 1$. –  Suresh Venkat Oct 26 '12 at 19:48

1 Answer 1

up vote 7 down vote accepted

It seems to me you might be looking for a variant of Schoenberg's theorem:

(Think $\Psi(x,y) = d(x,y)^2$ in the following).

The function $\Psi \colon X \times X \to \mathbb{R}$ is said to be a kernel of conditionally negative type if

  1. $\Psi(x,x) = 0$ for all $x \in X$.
  2. $\Psi(x,y) = \Psi(y,x)$ for all $x,y \in X$.
  3. For all $n \in \mathbb{N}$, all $x_1,\dots,x_n \in X$ and all $c_1,\dots,c_n \in \mathbb{R}$ such that $\sum_{i=1}^n c_i = 0$ the inequality $$ \sum_{i,j=1}^n c_i c_j \Psi(x_i,x_j) \leq 0 $$ holds.

A positive semidefinite kernel is a kernel in your sense but without the condition $K(x,x) = 0$ iff $x = 0$ (presumably you meant $K(x,x)=1$ here, otherwise this would be incompatible with positive definiteness) and with positive definiteness weakened to positive semi-definiteness.

Theorem. For a symmetric function $\Psi\colon X \times X \to \mathbb{R}$ with $\Psi(x,x) = 0$ for all $x$ the following are equivalent:

  1. $\Psi$ is a kernel of conditionally negative type.
  2. The function $K(x,y) = \exp(-\gamma \Psi(x,y))$ is a positive semidefinite kernel for all $\gamma \geq 0$.

You can find a proof of this as Theorem C.3.2 on page 370 of the book Kazhdan's Property $(T)$ by Bekka, de la Harpe, and Valette, (link goes to Bekka's homepage). The rest of this appendix might have some useful information, too.


Added: Schoenberg's original article: Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938), 522-536.

share|improve this answer
    
This is precisely what I need, and yes I erred in the condition on the kernel. Thanks ! –  Suresh Venkat Oct 26 '12 at 19:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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