Inmachine learning, thepolynomial kernel is akernel function commonly used withsupport vector machines (SVMs) and otherkernelized models, that represents the similarity of vectors (training samples) in a feature space over polynomials of the original variables, allowing learning of non-linear models.

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 ofregression analysis, such combinations are known as interaction features. The (implicit) feature space of a polynomial kernel is equivalent to that ofpolynomial 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 tological conjunctions of input features.^[1]

For degree-d polynomials, the polynomial kernel is defined as^[2]

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

wherex andy are vectors of sizen in theinput space, i.e. vectors of features computed from training or test samples andc ≥ 0 is a free parameter trading off the influence of higher-order versus lower-order terms in the polynomial. Whenc = 0, the kernel is called homogeneous.^[3] (A further generalized polykernel dividesx^Ty by a user-specified scalar parametera.^[4])

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. Letd = 2, so we get the special case of the quadratic kernel. After using themultinomial theorem (twice—the outermost application is thebinomial 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 themultinomial theorem:

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}$

Although theRBF kernel is more popular in SVM classification than the polynomial kernel, the latter is quite popular innatural language processing (NLP).^[1][5]The most common degree isd = 2 (quadratic), since larger degrees tend tooverfit 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,^[5] i.e. full computation of the mappingφ as in polynomial regression;
• basket mining (using a variant of theapriori algorithm) for the most commonly occurring feature conjunctions in a training set to produce an approximate expansion;^[6]
• inverted indexing of support vectors.^[6][1]

One problem with the polynomial kernel is that it may suffer fromnumerical instability: whenx^Ty +c < 1,K(x,y) = (x^Ty +c)^d tends to zero with increasingd, whereas whenx^Ty +c > 1,K(x,y) tends to infinity.^[4]

^[7]

• Kernel methods for machine learning

• CS1 maint: archived copy as title
• Articles with short description
• Short description matches Wikidata