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.


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.