Kernel method

Kernel methods can be thought of as instance-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, is treated by the application of a similarity function ${\displaystyle k}$, called a kernel, between the unlabeled input ${\displaystyle \mathbf {x'} }$ and each of the training inputs ${\displaystyle \mathbf {x} _{i}}$. For instance, a kernelized binary classifier typically computes a weighted sum of similarities

${\displaystyle {\hat {y}}=\operatorname {sgn} \sum _{i=1}^{n}w_{i}y_{i}k(\mathbf {x} _{i},\mathbf {x'} )}$,

where

• ${\displaystyle {\hat {y}}\in \{-1,+1\}}$ is the kernelized binary classifier's predicted label for the unlabeled input ${\displaystyle \mathbf {x'} }$ whose hidden true label ${\displaystyle y}$ is of interest;
• ${\displaystyle k\colon {\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'} \in {\mathcal {X}}}$;
• the sum ranges over the n 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;
• the sign function ${\displaystyle \operatorname {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 the kernel perceptron.[2] 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 neural networks on tasks such as handwriting recognition.

SVM with kernel given by φ((a, b)) = (a, b, a² + b²) and thus K(x , y) = ${\displaystyle \mathbf {x} \cdot \mathbf {y} +\left\|\mathbf {x} \right\|^{2}\left\|\mathbf {y} \right\|^{2}}$. 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 ${\displaystyle \mathbf {x} }$ and ${\displaystyle \mathbf {x'} }$ in the input space ${\displaystyle {\mathcal {X}}}$, certain functions ${\displaystyle k(\mathbf {x} ,\mathbf {x'} )}$ can be expressed as an inner product in another space ${\displaystyle {\mathcal {V}}}$. The function ${\displaystyle k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$ 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 ${\displaystyle k}$. The computation is made much simpler if the kernel can be written in the form of a "feature map" ${\displaystyle \varphi \colon {\mathcal {X}}\to {\mathcal {V}}}$ which satisfies

${\displaystyle k(\mathbf {x} ,\mathbf {x'} )=\langle \varphi (\mathbf {x} ),\varphi (\mathbf {x'} )\rangle _{\mathcal {V}}.}$

The key restriction is that ${\displaystyle \langle \cdot ,\cdot \rangle _{\mathcal {V}}}$ must be a proper inner product. On the other hand, an explicit representation for ${\displaystyle \varphi }$ is not necessary, as long as ${\displaystyle {\mathcal {V}}}$ is an inner product space. The alternative follows from Mercer's theorem: an implicitly defined function ${\displaystyle \varphi }$ exists whenever the space ${\displaystyle {\mathcal {X}}}$ can be equipped with a suitable measure ensuring the function ${\displaystyle k}$ satisfies Mercer's condition.

Mercer's theorem is similar to a generalization of the result from linear algebra that 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 ${\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}\geq 0.}$

If this summation holds for all finite sequences of points ${\displaystyle (\mathbf {x} _{1},\dotsc ,\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 \varphi }$. The linear interpretation gives us insight about the algorithm. Furthermore, there is often no need to compute ${\displaystyle \varphi }$ directly during computation, as is the case with support 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, a Gram matrix ${\displaystyle \mathbf {K} \in \mathbb {R} ^{n\times n}}$ with respect to ${\displaystyle \{\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n}\}}$ (sometimes also called a "kernel matrix"[3]), where ${\displaystyle K_{ij}=k(\mathbf {x} _{i},\mathbf {x} _{j})}$, must be positive semi-definite (PSD).[4] 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.[5] 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 a covariance function as used in Gaussian processes, then the Gram matrix ${\displaystyle \mathbf {K} }$ can also be called a covariance matrix.[6]

Application areas of kernel methods are diverse and include geostatistics,[7] kriging, inverse distance weighting, 3D reconstruction, bioinformatics, chemoinformatics, information extraction and handwriting 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
• Representer theorem
• Cover's theorem

• Shawe-Taylor, J.; Cristianini, N. (2004). Kernel Methods for Pattern Analysis. Cambridge University Press.
• Liu, W.; Principe, J.; Haykin, S. (2010). Kernel Adaptive Filtering: A Comprehensive Introduction. Wiley.
• 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.

• Kernel-Machines Org—community website
• www.support-vector-machines.org (Literature, Review, Software, Links related to Support Vector Machines - Academic Site)
• onlineprediction.net Kernel Methods Article