Support Vector Machines & Kernels

Maximum-margin classifiers and the kernel trick.

The idea

A support vector machine separates two labeled classes with a hyperplane $\mathbf{w}^{\top}\mathbf{x} + b = 0$, chosen to leave the widest possible gap between the classes. When one hyperplane separates the classes, a great many do, and the machine settles the choice: take the separator whose distance to the nearest point of either class is greatest. That distance is the margin, and the points achieving it are the support vectors. They alone fix the boundary: any other point can move, so long as it does not cross the margin, without changing the answer.

Scaling $\mathbf{w}$ and $b$ by the same factor leaves the hyperplane where it is, so we pin the scale down by demanding $y_{i}(\mathbf{w}^{\top}\mathbf{x}_{i} + b) \ge 1$ for every point, with equality at the support vectors. Under that normalization the margin works out to $1/\lVert \mathbf{w} \rVert$, so minimizing $\lVert \mathbf{w} \rVert$ subject to those constraints finds the widest-margin separator — a convex problem with a single solution.

Solving it shows the data entering only through inner products $\mathbf{x}_{i}^{\top}\mathbf{x}_{j}$. So if some map $\phi$ carries the inputs into a larger space where a hyperplane does separate them, we never need $\phi$ itself, only the numbers $\phi(\mathbf{x}_{i})^{\top}\phi(\mathbf{x}_{j})$. A kernel $K$ computes exactly those numbers in the original space.

Ways to work on it

• Walkthrough. Margins, support vectors, and the kernel trick.
• Practice. Compute the geometric margin from the weight vector.
• Hardest. Evaluate a polynomial kernel and verify it against the explicit feature map.

Not sure where to start? Take the ten-question placement test.