Support Vector Machines and Kernels

Definition

Of all the lines that separate two groups, which is the safest?

A support vector machine (SVM) finds the hyperplane that separates two classes with the largest margin, the distance to the nearest training points, which are called support vectors. The soft-margin SVM allows some violations, controlled by C. The kernel trick replaces dot products with a kernel function, such as the RBF kernel, letting the SVM learn non-linear boundaries without computing the high-dimensional features explicitly.

In simple words

Draw the widest possible road between the two groups; the decision line runs down the middle. Only the points on the edge of the road matter. Large C insists on few points inside the road (risking overfitting); small C allows a wider, more forgiving road. Kernels let the road bend.

Why it matters

SVMs give strong results on small and medium datasets with many features, such as text and genomics, and their maths, margins, duality and kernels, underpins much of modern learning theory.

How it works

Kernel	Shape of boundary	Key parameter
linear	Straight hyperplane	C
poly	Polynomial curves	C, degree
rbf	Smooth, flexible regions	C, gamma (larger = wigglier)

The maths

Soft-margin SVM objective

w, b, ξ min \frac{1}{2} ∥ w ∥^{2} + C i = 1 \sum n ξ_{i} s.t. y_{i} (w^{⊤} x_{i} + b) \geq 1 - ξ_{i}, ξ_{i} \geq 0

The margin width

margin = \frac{2}{∥ w ∥}

RBF kernel

K (x, z) = exp (- γ ∥ x - z ∥^{2})

In code

Linear and RBF SVMs on two interleaving half-moons, and the effect of C on the number of support vectors.

svm.py

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

X, y = make_moons(n_samples=400, noise=0.25, random_state=0)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0)

for kernel in ["linear", "rbf"]:
    model = make_pipeline(StandardScaler(), SVC(kernel=kernel)).fit(X_tr, y_tr)
    print(f"{kernel:>6} kernel: test accuracy {model.score(X_te, y_te):.3f}")

print("   C   support vectors   test accuracy")
for C in [0.01, 1, 100]:
    svc = SVC(kernel="rbf", C=C).fit(StandardScaler().fit(X_tr).transform(X_tr), y_tr)
    model = make_pipeline(StandardScaler(), SVC(kernel="rbf", C=C)).fit(X_tr, y_tr)
    print(f"{C:>5}   {svc.n_support_.sum():>15}   {model.score(X_te, y_te):13.3f}")

Output

linear kernel: test accuracy 0.908
   rbf kernel: test accuracy 0.933
   C   support vectors   test accuracy
 0.01               278           0.750
    1                88           0.933
  100                55           0.942

Try it yourself

Which kernel fits?

Match each dataset description to the kernel you'd try first.

Text with 50,000 word features
Two moons curling round each other
A known quadratic relationship

Common mistakes

Running an RBF SVM on unscaled data.
Tuning C without gamma, or on a linear grid.
Using SVMs on millions of rows, where training time grows faster than linearly.

Check yourself

1. Which points define the SVM boundary?

2. A larger C usually means…

3. What does the kernel trick avoid?

Summary

SVMs maximise the margin 2/‖w‖ between classes.
C trades margin width against violations.
Kernels such as RBF give non-linear boundaries; scale and tune C with gamma.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: scikit-learn: Support vector machines · Hastie et al., The Elements of Statistical Learning