Simple Algorithm
Artificial Intelligence · Deep Layer · 30 min

Kernels & Support Vector Machines

Maximum margins and the kernel trick.

Among all the lines that separate two classes, pick the one farthest from both. That single geometric choice leads to a convex quadratic program whose solution depends on only a few training points, whose dual sees the data only through inner products, and whose generalization can be bounded without reference to the dimension. Replace the inner products by a kernel and the same machinery learns curved boundaries in infinite-dimensional feature spaces.

What you’ll learn

  • Derive the hard-margin SVM's primal and dual problems, use the KKT conditions to characterize support vectors, and prove the leave-one-out bound #SV/n\#\mathrm{SV}/n.
  • Formulate the soft-margin SVM as regularized hinge-loss minimization, derive its box-constrained dual, and explain why the hinge loss is classification-calibrated.
  • State Mercer's condition and the Moore–Aronszajn construction of a reproducing kernel Hilbert space, and compute the feature map of a polynomial kernel.
  • State and sketch a margin-based generalization bound that depends on R/ρR/\rho rather than on the dimension.

The maximum-margin hyperplane

A linear classifier predicts sign⁡(w⊤x+b)\sign(\mathbf w^\top\mathbf x+b). On a training point, yi(w⊤xi+b)y_i(\mathbf w^\top\mathbf x_i+b) is its functional margin, positive when the point is classified correctly, and dividing by ∥w∥\norm{\mathbf w} gives its geometric margin, the signed distance to the hyperplane. Rescaling (w,b)(\mathbf w,b) changes neither the classifier nor the geometric margin, so fix the scale by requiring min⁡iyi(w⊤xi+b)=1\min_iy_i(\mathbf w^\top\mathbf x_i+b)=1. The margin is then 1/∥w∥1/\norm{\mathbf w}, and maximizing it is a convex quadratic program:

min⁡w,b 12∥w∥2subject toyi(w⊤xi+b)≥1,i=1,…,n\min_{\mathbf w,b}\ \tfrac12\norm{\mathbf w}^2\quad\text{subject to}\quad y_i\big(\mathbf w^\top\mathbf x_i+b\big)\ge1,\quad i=1,\dots,n
The hard-margin support vector machine (Boser, Guyon & Vapnik, 1992). If the data are linearly separable, the feasible set is a nonempty polyhedron and the objective is strictly convex in w\mathbf w, so the optimal w\mathbf w is unique; bb is then fixed by the points on the margin.

