QuantumCore

Lesson 33 · 100 min · core

Kernel Methods & Support Vector Machines

Loading progress…

The support vector machine (SVM) chooses, among all hyperplanes that separate two classes, the one with the largest margin. This lesson derives the distance from a point to a hyperplane and the margin 2/∥w∥2/\lVert w\rVert, formulates the hard- and soft-margin primal problems, derives the Lagrangian dual term by term, reads off from the KKT conditions which training points become support vectors and how the bias is recovered, and shows that both training and prediction touch the data only through inner products. Replacing the inner product by a kernel k(x,x′)=⟨φ(x),φ(x′)⟩k(x,x')=\langle\varphi(x),\varphi(x')\rangle gives non-linear classifiers at the cost of a linear one: we construct the explicit feature maps of the polynomial kernel and of the Gaussian (RBF) kernel, whose feature space is infinite-dimensional, and prove that every Gram matrix of a kernel is symmetric positive semidefinite, the property that quantum kernels will inherit in Module 3.3.

Prerequisites: Supervised Learning & Gradient Descent, Inner Products, Norms & Gram–Schmidt

Objectives and key results

  • Derive the distance ∣w⊤x0+b∣/∥w∥\lvert w^\top x_0+b\rvert/\lVert w\rVert from a point to the hyperplane w⊤x+b=0w^\top x+b=0 and the margin width 2/∥w∥2/\lVert w\rVert of a canonical separating hyperplane.

  • Formulate the hard-margin primal min⁡12∥w∥2\min\tfrac12\lVert w\rVert^2 s.t. yi(w⊤xi+b)≥1y_i(w^\top x_i+b)\ge1 and the soft-margin primal with slacks ξi≥0\xi_i\ge0 and penalty CC, and identify the latter as hinge-loss regularised risk minimisation.

  • Derive the dual max⁡α∑iαi−12∑i,jαiαjyiyjk(xi,xj)\max_\alpha\sum_i\alpha_i-\tfrac12\sum_{i,j}\alpha_i\alpha_jy_iy_jk(x_i,x_j) subject to 0≤αi≤C0\le\alpha_i\le C and ∑iαiyi=0\sum_i\alpha_iy_i=0 from the Lagrangian, including every substitution step.

  • Use KKT complementary slackness to classify training points (αi=0\alpha_i=0, 0<αi<C0<\alpha_i<C, αi=C\alpha_i=C) and to recover the bias from free support vectors.

  • Apply the kernel trick and write the explicit feature maps of the polynomial kernel (x⊤x′+c)d(x^\top x'+c)^d and of the RBF kernel e−γ∥x−x′∥2e^{-\gamma\lVert x-x'\rVert^2}.

  • Prove that the Gram matrix of every kernel is symmetric positive semidefinite, and compute and validate an RBF Gram matrix in code.

formula · Margin of a canonical hyperplane
dist⁡(x0,{w⊤x+b=0})=∣w⊤x0+b∣∥w∥,min⁡iyi(w⊤xi+b)=1 ⇒ margin width=2∥w∥\operatorname{dist}(x_0,\{w^\top x+b=0\})=\frac{\lvert w^\top x_0+b\rvert}{\lVert w\rVert},\qquad\min_iy_i(w^\top x_i+b)=1\ \Rightarrow\ \text{margin width}=\frac{2}{\lVert w\rVert}
formula · Soft-margin SVM dual
max⁡α∈Rm ∑i=1mαi−12∑i,j=1mαiαjyiyjk(xi,xj)s.t.0≤αi≤C,  ∑i=1mαiyi=0\max_{\alpha\in\mathbb R^m}\ \sum_{i=1}^m\alpha_i-\frac12\sum_{i,j=1}^m\alpha_i\alpha_jy_iy_jk(x_i,x_j)\quad\text{s.t.}\quad0\le\alpha_i\le C,\ \ \sum_{i=1}^m\alpha_iy_i=0
theorem · Support vectors from complementary slackness
αi=0⇒yif(xi)≥1,0<αi<C⇒yif(xi)=1,αi=C⇒yif(xi)≤1\alpha_i=0\Rightarrow y_if(x_i)\ge1,\qquad0<\alpha_i<C\Rightarrow y_if(x_i)=1,\qquad\alpha_i=C\Rightarrow y_if(x_i)\le1
identity · Kernelised decision function
f(x)=∑i=1mαiyik(xi,x)+b,b=ys−∑i=1mαiyik(xi,xs)  (0<αs<C)f(x)=\sum_{i=1}^m\alpha_iy_ik(x_i,x)+b,\qquad b=y_s-\sum_{i=1}^m\alpha_iy_ik(x_i,x_s)\ \ (0<\alpha_s<C)
identity · RBF feature map
e−γ∥x−x′∥2=∑β∈Ndφβ(x)φβ(x′),φβ(x)=e−γ∥x∥2(2γ)∣β∣β! xβe^{-\gamma\lVert x-x'\rVert^2}=\sum_{\beta\in\mathbb N^d}\varphi_\beta(x)\varphi_\beta(x'),\qquad\varphi_\beta(x)=e^{-\gamma\lVert x\rVert^2}\sqrt{\frac{(2\gamma)^{\lvert\beta\rvert}}{\beta!}}\,x^\beta
theorem · Gram matrices are PSD
Kij=⟨φ(xi),φ(xj)⟩ ⇒ K=K⊤,c⊤Kc=∥∑iciφ(xi)∥2≥0∀c∈RmK_{ij}=\langle\varphi(x_i),\varphi(x_j)\rangle\ \Rightarrow\ K=K^\top,\qquad c^\top Kc=\Big\lVert\sum_ic_i\varphi(x_i)\Big\rVert^2\ge0\quad\forall c\in\mathbb R^m

Linear classifiers and the maximum margin#

We are given a training set {(xi,yi)}i=1m\{(x_i,y_i)\}_{i=1}^m with inputs xi∈Rnx_i\in\mathbb R^n and binary labels yi∈{−1,+1}y_i\in\{-1,+1\}. A linear classifier is the function f(x)=w⊤x+bf(x)=w^\top x+b with weight vector w∈Rn∖{0}w\in\mathbb R^n\setminus\{0\} and bias b∈Rb\in\mathbb R; it predicts y^=sign⁡f(x)\hat y=\operatorname{sign}f(x). In the language of the previous lesson this is empirical risk minimisation over the hypothesis class of affine functions, but with the 0–1 loss the risk is piecewise constant in (w,b)(w,b) and gradient descent has nothing to follow. The SVM replaces "any separating hyperplane" by a geometric criterion, the margin, which leads to a convex quadratic program with a unique optimal ww.

Definition

Separating hyperplane

The hyperplane of (w,b)(w,b) is Hw,b={x∈Rn: w⊤x+b=0}\mathcal H_{w,b}=\{x\in\mathbb R^n:\ w^\top x+b=0\}. The data are linearly separable if some (w,b)(w,b) satisfies yi(w⊤xi+b)>0y_i(w^\top x_i+b)>0 for every ii, i.e. every point lies strictly on the side of Hw,b\mathcal H_{w,b} given by its label. The number yif(xi)y_if(x_i) is the functional margin of point ii; it is positive exactly when the point is classified correctly.

Proposition

Distance from a point to a hyperplane

For w≠0w\neq0 and any x0∈Rnx_0\in\mathbb R^n, dist⁡(x0,Hw,b)=min⁡x∈Hw,b∥x0−x∥=∣w⊤x0+b∣∥w∥,\operatorname{dist}(x_0,\mathcal H_{w,b})=\min_{x\in\mathcal H_{w,b}}\lVert x_0-x\rVert=\frac{\lvert w^\top x_0+b\rvert}{\lVert w\rVert}, and the minimum is attained at the orthogonal projection p=x0−w⊤x0+b∥w∥2 wp=x_0-\frac{w^\top x_0+b}{\lVert w\rVert^2}\,w. If x0x_0 carries the label y0y_0 and is correctly classified, the distance equals y0(w⊤x0+b)/∥w∥y_0(w^\top x_0+b)/\lVert w\rVert.

