Machine Learning ML-04.04
Support Vector Machines and kernels
Find the boundary with the widest margin, see why only support vectors matter, tune the soft margin C, and bend boundaries with the kernel trick.
The big idea
When two classes can be separated by a straight line, there are usually infinitely many lines that do it. Logistic regression picks one by fitting probabilities. A support vector machineA classifier that chooses the decision boundary with the largest margin to the nearest training points of each class, optionally in a kernel-induced feature space. (SVM) asks a different question: which line leaves the widest empty street between the classes?
Picture a road between two villages. You want to build it as wide as possible without demolishing any house. The houses right at the edge of the road decide where it can go; houses deep inside a village are irrelevant. Those edge houses are the support vectorsThe training points that lie on or inside the margin. They alone determine the SVM's boundary; removing any other point changes nothing.. A wide road is a safe road: new points that land a little off from the training points are still classified correctly.
How it works
Step 1: Maximise the margin
A linear SVM uses the same boundary shape as logistic regression, w . x + b = 0, and predicts the sign of w . x + b. It adds two parallel lines, w . x + b = +1 and w . x + b = -1, and requires every training point to sit on the correct side of its line. The gap between them is the marginThe width of the empty band around an SVM's decision boundary, equal to 2 / ||w||., and its width is 2 / ||w||. So maximising the margin means making the weights as small as possible while keeping every point outside the band.
- Many lines separate the classes The red dashed line makes no training errors, but it passes close to the purple point at (1, -0.2). A new purple point slightly to its left would be misclassified.
- The SVM picks the widest street The gold boundary sits midway between the classes with the widest possible band. Three points touch the edges of the band: they are the support vectors, and only they fix the boundary.
Step 2: Soft margin and C
Real data overlaps, so no line separates it perfectly. A soft marginAn SVM formulation that allows some points inside the margin or on the wrong side, paying a penalty for each, controlled by the parameter C. lets points violate the band at a cost. The parameter C sets the price of each violation:
- Small C: violations are cheap. The SVM prefers a wide margin and tolerates many points inside it. Smoother, more regularized, more support vectors.
- Large C: violations are expensive. The SVM narrows the margin to classify more training points correctly. Closer fit, higher risk of overfitting.
On overlapping clusters in the code below, raising C from 0.01 to 100 shrinks the margin width from 2.96 to 1.23 and the number of support vectors from 104 to 42, while training accuracy barely moves. C plays the same role as the inverse regularization strength in logistic regression.
Step 3: When a line is not enough, lift the data
Take points on a line: one class in the middle, the other on both sides. No single cut point separates them. Now add a second feature, x^2. Each point moves up onto a parabola, the outer points rise higher than the inner ones, and a horizontal line separates them perfectly.
- One feature: not separable Cyan points sit in the middle, purple points on both sides. Any single threshold on x leaves purple points on both sides of it.
- Add x squared: separable Plot each point at (x, x squared). The purple points rise above 2.5, the cyan ones stay below 0.75, and the horizontal line at 1.6 separates them. In the original x space that line is two cut points, a curved boundary.
Step 4: The kernel trick
Lifting works, but explicitly building many new features is expensive: all pairwise products of 1,000 features is half a million new columns. The SVM's training and predictions only ever need dot products between pairs of points. A kernelA function K(a, b) that equals the dot product of a and b after some feature mapping, computed without building the mapped features explicitly. computes that dot product in the lifted space directly from the original features, without building the lifted features. This shortcut is the kernel trickReplacing every dot product in an algorithm with a kernel function, so the algorithm works in a high-dimensional feature space at the cost of the original one..
- Polynomial kernel:
K(a, b) = (a . b + 1)^dequals a dot product over all feature products up to degreed. - RBF kernel:
K(a, b) = exp(-gamma ||a - b||^2). A similarity score that is 1 for identical points and falls toward 0 with distance. It corresponds to an infinite-dimensional lift and can draw almost any smooth boundary.gammasets how far each point's influence reaches: small gamma gives smooth boundaries; large gamma gives tight blobs around each training point and overfits.
The prediction for a new point is a weighted sum of kernel similarities to the support vectors, sum of alpha_i y_i K(x_i, x) + b, where only support vectors have nonzero alpha_i.
Try it
Try this:
- On "two clusters" with a linear kernel, count the ringed support vectors. Then lower C to 0.01: the band widens and swallows more points, and every point inside it becomes a support vector.
- Switch to "ring around a blob". The linear kernel cannot do it: training errors stay high. Switch to RBF and watch a closed boundary appear.
- With RBF on the ring, push gamma to its maximum. The boundary shrinks into small islands around individual points: the classic overfit.
Going deeper
Code: C, kernels and gamma
import numpy as np
from sklearn.datasets import make_blobs, make_circles
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC
# Two overlapping blobs: how C changes the margin
X, y = make_blobs(n_samples=200, centers=[[-1.5, 0], [1.5, 0]], cluster_std=1.0, random_state=0)
print(" C support vectors margin width train acc")
for C in [0.01, 0.1, 1, 100]:
m = SVC(kernel="linear", C=C).fit(X, y)
width = 2 / np.linalg.norm(m.coef_)
print(f"{C:>5} {m.n_support_.sum():>15} {width:>12.2f} {m.score(X, y):.3f}")
# A ring around a blob: no straight line can separate it
X, y = make_circles(n_samples=400, factor=0.4, noise=0.1, random_state=0)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.5, random_state=0)
print("\nkernel test acc")
for name, m in [("linear", SVC(kernel="linear")),
("poly deg 2", SVC(kernel="poly", degree=2, coef0=1)),
("rbf", SVC(kernel="rbf", gamma=1))]:
print(f"{name:<12} {m.fit(Xtr, ytr).score(Xte, yte):.3f}")
# The lift by hand: add r^2 = x1^2 + x2^2 as a third feature, then a LINEAR SVM works
lift = lambda A: np.column_stack([A, (A ** 2).sum(axis=1)])
m = SVC(kernel="linear").fit(lift(Xtr), ytr)
print(f"linear on (x1, x2, x1^2 + x2^2): {m.score(lift(Xte), yte):.3f}")
print("\nRBF gamma train acc test acc support vectors")
for g in [0.1, 1, 10, 100]:
m = SVC(kernel="rbf", gamma=g).fit(Xtr, ytr)
print(f"{g:>9} {m.score(Xtr, ytr):.3f} {m.score(Xte, yte):.3f} {m.n_support_.sum()}")Output
C support vectors margin width train acc
0.01 104 2.96 0.915
0.1 56 1.75 0.910
1 45 1.36 0.915
100 42 1.23 0.910
kernel test acc
linear 0.615
poly deg 2 1.000
rbf 1.000
linear on (x1, x2, x1^2 + x2^2): 1.000
RBF gamma train acc test acc support vectors
0.1 0.890 0.845 186
1 1.000 1.000 35
10 1.000 1.000 52
100 1.000 0.995 154 On the ring data, a linear SVM gets 0.615 test accuracy, barely better than guessing. A degree-2 polynomial kernel and an RBF kernel both reach 1.000, and so does a plain linear SVM once you add the feature x1^2 + x2^2 by hand: the kernel is doing exactly that lift for you. The gamma table shows the other side: at gamma = 0.1 the boundary is too smooth (0.845 test), and at gamma = 100 the model needs 154 of 200 training points as support vectors and test accuracy starts to slip.
Practical notes
- Scale features first. Both the margin and the RBF distance are measured in feature units.
- Tune C and gamma together on a log grid with cross-validation ( Hyperparameter tuning ).
- Kernel SVM training scales between quadratically and cubically with the number of examples, so it is comfortable up to tens of thousands of rows, not millions. Linear SVMs scale much further.
- SVMs output distances, not probabilities. scikit-learn's
probability=Truefits a calibration on top ( Probability calibration ).
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Linear SVM | High-dimensional sparse data such as text, where classes are nearly linearly separable | Curved boundaries; you need probabilities directly |
| RBF SVM | Small to medium datasets with complex boundaries | Hundreds of thousands of rows; C and gamma need careful tuning |
| Logistic regression | You need calibrated probabilities and simple weights | You want the margin's robustness without probability modelling |
| Gradient boosted trees | Large tabular data with mixed feature types | Smooth geometric boundaries in a few continuous features |
Common mistakes
- Running an RBF SVM on unscaled features, so one feature's units decide every distance.
- Tuning C with gamma fixed (or the reverse); they interact and should be searched together.
- Training a kernel SVM on millions of rows and waiting hours; use a linear model or trees instead.
- Treating
decision_functionoutputs as probabilities. - Reading "only support vectors matter" as "the other data was useless"; it was needed to find which points are the support vectors.
In the wild
Before deep learning took over images and text, kernel SVMs were among the best general-purpose classifiers, used widely for text categorisation, handwritten digit recognition and bioinformatics, where datasets are small and features are many. Linear SVMs remain a standard tool for large sparse text problems, and the kernel idea lives on in Gaussian processes and other kernel methods.
Check yourself
-
You delete a training point that is far from the boundary and outside the margin. What happens to a trained SVM's boundary?
Show answer
B. Nothing: only support vectors define it Points outside the margin have zero weight (alpha = 0) in the solution. Only support vectors, on or inside the margin, shape the boundary.
-
An SVM with C = 1000 has a very narrow margin and 100 percent training accuracy, but poor validation accuracy. What should you try?
Show answer
B. Decrease C to allow a wider, softer margin Large C makes violations expensive, so the SVM contorts itself to fit every training point. Smaller C trades a few training errors for a wider, more robust margin.
-
What does the kernel trick avoid?
Show answer
B. Building the high-dimensional features explicitly; the kernel gives their dot products directly The algorithm only needs dot products between points, and a kernel computes those for the lifted space from the original features.
-
With an RBF kernel, raising gamma very high makes the boundary...
Show answer
B. Tight islands around individual training points, which overfits Large gamma makes each point's influence very local, so the boundary wraps around individual points. Training accuracy is high, generalisation suffers.
Recap
- An SVM picks the separating boundary with the widest margin; the margin width is 2 / ||w||.
- Only support vectors, the points on or inside the margin, determine the boundary.
- C sets the price of margin violations: small C means wide, tolerant margins; large C fits training data tightly.
- Kernels compute dot products in a lifted feature space, letting a linear method draw curved boundaries.
- Scale features and tune C with gamma together; kernel SVMs suit small to medium datasets.
Next up
- From notebook to production learning path