Solved – How to prove that the radial basis function is a kernel

kernel tricksvm

How to prove that the radial basis function $k(x, y) = \exp(-\frac{||x-y||^2)}{2\sigma^2})$ is a kernel? As far as I understand, in order to prove this we have to prove either of the following:

  1. For any set of vectors $x_1, x_2, …, x_n$ matrix $K(x_1, x_2, …, x_n)$ = $(k(x_i, x_j))_{n \times n}$ is positive semidefinite.

  2. A mapping $\Phi$ can be presented such as $k(x, y)$ = $\langle\Phi(x), \Phi(y)\rangle$.

Any help?

Best Answer

Zen used method 1. Here is method 2: Map $x$ to a spherically symmetric Gaussian distribution centered at $x$ in the Hilbert space $L^2$. The standard deviation and a constant factor have to be tweaked for this to work exactly. For example, in one dimension,

$$ \int_{-\infty}^\infty \frac{\exp[-(x-z)^2/(2\sigma^2)]}{\sqrt{2 \pi} \sigma} \frac{\exp[-(y-z)^2/(2 \sigma^2)}{\sqrt{2 \pi} \sigma} dz = \frac{\exp [-(x-y)^2/(4 \sigma^2)]}{2 \sqrt \pi \sigma}. $$

So, use a standard deviation of $\sigma/\sqrt 2$ and scale the Gaussian distribution to get $k(x,y) = \langle \Phi(x), \Phi(y)\rangle$. This last rescaling occurs because the $L^2$ norm of a normal distribution is not $1$ in general.

Related Question