Skip to content
Last Dictionary
Plane
Machine LearningMathematics & Statistics

kernel trick

nounAlso: kernel method, kernel methods, kernel machine, kernel function, Mercer kernel, radial basis function kernel, RBF kernel, Gaussian kernel, polynomial kernel, reproducing kernel Hilbert space, RKHS, Gram matrix

In plain wordsA mathematical shortcut that lets simple straight-line methods find curved patterns, by computing similarities between examples as if the data had been mapped into a far richer space — without ever building that space.

  1. The technique of replacing every inner product between inputs in an algorithm with a kernel function k(x, x′) that equals an inner product of feature maps φ(x)·φ(x′), so that a linear method operates implicitly in that feature space — which may be very high- or even infinite-dimensional — without computing φ. Any symmetric positive semidefinite function qualifies (Mercer's condition), such as the polynomial kernel and the radial basis function (Gaussian) kernel. By the representer theorem, solutions of many regularized problems are weighted sums of kernels centered on the training points. The trick turns support vector machinessupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too., ridge regressionridge regression, n.: Linear regression with a built-in brake: it fits the data while also keeping the weights small, which makes predictions more stable when there are many overlapping inputs., principal component analysisprincipal component analysis, n.: A technique that finds the few directions in which data vary the most and describes each item by its position along them, compressing many measurements into a handful of summary scores. and k-means into nonlinear kernel methods, and kernels serve as covariance functions of Gaussian processesGaussian process, n.: A way of predicting an unknown curve or surface that gives not just a best guess at each point but an honest error bar, narrow near measured points and wide far from them.. Its cost is the n × n kernel (Gram) matrix, which scales poorly with dataset size; random Fourier features and Nyström approximations address this.

    Swapping the linear kernel for an RBF kernel let the SVM separate the concentric rings.

k(x,x′)=⟨φ(x),φ(x′)⟩,kRBF(x,x′)=exp⁡ ⁣(−γ∥x−x′∥2)k(\mathbf{x}, \mathbf{x}') = \langle \varphi(\mathbf{x}), \varphi(\mathbf{x}') \rangle, \qquad k_{\mathrm{RBF}}(\mathbf{x}, \mathbf{x}') = \exp\!\big(-\gamma \lVert \mathbf{x} - \mathbf{x}' \rVert^2\big)

Origin

Positive-definite kernels trace back to James Mercer's 1909 theorem. Mark Aizerman, Emmanuel Braverman and Lev Rozonoer interpreted kernels as inner products in a feature space for their potential-function method of pattern recognition (1964), and Bernhard Boser, Isabelle Guyon and Vladimir Vapnik combined the idea with maximum-margin classifiers in 1992, launching the kernel-methods era. The phrase 'kernel trick' was established by 2000, when Bernhard Schölkopf used it in a paper title ('The Kernel Trick for Distances').

Usage note

'Kernel' has several unrelated AI meanings — a GPU program, a convolution filterfilter, n.: In an image-recognition network, a small grid of learned numbers that acts as a pattern detector, for vertical edges, a patch of fur or a wheel, scanned across the whole picture., the neural tangent kernelneural tangent kernel, n.: A mathematical tool showing that extremely wide neural networks learn like a simpler, well-understood method, because their internal settings barely move during training. It explains some, but not all, of deep learning's behavior.; see the hub entry kernelkernel, n.: A word with several AI meanings: a similarity measure used by some learning methods; a small grid of numbers that scans an image inside a neural network; or a small program that runs on a GPU..

Related

See also
  • support vector machinesupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too.
  • Gaussian processGaussian process, n.: A way of predicting an unknown curve or surface that gives not just a best guess at each point but an honest error bar, narrow near measured points and wide far from them.
  • kernelkernel, n.: A word with several AI meanings: a similarity measure used by some learning methods; a small grid of numbers that scans an image inside a neural network; or a small program that runs on a GPU.
  • ridge regressionridge regression, n.: Linear regression with a built-in brake: it fits the data while also keeping the weights small, which makes predictions more stable when there are many overlapping inputs.
  • neural tangent kernelneural tangent kernel, n.: A mathematical tool showing that extremely wide neural networks learn like a simpler, well-understood method, because their internal settings barely move during training. It explains some, but not all, of deep learning's behavior.
  • linear separabilitylinear separability, n.: When two groups of points can be perfectly divided by a single straight line or, in more dimensions, a flat surface. Many simple learning methods only fully succeed in this case.

Sources

  1. Aizerman, M. A., Braverman, E. M. & Rozonoer, L. I. (1964). Theoretical Foundations of the Potential Function Method in Pattern Recognition Learning. Automation and Remote Control, 25, 821–837.
  2. Boser, B. E., Guyon, I. M. & Vapnik, V. N. (1992). A Training Algorithm for Optimal Margin Classifiers. Proceedings of COLT '92.

Mentioned in

feature mapfeature map, n.: The grid of numbers produced when one learned pattern detector is scanned across an image, showing where, and how strongly, that pattern appears., Gaussian processGaussian process, n.: A way of predicting an unknown curve or surface that gives not just a best guess at each point but an honest error bar, narrow near measured points and wide far from them., kernelkernel, n.: A word with several AI meanings: a similarity measure used by some learning methods; a small grid of numbers that scans an image inside a neural network; or a small program that runs on a GPU., linear separabilitylinear separability, n.: When two groups of points can be perfectly divided by a single straight line or, in more dimensions, a flat surface. Many simple learning methods only fully succeed in this case., ridge regressionridge regression, n.: Linear regression with a built-in brake: it fits the data while also keeping the weights small, which makes predictions more stable when there are many overlapping inputs., support vector machinesupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too., Vladimir VapnikVladimir Vapnik, prop. n.: A Soviet-born American mathematician who built the statistical theory of how machines learn from examples and co-invented support vector machines, a leading method before deep learning., kernel fusionkernel fusion, n.: Merging several small calculation steps into one, so a chip finishes them in a single pass instead of saving and reloading data in between, like cooking at the counter without returning ingredients to the fridge after each step., neural tangent kernelneural tangent kernel, n.: A mathematical tool showing that extremely wide neural networks learn like a simpler, well-understood method, because their internal settings barely move during training. It explains some, but not all, of deep learning's behavior., radial basis function networkradial basis function network, n.: A three-layer network whose hidden neurons each respond to inputs near a particular reference point, like bells placed across the data; the output is a weighted mix of the bells.