# Why do some known kernel functions manage to achieve linear separation in feature space?

I'm currently learning the maximal margin classifier with kernels, and I'm wondering - why do they work? In which cases do they work best?

I'm especially interested in the RBF and polynomial kernels, but not only.

Intuitively for the Gaussian kernel: The decision function of the max-margin task for the two classes $\{-1,1\}$ is the following

$f_w(x) = \mbox{sign}(\langle x, w\rangle +b)$

That is when you want to classify a new observation $x$ you calculate the inner product of $x$ and the parameter vector $w$ and decide for the class according to the sign of the inner product. Given a training set $\{(x_i,y_i)\mid i=1,\dots, L\}$ with $y_i\in\{-1,1\}$ (upon which $w$ is learned) we know from optimisation theory that the parameter vector $w$ can be expressed as

$w = \sum_{i}\alpha_i y_i x_i$

for some $\alpha_i\geq 0$. The index $i$ runs over the elements of the training set . Substituting this into the above we get the decision function
$f(x) = \mbox{sign}(\sum_i\alpha_i y_i\langle x, x_i\rangle +b)$

Now if we use the gaussian kernel
$k_{Gauss}(x,x_i)=\exp(-\frac{\|x-x_i\|^2}{\sigma^2})$ instead of the linear kernel $k_{linear}=\langle x,x_i\rangle$
we get
$f(x) = \mbox{sign}(\sum_i\alpha_i y_i\exp(-\frac{\|x-x_i\|^2}{\sigma^2})+b)$.

Therein you can see that all training elements for which $\alpha_i > 0$ (the support vectors) have influence on the decision, since the element for which $\alpha_i=0$ do not contribute to the sum (this holds for all kernels). What can also be seen is that the support vectors which are close to $x$ give higher contribution to the sum than the ones which are far away because the term $exp(-\frac{\|x-x_i\|^2}{\sigma^2})$ decreased exponentially with the distance of the points $x$ and $x_i$. Especially for small $\sigma^2$ only the very nearby points to $x$ have significant influence on the sum which in the extreme case renders the max-margin classifier into a kind of nearest neighbour classifier. Therefore for a small enough $\sigma^2$ you can classify any given training set (as long as it is consistent) correct, but you might encounter difficulties later because of over-fitting onto the training set. Another thing is that you end up with more support vectors the more "powerful" your kernel is. Hence decreasing $\sigma^2$ gives more support vectors. Up to my knowledge there is no "elegant" way on how to determine the best value for $\sigma^2$. I thing this is mostly done by cross validation.