Proof (7 steps)
  1. Step 1:
    x,x′∈Hw,b ⇒ w⊤(x−x′)=(−b)−(−b)=0x,x'\in\mathcal H_{w,b}\ \Rightarrow\ w^\top(x-x')=(-b)-(-b)=0
    Subtract the two defining equations: ww is orthogonal to every vector lying inside the hyperplane, i.e. ww is a normal vector of Hw,b\mathcal H_{w,b}.
  2. Step 2:
    w⊤p+b=w⊤x0+b−w⊤x0+b∥w∥2 w⊤w=0 ⇒ p∈Hw,bw^\top p+b=w^\top x_0+b-\frac{w^\top x_0+b}{\lVert w\rVert^2}\,w^\top w=0\ \Rightarrow\ p\in\mathcal H_{w,b}
    Insert the definition of pp and use w⊤w=∥w∥2w^\top w=\lVert w\rVert^2.
  3. Step 3:
    ∥x0−x∥2=∥(x0−p)+(p−x)∥2=∥x0−p∥2+∥p−x∥2+2(x0−p)⊤(p−x)\lVert x_0-x\rVert^2=\lVert(x_0-p)+(p-x)\rVert^2=\lVert x_0-p\rVert^2+\lVert p-x\rVert^2+2(x_0-p)^\top(p-x)
    Expand the squared norm of a sum for an arbitrary x∈Hw,bx\in\mathcal H_{w,b}.
  4. Step 4:
    (x0−p)⊤(p−x)=w⊤x0+b∥w∥2 w⊤(p−x)=0(x_0-p)^\top(p-x)=\frac{w^\top x_0+b}{\lVert w\rVert^2}\,w^\top(p-x)=0
    x0−px_0-p is a multiple of ww, and p−xp-x lies inside the hyperplane (both pp and xx do), so step 1 applies.
  5. Step 5:
    ∥x0−x∥2=∥x0−p∥2+∥p−x∥2≥∥x0−p∥2,  with equality iff x=p\lVert x_0-x\rVert^2=\lVert x_0-p\rVert^2+\lVert p-x\rVert^2\ge\lVert x_0-p\rVert^2,\ \ \text{with equality iff }x=p
    Pythagoras: the cross term vanishes, and ∥p−x∥2≥0\lVert p-x\rVert^2\ge0 with equality only at x=px=p.
  6. Step 6:
    dist⁡(x0,Hw,b)=∥x0−p∥=∣w⊤x0+b∣∥w∥2 ∥w∥=∣w⊤x0+b∣∥w∥\operatorname{dist}(x_0,\mathcal H_{w,b})=\lVert x_0-p\rVert=\frac{\lvert w^\top x_0+b\rvert}{\lVert w\rVert^2}\,\lVert w\rVert=\frac{\lvert w^\top x_0+b\rvert}{\lVert w\rVert}
    Norm of the scalar multiple x0−p=w⊤x0+b∥w∥2wx_0-p=\frac{w^\top x_0+b}{\lVert w\rVert^2}w.
  7. Step 7:
    y0(w⊤x0+b)>0 ⇒ ∣w⊤x0+b∣=y0(w⊤x0+b)y_0(w^\top x_0+b)>0\ \Rightarrow\ \lvert w^\top x_0+b\rvert=y_0(w^\top x_0+b)
    y0∈{±1}y_0\in\{\pm1\} and correct classification means w⊤x0+bw^\top x_0+b has the sign of y0y_0.

∎

Definition

Geometric margin

For a separating (w,b)(w,b) the geometric margin of point ii is γi=yi(w⊤xi+b)/∥w∥\gamma_i=y_i(w^\top x_i+b)/\lVert w\rVert, its distance to the hyperplane, and the margin of the classifier on the training set is γ(w,b)=min⁡iγi\gamma(w,b)=\min_i\gamma_i. The maximum-margin hyperplane maximises γ(w,b)\gamma(w,b) over all separating (w,b)(w,b).

Derivation

From maximum margin to the hard-margin primal

  1. Step 1:
    γ(sw,sb)=min⁡iyi(sw⊤xi+sb)∥sw∥=min⁡is yi(w⊤xi+b)s∥w∥=γ(w,b)(s>0)\gamma(sw,sb)=\min_i\frac{y_i(sw^\top x_i+sb)}{\lVert sw\rVert}=\min_i\frac{s\,y_i(w^\top x_i+b)}{s\lVert w\rVert}=\gamma(w,b)\qquad(s>0)
    Rescaling (w,b)(w,b) by a positive factor does not move the hyperplane and does not change the margin, so we may fix the scale.
  2. Step 2:
    s=1min⁡iyi(w⊤xi+b) ⇒ min⁡iyi(sw⊤xi+sb)=1s=\frac1{\min_iy_i(w^\top x_i+b)}\ \Rightarrow\ \min_iy_i(sw^\top x_i+sb)=1
    For a separating hyperplane the minimum functional margin is positive, so this s>0s>0 exists. A pair with min⁡iyi(w⊤xi+b)=1\min_iy_i(w^\top x_i+b)=1 is called canonical.
  3. Step 3:
    canonical (w,b):γ(w,b)=min⁡iyi(w⊤xi+b)∥w∥=1∥w∥\text{canonical }(w,b):\quad\gamma(w,b)=\frac{\min_iy_i(w^\top x_i+b)}{\lVert w\rVert}=\frac1{\lVert w\rVert}
    Definition of the geometric margin with the normalisation of the previous step.
  4. Step 4:
    dist⁡({w⊤x+b=1},{w⊤x+b=−1})=∣w⊤x++b+1∣∥w∥=∣1+1∣∥w∥=2∥w∥\operatorname{dist}\big(\{w^\top x+b=1\},\{w^\top x+b=-1\}\big)=\frac{\lvert w^\top x_++b+1\rvert}{\lVert w\rVert}=\frac{\lvert1+1\rvert}{\lVert w\rVert}=\frac2{\lVert w\rVert}
    The closest points of the two classes lie on the parallel hyperplanes w⊤x+b=±1w^\top x+b=\pm1. Take any x+x_+ with w⊤x++b=1w^\top x_++b=1 and apply the distance formula to the hyperplane (w,b+1)(w,b+1): the empty band between the classes has width 2/∥w∥2/\lVert w\rVert.
  5. Step 5:
    yi(w⊤xi+b)≥1 ∀i ⇒ γ(w,b)≥1∥w∥y_i(w^\top x_i+b)\ge1\ \forall i\ \Rightarrow\ \gamma(w,b)\ge\frac1{\lVert w\rVert}
    Any (w,b)(w,b) satisfying these constraints (canonical or not) has every γi≥1/∥w∥\gamma_i\ge1/\lVert w\rVert; for the canonical rescaling of a separating pair equality holds. Hence max⁡γ=max⁡{1/∥w∥: yi(w⊤xi+b)≥1 ∀i}\max\gamma=\max\{1/\lVert w\rVert:\ y_i(w^\top x_i+b)\ge1\ \forall i\}.
  6. Step 6:
    max⁡1∥w∥  ⟺  min⁡∥w∥  ⟺  min⁡12∥w∥2\max\frac1{\lVert w\rVert}\iff\min\lVert w\rVert\iff\min\tfrac12\lVert w\rVert^2
    t↦1/tt\mapsto1/t is decreasing and t↦12t2t\mapsto\tfrac12t^2 is increasing on t>0t>0, so all three problems have the same minimisers. The square makes the objective differentiable and the factor 12\tfrac12 cancels the 22 of its gradient.

Result

min⁡w,b 12∥w∥2s.t.yi(w⊤xi+b)≥1,  i=1,…,m\boxed{\min_{w,b}\ \tfrac12\lVert w\rVert^2\quad\text{s.t.}\quad y_i(w^\top x_i+b)\ge1,\ \ i=1,\dots,m}

Quick check

A canonical separating hyperplane has w=(3,4)w=(3,4). What is the width 2/∥w∥2/\lVert w\rVert of the margin band? Give a decimal.

tolerance ±0.000001

Soft margins and slack variables#

Real data are rarely separable, and when they are, a single outlier can force a tiny margin. The soft-margin SVM (Cortes and Vapnik, 1995) allows each constraint to be violated by a slack ξi≥0\xi_i\ge0 and pays CξiC\xi_i for it. The constant C>0C>0 sets the trade-off between a wide margin (small ∥w∥\lVert w\rVert) and few violations (small ∑iξi\sum_i\xi_i).

Definition

Soft-margin primal problem

min⁡w,b,ξ 12∥w∥2+C∑i=1mξis.t.yi(w⊤xi+b)≥1−ξi,ξi≥0,i=1,…,m.\min_{w,b,\xi}\ \frac12\lVert w\rVert^2+C\sum_{i=1}^m\xi_i\quad\text{s.t.}\quad y_i(w^\top x_i+b)\ge1-\xi_i,\quad\xi_i\ge0,\qquad i=1,\dots,m. The problem is always feasible: w=0w=0, b=0b=0, ξi=1\xi_i=1 satisfies every constraint. Its objective is convex and its constraints are affine, so it is again a convex quadratic program.

Derivation

Eliminating the slacks: the hinge loss

  1. Step 1:
    ξi≥1−yif(xi)andξi≥0  ⟺  ξi≥max⁡(0, 1−yif(xi))\xi_i\ge1-y_if(x_i)\quad\text{and}\quad\xi_i\ge0\iff\xi_i\ge\max\big(0,\,1-y_if(x_i)\big)
    The two constraints on ξi\xi_i are two lower bounds; together they say ξi\xi_i exceeds their maximum.
  2. Step 2:
    ξi∗(w,b)=max⁡(0, 1−yif(xi))\xi_i^\ast(w,b)=\max\big(0,\,1-y_if(x_i)\big)
    For fixed (w,b)(w,b) the objective is strictly increasing in each ξi\xi_i (coefficient C>0C>0), so each slack sits at its lower bound.
  3. Step 3:
    min⁡w,b 12∥w∥2+C∑i=1mmax⁡(0, 1−yi(w⊤xi+b))\min_{w,b}\ \frac12\lVert w\rVert^2+C\sum_{i=1}^m\max\big(0,\,1-y_i(w^\top x_i+b)\big)
    Substitute the optimal slacks: the primal is equivalent to this unconstrained problem.
  4. Step 4:
    =Cm[1m∑i=1mℓhinge(yi,f(xi))+λ2∥w∥2],ℓhinge(y,f)=max⁡(0,1−yf),  λ=1Cm=Cm\Big[\frac1m\sum_{i=1}^m\ell_{\mathrm{hinge}}\big(y_i,f(x_i)\big)+\frac{\lambda}{2}\lVert w\rVert^2\Big],\qquad\ell_{\mathrm{hinge}}(y,f)=\max(0,1-yf),\ \ \lambda=\frac1{Cm}
    Factor out Cm>0Cm>0, which does not change the minimiser: the soft-margin SVM is regularised empirical risk minimisation with the hinge loss, a convex upper bound of the 0–1 loss.
  5. Step 5:
    yif(xi)≤0 ⇒ ξi∗≥1 ⇒ #{i: yif(xi)≤0}≤∑i=1mξi∗y_if(x_i)\le0\ \Rightarrow\ \xi_i^\ast\ge1\ \Rightarrow\ \#\{i:\ y_if(x_i)\le0\}\le\sum_{i=1}^m\xi_i^\ast
    A misclassified point has non-positive functional margin, hence slack at least 11; summing, the total slack bounds the number of training errors.