Why maximize the margin? A margin γ\gamma makes every training point robust: no perturbation smaller than γ\gamma can flip it. It also controls learning. The perceptron makes at most (R/γ)2(R/\gamma)^2 mistakes on data in a ball of radius RR that are separable with margin γ\gamma (Novikoff's theorem, in Perceptron Convergence & Its Limits), and the last step of this lesson turns the same ratio into a generalization bound that ignores the dimension.

Duality, KKT conditions and support vectors

DerivationFrom the primal to the dual
  1. L(w,b,α)=12∥w∥2−∑i=1nαi[yi(w⊤xi+b)−1]\mathcal L(\mathbf w,b,\boldsymbol\alpha)=\tfrac12\norm{\mathbf w}^2-\sum_{i=1}^n\alpha_i\big[y_i(\mathbf w^\top\mathbf x_i+b)-1\big]

    Attach a multiplier αi≥0\alpha_i\ge0 to each margin constraint:

  2. ∇wL=0 ⇒ w=∑iαiyixi,∂L∂b=0 ⇒ ∑iαiyi=0\nabla_{\mathbf w}\mathcal L=\mathbf 0\ \Rightarrow\ \mathbf w=\sum_i\alpha_iy_i\mathbf x_i,\qquad\frac{\partial\mathcal L}{\partial b}=0\ \Rightarrow\ \sum_i\alpha_iy_i=0

    Minimize over the primal variables. Setting the gradients to zero expresses w\mathbf w through the data and constrains the multipliers:

  3. max⁡α≥0 ∑iαi−12∑i,jαiαjyiyj xi⊤xjsubject to∑iαiyi=0\max_{\boldsymbol\alpha\ge\mathbf 0}\ \sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\,\mathbf x_i^\top\mathbf x_j\quad\text{subject to}\quad\sum_i\alpha_iy_i=0

    Substitute back. The data now appear only through inner products xi⊤xj\mathbf x_i^\top\mathbf x_j:

  4. αi[yi(w∗⊤xi+b∗)−1]=0for every i\alpha_i\big[y_i(\mathbf w^{*\top}\mathbf x_i+b^*)-1\big]=0\quad\text{for every }i

    The primal is a convex QP with affine constraints, so strong duality holds whenever it is feasible, and the KKT conditions of Optimization & Convexity characterize the optimum. Complementary slackness says that only points on the margin can carry weight:

The points with αi>0\alpha_i>0 are the support vectors. They alone determine w∗=∑i∈SVαiyixi\mathbf w^*=\sum_{i\in\mathrm{SV}}\alpha_iy_i\mathbf x_i, and any one of them gives b∗=ys−w∗⊤xsb^*=y_s-\mathbf w^{*\top}\mathbf x_s. Delete every other point and the solution does not change, which yields a clean bound on generalization.

Check your understanding

A hard-margin SVM trained on 1,000 linearly separable points has 25 support vectors. What does the leave-one-out argument guarantee?

  1. The test error is exactly 2.5%
  2. The leave-one-out error is at most 2.5%
  3. The training error is 2.5%
  4. Nothing, unless a kernel is used
Show the answer

B. The leave-one-out error is at most 2.5%

At most the 25 support vectors can be misclassified when left out, so the leave-one-out error is at most 25/1000=2.5%25/1000=2.5\%; in expectation over training sets, that bounds the test error of an SVM trained on 999 points. A sparse solution is evidence of good generalization, whatever the dimension of the feature space.

Soft margins and the hinge loss

Real data are rarely separable. The soft-margin SVM (Cortes & Vapnik, 1995) lets point ii violate its margin by a slack ξi≥0\xi_i\ge0, at a price CC per unit of slack:

min⁡w,b,ξ 12∥w∥2+C∑i=1nξisubject toyi(w⊤xi+b)≥1−ξi,ξi≥0\min_{\mathbf w,b,\boldsymbol\xi}\ \tfrac12\norm{\mathbf w}^2+C\sum_{i=1}^n\xi_i\quad\text{subject to}\quad y_i\big(\mathbf w^\top\mathbf x_i+b\big)\ge1-\xi_i,\quad\xi_i\ge0
A large CC approaches the hard margin; a small CC buys a wider margin at the cost of more violations.
DerivationHinge loss, the dual, and three kinds of points
  1. min⁡w,b ∑i=1nmax⁡(0, 1−yif(xi))+12C∥w∥2\min_{\mathbf w,b}\ \sum_{i=1}^n\max\big(0,\,1-y_if(\mathbf x_i)\big)+\frac1{2C}\norm{\mathbf w}^2

    At the optimum each slack is as small as allowed, ξi=max⁡(0,1−yif(xi))\xi_i=\max\big(0,1-y_if(\mathbf x_i)\big) with f(x)=w⊤x+bf(\mathbf x)=\mathbf w^\top\mathbf x+b. So the soft-margin SVM is ℓ2\ell_2-regularized empirical risk minimization with the hinge loss:

  2. max⁡α ∑iαi−12∑i,jαiαjyiyj xi⊤xjs.t.0≤αi≤C,∑iαiyi=0\max_{\boldsymbol\alpha}\ \sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\,\mathbf x_i^\top\mathbf x_j\quad\text{s.t.}\quad0\le\alpha_i\le C,\quad\sum_i\alpha_iy_i=0

    In the Lagrangian, the multipliers μi≥0\mu_i\ge0 of the constraints ξi≥0\xi_i\ge0 enter through ∂L/∂ξi=C−αi−μi=0\partial\mathcal L/\partial\xi_i=C-\alpha_i-\mu_i=0. The dual is the hard-margin dual with a box:

  3. αi=0⇒yif(xi)≥1,0<αi<C⇒yif(xi)=1,αi=C⇒yif(xi)≤1\alpha_i=0\Rightarrow y_if(\mathbf x_i)\ge1,\qquad0<\alpha_i<C\Rightarrow y_if(\mathbf x_i)=1,\qquad\alpha_i=C\Rightarrow y_if(\mathbf x_i)\le1

    Complementary slackness sorts the training points into three kinds:

  4. w∗=∑i: αi>0αiyixi\mathbf w^*=\sum_{i:\,\alpha_i>0}\alpha_iy_i\mathbf x_i

    Points beyond the margin carry no weight, points on it are the free support vectors, and points inside it or misclassified sit at the bound CC. The dual is solved by SMO (Platt, 1998) or, for linear SVMs, by dual coordinate descent (Hsieh et al., 2008).

Is the hinge loss a sensible surrogate for 0–1 loss? It upper-bounds it, 1{yf≤0}≤max⁡(0,1−yf)\mathbf 1\{yf\le0\}\le\max(0,1-yf), and it is classification-calibrated: the minimizer of the conditional hinge risk is sign⁡(2η(x)−1)\sign(2\eta(\mathbf x)-1), the Bayes classifier. Quantitatively, R(sign⁡f)−R∗≤Rhinge(f)−Rhinge∗R(\sign f)-R^*\le R_{\mathrm{hinge}}(f)-R^*_{\mathrm{hinge}} for every ff (Zhang, 2004; Bartlett, Jordan & McAuliffe, 2006), so driving the hinge risk to its minimum drives the classification risk to the Bayes error. The SVM's output is not a probability, though; Platt scaling fits a sigmoid to it afterwards (Platt, 1999).

Kernels: the trick, Mercer and the RKHS

In the dual, and in the classifier f(x)=∑iαiyi xi⊤x+bf(\mathbf x)=\sum_i\alpha_iy_i\,\mathbf x_i^\top\mathbf x+b, the data appear only through inner products. Replace each xi⊤xj\mathbf x_i^\top\mathbf x_j by k(xi,xj)=⟨ϕ(xi),ϕ(xj)⟩k(\mathbf x_i,\mathbf x_j)=\langle\boldsymbol\phi(\mathbf x_i),\boldsymbol\phi(\mathbf x_j)\rangle and the SVM becomes a maximum-margin linear classifier in the feature space of ϕ\boldsymbol\phi, which is a curved boundary in the original space, at the cost of evaluating kk: the kernel trick.

DerivationA kernel and its feature map
  1. (x⊤z)2=(x1z1+x2z2)2=x12z12+2 x1x2 z1z2+x22z22(\mathbf x^\top\mathbf z)^2=(x_1z_1+x_2z_2)^2=x_1^2z_1^2+2\,x_1x_2\,z_1z_2+x_2^2z_2^2

    In two dimensions, expand the square of an inner product:

  2. (x⊤z)2=ϕ(x)⊤ϕ(z),ϕ(x)=(x12, 2 x1x2, x22)(\mathbf x^\top\mathbf z)^2=\boldsymbol\phi(\mathbf x)^\top\boldsymbol\phi(\mathbf z),\qquad\boldsymbol\phi(\mathbf x)=\big(x_1^2,\ \sqrt2\,x_1x_2,\ x_2^2\big)

    That is an inner product of three-dimensional features, and a linear boundary in that space is a conic in the plane. On the classifier widget's disk-and-ring data, where a linear SVM manages only 67% test accuracy, the feature x12+x22x_1^2+x_2^2 alone separates the classes perfectly:

  3. e−∥x−z∥2/2ℓ2=e−∥x∥2/2ℓ2 e−∥z∥2/2ℓ2∑m=0∞(x⊤z)mℓ2m m!e^{-\norm{\mathbf x-\mathbf z}^2/2\ell^2}=e^{-\norm{\mathbf x}^2/2\ell^2}\,e^{-\norm{\mathbf z}^2/2\ell^2}\sum_{m=0}^\infty\frac{(\mathbf x^\top\mathbf z)^m}{\ell^{2m}\,m!}

    In general (x⊤z+c)d(\mathbf x^\top\mathbf z+c)^d with c>0c>0 corresponds to all monomials of degree at most dd, a feature space of dimension (p+dd)\binom{p+d}{d}, evaluated in O(p)\order{p} time. The Gaussian kernel is infinite-dimensional: factor out the norms and expand the exponential of the inner product:

DerivationWhy positive semidefiniteness is the right condition
  1. ∑i,jcicj k(xi,xj)=∥∑iciϕ(xi)∥2≥0\sum_{i,j}c_ic_j\,k(\mathbf x_i,\mathbf x_j)=\Big\|\sum_ic_i\boldsymbol\phi(\mathbf x_i)\Big\|^2\ge0

    Necessary. If kk is an inner product of features, every quadratic form of a Gram matrix is a squared norm:

  2. ⟨∑iaik(xi,⋅), ∑jbjk(zj,⋅)⟩=∑i,jaibj k(xi,zj)\Big\langle\sum_ia_ik(\mathbf x_i,\cdot),\ \sum_jb_jk(\mathbf z_j,\cdot)\Big\rangle=\sum_{i,j}a_ib_j\,k(\mathbf x_i,\mathbf z_j)

    Sufficient (Moore–Aronszajn). Take the functions k(x,⋅)k(\mathbf x,\cdot) as building blocks and define their inner product by the kernel. Positive semidefiniteness makes this a valid inner product on their span:

  3. f(x)=⟨f,k(x,⋅)⟩,k(x,z)=⟨k(x,⋅),k(z,⋅)⟩f(\mathbf x)=\langle f,k(\mathbf x,\cdot)\rangle,\qquad k(\mathbf x,\mathbf z)=\langle k(\mathbf x,\cdot),k(\mathbf z,\cdot)\rangle

    The reproducing property holds by construction, and Cauchy–Schwarz gives ∣f(x)∣≤k(x,x) ∥f∥\abs{f(\mathbf x)}\le\sqrt{k(\mathbf x,\mathbf x)}\,\norm f, so a function of norm 0 vanishes everywhere. Completing the span gives Hk\mathcal H_k, with feature map ϕ(x)=k(x,⋅)\boldsymbol\phi(\mathbf x)=k(\mathbf x,\cdot):

Kernels can be built from kernels: sums, products (by the Schur product theorem), positive multiples, limits, f(x)f(z)f(\mathbf x)f(\mathbf z) for any function ff, and the exponential of a kernel are all kernels. Kernels also exist on strings, graphs and sets, which is how SVMs classified text and protein sequences long before deep learning. By the representer theorem of Linear Models & Their Geometry, the optimal classifier is always a finite combination ∑iαiyik(xi,⋅)+b\sum_i\alpha_iy_ik(\mathbf x_i,\cdot)+b.

Why margins generalize

DerivationProof sketch
  1. 1{u≤0} ≤ Φρ(u) ≤ 1{u<ρ}\mathbf 1\{u\le0\}\ \le\ \Phi_\rho(u)\ \le\ \mathbf 1\{u<\rho\}

    Replace the 0–1 loss by the ramp loss Φρ\Phi_\rho: 1 below 0, 0 above ρ\rho, and linear in between. It is sandwiched between the two indicators of the bound and is 1/ρ1/\rho-Lipschitz:

  2. E Φρ(yf(x))≤1n∑iΦρ(yif(xi))+2R^S(Φρ∘F)+3ln⁡(2/δ)2n\E\,\Phi_\rho\big(yf(\mathbf x)\big)\le\frac1n\sum_i\Phi_\rho\big(y_if(\mathbf x_i)\big)+2\hat{\mathfrak R}_S(\Phi_\rho\circ\mathcal F)+3\sqrt{\frac{\ln(2/\delta)}{2n}}

    The standard Rademacher-complexity bound for a loss with values in [0,1][0,1] holds uniformly over F\mathcal F, with R^S\hat{\mathfrak R}_S the empirical Rademacher complexity:

  3. R^S(Φρ∘F)≤1ρ R^S(F)\hat{\mathfrak R}_S(\Phi_\rho\circ\mathcal F)\le\frac1\rho\,\hat{\mathfrak R}_S(\mathcal F)

    Talagrand's contraction lemma strips off the Lipschitz ramp at the price of a factor 1/ρ1/\rho; the labels yi=±1y_i=\pm1 do not change the complexity, because yiσiy_i\sigma_i has the same law as σi\sigma_i:

  4. R^S(F)=Λn Eσ∥∑iσiϕ(xi)∥≤Λn∑ik(xi,xi)≤ΛRn\hat{\mathfrak R}_S(\mathcal F)=\frac\Lambda n\,\E_{\boldsymbol\sigma}\Big\|\sum_i\sigma_i\boldsymbol\phi(\mathbf x_i)\Big\|\le\frac\Lambda n\sqrt{\sum_ik(\mathbf x_i,\mathbf x_i)}\le\frac{\Lambda R}{\sqrt n}

    For the linear class, Cauchy–Schwarz and then Jensen's inequality bound the complexity by the radius of the ball, with no dimension anywhere:

The bound depends on the hypothesis only through ΛR/ρ\Lambda R/\rho, which is scale-free: rescaling w\mathbf w changes Λ\Lambda and ρ\rho together. For the hard-margin SVM, take ρ=1\rho=1 and Λ=∥w∗∥=1/γ\Lambda=\norm{\mathbf w^*}=1/\gamma: the complexity term is 2R/(γn)2R/(\gamma\sqrt n), whatever the dimension of the feature space, even infinite as for the Gaussian kernel. Large margins relative to the data's radius, not few parameters, are what generalize. The bound is stated for a fixed ρ\rho; making it uniform over ρ\rho adds only a term of order log⁡log⁡(1/ρ)/n\sqrt{\log\log(1/\rho)/n}.

Predict before you look

Data lie in a ball of radius R=1R=1, the hard-margin SVM finds margin γ=0.1\gamma=0.1 (so Λ=10\Lambda=10 at ρ=1\rho=1), and n=10,000n=10{,}000. What is the complexity term 2ΛR/(ρn)2\Lambda R/(\rho\sqrt n)?

Show the answer

0.2

2⋅10⋅1/(1⋅100)=0.22\cdot10\cdot1/(1\cdot100)=0.2. With δ=0.05\delta=0.05 the confidence term adds about 0.04, and on separable data the empirical margin error is 0, so the bound guarantees a test error below about 24%. That is loose, as such bounds usually are, but it does not depend on the dimension, and it shrinks like 1/(γn)1/(\gamma\sqrt n).

Key takeaways

  • The hard-margin SVM maximizes the margin 1/∥w∥1/\norm{\mathbf w} by minimizing 12∥w∥2\frac12\norm{\mathbf w}^2 subject to yi(w⊤xi+b)≥1y_i(\mathbf w^\top\mathbf x_i+b)\ge1; its dual sees the data only through inner products.
  • KKT complementary slackness makes the solution sparse: only support vectors have αi>0\alpha_i>0, and the leave-one-out error is at most #SV/n\#\mathrm{SV}/n.
  • The soft margin is ℓ2\ell_2-regularized hinge-loss minimization, with box constraints 0≤αi≤C0\le\alpha_i\le C in the dual; the hinge loss is classification-calibrated but yields no probabilities.
  • A symmetric function is a kernel exactly when all its Gram matrices are positive semidefinite (Mercer, Moore–Aronszajn); polynomial kernels compute (p+dd)\binom{p+d}{d} monomials in O(p)\order{p} time, and the Gaussian kernel is infinite-dimensional.
  • Margin bounds of the form R^ρ+2ΛR/(ρn)\hat R_\rho+2\Lambda R/(\rho\sqrt n) are dimension-free: large margins relative to the data's radius, not few parameters, are what generalize.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A soft-margin SVM is retrained after deleting a training point that had αi=0\alpha_i=0. What happens to the solution?

  1. Nothing: the same (w,b)(\mathbf w,b) remains optimal
  2. The margin widens
  3. Every remaining αj\alpha_j changes slightly
  4. bb changes but w\mathbf w does not
Show the answer

A. Nothing: the same (w,b)(\mathbf w,b) remains optimal

The old solution satisfies the KKT conditions of the reduced problem: the deleted point contributed nothing to w=∑jαjyjxj\mathbf w=\sum_j\alpha_jy_j\mathbf x_j or to ∑jαjyj=0\sum_j\alpha_jy_j=0, and every other condition is unchanged. The widget shows the converse direction: points added far on the correct side leave the boundary untouched.

Question 2

Why can an SVM use the Gaussian kernel, whose feature space is infinite-dimensional?

  1. Because the SVM truncates the feature space to its first nn dimensions
  2. Because the dual problem and the classifier need only the kernel values k(xi,xj)k(\mathbf x_i,\mathbf x_j), an n×nn\times n Gram matrix
  3. Because the Gaussian kernel's feature vectors are sparse
  4. Because the margin bound rules out infinite dimensions
Show the answer

B. Because the dual problem and the classifier need only the kernel values k(xi,xj)k(\mathbf x_i,\mathbf x_j), an n×nn\times n Gram matrix

Both the dual objective and f(x)=∑iαiyik(xi,x)+bf(\mathbf x)=\sum_i\alpha_iy_ik(\mathbf x_i,\mathbf x)+b involve the data only through kernel values, so feature vectors are never formed. The representer theorem guarantees that nothing is lost by working in the span of the nn functions k(xi,⋅)k(\mathbf x_i,\cdot).

Question 3

Which of these functions on R\R is not a valid kernel?

  1. (xz+1)2(xz+1)^2
  2. e−(x−z)2e^{-(x-z)^2}
  3. −(x−z)2-(x-z)^2
  4. min⁡(x,z)\min(x,z), for x,z≥0x,z\ge0
Show the answer

C. −(x−z)2-(x-z)^2

For two points at distance dd, the Gram matrix of −(x−z)2-(x-z)^2 is (0−d2−d20)\begin{pmatrix}0&-d^2\\-d^2&0\end{pmatrix}, with eigenvalues ±d2\pm d^2: not positive semidefinite. The others are kernels: a polynomial kernel, the Gaussian kernel, and the covariance function of Brownian motion.

Question 4

At an input with η(x)=P(y=+1∣x)=0.7\eta(\mathbf x)=P(y=+1\mid\mathbf x)=0.7, which value of f(x)f(\mathbf x) minimizes the expected hinge loss E[max⁡(0,1−yf)∣x]\E[\max(0,1-yf)\mid\mathbf x]?

  1. 0.70.7
  2. 0.40.4, which is 2η−12\eta-1
  3. log⁡(0.7/0.3)≈0.85\log(0.7/0.3)\approx0.85
  4. +1+1
Show the answer

D. +1+1

The conditional hinge risk is 0.7max⁡(0,1−f)+0.3max⁡(0,1+f)0.7\max(0,1-f)+0.3\max(0,1+f). On [−1,1][-1,1] it equals 1−0.4f1-0.4f, which keeps falling, and beyond 11 it rises, so the minimum is at f=+1f=+1, with risk 0.6. The hinge loss recovers the Bayes classifier's label, sign⁡(2η−1)\sign(2\eta-1), but not the probability, unlike the log loss, whose minimizer is the log-odds, 0.85.

Further reading

  • B. E. Boser, I. M. Guyon & V. N. Vapnik, "A training algorithm for optimal margin classifiers," Proceedings of COLT (1992).
  • C. Cortes & V. Vapnik, "Support-vector networks," Machine Learning 20, 273–297 (1995).
  • B. Schölkopf & A. J. Smola, Learning with Kernels (MIT Press, 2002).
  • P. L. Bartlett & S. Mendelson, "Rademacher and Gaussian complexities: risk bounds and structural results," Journal of Machine Learning Research 3, 463–482 (2002).
  • M. Mohri, A. Rostamizadeh & A. Talwalkar, Foundations of Machine Learning, 2nd ed. (MIT Press, 2018).