1 Definition and Mathematical Formulation
1.1 Basic Formula
The polynomial kernel is a function that computes the similarity between two input vectors \(\mathbf{x}\) and \(\mathbf{y}\) in a feature space induced by a polynomial mapping. Its basic formula is:
\[ K(\mathbf{x}, \mathbf{y}) = (\gamma \, \mathbf{x}^\top \mathbf{y} + c)^d, \]
where \(\mathbf{x}^\top \mathbf{y}\) denotes the dot product, \(\gamma\) is a scaling parameter, \(c\) is a constant term, and \(d\) is a positive integer representing the degree of the polynomial.
1.2 Parameters
1.2.1 Degree (d)
The degree \(d\) controls the complexity of the decision boundary. Higher degrees allow the model to capture more intricate nonlinear relationships, but also increase the risk of overfitting. Common choices are \(d = 2\) (quadratic) and \(d = 3\) (cubic). The degree must be a positive integer; non-integer values are not typically used because they would break the polynomial expansion property.
1.2.2 Coefficient (c)
The constant term \(c\) (often called the "coefficient" or "bias") determines the influence of lower-order terms in the implicit feature space. When \(c > 0\), the kernel is *inhomogeneous*, meaning that the feature space includes monomials of all degrees from 0 up to \(d\). When \(c = 0\), the kernel is *homogeneous* and includes only monomials of exactly degree \(d\). A typical default is \(c = 1\).
1.2.3 Gamma (γ)
The scaling parameter \(\gamma\) adjusts the magnitude of the dot product before exponentiation. It is often set to \(1\) in many implementations, but can be tuned to normalize the influence of input features. In practice, \(\gamma\) is sometimes absorbed into the constant \(c\) or set to \(1/n\) where \(n\) is the dimensionality of the input, to prevent large numerical values.
1.3 Special Cases
1.3.1 Linear Kernel (d = 1)
When \(d = 1\), the polynomial kernel reduces to the linear kernel:
\[ K(\mathbf{x}, \mathbf{y}) = \gamma \, \mathbf{x}^\top \mathbf{y} + c. \]
This corresponds to the standard dot product (plus a constant), and the resulting model is a linear classifier or regressor. It can be seen as a special case where no nonlinear transformation is applied.
1.3.2 Quadratic Kernel (d = 2)
With \(d = 2\), the kernel becomes:
\[ K(\mathbf{x}, \mathbf{y}) = (\gamma \, \mathbf{x}^\top \mathbf{y} + c)^2. \]
Expanding this reveals that the implicit feature space includes all monomials of degree 1 and 2, such as \(x_i\), \(x_i x_j\), and a constant term (if \(c > 0\)). The quadratic kernel is one of the most commonly used for moderate nonlinearity.
2 Feature Space Interpretation
2.1 Polynomial Expansion
A key property of the polynomial kernel is that it corresponds to taking a dot product in a high-dimensional feature space constructed from monomials of the input features. Specifically, for an input vector \(\mathbf{x} = (x_1, x_2, \dots, x_n)\), the kernel implicitly maps \(\mathbf{x}\) to a vector \(\phi(\mathbf{x})\) containing all monomials of degree up to \(d\).
2.1.1 Homogeneous Polynomial Kernel (c = 0)
When \(c = 0\), the kernel is \(K(\mathbf{x}, \mathbf{y}) = (\gamma \, \mathbf{x}^\top \mathbf{y})^d\). The implicit feature map \(\phi\) contains only monomials of exact degree \(d\). For example, with \(d = 2\) and \(n = 2\), the mapping is \(\phi(x_1, x_2) = (\sqrt{\gamma} \, x_1^2, \sqrt{2\gamma} \, x_1 x_2, \sqrt{\gamma} \, x_2^2)\) (up to scaling).
2.1.2 Inhomogeneous Polynomial Kernel (c > 0)
With \(c > 0\), the expansion of \((\gamma \, \mathbf{x}^\top \mathbf{y} + c)^d\) via the binomial theorem yields terms of all degrees from 0 to \(d\). This includes a constant term (degree 0), linear terms, quadratic terms, and so on. The corresponding feature space is richer, incorporating both low-order and high-order interactions.
2.2 Dimensionality of Implicit Feature Space
2.2.1 Number of Monomials
For an \(n\)-dimensional input space and a polynomial kernel of degree \(d\) (inhomogeneous), the number of monomials (i.e., the dimension of the feature space) is given by:
\[ \binom{n + d}{d}. \]
This grows combinatorially with \(n\) and \(d\). For example, with \(n = 100\) and \(d = 3\), the dimension exceeds 176,000. The homogeneous case (\(c = 0\)) yields \(\binom{n + d - 1}{d}\) monomials.
2.2.2 Computational Advantages of Kernel Trick
Despite the potentially enormous feature space, the polynomial kernel avoids explicitly constructing the high-dimensional mapping. The "kernel trick" allows the algorithm to compute \(K(\mathbf{x}, \mathbf{y})\) directly using the original inputs, with complexity \(O(n)\) per evaluation. This makes it feasible to work with feature spaces that would be impossible to represent explicitly.
3 Properties
3.1 Mercer’s Condition and Positive Definiteness
The polynomial kernel satisfies Mercer’s condition, meaning that for any set of inputs, the Gram matrix \(K_{ij} = K(\mathbf{x}_i, \mathbf{x}_j)\) is positive semidefinite provided that \(\gamma \ge 0\), \(c \ge 0\), and \(d\) is a positive integer. This guarantees the existence of a valid reproducing kernel Hilbert space (RKHS) and ensures convexity in SVMs.
3.2 Reproducing Kernel Hilbert Space (RKHS)
The polynomial kernel defines an RKHS that contains all polynomial functions of degree up to \(d\) (with an appropriate norm). The reproducing property \(\langle K(\mathbf{x}, \cdot), f \rangle = f(\mathbf{x})\) holds for any function \(f\) in the space. The RKHS norm penalizes high-degree monomial coefficients more heavily, depending on the parameters.
3.3 Invariance and Scaling Sensitivity
Unlike translation-invariant kernels (e.g., the RBF kernel), the polynomial kernel is not invariant to translations of the input. Its value depends on the dot product, which is sensitive to the magnitude and scaling of the input vectors. Therefore, standardizing the data (zero mean, unit variance) is strongly recommended before using the polynomial kernel.
4 Applications
4.1 Support Vector Machines
4.1.1 Non-linear Classification
The polynomial kernel is widely used in SVMs for non-linear classification. By projecting data into a higher-dimensional monomial space, it enables the SVM to learn decision boundaries that are polynomial functions of the input, such as ellipses or hyperbolas in two dimensions. It is especially effective when the data exhibits polynomial relationships.
4.1.2 Regression (SVR)
In support vector regression (SVR), the polynomial kernel allows modeling non-linear target functions. It can capture curvature in the regression surface, with the degree \(d\) controlling the flexibility. However, caution is needed to avoid overfitting, as polynomial kernels can produce wiggly fits outside the training data range.
4.2 Kernel Principal Component Analysis (KPCA)
In KPCA, the polynomial kernel is used to find nonlinear principal components. The kernel matrix is computed on the data, and eigendecomposition yields components that correspond to polynomial features. This can reveal structure that standard PCA misses, such as clusters with polynomial boundaries.
4.3 Kernel Ridge Regression
Kernel ridge regression (KRR) with a polynomial kernel yields a solution that is a linear combination of polynomial basis functions. The regularization parameter balances fit and smoothness. The polynomial kernel is a natural choice when the underlying function is believed to be a polynomial.
4.4 Other Kernel Methods
The polynomial kernel also appears in kernelized versions of Fisher discriminant analysis, kernel k-means, and Gaussian processes. In Gaussian processes, it can be used as a covariance function with polynomial trends, though its non-stationarity limits its use in some spatial applications.
5 Comparison with Other Kernels
5.1 Radial Basis Function (RBF) Kernel
| The RBF kernel (or Gaussian kernel) \(K(\mathbf{x}, \mathbf{y}) = \exp(-\gamma \|\mathbf{x} - \mathbf{y}\|^2)\) is translation-invariant and infinitely differentiable, generating a smooth, local behavior. In contrast, the polynomial kernel is non-local (influences can be global) and has finite degrees of freedom (bounded by the degree). The RBF kernel often generalizes better to arbitrary non-linearities due to its infinite-dimensional feature space, while the polynomial kernel is more interpretable in terms of monomial interactions. |
|---|
5.2 Sigmoid Kernel
The sigmoid kernel \(K(\mathbf{x}, \mathbf{y}) = \tanh(\gamma \mathbf{x}^\top \mathbf{y} + c)\) is not positive semidefinite for all parameter choices, which can cause non-convex optimization in SVMs. The polynomial kernel, being always positive definite for valid parameters, is more reliable. Both kernels share a dependence on the dot product, but the sigmoid kernel saturates, while the polynomial kernel grows polynomially with the dot product.
5.3 String and Graph Kernels
String and graph kernels are specialized for structured data (e.g., sequences, trees, graphs). The polynomial kernel, by contrast, operates on fixed-length vector inputs. However, the idea of polynomial expansion can be adapted to these domains by counting occurrences of substructures – for instance, the substring kernel is analogous to a polynomial kernel on bag-of-words features.
6 Practical Considerations
6.1 Choosing the Degree d
6.1.1 Underfitting and Overfitting
A low degree (e.g., \(d = 1\)) may underfit complex data, while a high degree (e.g., \(d > 5\)) often leads to overfitting, especially with limited training samples. The polynomial kernel tends to extrapolate aggressively outside the data range, which can be harmful. As a rule of thumb, degrees 2 or 3 are most common in practice.
6.1.2 Cross-Validation Strategies
Selecting \(d\) is best done via cross-validation. Exhaustive grid search over \(d = 1, 2, \dots, D\) is feasible for small \(D\). Additionally, nested cross-validation should be used to avoid biased performance estimates, especially when tuning \(\gamma\) and \(c\) simultaneously.
6.2 Numerical Stability
6.2.1 Scaling of Input Data
Because the polynomial kernel involves exponentiation of the dot product, large input values can cause numerical overflow. Standardizing the data (e.g., scaling to unit variance and zero mean) mitigates this. Alternatively, scaling features to a range like \([-1, 1]\) is common.
6.2.2 Avoiding Overflow
For high degrees, the term \((\gamma \, \mathbf{x}^\top \mathbf{y} + c)^d\) can become extremely large or, if the dot product is negative, oscillatory. Normalizing the kernel (e.g., using \(K'(\mathbf{x}, \mathbf{y}) = K(\mathbf{x}, \mathbf{y}) / \sqrt{K(\mathbf{x}, \mathbf{x}) K(\mathbf{y}, \mathbf{y})}\)) can improve stability by ensuring values stay in a bounded range.
6.3 Optimizing γ and c
The parameters \(\gamma\) and \(c\) affect the scale and bias of the kernel. Typically, \(\gamma\) is set to \(1\) or \(1/n\), and \(c\) is set to \(1\). However, tuning them together with \(d\) via grid search or Bayesian optimization may improve performance. Cross-validation is recommended, but the search space should be limited to avoid overfitting on the validation set.
7 Extensions and Variants
7.1 Polynomial Kernel with Multiple Degrees
Instead of a single degree, one can define a kernel that sums polynomial kernels of different degrees: \(K(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^{m} \alpha_i (\gamma \mathbf{x}^\top \mathbf{y} + c)^{d_i}\), where \(\alpha_i\) are nonnegative weights. This creates a richer feature space without explicitly expanding in multiple degrees, but may introduce additional hyperparameters.
7.2 Weighted Polynomial Kernel
Different monomials can be given different weights. For instance, the kernel \(K(\mathbf{x}, \mathbf{y}) = ( \gamma \mathbf{x}^\top \mathbf{y} + c)^d\) implicitly weights all monomials of the same degree equally. A weighted variant would multiply each monomial by a coefficient, which can be achieved by using a diagonal matrix in the feature space. This is rarely used in practice due to increased complexity.
7.3 All-Subset Kernel
The all-subset kernel \(K(\mathbf{x}, \mathbf{y}) = \prod_{i=1}^{n} (1 + x_i y_i)\) is equivalent to a polynomial kernel with \(\gamma = 1\), \(c = 1\), and \(d = n\) (where \(n\) is the dimensionality). It includes all subsets of features (i.e., all monomials without repetition). This kernel is an important special case that illustrates the combinatorial richness of polynomial expansions.