2.5 Support vector machines and the kernel trick
A support vector machine draws the widest possible street between two classes, lets C decide how many points may stand in it, and uses a kernel to draw that street in a feature space it never has to build.
01The widest street
A linear classifier scores a point with and predicts its sign. The set is a line in 2D and a hyperplane in dimensions; is its normal and shifts it. Many lines separate the cyan () and amber () blobs in the viewport. The support vector machine picks the one that stays as far as possible from the closest points of both classes.
and describe the same line for any , so the scale is free: draws exactly the same line as , with every score doubled. Fix it by asking for every training point, with equality for the closest ones. Those points then sit at distance on either side, and the street between the lines and is wide.
- 1
Maximise the distance of the closest point, signed so that correct predictions count as positive.
The viewport is at (the next step introduces ), which here gives exactly the hard-margin solution: , , . Three points touch the emerald band, ringed in emerald. One of them is the cyan outlier at , deep in amber territory: it turns the normal to (it is once is lowered to 1 in step 3) and squeezes the street. Each cycle replays the solver on the floor, then lifts every point to a height that grows with its score . For the linear and RBF kernels the height is this score (squashed by a tanh so it fits the box), not a new feature; only the polynomial kernel in step 4 lifts the points into real feature-space coordinates. The score surface crosses the floor along the boundary, and the street is where it passes between the faint planes at : the larger , the steeper the surface and the narrower the street.
Lower the penalty to in the 3D scene and hold it on the floor.
Hands-On Machine Learning, Aurélien Géron, Ch. 5, Linear SVM classification
An Introduction to Statistical Learning, James, Witten, Hastie & Tibshirani, Sec. 9.1, Maximal margin classifier
02Soft margin: slack, hinge loss and C
Real classes overlap, and even separable data has outliers. The hard margin then has no solution at all, or, as in step 1, lets one point dictate a narrow street. The soft margin gives each point a slack , how far it sits on the wrong side of its own margin line, and charges per unit of slack:
- 1
Both constraints bound ξᵢ from below, and no other constraint involves it.
The hinge loss of the margin is zero for points beyond their margin line, grows linearly inside the street, and keeps growing for misclassified points. The panel at the bottom right plots it, with every training point placed at its own .
The viewport is at . The street widens from to ; 18 points now stand inside it, ringed in rose, and one of them is on the wrong side. Training accuracy falls to , yet on 200 fresh points from the same blobs accuracy rises from for the hard margin to . Drag : every step up buys training-set purity with margin.
An Introduction to Statistical Learning, James, Witten, Hastie & Tibshirani, Sec. 9.2, Support vector classifiers
The Elements of Statistical Learning, Hastie, Tibshirani & Friedman, Sec. 12.2, The support vector classifier
03The dual: only support vectors carry weight
Optional depth: this step uses Lagrange multipliers (lesson 1.4, Convexity, Lagrange multipliers and duality). The result in plain words comes first: the trained SVM puts a weight on every training point, and that weight is zero for every point safely outside the street. Only the points on the edge of the street or inside it get a weight, and is a weighted sum of those points. The derivation below shows why. Attach a multiplier to each margin constraint, form the Lagrangian, and minimise it over , and . Setting the derivatives to zero gives the facts the rest of the lesson rests on:
- 1
One multiplier αᵢ ≥ 0 per margin constraint and one μᵢ ≥ 0 per constraint ξᵢ ≥ 0.
Every training point therefore falls into one of three groups. : beyond its margin line, , and the model does not depend on it. : on the margin, with ; conversely, forces the point to sit exactly on the margin. : inside the street or misclassified, and . The last two groups are the .
One multiplier per training point. At C = 1 only 8 of the 74 entries are non-zero.
Qᵢⱼ = yᵢyⱼ xᵢᵀxⱼ. Its size grows with n², not with the number of features.
At the fit has 8 support vectors: two on the margin with (emerald rings) and six with inside the street (rose rings), among them both outliers, which are now misclassified. The other 66 points have ; hover to size every point by its multiplier. Each cycle replays the solver, sequential minimal optimisation (SMO): every iteration picks the pair of points that violates the optimality conditions most, solves the two-variable problem in closed form, and keeps . Here it converges in 6 iterations.
The Elements of Statistical Learning, Hastie, Tibshirani & Friedman, Sec. 12.2.1, Computing the support vector classifier
Hands-On Machine Learning, Aurélien Géron, Ch. 5, Under the hood: the dual problem
The rest of this lesson is in Pro
- 04Feature maps and the kernel trick
- 05The RBF kernel: a bump around every support vector
- 06γ and C: two knobs on one bias–variance trade-off
- 07SVMs today: where they still win
- Python challenge: RBF kernel, hinge loss and a linear SVM from scratch
- Knowledge check, 4 questions
Pro opens all 45 lessons, every graded Python challenge and the full 3D labs.
The Python challenge and knowledge check for this lesson are part of Pro.
Questions learners ask
- What is the difference between a support vector machine and logistic regression?
- Both learn a linear decision boundary, usually with an L2 penalty, and often reach similar accuracy. Logistic regression minimises the log loss, outputs probabilities and lets every training point influence the fit. A support vector machine minimises the hinge loss, so points beyond the margin have no influence at all and the solution depends only on the support vectors. Its output is a score rather than a probability, and it extends naturally to non-linear boundaries through kernels.
- How do I choose C and gamma for an RBF SVM?
- Standardise the features first, then run a cross-validated grid or random search over both parameters on a logarithmic scale, for example powers of ten from 0.001 to 1000. Large values of gamma and C fit the training data more closely and risk overfitting; small values give smoother, simpler boundaries that may underfit. A model in which nearly every training point is a support vector is usually overfitting.
- What is the kernel trick?
- Many algorithms, including the SVM dual, use the data only through inner products between pairs of points. A kernel function computes the inner product of two points after a feature map without constructing the mapped features. The polynomial kernel (x·z + 1) squared equals the inner product of six quadratic features in two dimensions, and the RBF kernel corresponds to infinitely many features, yet each costs about as much as one ordinary inner product to evaluate.
Next in Classical Machine Learning
2.6k-means, Gaussian mixtures and EMUnsupervised structure: Lloyd's algorithm, k-means++ seeding, and soft clustering with expectation-maximisation.Sources
- Hands-On Machine Learning, Aurélien Géron
- An Introduction to Statistical Learning, James, Witten, Hastie & Tibshirani
- The Elements of Statistical Learning, Hastie, Tibshirani & Friedman