Inmachine learning,kernel machines are a class of algorithms forpattern analysis, whose best known member is thesupport-vector machine (SVM). These methods involve using linear classifiers to solve nonlinear problems.^[1] The general task ofpattern analysis is to find and study general types of relations (for exampleclusters,rankings,principal components,correlations,classifications) in datasets. For many algorithms that solve these tasks, the data in raw representation have to be explicitly transformed intofeature vector representations via a user-specifiedfeature map: in contrast, kernel methods require only a user-specifiedkernel, i.e., asimilarity function over all pairs of data points computed usinginner products. The feature map in kernel machines is infinite dimensional but only requires a finite dimensional matrix from user-input according to therepresenter theorem. Kernel machines are slow to compute for datasets larger than a couple of thousand examples without parallel processing.

Kernel methods owe their name to the use ofkernel functions, which enable them to operate in a high-dimensional,implicitfeature space without ever computing the coordinates of the data in that space, but rather by simply computing theinner products between theimages of all pairs of data in the feature space. This operation is often computationally cheaper than the explicit computation of the coordinates. This approach is called the "kernel trick".^[2] Kernel functions have been introduced for sequence data,graphs, text, images, as well as vectors.

Algorithms capable of operating with kernels include thekernel perceptron, support-vector machines (SVM),Gaussian processes,principal components analysis (PCA),canonical correlation analysis,ridge regression,spectral clustering,linear adaptive filters and many others.

Most kernel algorithms are based onconvex optimization oreigenproblems and are statistically well-founded. Typically, their statistical properties are analyzed usingstatistical learning theory (for example, usingRademacher complexity).

Kernel methods can be thought of asinstance-based learners: rather than learning some fixed set of parameters corresponding to the features of their inputs, they instead "remember" the${\displaystyle i}$-th training example${\displaystyle ({\mathbf{x}}_i,y_i)}$ and learn for it a corresponding weight${\displaystyle w_i}$. Prediction for unlabeled inputs, i.e., those not in the training set, are treated by the application of asimilarity function${\displaystyle k}$, called akernel, between the unlabeled input${\displaystyle {\mathbf{x}}^{\prime }}$ and each of the training inputs${\displaystyle {\mathbf{x}}_i}$. For instance, a kernelizedbinary classifier typically computes a weighted sum of similarities$${\displaystyle \hat{y}=\mathrm{sgn}\sum _{i=1}^n{w}_i{y}_{i}k({\mathbf{x}}_i,{\mathbf{x}}^{\prime }),}$$where

• ${\displaystyle \hat{y}\in \{-1,+1\}}$ is the kernelized binary classifier's predicted label for the unlabeled input${\displaystyle {\mathbf{x}}^{\prime }}$ whose hidden true label${\displaystyle y}$ is of interest;
• ${\displaystyle k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}}$ is the kernel function that measures similarity between any pair of inputs${\displaystyle \mathbf{x},{\mathbf{x}}^{\prime }\in \mathcal{X}}$;
• the sum ranges over then labeled examples${\displaystyle \{({\mathbf{x}}_i,y_i){\}}_{i=1}^n}$ in the classifier's training set, with${\displaystyle y_i\in \{-1,+1\}}$;
• the${\displaystyle w_i\in \mathbb{R}}$ are the weights for the training examples, as determined by the learning algorithm;
• thesign function${\displaystyle \mathrm{sgn}}$ determines whether the predicted classification${\displaystyle \hat{y}}$ comes out positive or negative.

Kernel classifiers were described as early as the 1960s, with the invention of thekernel perceptron.^[3] They rose to great prominence with the popularity of thesupport-vector machine (SVM) in the 1990s, when the SVM was found to be competitive withneural networks on tasks such ashandwriting recognition.

The kernel trick avoids the explicit mapping that is needed to get linearlearning algorithms to learn a nonlinear function ordecision boundary. For all${\displaystyle \mathbf{x}}$ and${\displaystyle {\mathbf{x}}^{\prime }}$ in the input space${\displaystyle \mathcal{X}}$, certain functions${\displaystyle k(\mathbf{x},{\mathbf{x}}^{\prime })}$ can be expressed as aninner product in another space${\displaystyle \mathcal{V}}$. The function${\displaystyle k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}}$ is often referred to as akernel or akernel function. The word "kernel" is used in mathematics to denote a weighting function for a weighted sum orintegral.

