Which problems are best solved using which kernels and why?

Can you give a simple toy problem that isn't linearly separable in input space but is linearly separable in feature space, using an RBF kernel? A polynomial kernel?

  • $\begingroup$ maybe the most simple example is the case where you have a circle on the plane. You want to segment that circle by considering the points within that circle to belong to one class, and the points outside that circle to another one. This is not linearly separable, but mapping it in polar coordinates becomes linearly separable. $\endgroup$
    – jpmuc
    May 14 '13 at 11:56
  • $\begingroup$ what is the kernel that corresponds to mapping in polar coordinates? $\endgroup$ May 14 '13 at 19:57
  • 1
    $\begingroup$ The polar transformation corresponds to $(x,y) \rightarrow \left(\sqrt{x^{2}+y^{2}}, \arctan(x,y)\right)$. The closest related polynomial kernel might be $(x,y) \rightarrow \left( x^{2},y^{2},\sqrt{2}xy\right)$. In any case, this will work for that toy case. $\endgroup$
    – jpmuc
    May 14 '13 at 21:09

In my experience, unless you have some expert knowledge about the domain, it is better just to use a linear or RBF kernel. Many classification problems have optimal solutions that are linear, so a linear kernel is always worth trying. The RBF kernel gives rise to a universal approximator, so given enough data it ought to be possible to get a decent model. Choosing the kernel and optimising the kernel and regularisation parameter can lead to over-fitting the model selection criterion, and the more choices, the more likely this is to happen, so choosing between many kernels based on e.g. cross-validation is more risky than one might think.

Try Ripley's synthetic benchmark for a problem that can be classified well using an RBF kernel. Each class is drawn from a mixture of two spherical Gaussians with equal variances, so the kernel evaluated at the right four points allows the densities of both classes to be represented exactly, from which the Bayes optimal decision region can be calculated.

  • $\begingroup$ If the data is drawn from two gaussian spheres, then can't I just use a linear kernel (input space=feature space) to draw the separating hyperplane in the middle between their two means? I'm looking for an example when data which isn't linearly separable in input space would become separable in feature space... $\endgroup$ May 13 '13 at 23:41
  • $\begingroup$ Ripleys synthetic dataset has two Gaussians per class, so the Bayes optimal decision boundary is non-linear. However, it is worth noting that while a Gaussian kernel can give the Bayes optimal decision surface, whether the optimal values of the hyper-parameters and the coefficients of the kernel expansion can be estimated well from the data is another matter. $\endgroup$ May 14 '13 at 13:10
  • $\begingroup$ Is there an easy way to show that if two categories are drawn from two Gaussians each, then the Gaussian kernel will successfully separate them? $\endgroup$ May 14 '13 at 19:56
  • $\begingroup$ Yes, if you have a Gaussian RBF kernel of the appropriate width placed over the centroid of each Gaussian cluster, and give each a weight of one, then the output will be proportional to the conditional density. If you do the same with the other class, but use weights of -1, then the output will be zero where the two class conditional densities are the same, which is the Bayes decision region. However, whether a learning algorithm will find this solution from a particular sample of data is another matter, but the RBF kernel machine can express the ideal solution in a compact manner. $\endgroup$ May 15 '13 at 9:31

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.