Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to understand the math behind svm classifiers and I'm not clear and not able to visualize how does having inner products in the transformed space help us to separate data.

Think of a circle in 2d where there are four points intersecting the xy plane. So the four points will be (x1,0),(-x1,0) and (0,y1),(0-y1). These are your four black points and let there be four more points on the circle at 22.5 degrees from the origin in all four quadrants. These are your white points. I want to separate the black and white points. Hope this helps.

share|improve this question
    
Maybe you could give an example of what you meant by separating data? Regards. –  awllower Apr 7 '13 at 3:50

1 Answer 1

To understand this phenomena you should not try to make it in one step, from the inner product to the hyperplane.

There are two separate things:

  • Feature space, which is some custom space (often of bigger dimensionality then input space), in which datas' image is linearly spearable;
  • Kernel trick, which makes the computations in this (possibly infinitely dimensional) feature space efficient.

Linear separation in the feature space is possible due to its construction - for just some intuition - remember, then for any consistent data $D$ (in the sense that there are no such $i,j$ that $x_i = x_j \wedge y_i \neq y_j$) there is a feature space $F$, and a mapping $\phi$ such that $\phi(D)$ is linearly separable. You can simply take $F=\mathbb{R}$, and $\phi(x_i) = y_i$ (so all points with label $-1$ are projected to the point $-1$, and all with label $1$ to the $1$, and obviously $1$ and $-1$ are linearly separable in $F$). Of course such a mapping is artificial, but shows, that you can always find such mapping. The core idea of kernel-trick for SVM is that it can introduce feature space with many dimensions (and so - there is a great probability that data will be linearly separable there).

Simple example of the feature space transforming data from $\mathbb{R}^2$ to $\mathbb{R}^3$ is provided on the following image

polynomial kernel

Unfortunately, computation of such multi-dimensional feature space can be intracktable (inefficient) so you cannot simply transform your data through $\phi$ and run linear SVM. This is why a kernel trick is so valuable, it is based on the observation, that many algorithms can be described in such a way, that the only operation performed on the input data is a inner product. This way, you do not have to ever compute the actual features, instead - you just compute inner products, which in many cases - are very efficient (for example - polynomial kernel takes $O(n)$ operations to compute, while feature space projection takes $O(n^2)$).

For your example you could define a kernel $K(x_i,x_j) = y_iy_j$, where $y_i$ is a label of $x_i$ (it is easy to check that this is a correctly defined inner product and that it makes data separable).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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