8
$\begingroup$

In support vector machines, I understand it would be computationally prohibitive to calculate a basis function at every point in the data set. However, it is possible to find this optimal solution due to the so-called kernel trick.

Other answers to this question use advanced math and statistics jargon to answer the question (I assume) properly, causing it to be inaccessible to general a data science audience. Could someone post a "big-picture" description (i.e., not necessarily thorough or technically complete) illustrating what the kernel trick is and how it works?

$\endgroup$
13
$\begingroup$

The kernel trick is based on some concepts: you have a dataset, e.g. two classes of 2D data, represented on a cartesian plane. It is not linearly separable, so for example a SVM could not find a line that separates the two classes. Now, what you can do it project this data into an higher dimension space, for example 3D, where it could be divided linearly by a plane.

Now, a basic concept in ML is the dot product. You often do dot products of the features of a data sample with some weights w, the parameters of your model. Instead of doing explicitly this projection of the data in 3D and then evaluating the dot product, you can find a kernel function that simplifies this job by simply doing the dot product in the projected space for you, without the need to actually compute projections and then the dot product. This allows you to find a complex non linear boundary that is able to separate the classes in the dataset. This is a very intuitive explaination.

$\endgroup$
  • $\begingroup$ Thanks! I do have a follow-up: what vectors is the program taking the dot (inner?) product between? I have some linear algebra experience so should be able to get slightly more technical here. $\endgroup$ – user1717828 Mar 13 '17 at 0:17
  • $\begingroup$ Usually you take inner products between the input data and the weights to compute a prediction, or between couple of input data. For the SVM case, you can check this wiki page under "Kernel trick", it shows clearly every step and product to compute the non-linear SVM. en.m.wikipedia.org/wiki/Support_vector_machine $\endgroup$ – dante Mar 13 '17 at 10:29
0
$\begingroup$
  1. suppose you have a 5 classes of data ordered like a 5 on a dice.
  2. to separate the middle cluster from the Rest, you do a nonlinear transformation on all data points.
  3. since the middle cluster is in the middle of our "kernel" the other clusters will move to another direction, so that a linear separation will be possible.
$\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.