4
$\begingroup$

I trying to figure out intuitively how the kernel trick gives rise to a decision boundary. I've always thought of SVMs as hyperdimensional spaces with a decision plane dividing them up and I'm trying to understand how kernels fit into them aside from allowing the decision plane to be nonlinear.

In my particular case I'm looking at string kernels where strings are classified. I get that kernelization helps to make decision boundaries for nonlinearly separably data but whenever they're explaining they usually only seem to show how the dot product give you a similarity score between two data points not how it partitions a set of data into two categories.

https://www.quora.com/What-are-kernels-in-machine-learning-and-SVM-and-why-do-we-need-them

For example in this above link the Lili commentator simply gives an example of what looks like two datapoints in 3d space (x and y) and calculates the dot product between them. But I don't see an explanation about how this product can be used to determine similarity between the two points or how it can be extended into a decision boundary between two groups of points.

Does someone have some insight in regards to this?

$\endgroup$
  • 1
    $\begingroup$ How about that? Computing an svm with a general kernel k is nothing else than computing a usual SVM (as a liner separation) in a very ugly, complex, often infinite dimensional space. This is due to the fact that one can almost always express the kernel map as $k(x,y) = \langle \Phi(x), \Phi(y) \rangle$ I.e. as the natural inner product of the transformation $\Phi$ of the vectors into the ugly space. Is that the direction of the answer you expect? $\endgroup$ – Fabian Werner Nov 17 '17 at 14:16
  • $\begingroup$ I sortof get that the dot product can be used to calculate a distance between two points with an arbitrary number of features. I just don't understand how finding the distance between two datapoints in ndimensional space helps to classify them into two groups when they are just two points out of a massive set of data. $\endgroup$ – A D Nov 18 '17 at 23:30
  • $\begingroup$ humm the actual problem you are solving is finding the hyper plane (decision boundary) in the ugly space that allows for the “widest” alley around it until it hits the first example (positive or negative ) from the training set, i.e. you do not only calculate the distance of two point, you calculate the distance of the departing line to all the points in your data set and sort of maximize this quantity... $\endgroup$ – Fabian Werner Nov 19 '17 at 17:09
1
$\begingroup$

they usually only seem to show how the dot product give you a similarity score between two data points not how it partitions a set of data into two categories.

Linear SVM partitions space using a hyperplane. Hyperplane can be represented as $$H = \{x \in \mathbb{R}^k | x \cdot n = b \}$$ for some $n \in \mathbb{R}^k $.

$H$ partitions $\mathbb{R}^k$ according to the sign of $x \cdot n - b$.

But I don't see an explanation about how this product can be used to determine similarity between the two points

You can calculate Euclidean distance between two points using dot products: $$\|x - y\|^2 = (x - y)\cdot (x-y) = x \cdot x - 2 x \cdot y + y \cdot y$$

Kernel trick lets you to separate data which is not linearly separable in some other space - you just need the kernel to actually fit SVM, since its training objective is expressed solely using dot products (and not explicitly using coordinates from the space into which you embed your data).

$\endgroup$
  • $\begingroup$ I generally get what you're saying its just I'm having trouble relating how distance between two points in n-space allows you to separate two groups of points from each other. I looked up other explanations and I'm not very good at math so I get lost around the point where they pull out 'lagrangian multipliers' to somehow explain why the dot product works. $\endgroup$ – A D Nov 19 '17 at 6:53

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.