imported>Dough34: fix capitalization, remove space

2025-02-13T19:58:41Z

fix capitalization, remove space

New page

{{Short description|Class of algorithms for pattern analysis}}
{{Machine learning bar}}

In [[machine learning]], '''kernel machines''' are a class of algorithms for [[pattern analysis]], whose best known member is the [[support-vector machine]] (SVM). These methods involve using linear classifiers to solve nonlinear problems.<ref>{{Cite web |title=Kernel method |url=https://www.engati.com/glossary/kernel-method |access-date=2023-04-04 |website=Engati |language=en}}</ref> The general task of [[pattern analysis]] is to find and study general types of relations (for example [[Cluster analysis|clusters]], [[ranking]]s, [[principal components]], [[correlation]]s, [[Statistical classification|classifications]]) in datasets. For many algorithms that solve these tasks, the data in raw representation have to be explicitly transformed into [[feature vector]] representations via a user-specified ''feature map'': in contrast, kernel methods require only a user-specified ''kernel'', i.e., a [[similarity function]] over all pairs of data points computed using [[inner products]]. The feature map in kernel machines is infinite dimensional but only requires a finite dimensional matrix from user-input according to the [[representer 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 of [[Positive-definite kernel|kernel function]]s, which enable them to operate in a high-dimensional, ''implicit'' [[feature space]] without ever computing the coordinates of the data in that space, but rather by simply computing the [[inner product]]s between the [[Image (mathematics)|images]] 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'''".<ref>{{Cite book|title=Pattern Recognition|last=Theodoridis|first=Sergios|publisher=Elsevier B.V.|year=2008|isbn=9780080949123|pages=203}}</ref> Kernel functions have been introduced for sequence data, [[Graph kernel|graphs]], text, images, as well as vectors.

Algorithms capable of operating with kernels include the [[kernel perceptron]], support-vector machines (SVM), [[Gaussian process]]es, [[principal components analysis]] (PCA), [[canonical correlation analysis]], [[ridge regression]], [[spectral clustering]], [[Adaptive filter|linear adaptive filters]] and many others.

Most kernel algorithms are based on [[convex optimization]] or [[Eigenvalue, eigenvector and eigenspace|eigenproblems]] and are statistically well-founded. Typically, their statistical properties are analyzed using [[statistical learning theory]] (for example, using [[Rademacher complexity]]).

==Motivation and informal explanation==
Kernel methods can be thought of as [[instance-based learning|instance-based learners]]: rather than learning some fixed set of parameters corresponding to the features of their inputs, they instead "remember" the <math>i</math>-th training example <math>(\mathbf{x}_i, y_i)</math> and learn for it a corresponding weight <math>w_i</math>. Prediction for unlabeled inputs, i.e., those not in the training set, is treated by the application of a [[similarity function]] <math>k</math>, called a '''kernel''', between the unlabeled input <math>\mathbf{x'}</math> and each of the training inputs <math>\mathbf{x}_i</math>. For instance, a kernelized [[binary classifier]] typically computes a weighted sum of similarities
<math display="block">\hat{y} = \sgn \sum_{i=1}^n w_i y_i k(\mathbf{x}_i, \mathbf{x'}),</math>
where
* <math>\hat{y} \in \{-1, +1\}</math> is the kernelized binary classifier's predicted label for the unlabeled input <math>\mathbf{x'}</math> whose hidden true label <math>y</math> is of interest;
* <math>k \colon \mathcal{X} \times \mathcal{X} \to \mathbb{R}</math> is the kernel function that measures similarity between any pair of inputs <math>\mathbf{x}, \mathbf{x'} \in \mathcal{X}</math>;
* the sum ranges over the {{mvar|n}} labeled examples <math>\{(\mathbf{x}_i, y_i)\}_{i=1}^n</math> in the classifier's training set, with <math>y_i \in \{-1, +1\}</math>;
* the <math>w_i \in \mathbb{R}</math> are the weights for the training examples, as determined by the learning algorithm;
* the [[sign function]] <math>\sgn</math> determines whether the predicted classification <math>\hat{y}</math> comes out positive or negative.

Kernel classifiers were described as early as the 1960s, with the invention of the [[kernel perceptron]].<ref>{{cite journal |last1=Aizerman |first1=M. A. |first2=Emmanuel M. | last2 = Braverman |first3=L. I. |last3=Rozonoer |title=Theoretical foundations of the potential function method in pattern recognition learning |journal=Automation and Remote Control |volume=25 |year=1964 |pages=821–837}} Cited in {{Cite conference |last1=Guyon |first1=Isabelle |first2=B. |last2=Boser |first3=Vladimir |last3=Vapnik |title=Automatic capacity tuning of very large VC-dimension classifiers |conference=Advances in neural information processing systems |year=1993 |citeseerx = 10.1.1.17.7215}}</ref> They rose to great prominence with the popularity of the [[support-vector machine]] (SVM) in the 1990s, when the SVM was found to be competitive with [[artificial neural network|neural networks]] on tasks such as [[handwriting recognition]].

==Mathematics: the kernel trick==
[[Image:Kernel trick idea.svg|thumb|500px|SVM with feature map given by <math>\varphi((a, b)) = (a, b, a^2 + b^2)</math> and thus with the kernel function <math>k(\mathbf{x}, \mathbf{y}) = \mathbf{x} \cdot \mathbf{y} + \left\| \mathbf{x} \right\| ^2 \left\| \mathbf{y} \right\| ^2 </math>. The training points are mapped to a 3-dimensional space where a separating hyperplane can be easily found.]]
The kernel trick avoids the explicit mapping that is needed to get linear [[learning algorithms]] to learn a nonlinear function or [[decision boundary]]. For all <math>\mathbf{x}</math> and <math>\mathbf{x'}</math> in the input space <math>\mathcal{X}</math>, certain functions <math>k(\mathbf{x}, \mathbf{x'})</math> can be expressed as an [[inner product]] in another space <math>\mathcal{V}</math>. The function <math>k \colon \mathcal{X} \times \mathcal{X} \to \mathbb{R}</math> is often referred to as a ''kernel'' or a ''[[kernel function]]''. The word "kernel" is used in mathematics to denote a weighting function for a weighted sum or [[integral]].

Certain problems in machine learning have more structure than an arbitrary weighting function <math>k</math>. The computation is made much simpler if the kernel can be written in the form of a "feature map" <math>\varphi\colon \mathcal{X} \to \mathcal{V}</math> which satisfies
<math display="block">k(\mathbf{x}, \mathbf{x'}) = \langle \varphi(\mathbf{x}), \varphi(\mathbf{x'}) \rangle_\mathcal{V}.</math>The key restriction is that <math> \langle \cdot, \cdot \rangle_\mathcal{V}</math> must be a proper inner product. On the other hand, an explicit representation for <math>\varphi</math> is not necessary, as long as <math>\mathcal{V}</math> is an [[inner product space]]. The alternative follows from [[Mercer's theorem]]: an implicitly defined function <math>\varphi</math> exists whenever the space <math>\mathcal{X}</math> can be equipped with a suitable [[Measure (mathematics)|measure]] ensuring the function <math>k</math> satisfies [[Mercer's condition]].

Mercer's theorem is similar to a generalization of the result from linear algebra that [[Positive-definite matrix#Other characterizations|associates 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 the [[counting measure]] <math> \mu(T) = |T| </math> for all <math> T \subset X </math>, which counts the number of points inside the set <math>T</math>, then the integral in Mercer's theorem reduces to a summation<math display="block"> \sum_{i=1}^n\sum_{j=1}^n k(\mathbf{x}_i, \mathbf{x}_j) c_i c_j \geq 0.</math>If this summation holds for all finite sequences of points <math>(\mathbf{x}_1, \dotsc, \mathbf{x}_n)</math> in <math>\mathcal{X}</math> and all choices of <math>n</math> real-valued coefficients <math>(c_1, \dots, c_n)</math> (cf. [[positive definite kernel]]), then the function <math>k</math> satisfies Mercer's condition.

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

Theoretically, a [[Gram matrix]] <math>\mathbf{K} \in \mathbb{R}^{n \times n}</math> with respect to <math>\{\mathbf{x}_1, \dotsc, \mathbf{x}_n\}</math> (sometimes also called a "kernel matrix"<ref>{{cite journal | first1 = Thomas | last1 = Hofmann | first2 = Bernhard | last2 = Schölkopf | first3 = Alexander J. | last3 = Smola | date = 2008 | title = Kernel Methods in Machine Learning | journal = The Annals of Statistics | volume = 36 | issue = 3 | doi = 10.1214/009053607000000677 | s2cid = 88516979 |url=https://projecteuclid.org/download/pdfview_1/euclid.aos/1211819561| doi-access = free | arxiv = math/0701907 }}</ref>), where <math>K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)</math>, must be [[Positive-definite matrix|positive semi-definite (PSD)]].<ref>{{Cite Mehryar Afshin Ameet 2012}}</ref> Empirically, for machine learning heuristics, choices of a function <math>k</math> that do not satisfy Mercer's condition may still perform reasonably if <math>k</math> at least approximates the intuitive idea of similarity.<ref>{{cite web|url=http://www.svms.org/mercer/|title=Support Vector Machines: Mercer's Condition|first=Martin|last=Sewell|publisher=Support Vector Machines|access-date=2014-05-30|archive-date=2018-10-15|archive-url=https://web.archive.org/web/20181015031456/http://www.svms.org/mercer/|url-status=dead}}</ref> Regardless of whether <math>k</math> is a Mercer kernel, <math>k</math> may still be referred to as a "kernel".

If the kernel function <math>k</math> is also a [[covariance function]] as used in [[Gaussian processes]], then the Gram matrix <math>\mathbf{K}</math> can also be called a [[covariance matrix]].<ref>{{cite book | first1 = Carl Edward | last1 = Rasmussen | first2 = Christopher K. I. | last2 = Williams | date = 2006 | title = Gaussian Processes for Machine Learning|publisher=MIT Press|isbn=0-262-18253-X }} {{page needed|date=November 2023}}</ref>

==Applications==
Application areas of kernel methods are diverse and include [[geostatistics]],<ref>{{cite journal | last1 = Honarkhah | first1 = M. | last2 = Caers | first2 = J. | date = 2010 | doi = 10.1007/s11004-010-9276-7 | title = Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling |journal=[[Mathematical Geosciences]] | volume = 42 | issue = 5 | pages = 487–517 | bibcode = 2010MaGeo..42..487H | s2cid = 73657847 }}</ref> [[kriging]], [[inverse distance weighting]], [[3D reconstruction]], [[bioinformatics]], [[cheminformatics]], [[information extraction]] and [[handwriting recognition]].

==Popular kernels==
*[[Fisher kernel]]
*[[Graph kernel]]s
*[[Kernel smoother]]
*[[Polynomial kernel]]
*[[Radial basis function kernel]] (RBF)
*[[String kernel]]s
*[[Neural tangent kernel]]
*[[Neural network Gaussian process]] (NNGP) kernel

==See also==
*[[Kernel methods for vector output]]
*[[Kernel density estimation]]
*[[Representer theorem]]
*[[Similarity learning]]
*[[Cover's theorem]]

== References ==
{{Reflist|30em}}

== Further reading ==
* {{cite book | author-link1 = John Shawe-Taylor | first1 = J. | last1 = Shawe-Taylor | author-link2 = Nello Cristianini | first2 = N. | last2 = Cristianini | title = Kernel Methods for Pattern Analysis | publisher = Cambridge University Press | year = 2004|isbn=9780511809682}}
* {{cite book | first1 = W. | last1 = Liu | first2 = J. | last2 = Principe | first3 = S. | last3 = Haykin | title = Kernel Adaptive Filtering: A Comprehensive Introduction | publisher = Wiley | year = 2010 | isbn = 9781118211212 |url=https://books.google.com/books?id=eWUwB_P5pW0C }}
* {{cite book |first1=B. |last1=Schölkopf |author-link=Bernhard Schölkopf |first2=A. J. |last2=Smola |first3=F. |last3=Bach |title=Learning with Kernels : Support Vector Machines, Regularization, Optimization, and Beyond |publisher=MIT Press |year=2018 |isbn=978-0-262-53657-8 |url=https://books.google.com/books?id=ZQxiuAEACAAJ }}

==External links==
* [http://www.kernel-machines.org Kernel-Machines Org]—community website
* [http://onlineprediction.net/?n=Main.KernelMethods onlineprediction.net Kernel Methods Article]

{{DEFAULTSORT:Kernel Methods}}
[[Category:Kernel methods for machine learning]]
[[Category:Geostatistics]]
[[Category:Classification algorithms]]

Kernel method - Revision history

imported>Dough34: fix capitalization, remove space