20
$\begingroup$

The kernel trick is used in several machine learning models (e.g. SVM). It was first introduced in the "Theoretical foundations of the potential function method in pattern recognition learning" paper in 1964.

The wikipedia definition says that it is

a method for using a linear classifier algorithm to solve a non-linear problem by mapping the original non-linear observations into a higher-dimensional space, where the linear classifier is subsequently used; this makes a linear classification in the new space equivalent to non-linear classification in the original space.

One example of a linear model that has been extended to non-linear problems is the kernel PCA. Can the kernel trick be applied to any linear model, or does it have certain restrictions?

$\endgroup$
  • 1
    $\begingroup$ BTW, kernels are not really essential for SVM's. The "heart" of SVM is the principle of soft margin maximization. Going to kernel representation makes your problem dimensionality O(m^2) instead of O(d) where m is the number of examples and d is the dimension of your feature space, so if m^2 is more than d, you might be better off doing away with kernels jmlr.csail.mit.edu/papers/v6/keerthi05a.html $\endgroup$ – Yaroslav Bulatov Aug 27 '10 at 17:53
  • $\begingroup$ @Yaroslav: Thanks for the reference. Are you aware of any implementations of that "Modified Finite Newton Method"? $\endgroup$ – Shane Sep 1 '10 at 15:23
  • $\begingroup$ no, but Keerthi and Langford's pages have links to some software that may be related, since they both worked at Yahoo Research $\endgroup$ – Yaroslav Bulatov Sep 2 '10 at 3:53
17
$\begingroup$

The kernel trick can only be applied to linear models where the examples in the problem formulation appear as dot products (Support Vector Machines, PCA, etc).

$\endgroup$
  • $\begingroup$ Thanks for the answer. @mbq @ebony1: IMO we need to make more of an effort to post more serious machine learning questions on the site, in order to attract more of that community. $\endgroup$ – Shane Aug 27 '10 at 18:23
  • $\begingroup$ @Shane I completely agree, but what about other SO site like metaoptimize.com/qa? $\endgroup$ – chl Aug 27 '10 at 18:54
  • $\begingroup$ @chl: That's also an option, but it's not part of the StackExchange (it's controlled by one person, and on different software) and I personally would rather have these different data analysis communities mingle in one place. $\endgroup$ – Shane Aug 27 '10 at 19:01
  • $\begingroup$ @Shane Well, ok it makes sense. $\endgroup$ – chl Aug 27 '10 at 20:05
  • $\begingroup$ there's also Machine Learning stack exchange proposal area51.stackexchange.com/proposals/7607/machine-learning $\endgroup$ – Yaroslav Bulatov Aug 27 '10 at 21:11
7
$\begingroup$

Two further references from B. Schölkopf:

and a website dedicated to kernel machines.

$\endgroup$
2
$\begingroup$

@ebony1 gives the key point (+1), I was a co-author of a paper discussing how to kernelize generalised linear models, e.g. logistic regression and Poisson regression, it is pretty straightforward.

G. C. Cawley, G. J. Janacek and N. L. C. Talbot, Generalised kernel machines, in Proceedings of the IEEE/INNS International Joint Conference on Neural Networks (IJCNN-2007), pages 1732-1737, Orlando, Florida, USA, August 12-17, 2007. (www,pdf)

I also wrote a (research quality) MATLAB toolbox (sadly no instructions), which you can find here.

Being able to model the target distribution is pretty useful in uncertainty quanification etc. so it is a useful (if fairly incremental) addition to kernel learning methods.

$\endgroup$

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.