14
$\begingroup$

I am trying to understand the intuition behind kernel SVM's. Now, I understand how linear SVM's work, whereby a decision line is made which splits the data as best it can. I also understand the principle behind porting data to a higher-dimensional space, and how this can make it easier to find a linear decision line in this new space. What I do not understand is how a kernel is used to project data points to this new space.

What I know about a kernel is that it effectively represents the "similarity" between two data points. But how does this relate to the projection?

$\endgroup$
  • 3
    $\begingroup$ If you go to a high enough dimensional space, all training data points can be perfectly separated by a plane. That doesn't mean it will have any predictive power whatsoever. I think going to very high dimensional space is the moral equivalent (a form of) of overfitting. $\endgroup$ – Mark L. Stone Aug 20 '15 at 21:11
  • $\begingroup$ @Mark L. Stone: that's correct(+1) but it may still be a good question to ask how a kernel can map to in infinite dimensional space? How does that work? I tried, see my answer $\endgroup$ – user83346 Aug 21 '15 at 15:04
  • $\begingroup$ I would be careful about calling the feature mapping a "projection". The feature mapping is generally nonlinear transformation. $\endgroup$ – Paul Aug 23 '15 at 14:34
  • $\begingroup$ A very helpful post on the kernel trick visualises the inner product space of the kernel and describes how the high-dimensional feature vectors are used to achieve this, hopefully this answers the question concisely: eric-kim.net/eric-kim-net/posts/1/kernel_trick.html $\endgroup$ – JStrahl Nov 22 '16 at 13:57
5
$\begingroup$

Let $h(x)$ be the projection to high dimension space $\mathcal{F}$. Basically the kernel function $K(x_1,x_2)=\langle h(x_1),h(x_2)\rangle$, which is the inner-product. So it's not used to project data points, but rather an outcome of the projection. It can be considered a measure of similarity, but in an SVM, it's more than that.

The optimization for finding the best separating hyperplane in $\mathcal{F}$ involves $h(x)$ only through the inner-product form. That's to say, if you know $K(\cdot,\cdot)$, you don't need to know the exact form of $h(x)$, which makes the optimization easier.

Each kernel $K(\cdot,\cdot)$ has a corresponding $h(x)$ as well. So if you're using an SVM with that kernel, then you're implicitly finding the linear decision line in the space that $h(x)$ maps into.

Chapter 12 of Elements of Statistical Learning gives a brief introduction to SVM . This gives more detail about the connection between kernel and feature mapping: http://statweb.stanford.edu/~tibs/ElemStatLearn/

$\endgroup$
  • $\begingroup$ do you mean that for a kernel $K(x,y)$ there is a unique underlying $h(x)$? $\endgroup$ – user83346 Aug 20 '15 at 15:27
  • 2
    $\begingroup$ @fcoppens No; for a trivial example, consider $h$ and $-h$. However, there does exist a unique reproducing kernel Hilbert space corresponding to that kernel. $\endgroup$ – Dougal Aug 20 '15 at 16:10
  • $\begingroup$ @Dougal: Then I can agree with you, but in the answer above it was said 'a corresponding $h$' so I wanted to be sure. For the RKHS I see, but do you think that it is possible to explain in an 'intuitive way' what this transformation $h$ looks like for a Kernel $K(x,y)$ ? $\endgroup$ – user83346 Aug 20 '15 at 16:23
  • $\begingroup$ @fcoppens In general, no; finding explicit representations of these maps is difficult. For certain kernels it's either not too hard or been done before, though. $\endgroup$ – Dougal Aug 20 '15 at 16:26
  • 1
    $\begingroup$ @fcoppens you're right, the h(x) is not unique. You can easily make changes to h(x) while keeping the inner-product <h(x),h(x')> the same. However, you can consider them as basis functions, and the space they span (i.e the RKHS) is unique. $\endgroup$ – Lii Aug 20 '15 at 17:41
4
$\begingroup$

The useful properties of kernel SVM are not universal - they depend on the choice of kernel. To get intuition it's helpful to look at one of the most commonly used kernels, the Gaussian kernel. Remarkably, this kernel turns SVM into something very much like a k-nearest neighbor classifier.

This answer explains the following:

  1. Why perfect separation of positive and negative training data is always possible with a Gaussian kernel of sufficiently small bandwidth (at the cost of overfitting)
  2. How this separation may be interpreted as linear in a feature space.
  3. How the kernel is used to construct the mapping from data space to feature space. Spoiler: the feature space is a very mathematically abstract object, with an unusual abstract inner product based on the kernel.

