# Feature map for the Gaussian kernel

In SVM, the Gaussian kernel is defined as: $$K(x,y)=\exp\left({-\frac{\|x-y\|_2^2}{2\sigma^2}}\right)=\phi(x)^T\phi(y)$$ where $x, y\in \mathbb{R^n}$. I do not know the explicit equation of $\phi$. I want to know it.

I also want to know whether $$\sum_ic_i\phi(x_i)=\phi \left(\sum_ic_ix_i \right)$$ where $c_i\in \mathbb R$. Now, I think it is not equal, because using a kernel handles the situation where the linear classier does not work. I know $\phi$ projects x to a infinite space. So if it still remains linear, no matter how many dimensions it is, svm still can not make a good classification.

• why does this kernel imply a transformation? Or are you referring to the associated feature space? – Placidia Apr 9 '15 at 0:03
• Yes, what is the feature space $\phi(\cdot)$ so that $\phi^T(x)\phi(x^{'}) = exp(-\frac{1}{2\sigma^2}\|x-x^{'}\|^2)$ – user27886 Apr 9 '15 at 1:55

You can obtain the explicit equation of $\phi$ for the Gaussian kernel via the Tailor series expansion of $e^x$. For notational simplicity, assume $x\in \mathbb{R}^1$:

$$\phi(x) = e^{-x^2/2\sigma^2} \Big[ 1, \sqrt{\frac{1}{1!\sigma^2}}x,\sqrt{\frac{1}{2!\sigma^4}}x^2,\sqrt{\frac{1}{3!\sigma^6}}x^3,\ldots\Big]^T$$

This is also discussed in more detail in these slides by Chih-Jen Lin of NTU (slide 11 specifically). Note that in the slides $\gamma=\frac{1}{2\sigma^2}$ is used as kernel parameter.

The equation in the OP only holds for the linear kernel.

• Hi, but this equation above only suit one dimension. – Vivian Sep 11 '13 at 17:54
• So, here, the reproducing kernel Hilbert space is a subspace of $\ell^2$, correct? – The_Anomaly May 17 '17 at 22:51
• Is there also an explicit representation of the Laplacian kernel? – Felix Crazzolara Jun 23 '19 at 18:20

For any valid psd kernel $$k : \mathcal X \times \mathcal X \to \mathbb R$$, there exists a feature map $$\varphi : \mathcal X \to \mathcal H$$ such that $$k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$$. The space $$\mathcal H$$ and embedding $$\varphi$$ in fact need not be unique, but there is an important unique $$\mathcal H$$ known as the reproducing kernel Hilbert space (RKHS).

The RKHS is discussed by: Steinwart, Hush and Scovel, An Explicit Description of the Reproducing Kernel Hilbert Spaces of Gaussian RBF Kernels, IEEE Transactions on Information Theory 2006 (doi, free citeseer pdf).

It's somewhat complicated, and they need to analyze it via the extension of the Gaussian kernel to complex inputs and outputs, but it boils down to this: define $$e_n : \mathbb R \to \mathbb R$$ as $$e_n(x) := \sqrt{\frac{(2 \sigma^2)^n}{n!}} x^n e^{-\sigma^2 x^2}$$ and, for a tuple $$\nu = (\nu_1, \cdots, \nu_d) \in \mathbb N_0^d$$, its tensor product $$e_\nu : \mathbb R^d \to \mathbb R$$ as $$e_\nu(x) = e_{\nu_1}(x_1) \cdots e_{\nu_d}(x_d) .$$ Then their Proposition 3.6 says that any function $$f \in \mathcal H_\sigma$$, the RKHS for a Gaussian kernel of bandwidth $$\sigma > 0$$, can be written as $$f(x) = \sum_{\nu \in \mathbb N_0^d} b_\nu e_\nu(x) \qquad \lVert f \rVert_{\mathcal H_\sigma(X)}^2 = \sum_{\nu \in \mathbb N_0^d} b_\nu^2 .$$

We can think of $$\mathcal H_\sigma$$ as being essentially the space of square-summable coefficients $$(b_\nu)_{\nu \in \mathbb N_0^d}$$.