The optimal slack classifies every training point: ξi∗=0\xi_i^\ast=0 when yif(xi)≥1y_if(x_i)\ge1 (on or beyond its margin hyperplane), 0<ξi∗≤10<\xi_i^\ast\le1 when the point is inside the band but on the correct side, and ξi∗>1\xi_i^\ast>1 when it is misclassified. Large CC makes violations expensive; on separable data, as C→∞C\to\infty the soft-margin solution approaches the hard-margin one. Small CC tolerates many violations in exchange for a wider band, which is the main defence against overfitting noisy labels.

The Lagrangian dual#

Following Boyd and Vandenberghe (§5.1), write each constraint as g(⋅)≤0g(\cdot)\le0, attach a non-negative multiplier to it and add it to the objective. The multipliers are αi≥0\alpha_i\ge0 for 1−ξi−yi(w⊤xi+b)≤01-\xi_i-y_i(w^\top x_i+b)\le0 and μi≥0\mu_i\ge0 for −ξi≤0-\xi_i\le0. The dual function g(α,μ)=inf⁡w,b,ξL(w,b,ξ,α,μ)g(\alpha,\mu)=\inf_{w,b,\xi}L(w,b,\xi,\alpha,\mu) is a lower bound on the primal optimum for every α,μ≥0\alpha,\mu\ge0 (weak duality), because on any feasible point the added terms are ≤0\le0. The dual problem maximises this lower bound.

Derivation

