Chapter 9 · Part II: Supervised Learning
Kernel Methods and Support Vector Machines
Among all hyperplanes that separate the data, pick the one farthest from the closest points. Lagrange duality turns that idea into a problem that touches data only through inner products, and kernels then make it work in feature spaces of any dimension.
After this chapter you will be able to
- Define functional and geometric margins and derive the optimal-margin classifier as a quadratic program.
- Use Lagrange duality and the KKT conditions to derive the dual SVM, and explain why only support vectors matter.
- Apply the kernel trick, recognize valid kernels (Mercer’s condition), and choose between polynomial and RBF kernels.
- Relate the soft-margin SVM to the hinge loss and compare it with logistic regression.
- Describe the SMO algorithm that trains SVMs efficiently.
- Use the multiclass hinge loss for linear classifiers, and fit kernel ridge regression.
Logistic regression finds a separating hyperplane; any hyperplane that classifies the training data well has a low loss. Support vector machines (SVMs) (Cortes and Vapnik 1995) ask for the best one: the hyperplane that stays as far as possible from the closest training points. Combined with kernels (Boser et al. 1992), which let linear methods work in enormous feature spaces at the cost of computing similarities, SVMs were the dominant classifiers of the late 1990s and 2000s. They remain a useful tool for small and medium data sets, and the ideas they introduced (margins, duality, kernels, the hinge loss) run through all of machine learning.
Throughout this chapter labels are $y\in\{-1,+1\}$ (not $\{0,1\}$), and the classifier is $\hat y=\sign(\vw\T\vx+b)$.
9.1Margins
Consider a linear classifier with score $f(\vx)=\vw\T\vx+b$. For an example $(\vx^{(i)},y^{(i)})$:
- The functional margin $\hat\gamma^{(i)}=y^{(i)}(\vw\T\vx^{(i)}+b)$ is positive exactly when the example is classified correctly, and large when the score is confidently correct. But it can be inflated for free by scaling $\vw$ and $b$ by any factor, without changing the classifier.
The geometric margin is the signed distance from the point to the decision boundary. The distance from $\vx$ to the hyperplane $\{\vz:\vw\T\vz+b=0\}$ is $|\vw\T\vx+b|/\norm{\vw}$ (project onto the unit normal $\vw/\norm\vw$), so
$$\gamma^{(i)}=\frac{y^{(i)}(\vw\T\vx^{(i)}+b)}{\norm{\vw}_2}=\frac{\hat\gamma^{(i)}}{\norm{\vw}_2}, \tag{9.1}$$which does not change when $(\vw,b)$ is rescaled.
The margin of the whole training set is the smallest one, $\gamma=\min_i\gamma^{(i)}$: the distance from the boundary to the closest point.
Intuition: Why a large margin?
A boundary that passes close to training points is fragile: a small perturbation of those points (noise, or new examples from the same class) lands on the wrong side. A boundary in the middle of the gap between classes tolerates the most perturbation. Learning theory (Chapter 11) makes this precise: the generalization error of large-margin classifiers can be bounded in terms of the margin, independently of the number of features.
9.2The Optimal Margin Classifier
Assume the training data are linearly separable. We want the hyperplane with the largest geometric margin:
$$\max_{\gamma,\vw,b}\ \gamma\quad\text{s.t.}\quad \frac{y^{(i)}(\vw\T\vx^{(i)}+b)}{\norm\vw}\ge\gamma\quad\text{for all } i .$$Because rescaling $(\vw,b)$ does not change the classifier, we may fix the scale by requiring the smallest functional margin to equal 1. Then $\gamma=1/\norm\vw$, and maximizing $1/\norm\vw$ is the same as minimizing $\frac12\norm\vw^2$:
This is a quadratic program: a convex quadratic objective with linear constraints. It has a unique solution that off-the-shelf solvers find efficiently. But its dual form is more illuminating and leads to kernels.
9.3Lagrange Duality
Consider a general constrained problem, the primal:
$$\min_{\vw}\ f(\vw)\quad\text{s.t.}\quad g_i(\vw)\le0,\ i=1,\dots,m .$$Introduce a Lagrange multiplier $\alpha_i\ge0$ for each constraint and form the Lagrangian
$$\mathcal L(\vw,\bm\alpha)=f(\vw)+\sum_{i=1}^m\alpha_i\,g_i(\vw).$$For any feasible $\vw$ (all $g_i\le0$), $\max_{\bm\alpha\ge0}\mathcal L=f(\vw)$; for an infeasible one, the maximum is $+\infty$. So the primal is $p^*=\min_{\vw}\max_{\bm\alpha\ge0}\mathcal L(\vw,\bm\alpha)$. Swapping the order gives the dual problem:
$$d^*=\max_{\bm\alpha\ge0}\ \underbrace{\min_{\vw}\mathcal L(\vw,\bm\alpha)}_{\text{dual function } D(\bm\alpha)} .$$- Weak duality: $d^*\le p^*$ always (a max-min never exceeds a min-max). In particular, every dual feasible point gives a lower bound on the primal optimum.
- Strong duality: if $f$ and the $g_i$ are convex and there exists a strictly feasible point (all $g_i<0$; Slater’s condition), then $d^*=p^*$.
When strong duality holds, the optimal $\vw^*$ and $\bm\alpha^*$ satisfy the Karush–Kuhn–Tucker (KKT) conditions:
$$\nabla_{\vw}\mathcal L(\vw^*,\bm\alpha^*)=\mathbf 0,\qquad g_i(\vw^*)\le0,\qquad \alpha_i^*\ge0,\qquad \alpha_i^*\,g_i(\vw^*)=0 . \tag{9.3}$$The last condition, complementary slackness, says that each multiplier is zero unless its constraint is active (holds with equality). Appendix B summarizes these facts.
9.4The Dual SVM and Support Vectors
Write the SVM constraints as $g_i(\vw,b)=1-y^{(i)}(\vw\T\vx^{(i)}+b)\le0$. The Lagrangian is
$$\mathcal L(\vw,b,\bm\alpha)=\frac12\norm\vw^2-\sum_{i=1}^n\alpha_i\big[y^{(i)}(\vw\T\vx^{(i)}+b)-1\big].$$Minimize over $\vw$ and $b$ by setting derivatives to zero:
$$\nabla_{\vw}\mathcal L=\vw-\sum_i\alpha_iy^{(i)}\vx^{(i)}=\mathbf 0\ \Rightarrow\ \vw=\sum_i\alpha_iy^{(i)}\vx^{(i)},\qquad \pd{\mathcal L}{b}=-\sum_i\alpha_iy^{(i)}=0 .$$Substituting back gives the dual problem:
The problem is convex with a strictly feasible point for separable data, so strong duality holds, and three facts follow:
The weights are a combination of training points, $\vw=\sum_i\alpha_iy^{(i)}\vx^{(i)}$, so predictions are
$$\vw\T\vx+b=\sum_{i=1}^n\alpha_iy^{(i)}\,\vx^{(i)\top}\vx+b . \tag{9.5}$$- Most $\alpha_i$ are zero. By complementary slackness, $\alpha_i>0$ only if $y^{(i)}(\vw\T\vx^{(i)}+b)=1$, i.e. the point lies exactly on the margin. These points are the support vectors. All other points could be deleted without changing the solution.
- The data enter only through inner products $\vx^{(i)\top}\vx^{(j)}$ and $\vx^{(i)\top}\vx$. This is the door to kernels.
The intercept follows from any support vector $s$: $b=y^{(s)}-\vw\T\vx^{(s)}$ (in practice, averaged over all support vectors for numerical stability).
9.5Kernels
In Section 4.5 we made linear models nonlinear with feature maps $\bm\phi(\vx)$. The cost is that $\bm\phi$ may be huge: all degree-$p$ monomials of $d$ inputs number about $d^p$. But the dual SVM only needs inner products, and for many feature maps the inner product can be computed without ever forming $\bm\phi$. A kernel is a function
$$K(\vx,\vz)=\bm\phi(\vx)\T\bm\phi(\vz).$$Replacing every $\vx^{(i)\top}\vx^{(j)}$ in Equations (9.4) and (9.5) by $K(\vx^{(i)},\vx^{(j)})$ trains a linear classifier in feature space while computing only kernels in input space. This is the kernel trick.
Example: A quadratic kernel
Let $K(\vx,\vz)=(\vx\T\vz)^2$. Expanding,
$$(\vx\T\vz)^2=\Big(\sum_{i}x_iz_i\Big)\Big(\sum_jx_jz_j\Big)=\sum_{i,j}(x_ix_j)(z_iz_j)=\bm\phi(\vx)\T\bm\phi(\vz),$$where $\bm\phi(\vx)$ lists all $d^2$ products $x_ix_j$. Computing $K$ costs $O(d)$ operations instead of $O(d^2)$. The polynomial kernel $(\vx\T\vz+c)^p$ corresponds to all monomials up to degree $p$, at cost still $O(d)$.
The Gaussian (RBF) kernel. $K(\vx,\vz)=\exp\big(-\norm{\vx-\vz}^2/(2\sigma^2)\big)$, often written $\exp(-\gamma\norm{\vx-\vz}^2)$, is a similarity that equals 1 for identical points and decays with distance. Its feature space is infinite-dimensional (expand the exponential in a Taylor series), yet it costs one distance to compute. With an RBF kernel, Equation (9.5) is a weighted sum of bumps centered at the support vectors: small $\sigma$ (large $\gamma$) gives narrow bumps and wiggly, overfitting boundaries; large $\sigma$ gives smooth, nearly linear ones.
Which functions are kernels? Given any points $\vx^{(1)},\dots,\vx^{(m)}$, define the Gram matrix $K_{ij}=K(\vx^{(i)},\vx^{(j)})$. If $K$ is a kernel, the Gram matrix is symmetric and positive semidefinite, because for any $\vz$,
$$\vz\T\mathbf K\vz=\sum_{i,j}z_iz_j\,\bm\phi(\vx^{(i)})\T\bm\phi(\vx^{(j)})=\Big\Vert\sum_iz_i\bm\phi(\vx^{(i)})\Big\Vert^2\ge0 .$$Mercer’s theorem states the converse: a symmetric function is a valid kernel (has some feature map) if and only if its Gram matrix is positive semidefinite for every finite set of points. Valid kernels can be combined: sums, positive multiples, products of kernels, and $f(\vx)K(\vx,\vz)f(\vz)$ are kernels. Kernels exist for strings, graphs, and sets, which lets SVMs classify DNA sequences or molecules directly.
9.6Soft Margins and the Hinge Loss
Real data are rarely separable, and even when they are, one outlier can force a tiny margin. The soft-margin SVM allows violations with slack variables $\xi_i\ge0$ and charges $C$ per unit of slack:
$$\min_{\vw,b,\bm\xi}\ \frac12\norm\vw^2+C\sum_{i=1}^n\xi_i\quad\text{s.t.}\quad y^{(i)}(\vw\T\vx^{(i)}+b)\ge1-\xi_i,\ \ \xi_i\ge0 . \tag{9.6}$$Repeating the dual derivation gives exactly Equation (9.4) with the box constraint $0\le\alpha_i\le C$. The KKT conditions now sort points into three groups:
| Multiplier | Location of the point |
|---|---|
| $\alpha_i=0$ | outside the margin, correctly classified ($y^{(i)}f(\vx^{(i)})\ge1$) |
| $0<\alpha_i<C$ | exactly on the margin ($y^{(i)}f(\vx^{(i)})=1$) |
| $\alpha_i=C$ | inside the margin or misclassified ($y^{(i)}f(\vx^{(i)})\le1$) |
The hinge-loss view. At the optimum each slack is as small as allowed, $\xi_i=\max(0,1-y^{(i)}f(\vx^{(i)}))$. Substituting into Equation (9.6) and dividing by $Cn$ gives an unconstrained problem:
$$\min_{\vw,b}\ \frac1n\sum_{i=1}^n\max\big(0,\,1-y^{(i)}(\vw\T\vx^{(i)}+b)\big)+\frac{\lambda}{2}\norm\vw^2,\qquad\lambda=\frac{1}{Cn}. \tag{9.7}$$The SVM is empirical risk minimization with the hinge loss $\max(0,1-yf)$ and ridge regularization (Chapter 5). Compare it with the logistic loss $\log(1+e^{-yf})$ of logistic regression in the same notation: both are convex upper bounds on the 0–1 loss and behave alike for badly misclassified points (linear growth). The difference is at the right end: the hinge loss is exactly zero once $yf\ge1$, so confidently correct points contribute nothing, which is where sparsity in support vectors comes from; the logistic loss is never exactly zero, and in exchange it produces calibrated probabilities. Large $C$ means little regularization (narrow margin, few violations); small $C$ means strong regularization.
9.7The SMO Algorithm
The dual is a quadratic program with $n$ variables. General-purpose QP solvers are slow for large $n$. Sequential minimal optimization (SMO) (Platt 1998) exploits the structure of the problem with coordinate ascent (Section 5.4), with one twist: the equality constraint $\sum_i\alpha_iy^{(i)}=0$ makes it impossible to change a single $\alpha_i$ alone. So SMO changes two at a time.
Pick a pair $(\alpha_i,\alpha_j)$ and hold the rest fixed. The constraint forces $\alpha_iy^{(i)}+\alpha_jy^{(j)}=\text{const}$, so $\alpha_i$ is determined by $\alpha_j$, and the dual objective becomes a one-dimensional quadratic in $\alpha_j$ that can be maximized in closed form. With prediction errors $E_k=f(\vx^{(k)})-y^{(k)}$ and $\kappa=K_{ii}+K_{jj}-2K_{ij}$ (the squared feature-space distance between the two points), the unconstrained maximizer is
$$\alpha_j^{\text{new}}=\alpha_j+\frac{y^{(j)}(E_i-E_j)}{\kappa}, \tag{9.8}$$which is then clipped to the interval $[L,H]$ that keeps both multipliers inside $[0,C]$; finally $\alpha_i$ is updated to keep the equality constraint, and $b$ is recomputed so that the KKT conditions hold for the changed points. Heuristics choose pairs that violate the KKT conditions most. Each step is cheap and the method converges to the global optimum because the dual is concave. Project 8 implements SMO in full and compares it with scikit-learn’s SVC, which uses the same algorithm in the LIBSVM library.
9.8Multiclass SVMs and the Hinge Loss in Deep Learning
SVMs are binary. Two classic reductions handle $K$ classes: one-vs-rest trains $K$ classifiers (class $k$ against all others) and predicts the class with the largest score; one-vs-one trains $\binom K2$ pairwise classifiers and takes a vote.
A third option scores all classes jointly with a linear map $\vs=\mW\vx$ (one row per class) and uses the multiclass hinge loss (Weston–Watkins form):
$$L_i=\sum_{j\ne y_i}\max\big(0,\ s_j-s_{y_i}+\Delta\big), \tag{9.9}$$with margin $\Delta=1$. The correct class must outscore every other class by at least $\Delta$; once it does, the example contributes nothing. Its gradient is simple: for $j\ne y_i$, $\nabla_{\vw_j}L_i=\mathbb 1[s_j-s_{y_i}+\Delta>0]\,\vx_i$, and $\nabla_{\vw_{y_i}}L_i=-\big(\sum_{j\ne y_i}\mathbb 1[s_j-s_{y_i}+\Delta>0]\big)\vx_i$. Together with ridge regularization this is the “linear SVM classifier” of image classification (Chapter 17), where it is trained by SGD and compared with the softmax cross-entropy loss: softmax never stops pushing the correct class’s probability up, while the hinge loss is satisfied once the margin is met. Any neural network’s final layer can be trained with either.
9.9Kernel Methods Beyond SVMs
Any algorithm that touches data only through inner products can be kernelized. The representer theorem explains why this is so common: for any loss and a penalty $\lambda\norm\vw^2$ in a kernel’s feature space, the minimizer has the form $\vw=\sum_i\beta_i\bm\phi(\vx^{(i)})$, so predictions are $f(\vx)=\sum_i\beta_iK(\vx^{(i)},\vx)$.
Kernel ridge regression. Ridge regression in feature space has $\vw=\bm\Phi\T(\bm\Phi\bm\Phi\T+\lambda\mI)^{-1}\vy$ (the identity of the second exercise of Chapter 5), and $\bm\Phi\bm\Phi\T$ is the Gram matrix $\mathbf K$. So
$$f(\vx)=\sum_{i=1}^n\beta_iK(\vx^{(i)},\vx),\qquad \bm\beta=(\mathbf K+\lambda\mI)^{-1}\vy . \tag{9.10}$$The same predictive mean arises from Gaussian processes, the Bayesian counterpart of kernel methods. Kernel PCA applies PCA (Chapter 14) in feature space.
The price of kernels. Kernel methods store and manipulate the $n\times n$ Gram matrix: $O(n^2)$ memory and up to $O(n^3)$ time. Beyond tens of thousands of examples this becomes prohibitive, which is one reason neural networks, whose cost grows linearly with $n$, took over for large data. Approximations such as random Fourier features ($\bm\phi(\vx)=\sqrt{2/D}\cos(\mathbf\Omega\vx+\vb)$ with random $\mathbf\Omega$) turn a kernel back into an explicit feature map of moderate size. In the other direction, very wide neural networks trained with small steps behave like kernel machines, a connection studied under the name neural tangent kernel.
9.10Implementation
A linear SVM trained by stochastic subgradient descent on the hinge-loss objective, kernel ridge regression, and scikit-learn’s kernel SVM:
import numpy as np
from sklearn.datasets import make_moons
from sklearn.svm import SVC
X, y01 = make_moons(400, noise=0.2, random_state=0)
y = 2 * y01 - 1 # labels in {-1, +1}
def linear_svm_sgd(X, y, lam=1e-3, epochs=30, seed=0):
"""Pegasos: SGD on (1/n) sum hinge + (lam/2)||w||^2; bias via a constant feature."""
rng = np.random.default_rng(seed)
Xb = np.hstack([X, np.ones((len(X), 1))])
w, t = np.zeros(Xb.shape[1]), 0
for _ in range(epochs):
for i in rng.permutation(len(y)):
t += 1
eta = 1 / (lam * t) # Pegasos step size
margin = y[i] * (Xb[i] @ w)
w *= (1 - eta * lam) # gradient of (lam/2)||w||^2
if margin < 1: # hinge subgradient
w += eta * y[i] * Xb[i]
return w[:-1], w[-1]
def rbf(A, B, gamma):
d2 = (A**2).sum(1)[:, None] - 2 * A @ B.T + (B**2).sum(1)[None, :]
return np.exp(-gamma * d2)
def kernel_ridge(X, y, lam=1e-2, gamma=2.0):
beta = np.linalg.solve(rbf(X, X, gamma) + lam * np.eye(len(X)), y)
return lambda Z: rbf(Z, X, gamma) @ beta
w, b = linear_svm_sgd(X, y)
f = kernel_ridge(X, y.astype(float))
svc = SVC(kernel="rbf", C=1.0, gamma=2.0).fit(X, y)
print("linear SVM accuracy:", np.mean(np.sign(X @ w + b) == y))
print("kernel ridge accuracy:", np.mean(np.sign(f(X)) == y))
print("RBF SVM accuracy:", svc.score(X, y), " support vectors:", len(svc.support_))
9.11Common Pitfalls
Pitfall: Unscaled features
Both the margin and the RBF distance depend on feature scales. Standardize features before training an SVM.
Pitfall: Tuning $C$ and $\gamma$ one at a time
$C$ and $\gamma$ interact: a large $\gamma$ can overfit even with small $C$. Search them jointly on a logarithmic grid (for example $C,\gamma\in\{10^{-3},\dots,10^3\}$) with cross-validation (Section 5.5).
Pitfall: Reading SVM scores as probabilities
SVM scores are distances, not probabilities. If you need probabilities, calibrate them on held-out data (Platt scaling fits a logistic regression to the scores).
9.12Summary
- The geometric margin is the distance from the boundary to the closest point; maximizing it gives the quadratic program $\min\frac12\norm\vw^2$ subject to $y^{(i)}(\vw\T\vx^{(i)}+b)\ge1$.
- Lagrange duality turns it into a dual problem in multipliers $\alpha_i$; complementary slackness makes $\alpha_i>0$ only for support vectors.
- The dual uses data only through inner products; a kernel $K(\vx,\vz)=\bm\phi(\vx)\T\bm\phi(\vz)$ computes them in a feature space that may be infinite-dimensional. Valid kernels have positive semidefinite Gram matrices.
- The soft-margin SVM equals hinge loss plus ridge; $C$ trades margin width against violations.
- SMO solves the dual by optimizing two multipliers at a time in closed form.
- The multiclass hinge loss trains linear classifiers and network output layers; kernel ridge regression and other methods kernelize by the representer theorem, at $O(n^2)$ memory cost.
9.13Exercises
- MathShow that the distance from a point $\vx$ to the hyperplane $\vw\T\vz+b=0$ is $|\vw\T\vx+b|/\norm\vw$.
- MathDerive the dual of the soft-margin problem Equation (9.6) and show that the slack variables disappear, leaving the box constraint $0\le\alpha_i\le C$.
- MathShow that $K(\vx,\vz)=(\vx\T\vz+1)^2$ in two dimensions corresponds to a feature map with six features, and find it.
- MathProve that if $K_1$ and $K_2$ are kernels then $K_1+K_2$ and $K_1K_2$ are kernels. (Hint: for the product, use the Schur product theorem or construct the feature map from all products of features.)
- MathDerive the gradient of the multiclass hinge loss Equation (9.9) with respect to $\mW$, and show that it is zero when every incorrect score is at least $\Delta$ below the correct one.
- CodingOn
make_circles(noise=0.1, factor=0.4), grid-search $C$ and $\gamma$ for an RBF SVM with 5-fold cross-validation. Plot the cross-validation accuracy as a heatmap over $(\log C,\log\gamma)$ and plot the decision boundaries at the best setting and at an overfitting setting. - CodingTrain a linear multiclass SVM (hinge loss, SGD) and a softmax classifier on
load_digits. Compare test accuracy and the distribution of the margins $s_{y}-\max_{j\ne y}s_j$.