Polynomial kernel

Illustration of the mapping $\varphi$. On the left a set of samples in the input space, on the right the same samples in the feature space where the polynomial kernel $K(x,y)$ (for some values of the parameters $c$ and $d$ is the inner product. The hyperplane learned in feature space by an SVM is an ellipse in the input space.

In machine learning, the polynomial kernel is a kernel function commonly used with support vector machines (SVMs) and other kernelized models, that represents the similarity of vectors (training samples) in a feature space over polynomials of the original variables.

Definition

For degree-d polynomials, the polynomial kernel is defined as

$K(x,y)=(x^{\top }y+c)^{d}$

where $x$ and $y$ are vectors in the input space, i.e. vectors of features computed from training or test samples, $c\geq 0$ is a constant trading off the influence of higher-order versus lower-order terms in the polynomial. (A further generalized polykernel divides $x^{\top }y$ by a user-specified scalar parameter $a$.) For the case $d=2$ of the quadratic kernel, we have:

$K(x,y)=\left(\sum _{i=1}^{n}x_{i}y_{i}+c\right)^{2}=\sum _{i=1}^{n}x_{i}^{2}y_{i}^{2}+\sum _{i=2}^{n}\sum _{j=1}^{i-1}{\sqrt {2}}x_{i}y_{i}{\sqrt {2}}x_{j}y_{j}+\sum _{i=1}^{n}{\sqrt {2c}}x_{i}{\sqrt {2c}}y_{i}+c^{2}$

From this we see that $K$ is the inner product in a feature space induced by the mapping

$\varphi (x)=\langle x_{n}^{2},\ldots ,x_{1}^{2},{\sqrt {2}}x_{n}x_{n-1},\ldots ,{\sqrt {2}}x_{n}x_{1},{\sqrt {2}}x_{n-1}x_{n-2},\ldots ,{\sqrt {2}}x_{n-1}x_{1},\ldots ,{\sqrt {2}}x_{2}x_{1},{\sqrt {2c}}x_{n},\ldots ,{\sqrt {2c}}x_{1},c\rangle$

When the input features are binary-valued (booleans) and $c=1$, the mapped features correspond to conjunctions of input features. (The ${\sqrt {2}}$ terms in the expansion are immaterial.)

Practical use

Although the RBF kernel is more popular in SVM classification than the polynomial kernel, the latter is quite popular in natural language processing (NLP). The most common degree is d=2, since larger degrees tend to overfit on NLP problems.

Various ways of computing the polynomial kernel (both exact and approximate) have been devised as alternatives to the usual non-linear SVM training algorithms, including:

• full expansion of the kernel prior to training/testing with a linear SVM, i.e. full computation of the mapping $\varphi$
• basket mining (using a variant of the apriori algorithm) for the most commonly occurring feature conjunctions in a training set to produce an approximate expansion
• inverted indexing of support vectors

One problem with the polynomial kernel is that may it suffer from numerical instability: when $x^{\top }y+c<1$, $K(x,y)=(x^{\top }y+c)^{d}$ tends to zero as $d$ is increased, whereas when $x^{\top }y+c>1$, $K(x,y)$ tends to infinity.