Kernel Methods

In the previous chapter, a Support Vector Machine found the best linear decision boundary. That works beautifully when a straight line can separate the classes. But what if no straight line works?

Imagine predicting whether Jessie orders a burger using hunger level and burger price. The burger examples sit in the middle. The no-burger examples surround them.

        no  no  no
     no             no
  no      burger     no
     no             no
        no  no  no

No matter how we rotate a straight line, some examples will be on the wrong side. The linear SVM fails, not because margins are a bad idea, but because the original representation makes the pattern impossible to separate linearly.

Kernel methods begin with a change in question. Instead of asking whether we can find a better line, ask whether we can represent the data differently so that a line becomes possible.

A one-dimensional example makes the idea clear:

x:     -2   -1    0    1    2
class: no  yes  yes  yes   no

No single threshold on $x$ separates the classes. The positive class is in the middle and the negative class is on both ends.

Now create a new feature, $x^2$:

A simple threshold on $x^2$ now works. The classifier did not become more complicated. The representation became more useful.

Kernel methods are easiest to understand in two stages. First, explicit feature mapping explains why adding dimensions can help. Then the kernel trick explains how to get the benefit without explicitly constructing those dimensions.

The Algorithm: Feature Mapping

Suppose the original input is $x=(x_1,x_2)$. Instead of giving the SVM this input directly, construct a new representation:

The SVM is trained on $\phi(x)$ rather than $x$. The optimization problem is the same as before. Only the input representation changed.

This can make curved patterns look linear. A circular pattern in $(x_1,x_2)$ may become separable after adding $x_1^2+x_2^2$.

The Problem With Explicit Features

Feature mapping works until the mapped representation becomes enormous. Polynomial features of degree twenty, degree one hundred, or infinitely many basis functions may be impossible to construct directly.

This seems to make the approach impractical. But SVMs reveal a loophole.

The Kernel Trick

In the dual view of an SVM, the optimization does not need transformed vectors individually. It needs dot products between transformed vectors:

A kernel function computes that dot product directly:

This is the kernel trick. We get the effect of working in a rich feature space without explicitly building the feature vectors in that space.

Common Kernels

The RBF kernel is especially common because it defines local similarity. Nearby points have high similarity. Far-apart points have similarity close to zero.

The parameter $\gamma$ controls how quickly similarity fades with distance. Large $\gamma$ creates very local influence. Small $\gamma$ creates smoother, broader influence.

Why It Works

A kernel is a similarity function with a special interpretation: it behaves like a dot product in some feature space. Instead of asking where a point is in the original coordinates, a kernel method asks how similar the point is to important training examples.

Different kernels define different geometries. The kernel determines which points count as similar, and therefore which decision boundaries are easy to express.

Complexity

Kernel methods are often more expensive than linear methods. Training usually requires computing similarities between many pairs of training examples. Prediction depends on the number of support vectors, so models with many support vectors can be slow at inference time.

In practice, you usually choose a kernel through a library implementation. The point of this comparison is to train the same SVM with three different similarity functions and inspect how the boundary changes.

from sklearn.datasets import make_circles
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

X, y = make_circles(n_samples=300, factor=0.35, noise=0.08)

models = {
    "linear": SVC(kernel="linear", C=1.0),
    "polynomial": SVC(kernel="poly", degree=3, C=1.0),
    "rbf": SVC(kernel="rbf", gamma=2.0, C=1.0),
}

for name, model in models.items():
    clf = make_pipeline(StandardScaler(), model)
    clf.fit(X, y)
    print(name, clf.score(X, y))

Always scale features before using distance-sensitive kernels. Otherwise, one large-scale feature can dominate the similarity calculation.