What is an example of a SVM kernel, where one implicitly uses an infinity-dimensional space?

Question

Reading the Wikipedia article about SVMs, I noticed

More formally, a support vector machine constructs a hyperplane or set of hyperplanes in a high- or infinite-dimensional space, which can be used for classification, regression, or other tasks.

I continued with "A Tutorial on Support Vector Machines for Pattern Recognition" by Christopher JC Burges and stumbled over the following (please not that $x \cdot y$ is the dot product):

Now suppose we first mapped the data to some other (possibly infinite dimensional) Euclidean space $\mathcal{H}$, using a mapping which we will call $\Phi$: $$\Phi : \mathbb{R}^d \rightarrow \mathcal{H}$$ Then of course the training algorithm would only depend on the data through dot products in $\mathcal{H}$, i.e. on functions of the form $\Phi(\mathbf{x}_i)\cdot \Phi(\mathbf{x}_j)$. Now if there were a “kernel function” $K$ such that $K(\mathbf{x}_i, \mathbf{x}_j) = \Phi(\mathbf{x}_i)\cdot\Phi(\mathbf{x}_j)$, we would only need to use $K$ in the training algorithm, and would never need to explicitly even know what $\Phi$ is. One example is $$K(\mathbf{x}_i, \mathbf{x}_j ) = e^{- \| \mathbf{x}_i - \mathbf{x}_j\|^2 / 2 \sigma^2}$$ In this particular example, $\mathcal{H}$ is infinite dimensional, so it would not be very easy to work with $\Phi$ explicitly.

I have three questions which are closely related to this. I am happy with any answer which answers any of my questions:

1. Why would $\mathcal{H}$ be infinitely dimensional in this case?
2. What is $\Phi$ in this case?
3. In other sources I read that the Kernel function has to be positive definite. Why?

Answer 1

To understand the first two questions, let's consider $x, y \in \mathbb{R}^2, x=(x_1,x_2), y=(y_1, y_2)$ and examine the polynomial kernel of degree 2:

$$K(x,y)=(x^Ty)^2$$

Which can be rewritten as:

$$K(x,y) = (x_1y_1 + x_2y_2)^2 = x_1^2y_1^2 + 2x_1y_1x_2y_2 + x_2^2y_2^2$$

We know that the kernel function is $K(x,y)=\Phi(x)^T\Phi(y)$, therefore we try to find a feature map $\Phi$ that will be equivalent to the above. Let

$$\Phi(x)=(x_1^2, \sqrt{2}x_1x_2, x_2^2)$$

From this, we can see that $\Phi(x)^T\Phi(y) = x_1^2y_1^2 + 2x_1y_1x_2y_2 + x_2^2y_2^2$, which is the kernel function!

Notice that by using $\Phi$ we mapped the input vectors from $\mathbb{R}^2$ to $\mathbb{R}^3$, therefore when we compute $K(x,y)$, this mapping will be implicitly performed.

Now, going back to your example (the RBF kernel). Let $\gamma = \frac{1}{2\sigma^2}$ and let's assume $x \in \mathbb{R}^1$:

$$K(x_i, x_j) = e^{-\gamma||x_i - x_j||^2} = e^{-\gamma(x_i - x_j)^2} = e^{-\gamma x_i^2 + 2\gamma x_i x_j - \gamma x_j^2}$$

Using the Taylor expansion of the exponential function for $e^{2\gamma x_i x_j}$ we can rewrite the above as:

$$ K(x_i, x_j) = e^{-\gamma x_i^2-\gamma x_j^2} \left(1 + \frac{2\gamma x_i x_j}{1!} + \frac{(2\gamma x_i x_j)^2}{2!} + \frac{(2\gamma x_i x_j)^3}{3!} + \ldots \right)$$

$$ = e^{-\gamma x_i^2-\gamma x_j^2} \left(1 \cdot 1 + \sqrt{\frac{2\gamma}{1!}}x_i \cdot \sqrt{\frac{2\gamma}{1!}}x_j + \sqrt{\frac{(2\gamma)^2}{2!}}x_i^2 \cdot \sqrt{\frac{(2\gamma)^2}{2!}}x_j^2 + \sqrt{\frac{(2\gamma)^3}{3!}}x_i^3 \cdot \sqrt{\frac{(2\gamma)^3}{3!}}x_j^3 + \ldots \right) = \Phi(x_i)^T \Phi(x_j)$$

And, explicitly the feature map will be: $$\Phi(x) = e^{-\gamma x^2} \left[1, \sqrt{\frac{2\gamma}{1!}}x,\sqrt{\frac{(2\gamma)^2}{2!}}x^2, \sqrt{\frac{(2\gamma)^3}{3!}}x^3, \ldots\right]$$

Which is an infinite-dimensional vector. As you said, in kernel methods we will compute inner products in feature space without explicitly having to define the mapping $\Phi$. Avoiding this explicit mapping is the famous "kernel trick".