Polynomial kernel
Topic of Support vector machines, part of Statistical learning · Also in Support vector machines
Polynomial kernel
| Type | Topic |
| Taught in | Support vector machines · Support vector machines |
| Part | Statistical learning |
| Worked examples | 1 |
K(\mathbf{x}_i,\mathbf{x}_j)=(1+\mathbf{x}_i^\top\mathbf{x}_j)^d, the inner product of a feature map containing all monomials up to degree d, of dimension \binom{p+d}{d}. The quadratic kernel, d=2, separates XOR.
In Support vector machines
- 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.
Examples
The quadratic kernel
Worked example from Support vector machines
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.
Used in
See also
Kernel · XOR problem · Signed distance · Vapnik’s radius–margin bound · Hard-margin primal · Hard-margin dual · Soft-margin primal · Linear separators and the margin