The question remains, though: what is the the sequence $$b_\nu$$ for the function $$\phi(x)$$? The paper doesn't seem to directly answer this question (unless I'm missing it as an obvious implication somewhere).

The do also give a more straightforward embedding into $$L_2(\mathbb R^d)$$, the Hilbert space of square-integrable functions from $$\mathbb R^d \to \mathbb R$$: $$\Phi(x) = \frac{(2 \sigma)^{\frac{d}{2}}}{\pi^{\frac{d}{4}}} e^{- 2 \sigma^2 \lVert x - \cdot \rVert_2^2} .$$ Note that $$\Phi(x)$$ is itself a function from $$\mathbb R^d$$ to $$\mathbb R$$. It's basically the density of a $$d$$-dimensional Gaussian with mean $$x$$ and covariance $$\frac{1}{4 \sigma^2} I$$; only the normalizing constant is different. Thus when we take $$\langle \Phi(x), \Phi(y) \rangle_{L_2} = \int [\Phi(x)](t) \; [\Phi(y)](t) \,\mathrm d t ,$$ we're taking the product of Gaussian density functions, which is itself a certain constant times a Gaussian density functions. When you do that integral by $$t$$, then, the constant that falls out ends up being exactly $$k(x, y)$$.

These are not the only embeddings that work.

Another is based on the Fourier transform, which the celebrated paper of Rahimi and Recht (Random Features for Large-Scale Kernel Machines, NIPS 2007) approximates to great effect.

You can also do it using Taylor series: effectively the infinite version of Cotter, Keshet, and Srebro, Explicit Approximations of the Gaussian Kernel, arXiv:1109.4603.

• Douglas Zare gave a 1d version of the "more straightforward" embedding in an interesting thread here. – Danica May 6 '15 at 3:11
• Here you find a more 'intuitive' explanation that the $\Phi$ can map onto a spave of dimension equal to the size of the training sample, even for an infinite training sample: stats.stackexchange.com/questions/80398/… – user83346 Aug 22 '15 at 8:40

It seems to me that your second equation will only be true if $\phi$ is a linear mapping (and hence $K$ is a linear kernel). As the Gaussian kernel is non-linear, the equality will not hold (except perhaps in the limit as $\sigma$ goes to zero).

• thank you for your answer. When $\sigma\rightarrow 0$, the dimension of the Gaussian kernel projects would increase. And by your inspiration, now I think it is not equal. Because, using kernel just handle the situation that linear classification does not work. – Vivian Sep 11 '13 at 15:40

# EXPLICIT EXPRESSION AND DERIVATION VIA DIRECT PROOF

The explicit expression for $$\phi$$ you are asking for is the following:

## Theorem:

Given the Gaussian RBF Kernel $$K_\sigma$$ between two $$n$$-dimensional vectors ($$x$$ and another), for each $$j$$ from 0 to infinity and for every combination of $$n$$ indices (labeled as $$k$$) that add up to $$j$$, the feature vector $$\phi(x)$$ has a feature that looks like this:

$$\phi_{\sigma, j, k}(x) = c_{\sigma, j}(x) \cdot f_{j, k}(x)$$

Where:

\begin{aligned} c_{\sigma, j}(x) &= \frac{K_\sigma(x, 0)}{\sigma^j \sqrt{j!}}\\ f_{j, k}(x) &= \begin{pmatrix} j\\k_1,k_2, \dots, k_n \end{pmatrix}^{\frac{1}{2}} \prod_{d=1}^n{x_d^{k_d}} \end{aligned}

This can be directly derived as follows:

## Definitions:

\begin{aligned} K_\sigma(x, y) = &e^{-\frac{\|x-y\|_2^2}{2\sigma^2}}\\ \epsilon := &e^{\frac{1}{\sigma^2}}\\ \epsilon^x = &\sum_{j=0}^{\infty}\left\{ \frac{x^j}{\sigma^{2j} \cdot j!} \right\}\\ (x_1 + x_2 + \dots + x_n)^j = &\sum_{k_1+k_2+\dots+k_n=j}\left\{ \begin{pmatrix} j\\k_1,k_2, \dots, k_n \end{pmatrix} \prod_{d=1}^n{x_d^{k_d}} \right\}\\ \end{aligned}