Derivation of the soft-margin dual

  1. Step 1:
    L(w,b,ξ,α,μ)=12∥w∥2+C∑iξi−∑iαi[yi(w⊤xi+b)−1+ξi]−∑iμiξiL(w,b,\xi,\alpha,\mu)=\frac12\lVert w\rVert^2+C\sum_i\xi_i-\sum_i\alpha_i\big[y_i(w^\top x_i+b)-1+\xi_i\big]-\sum_i\mu_i\xi_i
    Objective plus multiplier times constraint function: αi(1−ξi−yi(w⊤xi+b))=−αi[yi(w⊤xi+b)−1+ξi]\alpha_i\big(1-\xi_i-y_i(w^\top x_i+b)\big)=-\alpha_i[y_i(w^\top x_i+b)-1+\xi_i] and μi(−ξi)\mu_i(-\xi_i).
  2. Step 2:
    L=12∥w∥2−w⊤(∑iαiyixi)−b∑iαiyi+∑iξi(C−αi−μi)+∑iαiL=\frac12\lVert w\rVert^2-w^\top\Big(\sum_i\alpha_iy_ix_i\Big)-b\sum_i\alpha_iy_i+\sum_i\xi_i\big(C-\alpha_i-\mu_i\big)+\sum_i\alpha_i
    Expand the bracket and collect the terms in ww, in bb, in each ξi\xi_i, and the constant ∑iαi\sum_i\alpha_i.
  3. Step 3:
    inf⁡b∈R(−b∑iαiyi)={0if ∑iαiyi=0−∞otherwise\inf_{b\in\mathbb R}\Big(-b\sum_i\alpha_iy_i\Big)=\begin{cases}0&\text{if }\sum_i\alpha_iy_i=0\\-\infty&\text{otherwise}\end{cases}
    A linear function of bb is bounded below only if its slope is zero. Stationarity in bb: ∂L/∂b=−∑iαiyi=0\partial L/\partial b=-\sum_i\alpha_iy_i=0.
  4. Step 4:
    inf⁡ξi∈Rξi(C−αi−μi)={0if C−αi−μi=0−∞otherwise\inf_{\xi_i\in\mathbb R}\xi_i\big(C-\alpha_i-\mu_i\big)=\begin{cases}0&\text{if }C-\alpha_i-\mu_i=0\\-\infty&\text{otherwise}\end{cases}
    Same argument for each slack: ∂L/∂ξi=C−αi−μi=0\partial L/\partial\xi_i=C-\alpha_i-\mu_i=0.
  5. Step 5:
    μi=C−αi≥0  and  αi≥0  ⟺  0≤αi≤C\mu_i=C-\alpha_i\ge0\ \text{ and }\ \alpha_i\ge0\iff0\le\alpha_i\le C
    The multiplier μi\mu_i only appears through this equation, so it can be eliminated; its sign constraint turns into the box constraint αi≤C\alpha_i\le C.
  6. Step 6:
    ∇wL=w−∑iαiyixi=0 ⇒ w=∑i=1mαiyixi\nabla_wL=w-\sum_i\alpha_iy_ix_i=0\ \Rightarrow\ w=\sum_{i=1}^m\alpha_iy_ix_i
    LL is a strictly convex quadratic in ww (Hessian I≻0I\succ0), so the unique stationary point is its global minimiser: the optimal weight vector is a linear combination of training inputs.
  7. Step 7:
    12∥w∥2=12(∑iαiyixi)⊤(∑jαjyjxj)=12∑i,jαiαjyiyj xi⊤xj\frac12\lVert w\rVert^2=\frac12\Big(\sum_i\alpha_iy_ix_i\Big)^\top\Big(\sum_j\alpha_jy_jx_j\Big)=\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\,x_i^\top x_j
    First term after substitution: expand the inner product bilinearly.
  8. Step 8:
    w⊤(∑iαiyixi)=w⊤w=∑i,jαiαjyiyj xi⊤xjw^\top\Big(\sum_i\alpha_iy_ix_i\Big)=w^\top w=\sum_{i,j}\alpha_i\alpha_jy_iy_j\,x_i^\top x_j
    Second term: the vector in brackets is ww itself, so the term equals ∥w∥2\lVert w\rVert^2, i.e. twice the first term.
  9. Step 9:
    −b∑iαiyi=0,∑iξi(C−αi−μi)=0-b\sum_i\alpha_iy_i=0,\qquad\sum_i\xi_i\big(C-\alpha_i-\mu_i\big)=0
    Third and fourth terms vanish on the set where the dual function is finite (steps 3 and 4).
  10. Step 10:
    g(α)=12∑i,jαiαjyiyjxi⊤xj−∑i,jαiαjyiyjxi⊤xj+∑iαi=∑iαi−12∑i,jαiαjyiyjxi⊤xjg(\alpha)=\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_jx_i^\top x_j-\sum_{i,j}\alpha_i\alpha_jy_iy_jx_i^\top x_j+\sum_i\alpha_i=\sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_jx_i^\top x_j
    Add the four terms and the constant ∑iαi\sum_i\alpha_i; bb, ξ\xi and μ\mu have disappeared.
  11. Step 11:
    ∑i,jαiαjyiyjxi⊤xj=∥∑iαiyixi∥2≥0\sum_{i,j}\alpha_i\alpha_jy_iy_jx_i^\top x_j=\Big\lVert\sum_i\alpha_iy_ix_i\Big\rVert^2\ge0
    The quadratic form is a squared norm, so it is convex in α\alpha and gg is concave: the dual is a concave maximisation (a convex QP) over the compact set [0,C]m∩{∑iαiyi=0}[0,C]^m\cap\{\sum_i\alpha_iy_i=0\}.

Result

max⁡α∈Rm ∑i=1mαi−12∑i,j=1mαiαjyiyj xi⊤xjs.t.0≤αi≤C,  ∑i=1mαiyi=0\boxed{\max_{\alpha\in\mathbb R^m}\ \sum_{i=1}^m\alpha_i-\frac12\sum_{i,j=1}^m\alpha_i\alpha_jy_iy_j\,x_i^\top x_j\quad\text{s.t.}\quad0\le\alpha_i\le C,\ \ \sum_{i=1}^m\alpha_iy_i=0}
Proposition

Strong duality for the soft-margin SVM

The primal and dual optimal values are equal and both are attained. Consequently a primal-feasible (w,b,ξ)(w,b,\xi) and a dual-feasible (α,μ)(\alpha,\mu) are both optimal if and only if they satisfy the KKT conditions of the next section.

Proof (5 steps)
  1. Step 1:
    (w,b,ξ)=(0,0,1) is feasible(w,b,\xi)=(0,0,\mathbf 1)\ \text{is feasible}
    yi(0+0)=0≥1−1y_i(0+0)=0\ge1-1 and ξi=1≥0\xi_i=1\ge0: the primal feasible set is a non-empty polyhedron.
  2. Step 2:
    p∗=min⁡feasible(12∥w∥2+C∑iξi) existsp^\ast=\min_{\text{feasible}}\Big(\tfrac12\lVert w\rVert^2+C\textstyle\sum_i\xi_i\Big)\ \text{exists}
    A convex quadratic function bounded below (here by 00) on a non-empty polyhedron attains its infimum (Frank–Wolfe theorem).
  3. Step 3:
    d∗=max⁡0≤α≤C, ∑iαiyi=0g(α) existsd^\ast=\max_{0\le\alpha\le C,\ \sum_i\alpha_iy_i=0}g(\alpha)\ \text{exists}
    The dual feasible set contains α=0\alpha=0 and is closed and bounded; gg is continuous, so Weierstrass' theorem gives a maximiser.
  4. Step 4:
    d∗≤p∗d^\ast\le p^\ast
    Weak duality: for feasible primal points and α,μ≥0\alpha,\mu\ge0 the multiplier terms in LL are ≤0\le0, so g(α,μ)≤L≤g(\alpha,\mu)\le L\le primal objective.
  5. Step 5:
    d∗=p∗d^\ast=p^\ast
    The objective is convex and every constraint is affine, so the refined Slater condition reduces to feasibility, which holds by step 1; Slater's theorem (Boyd and Vandenberghe §5.2.3) gives a zero duality gap.

∎

KKT conditions and support vectors#

Theorem

KKT conditions of the soft-margin SVM

Let (w,b,ξ)(w,b,\xi) be primal feasible and α,μ≥0\alpha,\mu\ge0. Both are optimal if and only if (stationarity) w=∑iαiyixiw=\sum_i\alpha_iy_ix_i, ∑iαiyi=0\sum_i\alpha_iy_i=0, μi=C−αi\mu_i=C-\alpha_i, and (complementary slackness) αi[yi(w⊤xi+b)−1+ξi]=0,μiξi=(C−αi) ξi=0for every i.\alpha_i\big[y_i(w^\top x_i+b)-1+\xi_i\big]=0,\qquad\mu_i\xi_i=(C-\alpha_i)\,\xi_i=0\qquad\text{for every }i.

Proof (6 steps)
  1. Step 1:
    p∗=d∗=g(α,μ)=inf⁡w′,b′,ξ′L(w′,b′,ξ′,α,μ)≤L(w,b,ξ,α,μ)p^\ast=d^\ast=g(\alpha,\mu)=\inf_{w',b',\xi'}L(w',b',\xi',\alpha,\mu)\le L(w,b,\xi,\alpha,\mu)
    (⇒\Rightarrow) Optimality of both together with strong duality; the infimum is at most the value at the particular point (w,b,ξ)(w,b,\xi).
  2. Step 2:
    L(w,b,ξ,α,μ)=p∗−∑iαi[yi(w⊤xi+b)−1+ξi]−∑iμiξi≤p∗L(w,b,\xi,\alpha,\mu)=p^\ast-\sum_i\alpha_i\big[y_i(w^\top x_i+b)-1+\xi_i\big]-\sum_i\mu_i\xi_i\le p^\ast
    The objective at the optimal primal point is p∗p^\ast; each bracket and each ξi\xi_i is ≥0\ge0 by feasibility and the multipliers are ≥0\ge0.
  3. Step 3:
    ∑iαi[yi(w⊤xi+b)−1+ξi]+∑iμiξi=0\sum_i\alpha_i\big[y_i(w^\top x_i+b)-1+\xi_i\big]+\sum_i\mu_i\xi_i=0
    Steps 1 and 2 squeeze LL between p∗p^\ast and p∗p^\ast.
  4. Step 4:
    αi[yi(w⊤xi+b)−1+ξi]=0,μiξi=0∀i\alpha_i\big[y_i(w^\top x_i+b)-1+\xi_i\big]=0,\qquad\mu_i\xi_i=0\quad\forall i
    A sum of non-negative terms is zero only if every term is zero: complementary slackness. Since L(⋅,α,μ)L(\cdot,\alpha,\mu) attains its infimum at (w,b,ξ)(w,b,\xi) (steps 1–3) and gg is finite, the stationarity equations of the dual derivation hold.
  5. Step 5:
    L(w,b,ξ,α,μ)=inf⁡L=g(α,μ)L(w,b,\xi,\alpha,\mu)=\inf L=g(\alpha,\mu)
    (⇐\Leftarrow) If stationarity holds, (w,b,ξ)(w,b,\xi) is a stationary point of the convex function L(⋅,α,μ)L(\cdot,\alpha,\mu), hence a global minimiser.
  6. Step 6:
    g(α,μ)=12∥w∥2+C∑iξi ⇒ both optimalg(\alpha,\mu)=\tfrac12\lVert w\rVert^2+C\textstyle\sum_i\xi_i\ \Rightarrow\ \text{both optimal}
    By complementary slackness the multiplier terms of LL vanish, so the dual value equals the primal objective; weak duality then forces both to be optimal.

∎

Corollary

Which points are support vectors

At an optimum, with f(x)=w⊤x+bf(x)=w^\top x+b: (i) αi=0⇒yif(xi)≥1\alpha_i=0\Rightarrow y_if(x_i)\ge1; (ii) 0<αi<C⇒yif(xi)=10<\alpha_i<C\Rightarrow y_if(x_i)=1, the point lies exactly on its margin hyperplane; (iii) αi=C⇒yif(xi)=1−ξi≤1\alpha_i=C\Rightarrow y_if(x_i)=1-\xi_i\le1, the point is on, inside or beyond the margin. Conversely yif(xi)>1⇒αi=0y_if(x_i)>1\Rightarrow\alpha_i=0 and yif(xi)<1⇒αi=Cy_if(x_i)<1\Rightarrow\alpha_i=C. The points with αi>0\alpha_i>0 are the support vectors; only they enter w=∑i:αi>0αiyixiw=\sum_{i:\alpha_i>0}\alpha_iy_ix_i.

Proof (6 steps)
  1. Step 1:
    αi=0 ⇒ μi=C>0 ⇒ ξi=0 ⇒ yif(xi)≥1−ξi=1\alpha_i=0\ \Rightarrow\ \mu_i=C>0\ \Rightarrow\ \xi_i=0\ \Rightarrow\ y_if(x_i)\ge1-\xi_i=1
    (i) Stationarity μi=C−αi\mu_i=C-\alpha_i, then μiξi=0\mu_i\xi_i=0, then primal feasibility.
  2. Step 2:
    0<αi<C ⇒ μi>0 ⇒ ξi=0;αi>0 ⇒ yif(xi)=1−ξi=10<\alpha_i<C\ \Rightarrow\ \mu_i>0\ \Rightarrow\ \xi_i=0;\qquad\alpha_i>0\ \Rightarrow\ y_if(x_i)=1-\xi_i=1
    (ii) Both complementary-slackness equations are active: the bracket must vanish and the slack is zero.
  3. Step 3:
    αi=C>0 ⇒ yif(xi)=1−ξi≤1\alpha_i=C>0\ \Rightarrow\ y_if(x_i)=1-\xi_i\le1
    (iii) The first complementary-slackness equation with ξi≥0\xi_i\ge0; now μi=0\mu_i=0 leaves ξi\xi_i free to be positive.
  4. Step 4:
    yif(xi)>1 ⇒ yif(xi)−1+ξi>0 ⇒ αi=0y_if(x_i)>1\ \Rightarrow\ y_if(x_i)-1+\xi_i>0\ \Rightarrow\ \alpha_i=0
    Converse 1: the bracket is strictly positive because ξi≥0\xi_i\ge0, so its multiplier vanishes.
  5. Step 5:
    yif(xi)<1 ⇒ ξi≥1−yif(xi)>0 ⇒ μi=0 ⇒ αi=Cy_if(x_i)<1\ \Rightarrow\ \xi_i\ge1-y_if(x_i)>0\ \Rightarrow\ \mu_i=0\ \Rightarrow\ \alpha_i=C
    Converse 2: feasibility forces positive slack, μiξi=0\mu_i\xi_i=0 forces μi=0\mu_i=0, and stationarity gives αi=C\alpha_i=C.
  6. Step 6:
    w=∑i=1mαiyixi=∑i: αi>0αiyixiw=\sum_{i=1}^m\alpha_iy_ix_i=\sum_{i:\,\alpha_i>0}\alpha_iy_ix_i
    Terms with αi=0\alpha_i=0 drop out: points strictly outside the margin can be deleted without changing the classifier.

∎

Derivation

Recovering the bias from free support vectors

  1. Step 1:
    0<αs<C ⇒ ys(w⊤xs+b)=10<\alpha_s<C\ \Rightarrow\ y_s\big(w^\top x_s+b\big)=1
    Case (ii) of the corollary for a free support vector ss.
  2. Step 2:
    w⊤xs+b=ysw^\top x_s+b=y_s
    Multiply by ysy_s and use ys2=1y_s^2=1.
  3. Step 3:
    b=ys−w⊤xs=ys−∑i=1mαiyi xi⊤xsb=y_s-w^\top x_s=y_s-\sum_{i=1}^m\alpha_iy_i\,x_i^\top x_s
    Solve for bb and insert w=∑iαiyixiw=\sum_i\alpha_iy_ix_i.
  4. Step 4:
    b=1∣S∣∑s∈S(ys−∑i=1mαiyi xi⊤xs),S={s: 0<αs<C}b=\frac1{\lvert S\rvert}\sum_{s\in S}\Big(y_s-\sum_{i=1}^m\alpha_iy_i\,x_i^\top x_s\Big),\qquad S=\{s:\ 0<\alpha_s<C\}
    Every free support vector gives the same bb in exact arithmetic; averaging over all of them reduces round-off. If SS is empty, every bb in the interval allowed by the bound vectors is optimal and SMO takes the midpoint.

Quick check

After training, a point has αi=C\alpha_i=C and slack ξi=1.4\xi_i=1.4. Where does it lie?

Select one answer

The kernel trick#

Look again at the result of the dual derivation and at the classifier it produces. The dual objective contains the inputs only through the numbers xi⊤xjx_i^\top x_j. The decision function is f(x)=w⊤x+b=∑iαiyi xi⊤x+bf(x)=w^\top x+b=\sum_i\alpha_iy_i\,x_i^\top x+b, which needs only xi⊤xx_i^\top x, and the bias formula needs only xi⊤xsx_i^\top x_s. Nothing in training or prediction ever uses a coordinate of xx on its own. So if we first send the data through a map φ:Rn→H\varphi:\mathbb R^n\to\mathcal H into a (possibly huge) inner-product space and run the linear SVM there, we only have to be able to evaluate ⟨φ(x),φ(x′)⟩\langle\varphi(x),\varphi(x')\rangle, never φ\varphi itself.

Definition

Kernel and feature map

A function k:X×X→Rk:\mathcal X\times\mathcal X\to\mathbb R is a kernel if there are a real Hilbert space H\mathcal H (the feature space) and a map φ:X→H\varphi:\mathcal X\to\mathcal H (the feature map) with k(x,x′)=⟨φ(x),φ(x′)⟩Hfor all x,x′∈X.k(x,x')=\langle\varphi(x),\varphi(x')\rangle_{\mathcal H}\qquad\text{for all }x,x'\in\mathcal X. The linear kernel k(x,x′)=x⊤x′k(x,x')=x^\top x' has φ=id\varphi=\mathrm{id}. The feature map is not unique: φ\varphi followed by any isometry of H\mathcal H gives the same kk.

Proposition

The kernelised SVM

Running the soft-margin SVM on φ(x1),…,φ(xm)∈H\varphi(x_1),\dots,\varphi(x_m)\in\mathcal H gives the dual of the previous section with xi⊤xjx_i^\top x_j replaced by Kij=k(xi,xj)K_{ij}=k(x_i,x_j), the optimal weight w=∑iαiyiφ(xi)∈Hw=\sum_i\alpha_iy_i\varphi(x_i)\in\mathcal H, and the decision function f(x)=⟨w,φ(x)⟩+b=∑i=1mαiyi k(xi,x)+b,b=ys−∑i=1mαiyi k(xi,xs)  (0<αs<C).f(x)=\langle w,\varphi(x)\rangle+b=\sum_{i=1}^m\alpha_iy_i\,k(x_i,x)+b,\qquad b=y_s-\sum_{i=1}^m\alpha_iy_i\,k(x_i,x_s)\ \ (0<\alpha_s<C). This holds even when H\mathcal H is infinite-dimensional.

Proof (6 steps)
  1. Step 1:
    L=12∥w∥H2−⟨w,v⟩H−b∑iαiyi+∑iξi(C−αi−μi)+∑iαi,v:=∑iαiyiφ(xi)L=\tfrac12\lVert w\rVert_{\mathcal H}^2-\langle w,v\rangle_{\mathcal H}-b\textstyle\sum_i\alpha_iy_i+\sum_i\xi_i(C-\alpha_i-\mu_i)+\sum_i\alpha_i,\qquad v:=\sum_i\alpha_iy_i\varphi(x_i)
    The Lagrangian is the same expression with w⊤xiw^\top x_i replaced by ⟨w,φ(xi)⟩\langle w,\varphi(x_i)\rangle and linearity of the inner product used to collect the ww terms.
  2. Step 2:
    12∥w∥2−⟨w,v⟩=12∥w−v∥2−12∥v∥2 ≥ −12∥v∥2,  equality iff w=v\tfrac12\lVert w\rVert^2-\langle w,v\rangle=\tfrac12\lVert w-v\rVert^2-\tfrac12\lVert v\rVert^2\ \ge\ -\tfrac12\lVert v\rVert^2,\ \ \text{equality iff }w=v
    Complete the square, valid in any inner-product space; no derivatives or coordinates are needed, so the minimisation over w∈Hw\in\mathcal H is exact even in infinite dimension.
  3. Step 3:
    ∥v∥2=⟨∑iαiyiφ(xi),∑jαjyjφ(xj)⟩=∑i,jαiαjyiyj k(xi,xj)\lVert v\rVert^2=\Big\langle\sum_i\alpha_iy_i\varphi(x_i),\sum_j\alpha_jy_j\varphi(x_j)\Big\rangle=\sum_{i,j}\alpha_i\alpha_jy_iy_j\,k(x_i,x_j)
    Bilinearity of the inner product and the definition of the kernel.
  4. Step 4:
    g(α)=∑iαi−12∑i,jαiαjyiyjKijs.t. 0≤αi≤C, ∑iαiyi=0g(\alpha)=\sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_jK_{ij}\quad\text{s.t. }0\le\alpha_i\le C,\ \textstyle\sum_i\alpha_iy_i=0
    The bb, ξ\xi and μ\mu steps are unchanged; insert the minimum −12∥v∥2-\tfrac12\lVert v\rVert^2 of the ww part.
  5. Step 5:
    ⟨w,φ(x)⟩=∑iαiyi⟨φ(xi),φ(x)⟩=∑iαiyi k(xi,x)\langle w,\varphi(x)\rangle=\sum_i\alpha_iy_i\langle\varphi(x_i),\varphi(x)\rangle=\sum_i\alpha_iy_i\,k(x_i,x)
    With w=vw=v, the decision function needs mm kernel evaluations and no coordinate of φ\varphi.
  6. Step 6:
    b=ys−⟨w,φ(xs)⟩=ys−∑iαiyi k(xi,xs)b=y_s-\langle w,\varphi(x_s)\rangle=y_s-\sum_i\alpha_iy_i\,k(x_i,x_s)
    The bias derivation for a free support vector, with the same substitution.

∎

Derivation

XOR is not linearly separable

  1. Step 1:
    x∈{(1,1),(−1,−1)}↦y=+1,x∈{(1,−1),(−1,1)}↦y=−1x\in\{(1,1),(-1,-1)\}\mapsto y=+1,\qquad x\in\{(1,-1),(-1,1)\}\mapsto y=-1
    The XOR pattern: the label is the product x1x2x_1x_2 of the coordinates.
  2. Step 2:
    (w1+w2+b)+(−w1−w2+b)=2b>0(w_1+w_2+b)+(-w_1-w_2+b)=2b>0
    Suppose f=w⊤x+bf=w^\top x+b separates the data. Both positive points need f>0f>0; add the two inequalities.
  3. Step 3:
    (w1−w2+b)+(−w1+w2+b)=2b<0(w_1-w_2+b)+(-w_1+w_2+b)=2b<0
    Both negative points need f<0f<0; add those two inequalities.
  4. Step 4:
    b>0 and b<0 ⇒ no separating hyperplaneb>0\ \text{and}\ b<0\ \Rightarrow\ \text{no separating hyperplane}
    Contradiction, so no linear classifier on R2\mathbb R^2 is correct on all four points.
  5. Step 5:
    φ(x)=(x1,x2,x1x2),  w=(0,0,1), b=0 ⇒ f(x)=x1x2=y\varphi(x)=(x_1,x_2,x_1x_2),\ \ w=(0,0,1),\ b=0\ \Rightarrow\ f(x)=x_1x_2=y
    After adding the single product feature, the hyperplane z3=0z_3=0 in R3\mathbb R^3 separates the data with yif(xi)=1y_if(x_i)=1 for all four points: a non-linear boundary x1x2=0x_1x_2=0 in input space.
Proposition

Feature map of the polynomial kernel

For c≥0c\ge0 and an integer d≥1d\ge1, k(x,x′)=(x⊤x′+c)dk(x,x')=(x^\top x'+c)^d on Rn\mathbb R^n is a kernel with the finite feature map indexed by multi-indices β=(β0,β1,…,βn)∈Nn+1\beta=(\beta_0,\beta_1,\dots,\beta_n)\in\mathbb N^{n+1} with β0+β1+⋯+βn=d\beta_0+\beta_1+\dots+\beta_n=d: φβ(x)=d!β0! β1!⋯βn! cβ0  x1β1⋯xnβn.\varphi_\beta(x)=\sqrt{\frac{d!}{\beta_0!\,\beta_1!\cdots\beta_n!}\,c^{\beta_0}}\;x_1^{\beta_1}\cdots x_n^{\beta_n}. The feature space has dimension (n+dd)\binom{n+d}{d}, while one evaluation of kk costs O(n)O(n) operations.

Proof (6 steps)
  1. Step 1:
    x⊤x′+c=c+∑j=1nxjxj′x^\top x'+c=c+\sum_{j=1}^nx_jx_j'
    Write the base as a sum of n+1n+1 terms t0=ct_0=c, tj=xjxj′t_j=x_jx'_j.
  2. Step 2:
    (∑j=0ntj)d=∑β0+⋯+βn=dd!β0!⋯βn! t0β0t1β1⋯tnβn\Big(\sum_{j=0}^nt_j\Big)^d=\sum_{\beta_0+\dots+\beta_n=d}\frac{d!}{\beta_0!\cdots\beta_n!}\,t_0^{\beta_0}t_1^{\beta_1}\cdots t_n^{\beta_n}
    Multinomial theorem: expanding the dd-fold product, the monomial tβt^\beta arises from choosing which of the dd factors contribute each tjt_j, in d!/(β0!⋯βn!)d!/(\beta_0!\cdots\beta_n!) ways.
  3. Step 3:
    t0β0∏j=1ntjβj=cβ0∏j=1nxjβj∏j=1nxj′βjt_0^{\beta_0}\prod_{j=1}^nt_j^{\beta_j}=c^{\beta_0}\prod_{j=1}^nx_j^{\beta_j}\prod_{j=1}^n{x'_j}^{\beta_j}
    Each tjβj=xjβjxj′βjt_j^{\beta_j}=x_j^{\beta_j}{x'_j}^{\beta_j} splits into an xx part and an x′x' part.
  4. Step 4:
    d! cβ0β0!⋯βn! x1β1⋯xnβn x1′β1⋯xn′βn=φβ(x) φβ(x′)\frac{d!\,c^{\beta_0}}{\beta_0!\cdots\beta_n!}\,x_1^{\beta_1}\cdots x_n^{\beta_n}\,{x'_1}^{\beta_1}\cdots{x'_n}^{\beta_n}=\varphi_\beta(x)\,\varphi_\beta(x')
    The coefficient is non-negative because c≥0c\ge0, so it has a real square root that can be shared equally between the xx factor and the x′x' factor.
  5. Step 5:
    (x⊤x′+c)d=∑∣β∣=dφβ(x)φβ(x′)=⟨φ(x),φ(x′)⟩RN(x^\top x'+c)^d=\sum_{\lvert\beta\rvert=d}\varphi_\beta(x)\varphi_\beta(x')=\langle\varphi(x),\varphi(x')\rangle_{\mathbb R^N}
    Sum over all multi-indices: the kernel is the Euclidean inner product of the vectors φ(x)=(φβ(x))β\varphi(x)=(\varphi_\beta(x))_\beta.
  6. Step 6:
    N=#{β∈Nn+1: ∣β∣=d}=(n+dd)N=\#\{\beta\in\mathbb N^{n+1}:\ \lvert\beta\rvert=d\}=\binom{n+d}{d}
    Stars and bars: distributing dd identical units over n+1n+1 slots. For n=2n=2, d=2d=2, c=1c=1 this gives N=6N=6 with φ(x)=(1,2x1,2x2,x12,2x1x2,x22)\varphi(x)=(1,\sqrt2x_1,\sqrt2x_2,x_1^2,\sqrt2x_1x_2,x_2^2).

∎

The degree-2 polynomial kernel contains the coordinate 2 x1x2\sqrt2\,x_1x_2, so it separates XOR exactly as the hand-made map above. For n=1000n=1000 and d=3d=3 its feature space has (10033)≈1.7×108\binom{1003}{3}\approx1.7\times10^8 dimensions, yet each kernel value is one inner product of length 10001000, one addition and two multiplications. This is the kernel trick: the cost of the SVM depends on mm (through the m×mm\times m Gram matrix) and on the cost of evaluating kk, never on dim⁡H\dim\mathcal H. A quantum feature map x↦∣ϕ(x)⟩x\mapsto\lvert\phi(x)\rangle on qq qubits is the extreme case: dim⁡H=2q\dim\mathcal H=2^q, and the kernel ∣⟨ϕ(x)∣ϕ(x′)⟩∣2\lvert\langle\phi(x)\vert\phi(x')\rangle\rvert^2 is estimated by a circuit.

Quick check

What is the dimension of the feature space of the kernel k(x,x′)=(x⊤x′+1)2k(x,x')=(x^\top x'+1)^2 on R3\mathbb R^3?

tolerance ±1e-9

The RBF kernel and its infinite-dimensional feature map#

Definition

Gaussian (RBF) kernel

For γ>0\gamma>0 the Gaussian or radial basis function (RBF) kernel on Rd\mathbb R^d is kγ(x,x′)=e−γ∥x−x′∥2=exp⁡(−γ∑t=1d(xt−xt′)2).k_\gamma(x,x')=e^{-\gamma\lVert x-x'\rVert^2}=\exp\Big(-\gamma\sum_{t=1}^d(x_t-x'_t)^2\Big). It depends only on the squared distance, equals 11 on the diagonal and decays to 00 for distant points. It is often written e−∥x−x′∥2/(2σ2)e^{-\lVert x-x'\rVert^2/(2\sigma^2)}, i.e. γ=1/(2σ2)\gamma=1/(2\sigma^2) with length scale σ\sigma. Multi-index notation: for β∈Nd\beta\in\mathbb N^d, ∣β∣=∑tβt\lvert\beta\rvert=\sum_t\beta_t, β!=∏tβt!\beta!=\prod_t\beta_t! and xβ=∏txtβtx^\beta=\prod_tx_t^{\beta_t}.

Theorem

Explicit feature map of the RBF kernel

In one dimension, e−γ(x−x′)2=∑k=0∞φk(x)φk(x′)e^{-\gamma(x-x')^2}=\sum_{k=0}^\infty\varphi_k(x)\varphi_k(x') with φk(x)=e−γx2(2γ)kk! xk,k=0,1,2,…\varphi_k(x)=e^{-\gamma x^2}\sqrt{\frac{(2\gamma)^k}{k!}}\,x^k,\qquad k=0,1,2,\dots In dd dimensions, e−γ∥x−x′∥2=∑β∈Ndφβ(x)φβ(x′)e^{-\gamma\lVert x-x'\rVert^2}=\sum_{\beta\in\mathbb N^d}\varphi_\beta(x)\varphi_\beta(x') with φβ(x)=e−γ∥x∥2(2γ)∣β∣/β!  xβ\varphi_\beta(x)=e^{-\gamma\lVert x\rVert^2}\sqrt{(2\gamma)^{\lvert\beta\rvert}/\beta!}\;x^\beta. Every φ(x)\varphi(x) is a unit vector of the sequence space ℓ2\ell^2, and the series is the ℓ2\ell^2 inner product, so kγk_\gamma is a kernel with feature space ℓ2\ell^2.

Proof (9 steps)
  1. Step 1:
    ∥x−x′∥2=∥x∥2−2x⊤x′+∥x′∥2\lVert x-x'\rVert^2=\lVert x\rVert^2-2x^\top x'+\lVert x'\rVert^2
    Expand the squared norm of a difference.
  2. Step 2:
    e−γ∥x−x′∥2=e−γ∥x∥2 e−γ∥x′∥2 e2γx⊤x′e^{-\gamma\lVert x-x'\rVert^2}=e^{-\gamma\lVert x\rVert^2}\,e^{-\gamma\lVert x'\rVert^2}\,e^{2\gamma x^\top x'}
    ea+b+c=eaebece^{a+b+c}=e^ae^be^c. The first two factors each depend on one argument only; all coupling sits in e2γx⊤x′e^{2\gamma x^\top x'}.
  3. Step 3:
    e2γx⊤x′=∑k=0∞(2γ)k (x⊤x′)kk!e^{2\gamma x^\top x'}=\sum_{k=0}^\infty\frac{(2\gamma)^k\,(x^\top x')^k}{k!}
    Taylor series eu=∑kuk/k!e^u=\sum_ku^k/k!, which converges absolutely for every real uu.
  4. Step 4:
    d=1:(2γ)k(xx′)kk!=[(2γ)kk! xk][(2γ)kk! x′k]d=1:\quad\frac{(2\gamma)^k(xx')^k}{k!}=\Big[\sqrt{\tfrac{(2\gamma)^k}{k!}}\,x^k\Big]\Big[\sqrt{\tfrac{(2\gamma)^k}{k!}}\,x'^k\Big]
    In one dimension (xx′)k=xkx′k(xx')^k=x^kx'^k and the positive coefficient (2γ)k/k!(2\gamma)^k/k! is split by its square root.
  5. Step 5:
    e−γ(x−x′)2=∑k=0∞[e−γx2(2γ)kk! xk][e−γx′2(2γ)kk! x′k]=∑k=0∞φk(x)φk(x′)e^{-\gamma(x-x')^2}=\sum_{k=0}^\infty\Big[e^{-\gamma x^2}\sqrt{\tfrac{(2\gamma)^k}{k!}}\,x^k\Big]\Big[e^{-\gamma x'^2}\sqrt{\tfrac{(2\gamma)^k}{k!}}\,x'^k\Big]=\sum_{k=0}^\infty\varphi_k(x)\varphi_k(x')
    Multiply the series of step 4 by the two prefactors of step 2 and absorb one prefactor into each bracket.
  6. Step 6:
    (x⊤x′)k=(∑t=1dxtxt′)k=∑∣β∣=kk!β! xβx′β(x^\top x')^k=\Big(\sum_{t=1}^dx_tx'_t\Big)^k=\sum_{\lvert\beta\rvert=k}\frac{k!}{\beta!}\,x^\beta x'^\beta
    dd dimensions: multinomial theorem with the dd terms xtxt′x_tx'_t, and ∏t(xtxt′)βt=xβx′β\prod_t(x_tx'_t)^{\beta_t}=x^\beta x'^\beta.
  7. Step 7:
    e2γx⊤x′=∑k=0∞(2γ)kk!∑∣β∣=kk!β!xβx′β=∑β∈Nd(2γ)∣β∣β! xβx′βe^{2\gamma x^\top x'}=\sum_{k=0}^\infty\frac{(2\gamma)^k}{k!}\sum_{\lvert\beta\rvert=k}\frac{k!}{\beta!}x^\beta x'^\beta=\sum_{\beta\in\mathbb N^d}\frac{(2\gamma)^{\lvert\beta\rvert}}{\beta!}\,x^\beta x'^\beta
    The k!k! cancels. Regrouping the double sum into one sum over Nd\mathbb N^d is allowed because the series of absolute values, ∑β(2γ)∣β∣β!∣xβ∣∣x′β∣=e2γ∑t∣xt∣∣xt′∣\sum_\beta\frac{(2\gamma)^{\lvert\beta\rvert}}{\beta!}\lvert x^\beta\rvert\lvert x'^\beta\rvert=e^{2\gamma\sum_t\lvert x_t\rvert\lvert x'_t\rvert}, is finite.
  8. Step 8:
    e−γ∥x−x′∥2=∑β∈Nd[e−γ∥x∥2(2γ)∣β∣β! xβ][e−γ∥x′∥2(2γ)∣β∣β! x′β]e^{-\gamma\lVert x-x'\rVert^2}=\sum_{\beta\in\mathbb N^d}\Big[e^{-\gamma\lVert x\rVert^2}\sqrt{\tfrac{(2\gamma)^{\lvert\beta\rvert}}{\beta!}}\,x^\beta\Big]\Big[e^{-\gamma\lVert x'\rVert^2}\sqrt{\tfrac{(2\gamma)^{\lvert\beta\rvert}}{\beta!}}\,x'^\beta\Big]
    Multiply by the two prefactors of step 2 and split each coefficient by its square root: this is ∑βφβ(x)φβ(x′)\sum_\beta\varphi_\beta(x)\varphi_\beta(x').
  9. Step 9:
    ∑βφβ(x)2=e−2γ∥x∥2∑β(2γ)∣β∣β! x2β=e−2γ∥x∥2e2γ∥x∥2=1\sum_{\beta}\varphi_\beta(x)^2=e^{-2\gamma\lVert x\rVert^2}\sum_\beta\frac{(2\gamma)^{\lvert\beta\rvert}}{\beta!}\,x^{2\beta}=e^{-2\gamma\lVert x\rVert^2}e^{2\gamma\lVert x\rVert^2}=1
    Step 7 with x′=xx'=x (so x⊤x=∥x∥2x^\top x=\lVert x\rVert^2): φ(x)\varphi(x) is square-summable with norm 1=kγ(x,x)1=k_\gamma(x,x), hence an element of ℓ2\ell^2, and by Cauchy–Schwarz the series in step 8 is the convergent inner product ⟨φ(x),φ(x′)⟩ℓ2\langle\varphi(x),\varphi(x')\rangle_{\ell^2}.

∎

Proposition

No finite feature space reproduces the RBF kernel

Let d=1d=1. For any distinct points x1,…,xm∈Rx_1,\dots,x_m\in\mathbb R the vectors φ(x1),…,φ(xm)∈ℓ2\varphi(x_1),\dots,\varphi(x_m)\in\ell^2 are linearly independent and the Gram matrix Kij=e−γ(xi−xj)2K_{ij}=e^{-\gamma(x_i-x_j)^2} is positive definite. Consequently there is no feature map ψ:R→RD\psi:\mathbb R\to\mathbb R^D with kγ(x,x′)=ψ(x)⊤ψ(x′)k_\gamma(x,x')=\psi(x)^\top\psi(x') for any finite DD.

Proof (6 steps)
  1. Step 1:
    ∑i=1mciφ(xi)=0 ⇒ ∑i=1mci e−γxi2(2γ)kk! xik=0(k=0,…,m−1)\sum_{i=1}^mc_i\varphi(x_i)=0\ \Rightarrow\ \sum_{i=1}^mc_i\,e^{-\gamma x_i^2}\sqrt{\tfrac{(2\gamma)^k}{k!}}\,x_i^k=0\quad(k=0,\dots,m-1)
    A vector of ℓ2\ell^2 is zero iff every coordinate is zero; keep the first mm coordinates.
  2. Step 2:
    ∑i=1mxik ui=0(k=0,…,m−1),ui:=cie−γxi2\sum_{i=1}^mx_i^k\,u_i=0\quad(k=0,\dots,m-1),\qquad u_i:=c_ie^{-\gamma x_i^2}
    Divide coordinate kk by the positive constant (2γ)k/k!\sqrt{(2\gamma)^k/k!}.
  3. Step 3:
    V⊤u=0,Vik=xi k,det⁡V=∏1≤i<j≤m(xj−xi)≠0V^\top u=0,\qquad V_{ik}=x_i^{\,k},\qquad\det V=\prod_{1\le i<j\le m}(x_j-x_i)\neq0
    The system is the transpose of the Vandermonde matrix, whose determinant is non-zero for distinct nodes.
  4. Step 4:
    u=0 ⇒ ci=ui eγxi2=0  ∀iu=0\ \Rightarrow\ c_i=u_i\,e^{\gamma x_i^2}=0\ \ \forall i
    An invertible matrix has trivial kernel, and eγxi2≠0e^{\gamma x_i^2}\neq0.
  5. Step 5:
    c≠0 ⇒ c⊤Kc=∥∑iciφ(xi)∥2>0c\neq0\ \Rightarrow\ c^\top Kc=\Big\lVert\sum_ic_i\varphi(x_i)\Big\rVert^2>0
    The Gram-matrix identity proved in the next section, with strict inequality because the combination is non-zero by linear independence.
  6. Step 6:
    K=ΨΨ⊤,  Ψ∈Rm×D ⇒ rank⁡K≤D<m for m=D+1K=\Psi\Psi^\top,\ \ \Psi\in\mathbb R^{m\times D}\ \Rightarrow\ \operatorname{rank}K\le D<m\ \text{for}\ m=D+1
    A finite feature map would make KK (rows ψ(xi)⊤\psi(x_i)^\top of Ψ\Psi) of rank at most DD, contradicting positive definiteness for D+1D+1 distinct points.

∎

Quick check

Compute kγ(x,x′)=e−γ∥x−x′∥2k_\gamma(x,x')=e^{-\gamma\lVert x-x'\rVert^2} for x=(1,2)x=(1,2), x′=(2,0)x'=(2,0) and γ=0.5\gamma=0.5. Give a decimal.

tolerance ±0.0001

Gram matrices are symmetric positive semidefinite#

Definition

Gram matrix

For a kernel kk and points x1,…,xmx_1,\dots,x_m the Gram matrix (kernel matrix) is K∈Rm×mK\in\mathbb R^{m\times m} with Kij=k(xi,xj)K_{ij}=k(x_i,x_j). A real matrix is positive semidefinite (PSD), K⪰0K\succeq0, if it is symmetric and c⊤Kc≥0c^\top Kc\ge0 for every c∈Rmc\in\mathbb R^m.

Theorem

The Gram matrix of a kernel is symmetric positive semidefinite

If k(x,x′)=⟨φ(x),φ(x′)⟩Hk(x,x')=\langle\varphi(x),\varphi(x')\rangle_{\mathcal H} for a real Hilbert space H\mathcal H, then for all mm and all x1,…,xmx_1,\dots,x_m the Gram matrix satisfies K=K⊤K=K^\top and c⊤Kc=∥∑iciφ(xi)∥2≥0c^\top Kc=\lVert\sum_ic_i\varphi(x_i)\rVert^2\ge0 for every c∈Rmc\in\mathbb R^m. Equivalently, all eigenvalues of KK are real and non-negative.

Proof (6 steps)
  1. Step 1:
    Kij=⟨φ(xi),φ(xj)⟩=⟨φ(xj),φ(xi)⟩=KjiK_{ij}=\langle\varphi(x_i),\varphi(x_j)\rangle=\langle\varphi(x_j),\varphi(x_i)\rangle=K_{ji}
    A real inner product is symmetric.
  2. Step 2:
    c⊤Kc=∑i=1m∑j=1mcicj ⟨φ(xi),φ(xj)⟩c^\top Kc=\sum_{i=1}^m\sum_{j=1}^mc_ic_j\,\langle\varphi(x_i),\varphi(x_j)\rangle
    Write the quadratic form entrywise.
  3. Step 3:
    =⟨∑i=1mciφ(xi), ∑j=1mcjφ(xj)⟩=\Big\langle\sum_{i=1}^mc_i\varphi(x_i),\ \sum_{j=1}^mc_j\varphi(x_j)\Big\rangle
    The inner product is linear in each argument, so the double sum moves inside.
  4. Step 4:
    =∥∑i=1mciφ(xi)∥H2 ≥ 0=\Big\lVert\sum_{i=1}^mc_i\varphi(x_i)\Big\rVert_{\mathcal H}^2\ \ge\ 0
    The inner product of a vector with itself is its squared norm, which is non-negative.
  5. Step 5:
    K=VΛV⊤,λk=vk⊤Kvk≥0K=V\Lambda V^\top,\qquad\lambda_k=v_k^\top Kv_k\ge0
    KK is real symmetric, so the spectral theorem gives an orthonormal eigenbasis vkv_k with real eigenvalues; take c=vkc=v_k in step 4.
  6. Step 6:
    η=K11+K22−2K12=(e1−e2)⊤K(e1−e2)=∥φ(x1)−φ(x2)∥2≥0\eta=K_{11}+K_{22}-2K_{12}=(e_1-e_2)^\top K(e_1-e_2)=\lVert\varphi(x_1)-\varphi(x_2)\rVert^2\ge0
    Consequence for SMO: the curvature of the dual along a two-variable update is a value of the PSD quadratic form, so the pair subproblem is concave. The SVM dual's quadratic term (y∘α)⊤K(y∘α)≥0(y\circ\alpha)^\top K(y\circ\alpha)\ge0 is concave for the same reason.

∎

The theorem has a practical reading in both directions. Every kernel produces PSD Gram matrices: the linear, polynomial and RBF kernels above, and the quantum fidelity kernels ∣⟨ϕ(x)∣ϕ(x′)⟩∣2\lvert\langle\phi(x)\vert\phi(x')\rangle\rvert^2 of Module 3.3. Contrapositively, a symmetric function whose Gram matrix on some finite set has a negative eigenvalue cannot be written as an inner product of features. For example, s(x,x′)=∥x−x′∥2s(x,x')=\lVert x-x'\rVert^2 on two points at distance 11 gives (0110)\begin{pmatrix}0&1\\1&0\end{pmatrix} with eigenvalues ±1\pm1, so it is not a kernel. The converse statement, that every symmetric function with PSD Gram matrices on all finite sets is a kernel, is the Moore–Aronszajn theorem of the next lesson.

Derivation

Worked example: an RBF Gram matrix on three points

  1. Step 1:
    x0=(0,0), x1=(1,0), x2=(0,2), γ=12:∥x0−x1∥2=1, ∥x0−x2∥2=4, ∥x1−x2∥2=1+4=5x_0=(0,0),\ x_1=(1,0),\ x_2=(0,2),\ \gamma=\tfrac12:\quad\lVert x_0-x_1\rVert^2=1,\ \lVert x_0-x_2\rVert^2=4,\ \lVert x_1-x_2\rVert^2=1+4=5
    Squared Euclidean distances, coordinate by coordinate.
  2. Step 2:
    K=(1e−1/2e−2e−1/21e−5/2e−2e−5/21)≈(10.60653065970.13533528320.606530659710.08208499860.13533528320.08208499861)K=\begin{pmatrix}1&e^{-1/2}&e^{-2}\\e^{-1/2}&1&e^{-5/2}\\e^{-2}&e^{-5/2}&1\end{pmatrix}\approx\begin{pmatrix}1&0.6065306597&0.1353352832\\0.6065306597&1&0.0820849986\\0.1353352832&0.0820849986&1\end{pmatrix}
    Kij=e−γ∥xi−xj∥2K_{ij}=e^{-\gamma\lVert x_i-x_j\rVert^2} with exponents −12⋅1-\tfrac12\cdot1, −12⋅4-\tfrac12\cdot4, −12⋅5-\tfrac12\cdot5; the diagonal is e0=1e^0=1. This is the visible test of the lab.
  3. Step 3:
    Δ1=1>0,Δ2=1−e−1≈0.6321>0\Delta_1=1>0,\qquad\Delta_2=1-e^{-1}\approx0.6321>0
    Leading principal minors of order 1 and 2.
  4. Step 4:
    Δ3=1+2abc−a2−b2−c2,a=e−1/2, b=e−2, c=e−5/2\Delta_3=1+2abc-a^2-b^2-c^2,\quad a=e^{-1/2},\ b=e^{-2},\ c=e^{-5/2}
    Determinant of a symmetric 3×33\times3 matrix with unit diagonal and off-diagonal entries aa (01)(01), bb (02)(02), cc (12)(12), by the rule of Sarrus.
  5. Step 5:
    abc=e−5, a2=e−1, b2=e−4, c2=e−5 ⇒ Δ3=1+e−5−e−1−e−4≈0.6205428669>0abc=e^{-5},\ a^2=e^{-1},\ b^2=e^{-4},\ c^2=e^{-5}\ \Rightarrow\ \Delta_3=1+e^{-5}-e^{-1}-e^{-4}\approx0.6205428669>0
    Add the exponents. All leading principal minors are positive, so KK is positive definite by Sylvester's criterion, as the RBF theory predicts for distinct points.
  6. Step 6:
    λ(K)≈{0.3910642162, 0.9656007564, 1.6433350273},∑kλk=Tr⁡K=3,  ∏kλk=Δ3\lambda(K)\approx\{0.3910642162,\ 0.9656007564,\ 1.6433350273\},\qquad\textstyle\sum_k\lambda_k=\operatorname{Tr}K=3,\ \ \prod_k\lambda_k=\Delta_3
    Eigenvalues from the engine's Hermitian eigensolver; their sum and product reproduce the trace and the determinant.
Kij=e−12∥xi−xj∥2K_{ij}=e^{-\frac12\lVert x_i-x_j\rVert^2}
RBF Gram matrix of (0,0), (1,0), (0,2) at γ = 0.53×3

The code below puts the whole lesson together on the XOR points (±1,±1)(\pm1,\pm1) with γ=12\gamma=\tfrac12. The squared distances are 44 between neighbours and 88 between opposite corners, so KK has 11 on the diagonal, e−2e^{-2} for neighbours and e−4e^{-4} for opposite corners. Its eigenvectors are (1,1,1,1)(1,1,1,1), (1,1,−1,−1)(1,1,-1,-1), (1,−1,0,0)(1,-1,0,0) and (0,0,1,−1)(0,0,1,-1), with eigenvalues 1+e−4+2e−21+e^{-4}+2e^{-2}, 1+e−4−2e−21+e^{-4}-2e^{-2} and 1−e−41-e^{-4} (twice), all positive. Because KK is positive definite the dual objective is strictly concave and has a unique maximiser; the symmetries of the square (swapping the two points of a class, or swapping the classes) map maximisers to maximisers, so every αi\alpha_i equals one number aa. The dual becomes 4a−12a2 y⊤Ky=4a−2a2(1+e−4−2e−2)4a-\tfrac12a^2\,y^\top Ky=4a-2a^2(1+e^{-4}-2e^{-2}) because y=(1,1,−1,−1)y=(1,1,-1,-1) is an eigenvector with eigenvalue 1+e−4−2e−21+e^{-4}-2e^{-2}. The maximiser is a∗=1/(1+e−4−2e−2)≈1.3375<C=10a^\ast=1/(1+e^{-4}-2e^{-2})\approx1.3375<C=10, so all four points are free support vectors lying exactly on the margin. The bias from the free support vector x0x_0 is b=1−a∗(1+e−4−2e−2)=0b=1-a^\ast(1+e^{-4}-2e^{-2})=0, and SMO reproduces these closed forms.

TypeScriptrunnable
import { eigvalsh, matrix } from '@/lib/quantum-simulator';
import { svmDecision, trainSvm } from '@/lib/qml';

// RBF kernel k(x, z) = exp(-gamma * ||x - z||^2) and its Gram matrix (rows as Float64Array for trainSvm).
const rbf = (x: number[], z: number[], gamma: number): number =>
  Math.exp(-gamma * x.reduce((s, xi, t) => s + (xi - z[t]) ** 2, 0));
const gram = (X: number[][], gamma: number): Float64Array[] =>
  X.map((x) => Float64Array.from(X, (z) => rbf(x, z, gamma)));

// XOR: label +1 when both coordinates have the same sign. No line separates these four points.
const X = [[-1, -1], [1, 1], [-1, 1], [1, -1]];
const y = [1, 1, -1, -1];
const gamma = 0.5;
const K = gram(X, gamma);
console.log('K (gamma = 0.5):');
for (const row of K) console.log(Array.from(row, (v) => v.toFixed(6)).join(' '));

// The Gram matrix of a kernel is symmetric positive semidefinite: all eigenvalues are >= 0.
const lam = Array.from(eigvalsh(matrix.fromRows(K.map((r) => Array.from(r))))).sort((a, b) => a - b);
console.log('eigenvalues: ' + lam.map((v) => v.toFixed(10)).join(' '));
const e2 = Math.exp(-2);
const e4 = Math.exp(-4);
console.log('closed form: ' + [1 + e4 - 2 * e2, 1 - e4, 1 - e4, 1 + e4 + 2 * e2].map((v) => v.toFixed(10)).join(' '));

// Soft-margin SVM: the dual QP is solved by SMO on the precomputed Gram matrix.
const model = trainSvm(K, y, { C: 10 });
console.log('alpha = ' + Array.from(model.alpha, (a) => a.toFixed(4)).join(' ') + ', closed form ' + (1 / (1 + e4 - 2 * e2)).toFixed(4));
console.log('support vectors: ' + model.supportIndices.join(' ') + ', |b| < 1e-9: ' + (Math.abs(model.b) < 1e-9));
for (const p of [[0.5, 0.5], [-0.5, 0.5], [0.9, -0.2], [-1.5, -1.2]]) {
  const f = svmDecision(model, X.map((x) => rbf(x, p, gamma)));
  console.log('f(' + p.join(', ') + ') = ' + f.toFixed(4) + ' -> ' + (f >= 0 ? '+1' : '-1'));
}

Expected output

K (gamma = 0.5):
1.000000 0.018316 0.135335 0.135335
0.018316 1.000000 0.135335 0.135335
0.135335 0.135335 1.000000 0.018316
0.135335 0.135335 0.018316 1.000000
eigenvalues: 0.7476450724 0.9816843611 0.9816843611 1.2889862054
closed form: 0.7476450724 0.9816843611 0.9816843611 1.2889862054
alpha = 1.3375 1.3375 1.3375 1.3375, closed form 1.3375
support vectors: 0 1 2 3, |b| < 1e-9: true
f(0.5, 0.5) = 0.4162 -> +1
f(-0.5, 0.5) = -0.4162 -> -1
f(0.9, -0.2) = -0.2659 -> -1
f(-1.5, -1.2) = 0.9997 -> +1

Quick check

Which of these symmetric matrices cannot be the Gram matrix of any kernel?

Select one answer

References

  1. C. Cortes and V. Vapnik, Support-vector networks, Machine Learning 20, 273–297 (1995).doi:10.1007/BF00994018
  2. B. Schölkopf and A. J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press (2002), chapters 1, 2 and 7.
  3. J. C. Platt, Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines, Microsoft Research Technical Report MSR-TR-98-14 (1998).microsoft.com
  4. S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press (2004), §5.1–§5.5 (Lagrange duality, Slater condition, KKT conditions).doi:10.1017/CBO9780511804441

Hands-on labs

  • The RBF Gram matrix

    1 step · auto-graded

    Implement the Gram matrix Kij=k(xi,xj)=e−γ∥xi−xj∥2K_{ij}=k(x_i,x_j)=e^{-\gamma\lVert x_i-x_j\rVert^2} of the Gaussian (RBF) kernel, the matrix that the SVM dual and every kernel method consume. The grader checks your values on a visible three-point example and on three hidden sets of 2020 random points in [−2,2]2[-2,2]^2 (γ=0.5,1,2\gamma=0.5,1,2), and verifies the two structural properties that every valid Gram matrix has: symmetry and positive semidefiniteness.

    Open lab