4
$\begingroup$

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?
$\endgroup$
2
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ @hardmath Judging from the next line, I think it is quite obvious that he means column vectors. $\endgroup$ – Martin Thoma Jan 21 '16 at 6:08
  • $\begingroup$ @moose: I suggest sticking with your Question's notation $x\cdot y$ and $\Phi(x) \cdot \Phi(y)$ (if only out of petty consistency). $\endgroup$ – hardmath Jan 21 '16 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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