Kernel method
These methods involve using linear classifiers to solve nonlinear problems.
[1] The general task of pattern analysis is to find and study general types of relations (for example clusters, rankings, principal components, correlations, 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 kernel functions, 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 products between the images of all pairs of data in the feature space.
[2] Kernel functions have been introduced for sequence data, graphs, text, images, as well as vectors.
Algorithms capable of operating with kernels include the kernel 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 on convex optimization or eigenproblems and are statistically well-founded.
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
Prediction for unlabeled inputs, i.e., those not in the training set, is treated by the application of a similarity function
For instance, a kernelized binary classifier typically computes a weighted sum of similarities
[3] 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.
The kernel trick avoids the explicit mapping that is needed to get linear learning algorithms to learn a nonlinear function or decision boundary.
Certain problems in machine learning have more structure than an arbitrary weighting function
The computation is made much simpler if the kernel can be written in the form of a "feature map"
The alternative follows from Mercer's theorem: an implicitly defined function
can be equipped with a suitable measure ensuring the function
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.
, which counts the number of points inside the set
, then the integral in Mercer's theorem reduces to a summation
If this summation holds for all finite sequences of points
Some algorithms that depend on arbitrary relationships in the native space
would, in fact, have a linear interpretation in a different setting: the range space of
Some cite this running time shortcut as the primary benefit.
Researchers also use it to justify the meanings and properties of existing algorithms.
[5] Empirically, for machine learning heuristics, choices of a function
is also a covariance function as used in Gaussian processes, then the Gram matrix
[7] Application areas of kernel methods are diverse and include geostatistics,[8] kriging, inverse distance weighting, 3D reconstruction, bioinformatics, cheminformatics, information extraction and handwriting recognition.
