{ "id": "ep9q7txv99", "slug": "polynomial-kernel", "title": "Polynomial kernel", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.ml_computation" }, { "id": "technology.computing.ai.ml_methods", "label": "Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.ml_methods" }, { "id": "technology.computing.ai.supervised_unsupervised", "label": "Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.supervised_unsupervised" }, { "id": "technology.computing.ai.supervised_unsupervised.kernel_methods_svms", "label": "Kernel methods and support vector machines", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.supervised_unsupervised.kernel_methods_svms" } ], "geo": [ { "id": "geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised", "label": "Non-geographic · 1946 to 2000: Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" }, { "id": "geo.nongeo.t1946.technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.ml_computation" }, { "id": "geo.nongeo.t1946.technology.computing.ai.ml_methods", "label": "Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.ml_methods" }, { "id": "geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised", "label": "Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised" } ] } ], "excerpt": "The polynomial kernel is a kernel function in machine learning that computes a scaled, shifted inner product raised to a degree, letting support vector machines learn nonlinear boundaries.", "snippet": "The polynomial kernel is a kernel function in machine learning that computes a scaled, shifted inner product raised to a degree, letting support vector machines learn nonlinear boundaries.", "node": "technology.computing.ai.supervised_unsupervised.kernel_methods_svms", "markdown": "# Polynomial kernel\n\nThe polynomial kernel is a kernel function used in machine learning that computes \\( (\\gamma \\langle x, y \\rangle + c)^{d} \\), the inner product of two vectors scaled by \\( \\gamma \\), shifted by a constant \\( c \\), and raised to a degree \\( d \\). Inside support vector machines and other kernelized algorithms it plays the role of an inner product in a much larger feature space, so a nonlinear, polynomial decision boundary is learned while the algorithm only works with \\( d \\)-dimensional inner products.[1](https://www.csie.ntu.edu.tw/~cjlin/papers/lowpoly_journal.pdf)\n\n| Key fact | Detail |\n|---|---|\n| Formula | \\( K(x, y) = (\\gamma \\langle x, y \\rangle + c)^{d} \\); the inhomogeneous form uses \\( c = 1 \\), the homogeneous form drops the constant[1](https://www.csie.ntu.edu.tw/~cjlin/papers/lowpoly_journal.pdf) • [2](https://people.eecs.berkeley.edu/~jrs/189s24/lec/16.pdf) |\n| Implicit feature space | All monomials of degree 0 through \\( d \\); dimension \\( \\binom{n+d}{d} \\) for \\( n \\)-dimensional inputs[3](https://people.eecs.berkeley.edu/~jordan/kernels/0521813972c09_p291-326.pdf) |\n| Exact-degree space | Monomials of exactly degree \\( d \\) span a space of dimension \\( \\binom{n+d-1}{d} \\)[4](https://ar5iv.labs.arxiv.org/html/1402.0099) |\n| Evaluation cost | One \\( n \\)-dimensional inner product plus exponentiation, \\( O(n) \\), versus a combinatorial number of operations for an explicit dot product in feature space[5](https://www.di.ens.fr/%7Emallat/papiers/svmtutorial.pdf) • [6](https://davidrosenberg.github.io/mlcourse/Archive/2017/Labs/5-Kernels-Slides.pdf) |\n| Practical settings | Low-degree mappings use \\( d = 2 \\) or \\( 3 \\) with \\( r \\) fixed to 1, leaving the same number of tuned parameters as the RBF kernel[1](https://www.csie.ntu.edu.tw/~cjlin/papers/lowpoly_journal.pdf) |\n| Main approximation | Tensor Sketch approximates the feature map in \\( O(n(d + D \\log D)) \\) time for \\( D \\)-dimensional embeddings[7](https://arxiv.org/html/2505.08146v1) |\n\n## How it works\n\nRaising an inner product to a power is equivalent to taking an inner product in a space of monomial features. For the common form \\( k(x, z) = (x^{\\top} z + 1)^{p} \\), a theorem states that this equals \\( \\varphi(x)^{\\top} \\cdot \\varphi(z) \\) for a feature map \\( \\varphi \\) containing every monomial in \\( x \\) of degree 0 through \\( p \\).[2](https://people.eecs.berkeley.edu/~jrs/189s24/lec/16.pdf) The binomial expansion shows why: \\( (\\langle x, z \\rangle + R)^{d} \\) expands into a reweighting of the monomial kernels \\( \\langle x, z \\rangle^{s} \\) for \\( s = 0, \\ldots, d \\), so the kernel's features are all products of up to \\( d \\) input coordinates.[3](https://people.eecs.berkeley.edu/~jordan/kernels/0521813972c09_p291-326.pdf) A degree-2 example makes the counting concrete: \\( \\varphi(x)^{\\top} \\varphi(x') = 1 + x^{\\top}x' + (x^{\\top}x')^{2} \\), an inner product in dimension \\( D = (d+1)^{2} \\), computed instead with \\( d \\)-dimensional inner products; this is the kernel trick.[8](https://machine-learning-upenn.github.io/assets/notes/Lec9.pdf)\n\nThe dimension of the implicit space follows from this counting. For the inhomogeneous kernel \\( \\kappa_{d}(x, z) = (\\langle x, z \\rangle + R)^{d} \\) on an \\( n \\)-dimensional input space, the feature space has dimension \\( \\binom{n+d}{d} \\).[3](https://people.eecs.berkeley.edu/~jordan/kernels/0521813972c09_p291-326.pdf) For the homogeneous kernel \\( K(x_1, x_2) = (x_1 \\cdot x_2)^{p} \\), the minimal embedding space has dimension \\( \\binom{d_L + p - 1}{p} \\), and the space of polynomials of exactly degree \\( d \\) has dimension \\( \\binom{n+d-1}{d} \\).[5](https://www.di.ens.fr/%7Emallat/papiers/svmtutorial.pdf) • [4](https://ar5iv.labs.arxiv.org/html/1402.0099) The computational advantage is the point of the construction: a dot product in the embedded space would require on the order of \\( \\binom{d_L + p - 1}{p} \\) operations, while computing \\( K(x_i, x_j) = (x_i \\cdot x_j)^{p} \\) requires only \\( O(d_L) \\).[5](https://www.di.ens.fr/%7Emallat/papiers/svmtutorial.pdf)\n\n## How it is done\n\nIn practice the kernel is used through its three parameters \\( d \\), \\( \\gamma \\), and \\( r \\). Guidance from a study of low-degree polynomial mappings is to use \\( d = 2 \\) or \\( 3 \\) and fix \\( r = 1 \\), which leaves the same number of parameters to tune as the Gaussian RBF kernel.[1](https://www.csie.ntu.edu.tw/~cjlin/papers/lowpoly_journal.pdf) For \\( d = 2 \\) and \\( r = 1 \\) the explicit feature map contains the constant term, scaled linear terms \\( \\sqrt{2\\gamma}\\,x_i \\), squares \\( \\gamma \\cdot x_i^{2} \\), and cross terms \\( \\sqrt{2\\gamma}\\,x_i \\cdot x_j \\), with dimensionality \\( \\binom{n+d}{d} \\).[1](https://www.csie.ntu.edu.tw/~cjlin/papers/lowpoly_journal.pdf)\n\nTwo evaluation routes exist. For natural-number degrees the kernel admits both an explicit feature map and the implicit kernel formula; the Kerch library notes that a kernel matrix over \\( n \\) points is typically cheaper to compute through the explicit map when the feature dimension is smaller than \\( n \\), and through the kernel formula otherwise, while non-natural degrees allow only the implicit form.[9](https://kerch.readthedocs.io/en/stable/kernel/generic/polynomial.html) Software implementations include scikit-learn, which ships both the kernel and a Tensor Sketch approximation of its feature map.[10](https://scikit-learn.org/dev/auto_examples/kernel_approximation/plot_scalable_poly_kernels.html)\n\n## Origin\n\nThe polynomial kernel sits in a 1992 lineage of Vapnik-era work on large-margin classifiers. A 1992 paper by Bernhard E. Boser and colleagues, *A Training Algorithm for Optimal Margin Classifiers*, presented a training algorithm that maximizes the margin between training patterns and the decision boundary and is applicable to a wide variety of classification functions, including perceptrons, polynomials, and radial basis functions, with the solution expressed as a linear combination of supporting patterns. In the same year, Isabelle Guyon, Bernhard E. Boser, and [Vladimir Vapnik](https://www.edgepedia.org/vladimir-vapnik) described second-order polynomial classifiers whose decision surface is a weighted sum including pairwise interaction terms \\( W_{ij} X_i \\cdot X_j \\), an explicit polynomial feature-expansion formulation. Related later work includes the ANOVA kernel's treatment in *Kernel Methods for Pattern Analysis* by John Shawe-Taylor and Nello Cristianini (2004, [Cambridge University Press](https://www.edgepedia.org/cambridge-university-press)),[3](https://people.eecs.berkeley.edu/~jordan/kernels/0521813972c09_p291-326.pdf) polynomial networks in a 2013 paper by Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir on arXiv,[11](https://doi.org/10.48550/arxiv.1304.7045) and factorization machines in Steffen Rendle's 2012 libFM paper in ACM Transactions on [Intelligent Systems](https://www.edgepedia.org/intelligent-systems) and Technology.[12](https://doi.org/10.1145/2168752.2168771)\n\n## Variants\n\n**Homogeneous and inhomogeneous forms.** Appending \\( \\sqrt{\\nu} \\) to the input vectors reduces the inhomogeneous case \\( \\nu > 0 \\) to the homogeneous one: with \\( \\tilde{x} = [x^{\\top}, \\sqrt{\\nu}]^{\\top} \\), \\( (x^{\\top} \\cdot y + \\nu)^{p} = (\\tilde{x}^{\\top} \\cdot \\tilde{y})^{p} \\).[13](https://jmlr.org/papers/volume25/22-0118/22-0118.pdf)\n\n**ANOVA kernel.** The ANOVA (ANalysis Of VAriance) kernel of degree \\( d \\) is like the all-subsets kernel restricted to subsets of cardinality \\( d \\).[14](http://www.cs.cmu.edu/%7Eninamf/ML11/lect1020.pdf) It differs from the polynomial kernel by the exclusion of repeated coordinates: the polynomial kernel uses all monomials of degree \\( m \\) with replacement, while the ANOVA kernel uses only monomials composed of distinct features, giving an embedding dimension of \\( \\binom{n}{d} \\).[3](https://people.eecs.berkeley.edu/~jordan/kernels/0521813972c09_p291-326.pdf) • [15](http://proceedings.mlr.press/v48/blondel16.pdf)\n\n## Applications\n\nDocumented applications center on text and vision tasks with low-degree kernels. In a dependency-parsing NLP application, LIBSVM with the polynomial kernel gave better accuracy than RBF (unlabeled attachment score 91.67 versus 89.92, labeled 90.60 versus 88.55 with \\( C = 0.5 \\)).[1](https://www.csie.ntu.edu.tw/~cjlin/papers/lowpoly_journal.pdf) In face detection, a simplified SVM exploiting a closed-form solution for second-degree polynomial kernels gained an acceleration factor of 20 without degrading classification quality.[16](https://bitsavers.org/pdf/mit/ai/aim/AIM-1602.pdf)\n\nAgainst the RBF kernel, experiments across datasets found that degree-2 polynomial mappings could compete with RBF in testing accuracy on nearly all problems, except covtype where performance was only similar to linear; theoretical limits connect the two, since as \\( \\sigma^2 \\to \\infty \\) the RBF SVM approaches an SVM with a degree-\\( d \\) polynomial mapping of the data.[1](https://www.csie.ntu.edu.tw/~cjlin/papers/lowpoly_journal.pdf) LIBLINEAR with degree-2 polynomial mappings trains faster than LIBSVM with RBF.[1](https://www.csie.ntu.edu.tw/~cjlin/papers/lowpoly_journal.pdf) Work since 2023 extends the kernel into new settings: PolySketchFormer (2024) uses polynomial-kernel sketching inside transformers, achieving a 2x training speedup over [FlashAttention](https://www.edgepedia.org/flashattention) for 32k context lengths in GPT-2 style models on Google Cloud TPUs, tested on PG19, Wikipedia, and C4.[17](https://proceedings.mlr.press/v235/kacham24a.html)\n\n## Limitations and alternatives\n\n**Scaling costs.** Kernelized models avoid the \\( O(d^{m}) \\) parameter growth of an explicit monomial expansion, but model storage and evaluation become proportional to the number of training instances, a situation called the curse of kernelization.[15](http://proceedings.mlr.press/v48/blondel16.pdf) Training requires the \\( t \\times t \\) [Gram matrix](https://www.edgepedia.org/gram-matrix) of kernel values, which can be infeasible for massive datasets, and the number of support vectors grows with dataset size, slowing prediction; per test point, kernel prediction costs \\( O(\\#\\mathrm{SV} \\cdot \\bar{n}) \\) versus \\( O(\\hat{n}) \\) for an explicit linear-mapping weight vector.[1](https://www.csie.ntu.edu.tw/~cjlin/papers/lowpoly_journal.pdf) • [18](https://towardsdatascience.com/explicit-feature-maps-for-non-linear-kernel-functions-171a9043da38/) A limitation of the polynomial kernel itself is that it can only use all monomials of degree \\( d \\) or up to \\( d \\), with a weighting scheme depending on the single parameter \\( R \\), so it offers limited control over which features it uses.[3](https://people.eecs.berkeley.edu/~jordan/kernels/0521813972c09_p291-326.pdf)\n\n**Approximation methods.** Because polynomial kernels are not shift-invariant, random Fourier features cannot be applied directly; polynomial sketches instead implicitly project the explicit high-dimensional feature maps.[13](https://jmlr.org/papers/volume25/22-0118/22-0118.pdf) Remedies include the [Nyström method](https://www.edgepedia.org/nystrom-method), which computes a rank-\\( k \\) kernel-matrix approximation in \\( O(nk^{2} + k^{3}) \\) time; random features; and sketching.[15](http://proceedings.mlr.press/v48/blondel16.pdf) • [7](https://arxiv.org/html/2505.08146v1) Tensor Sketch approximates \\( \\kappa(x, y) = (c + \\langle x, y \\rangle)^{p} \\) by exploiting the connection between tensor products and the fast convolution structure of Count Sketch, computing \\( D \\)-dimensional embeddings in \\( O(n(d + D \\log D)) \\) time with \\( O(1) \\) extra space for the sketch randomness;[7](https://arxiv.org/html/2505.08146v1) scikit-learn's PolynomialCountSketch implements it, with the best score/runtime balance typically around \\( n_{\\mathrm{components}} = 10 \\cdot n_{\\mathrm{features}} \\).[19](https://sklearn.org/stable/modules/generated/sklearn.kernel_approximation.PolynomialCountSketch.html) Published comparisons document scaling-related failure modes but do not settle numerical-overflow behavior at large degrees or norms.\n\n## References\n\n1. [Training and Testing Low-degree Polynomial Data Mappings via Linear SVM](https://www.csie.ntu.edu.tw/~cjlin/papers/lowpoly_journal.pdf)\n2. [The Kernel Trick (UC Berkeley CS 189 lecture notes, Spring 2024)](https://people.eecs.berkeley.edu/~jrs/189s24/lec/16.pdf)\n3. [Kernel Methods for Pattern Analysis, Chapter 9 (Shawe-Taylor and Cristianini)](https://people.eecs.berkeley.edu/~jordan/kernels/0521813972c09_p291-326.pdf)\n4. [Dual-to-Kernel Learning with Ideals](https://ar5iv.labs.arxiv.org/html/1402.0099)\n5. [A Tutorial on Support Vector Machines for Pattern Recognition (Burges, 1998)](https://www.di.ens.fr/%7Emallat/papiers/svmtutorial.pdf)\n6. [Recitation 5 - Kernels (David Rosenberg, NYU mldata course)](https://davidrosenberg.github.io/mlcourse/Archive/2017/Labs/5-Kernels-Slides.pdf)\n7. [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://arxiv.org/html/2505.08146v1)\n8. [Kernels (UPenn machine learning lecture notes)](https://machine-learning-upenn.github.io/assets/notes/Lec9.pdf)\n9. [Polynomial kernel (Kerch library documentation)](https://kerch.readthedocs.io/en/stable/kernel/generic/polynomial.html)\n10. [Scalable learning with polynomial kernel approximation, scikit-learn example](https://scikit-learn.org/dev/auto_examples/kernel_approximation/plot_scalable_poly_kernels.html)\n11. [Livni, Roi, Shalev-Shwartz, Shai, Shamir, Ohad (2013). An Algorithm for Training Polynomial Networks. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1304.7045)\n12. [Steffen Rendle (2012). Factorization Machines with libFM. ACM Transactions on Intelligent Systems and Technology.](https://doi.org/10.1145/2168752.2168771)\n13. [Improved Random Features for Dot Product Kernels (JMLR, volume 25)](https://jmlr.org/papers/volume25/22-0118/22-0118.pdf)\n14. [CMU 10-701/10-601 Machine Learning lecture notes: Kernels](http://www.cs.cmu.edu/%7Eninamf/ML11/lect1020.pdf)\n15. [Polynomial Networks and Factorization Machines: New Insights and Efficient Training Algorithms (ICML 2016)](http://proceedings.mlr.press/v48/blondel16.pdf)\n16. [Support Vector Machines: Training and Applications (MIT AI Memo 1602, Osuna, Freund, Girosi)](https://bitsavers.org/pdf/mit/ai/aim/AIM-1602.pdf)\n17. [PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels (ICML 2024)](https://proceedings.mlr.press/v235/kacham24a.html)\n18. [Explicit feature maps for non-linear kernel functions (Towards Data Science)](https://towardsdatascience.com/explicit-feature-maps-for-non-linear-kernel-functions-171a9043da38/)\n19. [PolynomialCountSketch, scikit-learn 1.9.0 documentation](https://sklearn.org/stable/modules/generated/sklearn.kernel_approximation.PolynomialCountSketch.html)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Machine learning and neural computation › Machine learning methods › Supervised, unsupervised, and semi-supervised learning › Kernel methods and support vector machines*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Oct 15, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://people.eecs.berkeley.edu/~jrs/189s24/lec/16.pdf", "https://people.eecs.berkeley.edu/~jordan/kernels/0521813972c09_p291-326.pdf" ], "url": "https://www.edgepedia.org/polynomial-kernel", "markdown_url": "https://www.edgepedia.org/polynomial-kernel.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Polynomial kernel\", Edgepedia (EdgeChat), https://www.edgepedia.org/polynomial-kernel. Edgepedia Community License 1.0.", "credit_md": "\"[Polynomial kernel](https://www.edgepedia.org/polynomial-kernel)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/polynomial-kernel](https://www.edgepedia.org/polynomial-kernel). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Polynomial kernel\", Edgepedia (EdgeChat), https://www.edgepedia.org/polynomial-kernel. Edgepedia Community License 1.0.", "speakable": "The polynomial kernel is a kernel function in machine learning that computes a scaled, shifted inner product raised to a degree, letting support vector machines learn nonlinear boundaries." }