Polynomial kernel

Intuitively, the polynomial kernel looks not only at the given features of input samples to determine their similarity, but also combinations of these. In the context of regression analysis, such combinations are known as interaction features. The (implicit) feature space of a polynomial kernel is equivalent to that of polynomial regression, but without the combinatorial blowup in the number of parameters to be learned. When the input features are binary-valued (booleans), then the features correspond to logical conjunctions of input features.

Definition

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

${\displaystyle K(\mathbf{x},\mathbf{y})=({\mathbf{x}}^{\mathsf{T}}\mathbf{y}+c{)}^d}$

where x and y are vectors of size n in the input space, i.e. vectors of features computed from training or test samples and c ≥ 0 is a free parameter trading off the influence of higher-order versus lower-order terms in the polynomial. When c = 0, the kernel is called homogeneous. (A further generalized polykernel divides x^Ty by a user-specified scalar parameter a.)

As a kernel, K corresponds to an inner product in a feature space based on some mapping φ:

${\displaystyle K(\mathbf{x},\mathbf{y})=⟨\phi (\mathbf{x}),\phi (\mathbf{y})⟩}$

The nature of φ can be seen from an example. Let d = 2, so we get the special case of the quadratic kernel. After using the multinomial theorem (twice—the outermost application is the binomial theorem) and regrouping,

${\displaystyle K(\mathbf{x},\mathbf{y})={\left(\sum _{i=1}^n{x}_i{y}_i+c\right)}^2=\sum _{i=1}^n\left(x_i^2\right)\left(y_i^2\right)+\sum _{i=2}^n\sum _{j=1}^{i-1}\left(\sqrt{2}{x}_i{x}_j\right)\left(\sqrt{2}{y}_i{y}_j\right)+\sum _{i=1}^n\left(\sqrt{2c}{x}_i\right)\left(\sqrt{2c}{y}_i\right)+c^2}$

From this it follows that the feature map is given by:

${\displaystyle \phi (x)=\left(x_n^2,\dots ,x_1^2,\sqrt{2}{x}_n{x}_{n-1},\dots ,\sqrt{2}{x}_n{x}_1,\sqrt{2}{x}_{n-1}{x}_{n-2},\dots ,\sqrt{2}{x}_{n-1}{x}_1,\dots ,\sqrt{2}{x}_2{x}_1,\sqrt{2c}{x}_n,\dots ,\sqrt{2c}{x}_1,c\right)}$

generalizing for ${\displaystyle {\left({\mathbf{x}}^T\mathbf{y}+c\right)}^d}$, where ${\displaystyle \mathbf{x}\in {\mathbb{R}}^n}$, ${\displaystyle \mathbf{y}\in {\mathbb{R}}^n}$ and applying the multinomial theorem:

${\displaystyle \begin{array}{rl}{\left({\mathbf{x}}^T\mathbf{y}+c\right)}^d& =\sum _{j_1+j_2+\cdots +j_{n+1}=d}\frac{\sqrt{d!}}{\sqrt{j_1!\cdots j_n!j_{n+1}!}}{x}_1^{j_1}\cdots x_n^{j_n}{\sqrt{c}}^{j_{n+1}}\frac{\sqrt{d!}}{\sqrt{j_1!\cdots j_n!j_{n+1}!}}{y}_1^{j_1}\cdots y_n^{j_n}{\sqrt{c}}^{j_{n+1}}\\ & =\phi (\mathbf{x}{)}^T\phi (\mathbf{y})\end{array}}$

The last summation has ${\displaystyle l_d=(\genfrac{}{}{0ex}{}{n+d}{d})}$ elements, so that:

${\displaystyle \phi (\mathbf{x})=\left(a_1,\dots ,a_l,\dots ,a_{l_d}\right)}$

where ${\displaystyle l=(j_1,j_2,...,j_n,j_{n+1})}$ and

${\displaystyle a_l=\frac{\sqrt{d!}}{\sqrt{j_1!\cdots j_n!j_{n+1}!}}{x}_1^{j_1}\cdots x_n^{j_n}{\sqrt{c}}^{j_{n+1}}|j_1+j_2+\cdots +j_n+j_{n+1}=d}$