Radial basis function kernel

The RBF kernel on two samples ${\displaystyle \mathbf{x}\in {\mathbb{R}}^k}$ and ${\displaystyle {\mathbf{x}}^{\prime }}$, represented as feature vectors in some input space, is defined as

${\displaystyle K(\mathbf{x},{\mathbf{x}}^{\prime })=\exp \left(-\frac{\Vert \mathbf{x}-{\mathbf{x}}^{\prime }{\Vert }^2}{2{\sigma }^2}\right)}$

${\displaystyle \Vert \mathbf{x}-{\mathbf{x}}^{\prime }{\Vert }^2}$ may be recognized as the squared Euclidean distance between the two feature vectors. ${\displaystyle \sigma }$ is a free parameter. An equivalent definition involves a parameter ${\displaystyle \gamma =\frac{1}{2{\sigma }^2}}$:

${\displaystyle K(\mathbf{x},{\mathbf{x}}^{\prime })=\exp (-\gamma \Vert \mathbf{x}-{\mathbf{x}}^{\prime }{\Vert }^2)}$

Since the value of the RBF kernel decreases with distance and ranges between zero (in the infinite-distance limit) and one (when x = x'), it has a ready interpretation as a similarity measure. The feature space of the kernel has an infinite number of dimensions; for ${\displaystyle \sigma =1}$, its expansion using the multinomial theorem is:

${\displaystyle \begin{array}{rl}\exp \left(-\frac{1}{2}\Vert \mathbf{x}-{\mathbf{x}}^{\prime }{\Vert }^2\right)& =\exp (\frac{2}{2}{\mathbf{x}}^{\mathrm{\top }}{\mathbf{x}}^{\prime }-\frac{1}{2}\Vert \mathbf{x}{\Vert }^2-\frac{1}{2}\Vert {\mathbf{x}}^{\prime }{\Vert }^2)\\ & =\exp ({\mathbf{x}}^{\mathrm{\top }}{\mathbf{x}}^{\prime })\exp (-\frac{1}{2}\Vert \mathbf{x}{\Vert }^2)\exp (-\frac{1}{2}\Vert {\mathbf{x}}^{\prime }{\Vert }^2)\\ & =\sum _{j=0}^{\mathrm{\infty }}\frac{({\mathbf{x}}^{\mathrm{\top }}{\mathbf{x}}^{\prime }{)}^j}{j!}\exp \left(-\frac{1}{2}\Vert \mathbf{x}{\Vert }^2\right)\exp \left(-\frac{1}{2}\Vert {\mathbf{x}}^{\prime }{\Vert }^2\right)\\ & =\sum _{j=0}^{\mathrm{\infty }}\sum _{n_1+n_2+\cdots +n_k=j}\exp \left(-\frac{1}{2}\Vert \mathbf{x}{\Vert }^2\right)\frac{x_1^{n_1}\cdots x_k^{n_k}}{\sqrt{n_1!\cdots n_k!}}\exp \left(-\frac{1}{2}\Vert {\mathbf{x}}^{\prime }{\Vert }^2\right)\frac{{x^{\prime }}_1^{n_1}\cdots {x^{\prime }}_k^{n_k}}{\sqrt{n_1!\cdots n_k!}}\\ & =⟨\phi (\mathbf{x}),\phi ({\mathbf{x}}^{\prime })⟩\end{array}}$

${\displaystyle \phi (\mathbf{x})=\exp \left(-\frac{1}{2}\Vert \mathbf{x}{\Vert }^2\right)\left(a_{{\ell }_0}^{(0)},a_1^{(1)},\dots ,a_{{\ell }_1}^{(1)},\dots ,a_1^{(j)},\dots ,a_{{\ell }_j}^{(j)},\dots \right)}$

where ${\displaystyle {\ell }_j=(\genfrac{}{}{0ex}{}{k+j-1}{j})}$,

${\displaystyle a_{\ell }^{(j)}=\frac{x_1^{n_1}\cdots x_k^{n_k}}{\sqrt{n_1!\cdots n_k!}}|n_1+n_2+\cdots +n_k=j\wedge 1\le \ell \le {\ell }_j}$

Approximations

Because support vector machines and other models employing the kernel trick do not scale well to large numbers of training samples or large numbers of features in the input space, several approximations to the RBF kernel (and similar kernels) have been introduced. Typically, these take the form of a function z that maps a single vector to a vector of higher dimensionality, approximating the kernel:

${\displaystyle ⟨z(\mathbf{x}),z({\mathbf{x}}^{\prime })⟩\approx ⟨\phi (\mathbf{x}),\phi ({\mathbf{x}}^{\prime })⟩=K(\mathbf{x},{\mathbf{x}}^{\prime })}$

where ${\displaystyle \phi }$ is the implicit mapping embedded in the RBF kernel.

Fourier random features

One way to construct such a z is to randomly sample from the Fourier transformation of the kernel$${\displaystyle \phi (x)=\frac{1}{\sqrt{D}}[\cos ⟨w_1,x⟩,\sin ⟨w_1,x⟩,\dots ,\cos ⟨w_D,x⟩,\sin ⟨w_D,x⟩{]}^T}$$where ${\displaystyle w_1,...,w_D}$ are independent samples from the normal distribution ${\displaystyle N(0,{\sigma }^{-2}I)}$.

Theorem: ${\displaystyle \mathrm{E}[⟨\phi (x),\phi (y)⟩]=e^{\Vert x-y{\Vert }^2/(2{\sigma }^2)}.}$

Proof: It suffices to prove the case of ${\displaystyle D=1}$. Use the trigonometric identity ${\displaystyle \cos (a-b)=\cos (a)\cos (b)+\sin (a)\sin (b)}$, the spherical symmetry of gaussian distribution, then evaluate the integral

${\displaystyle {\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}\frac{\cos (kx)e^{-x^2/2}}{\sqrt{2\pi }}dx=e^{-k^2/2}.}$

Theorem: ${\displaystyle \mathrm{Var}[⟨\phi (x),\phi (y)⟩]=O(D^{-1})}$. (Appendix A.2).

Nyström method

Another approach uses the Nyström method to approximate the eigendecomposition of the Gram matrix K, using only a random sample of the training set.