## Direct Proof:

First, we decompose the squared euclidean distance into its components, and perform the Taylor expansion for the $$xy$$ component:

\begin{aligned} K(x,y)= &e^{-\frac{\|x-y\|_2^2}{2\sigma^2}} =\epsilon^{\langle x, y \rangle} \cdot\epsilon^{-\frac{\|x\|_2^2}{2}} \cdot \epsilon^{-\frac{\|y\|_2^2}{2}}\\ = &\sum_{j=0}^{\infty}\left\{ \frac{\langle x, y \rangle^j}{\sigma^{2j} \cdot j!} \right\} \cdot\epsilon^{-\frac{\|x\|_2^2}{2}} \cdot \epsilon^{-\frac{\|y\|_2^2}{2}} \end{aligned}

For further convenience, we refactor the expression (using $$c$$ for more compact notation):

\begin{aligned} K(x,y) = &\sum_{j=0}^{\infty}\left\{\frac{\epsilon^{-\frac{\|x\|_2^2}{2}}}{\sigma^j \cdot \sqrt{j!}} \cdot \frac{\epsilon^{-\frac{\|y\|_2^2}{2}}}{\sigma^j \cdot \sqrt{j!}} \cdot \langle x, y \rangle^j \right\}\\ = &\sum_{j=0}^{\infty}\left\{ c_{\sigma, j}(x) \cdot c_{\sigma, j}(y) \cdot \langle x, y \rangle^j \right\}\\ \end{aligned}

And with help of the multinomial theorem, we can express the power of the dot product as follows (using $$f$$ for more compact notation):

\begin{aligned} \langle x, y \rangle^j = &\left(\sum_{d=1}^n x_d y_d \right)^j\\ = &\sum_{k_1+k_2+\dots+k_n=j}\left\{ \begin{pmatrix} j\\k_1,k_2, \dots, k_n \end{pmatrix} \prod_{d=1}^n{(x_dy_d)^{k_d}} \right\}\\ = &\sum_{k_1+k_2+\dots+k_n=j}\left\{ \begin{pmatrix} j\\k_1,\dots, k_n \end{pmatrix}^{\frac{1}{2}} \prod_{d=1}^n{x_d^{k_d}} \cdot \begin{pmatrix} j\\k_1, \dots, k_n \end{pmatrix}^{\frac{1}{2}} \prod_{d=1}^n{y_d^{k_d}} \right\}\\ =: &\sum_{k_1+k_2+\dots+k_n=j}\left\{f_{j,k}(x) \cdot f_{j, k}(y) \right\}\\ \end{aligned}

Now replacing in $$K$$ will allow us to end the proof:

\begin{aligned} K(x,y) = &\sum_{j=0}^{\infty}\left\{ c_{\sigma, j}(x) \cdot c_{\sigma, j}(y) \cdot \sum_{k_1+k_2+\dots+k_n=j}\left\{f_{j,k}(x) \cdot f_{j, k}(y) \right\} \right\}\\ = &\sum_{j=0}^{\infty} \sum_{k_1+k_2+\dots+k_n=j}\left\{ c_{\sigma, j}(x) f_{j,k}(x) \cdot c_{\sigma, j}(y) f_{j, k}(y) \right\}\\ = &\langle \phi(x), \phi(y) \rangle\\ &\square \end{aligned}

Where each $$\phi$$ is a vector with one entry for every combination of $$n$$ indices (labeled as $$k$$) that add up to $$j$$, and this for each $$j$$ from 0 to infinity.

hope this helps! Cheers,
Andres

• This should be the top answer man. Good Job! – hoymkot Mar 6 at 22:51
• Thanks! Glad it helps – fr_andres Mar 7 at 12:47
• explicit and clear – YUAN Zhiri Mar 9 at 3:42