11
$\begingroup$

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.

$\endgroup$

migrated from ai.stackexchange.com Feb 24 '14 at 18:14

This question came from our site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment.

7
$\begingroup$

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).

$\endgroup$
10
$\begingroup$

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:

$\endgroup$
  • 1
    $\begingroup$ "is also linear in terms of the number of weights" in terms of space dimension, not the number of weights. You can have linear classifier parametrized with as many weights as you want, but its VC dimension is still d+1 (where d is space dimensionality). "the VC dimension for SVM models is related to the number of Support Vectors " How exactly is VC dimension realted to the number of SV? I'm aware of the hard margin bound, but afaik in the soft margin case there is no such relation. Even in Radamacher's complexity bounds you won't find the number of SVs as a variable. $\endgroup$ – lejlot Feb 8 '14 at 21:15
  • $\begingroup$ Also "so its irrelevant how "big" the kernel target space is, you don't loose anything in terms of the generalization bound" is as far as I know completely false. High dimensional spaces will lead to loose of generalization capabilities, even with such strongly regularized model as SVM. $\endgroup$ – lejlot Feb 8 '14 at 21:19
  • 1
    $\begingroup$ @lejlot Thanks, corrected the first two mistakes. I need some time to relate to your last two remarks - I'll try to improve the answer and provide some sources, after I recheck my information :) $\endgroup$ – BartoszKP Feb 8 '14 at 21:20
  • 1
    $\begingroup$ It is now almost correct, but what is the reason for assumption, that size of the kernel space in irrelevant? Take any dataset, run a SVM with RBF kernel and C->inf and you will overfit badly. It is not so simple. Number of dimensions in the feature space is relevant, yet it can be controlled with C (as an upper bound of lagrange multipliers). In particular - VC dimension for SVM with RBF is infinity, and generalization bound (Vapnik's) is useless (Radamacher could work but this is whole different story). $\endgroup$ – lejlot Feb 9 '14 at 8:17
  • 1
    $\begingroup$ @lejlot I've given another reference - they provide a bound for soft-margin case explicitly, and it's not dependent on the number of dimensions. $\endgroup$ – BartoszKP Feb 9 '14 at 9:10
6
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ That's an interesing insight on "working with dual" leading to an inability to claim feature importances. Would you have some reference to material explaining further? $\endgroup$ – javadba Nov 4 '17 at 21:37

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.