Should I use the Kernel Trick whenever possible for non-linear data?

Question

I recently learned about the use of the Kernel trick, which maps data into higher dimensional spaces in an attempt to linearize the data in those dimensions. Are there any cases where I should avoid using this technique? Is it just a matter of finding the right kernel function?

For linear data this is of course not helpful, but for non-linear data, this seems always useful. Using linear classifiers is much easier than non-linear in terms of training time and scalability.

Answer 1

For linear data this is of course not helpful, but for non-linear data, this seems always useful. Using linear classifiers is much easier than non-linear in terms of training time and scalability.

@BartoszKP already explained why is kernel trick useful. To fully address your question however I would like to point out, that kernelization is not the only option to deal with non linearly separable data.

There are at least three good, common alternatives for delinearization of the model:

• Neutal network based methods, where you add one (or more) layers of processing units, able to transform your data into the linearly separable case. In the simplest case it is a sigmoid-based layer, which adds non-linearity to the process. Once randomly initialized they are getting updates during the gradient-based optimization of the upper layer (which actualy solves the linear problem).
• In particular - deep learning techniques can be used here to prepare data for further linear classification. It is very similar idea to the previous one, but here you first train your processing layers in order to find a good starting point for further fine-tuning based on training of some linear model.
• Random projections - you can sample (non linear) projections from some predefined space and train linear classifier on top of them. This idea is heavily exploited in so called extreme machine learning, where very efficient linear solvers are used to train a simple classifier on random projections, and achieve very good performance (on non linear problems in both classification and regression, check out for example extreme learning machines).

To sum up - kernelization is a great delinearization technique, and you can use it, when the problem is not linear, but this should not be blind "if then" appraoch. This is just one of at least few interesting methods, which can lead to various results, depending on the problem and requirements. In particular, ELM tends to find very similar solutions to those given by kernelized SVM while in the same time can be trained rows of magnitude faster (so it scales up much better than kernelized SVMs).

Answer 2

The price you pay for the Kernel Trick in general, for linear methods, is having worse generalization bounds. For a linear model its VC dimension is also linear in terms of the number of dimensions (e.g. VC dimension for a Perceptron is d + 1).

Now, if you will perform a complex non-linear transform to a high dimensional space the VC dimension of your hypothesis set is significantly larger, as it's now linear in terms of the number of dimensions in the new, high dimensional space. And with it, the generalization bound goes up.

Support Vector Machines exploit the Kernel Trick in the most efficient way, by doing two things:

• the generalization bound for hard-margin SVM models is related to the number of Support Vectors, and for soft-margin is related to the norm of the weight vector - so it can be irrelevant in the first case, and almost irrelevant in the second case. No matter how "big" the kernel target space is, you don't loose anything/much in terms of the generalization (references: (i) C. Cortes and V. Vapnik. Support vector networks. Machine Learning, 20:273–297, 1995 ; (ii) Shawe-Taylor, J.; Cristianini, N., "On the generalization of soft margin algorithms," Information Theory, IEEE Transactions on , vol.48, no.10, pp.2721,2735, Oct 2002).

• SVMs find the separation plane that maximizes the margin, and this further simplifies the hypothesis set (we don't consider every possible separating plane, just those that maximize the margin). Simple hypothesis set also leads to better generalization bounds (this is related to the first point, but it's more intuitive).

Answer 3

I will try to provide a non-technical answer to your question.

Indeed, linear should be preferred and should be the first choice for the reasons you mention, training time, scalability, plus ease on interpreting the final model, choice of working on primal or dual, more tolerance to overfitting etc.

If the linear model doesn't result in satisfactory performance, then you can try non-linear solutions. Some trade-offs to consider include:

• the choice of kernel. This is not obvious, usually you need to test different options
• there is the danger of overfitting the training set. Actually it is pretty easy to overfit if you want. To avoid overfitting you need a stronger evaluation framework (you need to measure the variance/stability of performance on unseen data) and you need enough data in order to be able to do proper model selection
• you work on dual, and thus you can't interpret the final model, i.e., you can't claim that feature X is more important than feature Y etc.
• training time is increased with the volume of data (less with number of features since it's in the dual)