Certain problems in machine learning have more structure than an arbitrary weighting function${\displaystyle k}$. The computation is made much simpler if the kernel can be written in the form of a "feature map"${\displaystyle \phi :\mathcal{X}\to \mathcal{V}}$ which satisfies$${\displaystyle k(\mathbf{x},{\mathbf{x}}^{\prime })=⟨\phi (\mathbf{x}),\phi ({\mathbf{x}}^{\prime }){⟩}_{\mathcal{V}}.}$$The key restriction is that${\displaystyle ⟨\cdot ,\cdot {⟩}_{\mathcal{V}}}$ must be a proper inner product. On the other hand, an explicit representation for${\displaystyle \phi }$ is not necessary, as long as${\displaystyle \mathcal{V}}$ is aninner product space. The alternative follows fromMercer's theorem: an implicitly defined function${\displaystyle \phi }$ exists whenever the space${\displaystyle \mathcal{X}}$ can be equipped with a suitablemeasure ensuring the function${\displaystyle k}$ satisfiesMercer's condition.

Mercer's theorem is similar to a generalization of the result from linear algebra thatassociates an inner product to any positive-definite matrix. In fact, Mercer's condition can be reduced to this simpler case. If we choose as our measure thecounting measure${\displaystyle \mu (T)=|T|}$ for all${\displaystyle T\subset X}$, which counts the number of points inside the set${\displaystyle T}$, then the integral in Mercer's theorem reduces to a summation$${\displaystyle \sum _{i=1}^n\sum _{j=1}^{n}k({\mathbf{x}}_i,{\mathbf{x}}_j)c_i{c}_j\ge 0.}$$If this summation holds for all finite sequences of points${\displaystyle ({\mathbf{x}}_1,\dots ,{\mathbf{x}}_n)}$ in${\displaystyle \mathcal{X}}$ and all choices of${\displaystyle n}$ real-valued coefficients${\displaystyle (c_1,\dots ,c_n)}$ (cf.positive definite kernel), then the function${\displaystyle k}$ satisfies Mercer's condition.

Some algorithms that depend on arbitrary relationships in the native space${\displaystyle \mathcal{X}}$ would, in fact, have a linear interpretation in a different setting: the range space of${\displaystyle \phi }$. The linear interpretation gives us insight about the algorithm. Furthermore, there is often no need to compute${\displaystyle \phi }$ directly during computation, as is the case withsupport-vector machines. Some cite this running time shortcut as the primary benefit. Researchers also use it to justify the meanings and properties of existing algorithms.

Theoretically, aGram matrix${\displaystyle \mathbf{K}\in {\mathbb{R}}^{n\times n}}$ with respect to${\displaystyle \{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_n\}}$ (sometimes also called a "kernel matrix"^[4]), where${\displaystyle K_{ij}=k({\mathbf{x}}_i,{\mathbf{x}}_j)}$, must bepositive semi-definite (PSD).^[5] Empirically, for machine learning heuristics, choices of a function${\displaystyle k}$ that do not satisfy Mercer's condition may still perform reasonably if${\displaystyle k}$ at least approximates the intuitive idea of similarity.^[6] Regardless of whether${\displaystyle k}$ is a Mercer kernel,${\displaystyle k}$ may still be referred to as a "kernel".

If the kernel function${\displaystyle k}$ is also acovariance function as used inGaussian processes, then the Gram matrix${\displaystyle \mathbf{K}}$ can also be called acovariance matrix.^[7]

Application areas of kernel methods are diverse and includegeostatistics,^[8]kriging,inverse distance weighting,3D reconstruction,bioinformatics,cheminformatics,information extraction andhandwriting recognition.

• Fisher kernel
• Graph kernels
• Kernel smoother
• Polynomial kernel
• Radial basis function kernel (RBF)
• String kernels
• Neural tangent kernel
• Neural network Gaussian process (NNGP) kernel

• Kernel methods for vector output
• Kernel density estimation
• Representer theorem
• Similarity learning
• Cover's theorem

• Shawe-Taylor, J.;Cristianini, N. (2004).Kernel Methods for Pattern Analysis. Cambridge University Press.ISBN 9780511809682.
• Liu, W.; Principe, J.; Haykin, S. (2010).Kernel Adaptive Filtering: A Comprehensive Introduction. Wiley.ISBN 9781118211212.
• Schölkopf, B.; Smola, A. J.; Bach, F. (2018).Learning with Kernels : Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press.ISBN 978-0-262-53657-8.

• onlineprediction.net Kernel Methods Article

• Kernel methods for machine learning
• Geostatistics
• Classification algorithms
• Pattern recognition

• Wikipedia articles needing page number citations from November 2023
• Articles with short description
• Short description matches Wikidata