1. Achieving perfect separation

Perfect separation is always possible with a Gaussian kernel because of the kernel's locality properties, which lead to an arbitrarily flexible decision boundary. For sufficiently small kernel bandwidth, the decision boundary will look like you just drew little circles around the points whenever they are needed to separate the positive and negative examples:

Something like this

(Credit: Andrew Ng's online machine learning course).

So, why does this occur from a mathematical perspective?

Consider the standard setup: you have a Gaussian kernel $K(\mathbf{x},\mathbf{z}) = \exp(- ||\mathbf{x}-\mathbf{z}||^2 / \sigma^2)$ and training data $(\mathbf{x}^{(1)},y^{(1)}), (\mathbf{x}^{(2)},y^{(2)}), \ldots, (\mathbf{x}^{(n)},y^{(n)})$ where the $y^{(i)}$ values are $\pm 1$. We want to learn a classifier function

$$\hat{y}(\mathbf{x}) = \sum_i w_i y^{(i)} K(\mathbf{x}^{(i)},\mathbf{x})$$

Now how will we ever assign the weights $w_i$? Do we need infinite dimensional spaces and a quadratic programming algorithm? No, because I just want to show that I can separate the points perfectly. So I make $\sigma$ a billion times smaller than the smallest separation $||\mathbf{x}^{(i)} - \mathbf{x}^{(j)}||$ between any two training examples, and I just set $w_i = 1$. This means that all the training points are a billion sigmas apart as far as the kernel is concerned, and each point completely controls the sign of $\hat{y}$ in its neighborhood. Formally, we have

$$ \hat{y}(\mathbf{x}^{(k)}) = \sum_{i=1}^n y^{(k)} K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = y^{(k)} K(\mathbf{x}^{(k)},\mathbf{x}^{(k)}) + \sum_{i \neq k} y^{(i)} K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = y^{(k)} + \epsilon$$

where $\epsilon$ is some arbitrarily tiny value. We know $\epsilon$ is tiny because $\mathbf{x}^{(k)}$ is a billion sigmas away from any other point, so for all $i \neq k$ we have

$$K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = \exp(- ||\mathbf{x}^{(i)} - \mathbf{x}^{(k)}||^2 / \sigma^2) \approx 0.$$

Since $\epsilon$ is so small, $\hat{y}(\mathbf{x}^{(k)})$ definitely has the same sign as $y^{(k)}$, and the classifier achieves perfect accuracy on the training data. In practice this would be terribly overfitting but it shows the tremendous flexibility of the Gaussian kernel SVM, and how it can act very similar to a nearest neighbor classifier.

2. Kernel SVM learning as linear separation

The fact that this can be interpreted as "perfect linear separation in an infinite dimensional feature space" comes from the kernel trick, which allows you to interpret the kernel as an abstract inner product some new feature space:

$$K(\mathbf{x}^{(i)},\mathbf{x}^{(j)}) = \langle\Phi(\mathbf{x}^{(i)}),\Phi(\mathbf{x}^{(j)})\rangle$$

where $\Phi(\mathbf{x})$ is the mapping from the data space into the feature space. It follows immediately that the $\hat{y}(\mathbf{x})$ function as a linear function in the feature space:

$$ \hat{y}(\mathbf{x}) = \sum_i w_i y^{(i)} \langle\Phi(\mathbf{x}^{(i)}),\Phi(\mathbf{x})\rangle = L(\Phi(\mathbf{x}))$$

where the linear function $L(\mathbf{v})$ is defined on feature space vectors $\mathbf{v}$ as

$$ L(\mathbf{v}) = \sum_i w_i y^{(i)} \langle\Phi(\mathbf{x}^{(i)}),\mathbf{v}\rangle$$

This function is linear in $\mathbf{v}$ because it's just a linear combination of inner products with fixed vectors. In the feature space, the decision boundary $\hat{y}(\mathbf{x}) = 0$ is just $L(\mathbf{v}) = 0$, the level set of a linear function. This is the very definition of a hyperplane in the feature space.

3. How the kernel is used to construct the feature space

Kernel methods never actually "find" or "compute" the feature space or the mapping $\Phi$ explicitly. Kernel learning methods such as SVM do not need them to work; they only need the kernel function $K$. It is possible to write down a formula for $\Phi$ but the feature space it maps to is quite abstract and is only really used for proving theoretical results about SVM. If you're still interested, here's how it works.

Basically we define an abstract vector space $V$ where each vector is a function from $\mathcal{X}$ to $\mathbb{R}$. A vector $f$ in $V$ is a function formed from a finite linear combination of kernel slices: $$f(\mathbf{x}) = \sum_{i=1}^n \alpha_i K(\mathbf{x}^{(i)},\mathbf{x})$$ (Here the $\mathbf{x}^{(i)}$ are just an arbitrary set of points and need not be the same as the training set.) It is convenient to write $f$ more compactly as $$f = \sum_{i=1}^n \alpha_i K_{\mathbf{x}^{(i)}}$$ where $K_\mathbf{x}(\mathbf{y}) = K(\mathbf{x},\mathbf{y})$ is a function giving a "slice" of the kernel at $\mathbf{x}$.

The inner product on the space is not the ordinary dot product, but an abstract inner product based on the kernel:

$$\langle \sum_{i=1}^n \alpha_i K_{\mathbf{x}^{(i)}}, \sum_{j=1}^n \beta_j K_{\mathbf{x}^{(j)}} \rangle = \sum_{i,j} \alpha_i \beta_j K(\mathbf{x}^{(i)},\mathbf{x}^{(j)})$$

This definition is very deliberate: its construction ensures the identity we need for linear separation, $\langle \Phi(\mathbf{x}), \Phi(\mathbf{y}) \rangle = K(\mathbf{x},\mathbf{y})$.

With the feature space defined in this way, $\Phi$ is a mapping $\mathcal{X} \rightarrow V$, taking each point $\mathbf{x}$ to the "kernel slice" at that point:

$$\Phi(\mathbf{x}) = K_\mathbf{x}, \quad \text{where} \quad K_\mathbf{x}(\mathbf{y}) = K(\mathbf{x},\mathbf{y}). $$

You can prove that $V$ is an inner product space when $K$ is a positive definite kernel. See this paper for details.

$\endgroup$
  • $\begingroup$ Great explanation, but I think you have missed a minus for the definition of the gaussian kernel. K(x,z)=exp(-||x−z||2/σ2) . As it's written, it does not make sense with the ϵ found in the part (1) $\endgroup$ – hqxortn Feb 12 '16 at 9:42
1
$\begingroup$

For the background and the notations I refer to How to calculate decision boundary from support vectors?.

So the features in the 'original' space are the vectors $x_i$, the binary outcome $y_i \in \{-1, +1\}$ and the Lagrange multipliers are $\alpha_i$.

As said by @Lii (+1) the Kernel can be written as $K(x,y)=h(x) \cdot h(y)$ ('$\cdot$' represents the inner product.

I will try to give some 'intuitive' explanation of what this $h$ looks like, so this answer is no formal proof, it just wants to give some feeling of how I think that this works. Do not hesitate to correct me if I am wrong.

I have to 'transform' my feature space (so my $x_i$) into some 'new' feature space in which the linear separation will be solved.

For each observation $x_i$, I define functions $\phi_i(x)=K(x_i,x)$, so I have a function $\phi_i$ for each element of my training sample. These functions $\phi_i$ span a vector space. The vector space spanned by the $\phi_i$, note it $V=span(\phi_{i, i=1,2,\dots N})$.

I will try to argue that is the vector space in which linear separation will be possible. By definition of the span, each vector in the vector space $V$ can be written as as a linear combination of the $\phi_i$, i.e.: $\sum_{i=1}^N \gamma_i \phi_i$, where $\gamma_i$ are real numbers.

$N$ is the size of the training sample and therefore the dimension of the vector space $V$ can go up to $N$, depending on whether the $\phi_i$ are linear independent. As $\phi_i(x)=K(x_i,x)$ (see supra, we defined $\phi$ in this way), this means that the dimension of $V$ depends on the kernel used and can go up to the size of the training sample.

The transformation, that maps my original feature space to $V$ is defined as

$\Phi: x_i \to \phi(x)=K(x_i, x)$.

This map $\Phi$ maps my original feature space onto a vector space that can have a dimension that goed up to the size of my training sample.

Obviously, this transformation (a) depends on the kernel, (b) depends on the values $x_i$ in the training sample and (c) can, depending on my kernel, have a dimension that goes up to the size of my training sample and (d) the vectors of $V$ look like $\sum_{i=1}^N \gamma_i \phi_i$, where $\gamma_i$, $\gamma_i$ are real numbers.

Looking at the function $f(x)$ in How to calculate decision boundary from support vectors? it can be seen that $f(x)=\sum_i y_i \alpha_i \phi_i(x)+b$.

In other words, $f(x)$ is a linear combination of the $\phi_i$ and this is a linear separator in the V-space : it is a particular choice of the $\gamma_i$ namely $\gamma_i=\alpha_i y_i$ !

The $y_i$ are known from our observations, the $\alpha_i$ are the Lagrange multipliers that the SVM has found. In other words SVM find, through the use of a kernel and by solving a quadratic programming problem, a linear separation in the $V$-spave.

This is my intuitive understanding of how the 'kernel trick' allows one to 'implicitly' transform the original feature space into a new feature space $V$, with a different dimension. This dimension depends on the kernel you use and for the RBF kernel this dimension can go up to the size of the training sample.

So kernels are a technique that allows SVM to transform your feature space , see also What makes the Gaussian kernel so magical for PCA, and also in general?

$\endgroup$
  • $\begingroup$ "for each element of my training sample" -- is element here referring to a row or column (i.e. feature ) $\endgroup$ – user1761806 Aug 29 '17 at 19:26
  • $\begingroup$ what is x and x_i? If my X is an input of 5 columns, and 100 rows, what would x and x_i be? $\endgroup$ – user1761806 Aug 29 '17 at 22:17
  • $\begingroup$ @user1761806 an element is a row. The notation is explained in the link at the beginning of the answer $\endgroup$ – user83346 Aug 30 '17 at 6:35
1
$\begingroup$

Transform predictors (input data) to a high-dimensional feature space. It is sufficient to just specify the kernel for this step and the data is never explicitly transformed to the feature space. This process is commonly known as the kernel trick.

Let me explain it. The kernel trick is the key here. Consider the case of a Radial Basis Function (RBF) Kernel here. It transforms the input to infinite dimensional space. The transformation of input $x$ to $\phi(x)$ can be represented as shown below (taken from http://www.csie.ntu.edu.tw/~cjlin/talks/kuleuven_svm.pdf)

enter image description here

The input space is finite dimensional but the transformed space is infinite dimensional. Transforming the input to an infinite dimensional space is something that happens as a result of the kernel trick. Here $x$ which is the input and $\phi$ is the transformed input. But $\phi$ is not computed as it is, instead the product $\phi(x_i)^T\phi(x)$ is computed which is just the exponential of the norm between $x_i$ and $x$.

There is a related question Feature map for the Gaussian kernel to which there is a nice answer https://stats.stackexchange.com/a/69767/86202.

The output or decision function is a function of the kernel matrix $K(x_i,x)=\phi(x_i)^T\phi(x)$ and not of the input $x$ or transformed input $\phi$ directly. enter image description here

$\endgroup$
0
$\begingroup$

Mapping to a higher dimension is merely a trick to solve a problem that is defined in the original dimension; so concerns such as overfitting your data by going into a dimension with too many degrees of freedom are not a byproduct of the mapping process, but are inherent in your problem definition.

Basically, all that mapping does is converting conditional classification in the original dimension to a plane definition in the higher dimension, and because there is a 1 to 1 relationship between the plane in the higher dimension and your conditions in the lower dimension, you can always move between the two.

Taking the problem of overfitting, clearly, you can overfit any set of observations by defining enough conditions to isolate each observation into its own class, which is equivalent of mapping your data to (n-1)D where n is the number of your observations.

Taking the simplest problem, where your observations are [[1,-1], [0,0], [1,1]] [[feature, value]], by moving into the 2D dimension and separating your data with a line, your are simply turning the conditional classification of feature < 1 && feature > -1 : 0 to defining a line that passes through (-1 + epsilon, 1 - epsilon). If you had more data points and needed more condition, you just needed to add one more degree of freedom to your higher dimension by each new condition that your define.

You can replace the process of mapping to a higher dimension with any process that provides you with a 1 to 1 relationship between the conditions and the degrees of freedom of your new problem. Kernel tricks simply do that.

$\endgroup$
  • 1
    $\begingroup$ As a different example, take the problem where the phenomenon results in observations of the form of [x, floor(sin(x))]. Mapping your problem into a 2D dimension is not helpful here at all; in fact, mapping to any plane will not be helpful here, which is because defining the problem as a set of x < a && x > b : z is not helpful in this case. The simplest mapping in this case is mapping into a polar coordinate, or into the imaginary plane. $\endgroup$ – Hou May 26 '18 at 16:50

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.