Kernel trick
Section of Support vector machines, part of Statistical learning
Kernel trick
| Type | Section |
| Taught in | Support vector machines |
| Part | Statistical learning |
A margin in the original coordinates cannot separate XOR, and it cannot separate a one-dimensional sample whose middle values belong to one class and whose two tails belong to the other. A map into a higher-dimensional feature space can turn either problem into a linear one. In one dimension, mapping x\mapsto(x,x^2) separates the sandwiched classes with a line: the middle class sits at small x^2 and the two tails sit at large x^2. For a finite training set in which no two identical inputs carry opposite labels, some feature map makes the training set linearly separable. The general construction is a map \phi:x\mapsto\phi(x).
Both the dual and the classifier involve the data only through inner products. If every observation is mapped by \phi, the inner product becomes \phi(x_i)^\top\phi(x_j), and any function K that equals such an inner product can be written down without writing \phi.
Definition 1 (Kernel) A kernel is a function equivalent to an inner product in some feature space,
K(x_i,x_j)=\phi(x_i)^\top\phi(x_j).
The kernel trick replaces inner products in the feature space by K evaluated on the original points. The feature map is never computed.
Example 1 (The quadratic kernel) Question. For two-dimensional vectors x=(x_1,x_2)^\top, expand K(x_i,x_j)=(1+x_i^\top x_j)^2 as an inner product, and check it on x=(1,2) and x'=(3,1).
Solution. Expanding,
\begin{aligned} K(x_i,x_j) &=1+x_{i1}^2 x_{j1}^2+2 x_{i1}x_{j1}x_{i2}x_{j2}+x_{i2}^2 x_{j2}^2+2x_{i1}x_{j1}+2x_{i2}x_{j2}\\ &=\phi(x_i)^\top\phi(x_j), \end{aligned}
where
\phi(x)=\bigl(1,\, x_1^2,\, \sqrt{2}\,x_1 x_2,\, x_2^2,\, \sqrt{2}\,x_1,\, \sqrt{2}\,x_2\bigr)^\top.
Numerically, K=(1+3+2)^2=36, and
\phi(x)=(1,1,2.83,4,1.41,2.83),\qquad \phi(x')=(1,9,4.24,1,4.24,1.41)
have inner product 1+9+12+4+6+4=36.
Which functions are kernels?
Main article: Which functions are kernels?
A proposed similarity is not automatically an inner product. The necessary and sufficient condition is symmetry and positive semidefiniteness of every finite Gram matrix. This yields a representation in a Hilbert feature space. Mercer’s spectral theorem adds regularity and domain assumptions. The finite-Gram criterion is the condition needed for the convex dual:
\sum_{i=1}^{n}\sum_{j=1}^{n} c_i c_j K(x_i,x_j)\ge 0
for every finite choice of input points and every real vector c. Equivalently, the Gram matrix K_S=(K(x_i,x_j))_{ij} must be positive semidefinite. Checking one training Gram matrix checks that particular optimisation problem, not validity of the function on every possible data set.
If K_1 and K_2 are kernels in this sense, so are \alpha K_1+\beta K_2 for \alpha,\beta\ge 0, the product K_1 K_2, and the powers K^d for d\in\mathbb{N}. The product statement is the Schur product theorem for entrywise products of positive semi-definite matrices. These closure properties let new kernels be built from old ones.
Common kernels
Main article: Common kernels
- Linear. K(x_i,x_j)=x_i^\top x_j, with \phi(x)=x itself.
- Polynomial of power d. K(x_i,x_j)=(1+x_i^\top x_j)^d, with \phi(x) of dimension \binom{p+d}{d}. For p=2 and d=2 that dimension is \binom{4}{2}=6, as in the expansion above. The higher-dimensional space still has intrinsic dimension p, because the map is not onto. Linear separators in it correspond to nonlinear separators in the original space.
- Gaussian, or radial basis function. K(x_i,x_j)=\exp\bigl(-\lVert x_i-x_j\rVert^2/(2\sigma^2)\bigr), with \phi(x) infinite-dimensional. Every point is mapped to a function, a Gaussian, and a combination of such functions for the support vectors is the separator. The Taylor expansion shows the infinite dimension:
\begin{aligned} e^{-\lVert x-x'\rVert^2/(2\sigma^2)} &=e^{-\lVert x\rVert^2/(2\sigma^2)}\,e^{-\lVert x'\rVert^2/(2\sigma^2)}\,e^{x^\top x'/\sigma^2}\\ &=e^{-\lVert x\rVert^2/(2\sigma^2)}\,e^{-\lVert x'\rVert^2/(2\sigma^2)} \sum_{n=0}^{\infty}\frac{(x^\top x')^n}{\sigma^{2n}\,n!}. \end{aligned}
This is a positive combination of the polynomial kernels (x^\top x')^n of every degree n, times a(x)a(x'), where a(x)=\exp\bigl[-\lVert x\rVert^2/(2\sigma^2)\bigr]. The paired product is a rank-one kernel. Either one-variable factor by itself is not a two-input kernel.
The nonlinear programme
Main article: Kernel support vector machine
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 2 (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
See also
Kernel · Signed distance · Vapnik’s radius–margin bound · Hard-margin primal · Hard-margin dual · Soft-margin primal · Linear separators and the margin · Distance to a hyperplane