Kernel support vector machine

Section of Support vector machines, part of Statistical learning

Type	Section
Taught in	Support vector machines
Part	Statistical learning

Replace each inner product by K(x_i,x_j). The feature space may be infinite-dimensional, but the dual still has n coefficients. The computational cost depends on evaluating kernels, the sample size, and the optimisation algorithm. Explicit feature coordinates have been avoided. Training cost has not been made independent of the kernel.

\begin{aligned} Q(\alpha)&=\sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_j y_i y_j K(x_i,x_j)\\ \text{subject to}\quad &\sum_i\alpha_i y_i=0,\qquad 0\le\alpha_i\le C. \end{aligned}

The hard-margin version uses \alpha_i\ge 0. Combining it with the soft-margin approach adds the bound C. The solution is

f(x)=\sum_i\alpha_i y_i K(x_i,x)+b, \qquad b=y_k-\sum_i\alpha_i y_i K(x_i,x_k)

for any k with 0<\alpha_k<C. The optimisation techniques for finding the \alpha_i remain the same.

Example 1 (XOR with the quadratic kernel) Question. Return to XOR with labels y=\pm 1 and points x_1=(-1,-1) (y=-1), x_2=(-1,1) (+1), x_3=(1,-1) (+1), x_4=(1,1) (-1). Use K(x,x')=(1+x^\top x')^2 and the hard-margin dual.

Solution. The Gram matrix has K_{ii}=(1+2)^2=9 on the diagonal and, for i\neq j, x_i^\top x_j\in\{0,-2\} so K_{ij}=1:

K_S=\begin{pmatrix} 9&1&1&1\\ 1&9&1&1\\ 1&1&9&1\\ 1&1&1&9 \end{pmatrix}.

By symmetry take all \alpha_i=\alpha. The constraint \sum_i\alpha_i y_i=0 holds because two labels are +1 and two are -1. Then

\sum_{i,j} y_i y_j K_{ij} =4\cdot 9+\sum_{i\neq j} y_i y_j =36+\Bigl(\bigl(\sum_i y_i\bigr)^2-4\Bigr) =36+(0-4)=32,

so Q=4\alpha-16\alpha^2, maximised at \alpha=\tfrac18. The decision function is f(x)=\tfrac18\sum_i y_i K(x_i,x)+b. Using the feature map above,

w=\frac18\bigl(-\phi(x_1)+\phi(x_2)+\phi(x_3)-\phi(x_4)\bigr) =\frac18\bigl(0,0,-4\sqrt{2},0,0,0\bigr)^\top =\bigl(0,0,-\tfrac{\sqrt{2}}{2},0,0,0\bigr)^\top,

because only the cross-product coordinate \sqrt{2}\,x_1 x_2 differs in sign between the classes: \sqrt{2}\,x_1 x_2=+\sqrt{2} for x_1,x_4 and -\sqrt{2} for x_2,x_3. Then

f(x)=-\frac{\sqrt{2}}{2}\cdot\sqrt{2}\,x_1 x_2+b=-x_1 x_2+b.

The support-vector condition y_1 f(x_1)=1 with x_1=(-1,-1) gives -(-1+b)=1, so b=0. Hence f(x)=-x_1 x_2, which classifies all four XOR points correctly with functional margin exactly 1. All four are support vectors. Since \lVert w\rVert=1/\sqrt{2}, the geometric distance to the separating hyperplane in feature space is \sqrt{2} and the full slab width is 2\sqrt{2}. The rule classifies a new point (0.5,-0.5) as +1 (f=0.25) and (2,2) as -1 (f=-4). The hand-built hidden layers on the neural-units page compute AND and OR. The kernel supplies, in the cross-product coordinate, exactly the feature that makes XOR linearly separable. The KKT equalities and the positive multipliers verify the solution directly. The zero contours of -x_1 x_2 are the coordinate axes.

Used in

Taught in Support vector machines
All 10 questions on Support vector machines

Used in

See also