In
machine learning, kernel machines are a class of algorithms for
pattern analysis, whose best known member is the
support-vector machine (SVM). The general task of
pattern analysis is to find and study general types of relations (for example
clusters,
ranking
A ranking is a relationship between a set of items such that, for any two items, the first is either "ranked higher than", "ranked lower than" or "ranked equal to" the second.
In mathematics, this is known as a weak order or total preorder of ...
s,
principal components
Principal component analysis (PCA) is a popular technique for analyzing large datasets containing a high number of dimensions/features per observation, increasing the interpretability of data while preserving the maximum amount of information, and ...
,
correlations,
classifications) in datasets. For many algorithms that solve these tasks, the data in raw representation have to be explicitly transformed into
feature vector
In machine learning and pattern recognition, a feature is an individual measurable property or characteristic of a phenomenon. Choosing informative, discriminating and independent features is a crucial element of effective algorithms in pattern r ...
representations via a user-specified ''feature map'': in contrast, kernel methods require only a user-specified ''kernel'', i.e., a
similarity function
In statistics and related fields, a similarity measure or similarity function or similarity metric is a real-valued function that quantifies the similarity between two objects. Although no single definition of a similarity exists, usually such meas ...
over all pairs of data points computed using
Inner products
In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often ...
. 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 function In operator theory, a branch of mathematics, a positive-definite kernel is a generalization of a positive-definite function or a positive-definite matrix. It was first introduced by James Mercer in the early 20th century, in the context of solvi ...
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 products between the
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". 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
In machine learning, the kernel perceptron is a variant of the popular perceptron learning algorithm that can learn kernel machines, i.e. non-linear classifiers that employ a kernel function to compute the similarity of unseen samples to traini ...
, support-vector machines (SVM),
Gaussian processes,
principal components analysis
Principal component analysis (PCA) is a popular technique for analyzing large datasets containing a high number of dimensions/features per observation, increasing the interpretability of data while preserving the maximum amount of information, and ...
(PCA),
canonical correlation analysis
In statistics, canonical-correlation analysis (CCA), also called canonical variates analysis, is a way of inferring information from cross-covariance matrices. If we have two vectors ''X'' = (''X''1, ..., ''X'n'') and ''Y' ...
,
ridge regression
Ridge regression is a method of estimating the coefficients of multiple-regression models in scenarios where the independent variables are highly correlated. It has been used in many fields including econometrics, chemistry, and engineering. Also ...
,
spectral clustering,
linear adaptive filters and many others.
Most kernel algorithms are based on
convex optimization
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization pr ...
or
eigenproblems and are statistically well-founded. Typically, their statistical properties are analyzed using
statistical learning theory (for example, using
Rademacher complexity
In computational learning theory ( machine learning and theory of computation), Rademacher complexity, named after Hans Rademacher, measures richness of a class of real-valued functions with respect to a probability distribution.
Definitions Ra ...
).
Motivation and informal explanation
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
-th training example
and learn for it a corresponding weight
. Prediction for unlabeled inputs, i.e., those not in the training set, is treated by the application of a
similarity function
In statistics and related fields, a similarity measure or similarity function or similarity metric is a real-valued function that quantifies the similarity between two objects. Although no single definition of a similarity exists, usually such meas ...
, called a kernel, between the unlabeled input
and each of the training inputs
. For instance, a kernelized
binary classifier
Binary classification is the task of classifying the elements of a set into two groups (each called ''class'') on the basis of a classification rule. Typical binary classification problems include:
* Medical testing to determine if a patient has ...
typically computes a weighted sum of similarities
:
,
where
*
is the kernelized binary classifier's predicted label for the unlabeled input
whose hidden true label
is of interest;
*
is the kernel function that measures similarity between any pair of inputs
;
* the sum ranges over the labeled examples
in the classifier's training set, with
;
* the
are the weights for the training examples, as determined by the learning algorithm;
* the
sign function
In mathematics, the sign function or signum function (from '' signum'', Latin for "sign") is an odd mathematical function that extracts the sign of a real number. In mathematical expressions the sign function is often represented as . To a ...
determines whether the predicted classification
comes out positive or negative.
Kernel classifiers were described as early as the 1960s, with the invention of the
kernel perceptron
In machine learning, the kernel perceptron is a variant of the popular perceptron learning algorithm that can learn kernel machines, i.e. non-linear classifiers that employ a kernel function to compute the similarity of unseen samples to traini ...
. 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
A neural network is a network or circuit of biological neurons, or, in a modern sense, an artificial neural network, composed of artificial neurons or nodes. Thus, a neural network is either a biological neural network, made up of biological ...
on tasks such as
handwriting recognition.
Mathematics: the kernel trick
The kernel trick avoids the explicit mapping that is needed to get linear
learning algorithms to learn a nonlinear function or
decision boundary
__NOTOC__
In a statistical-classification problem with two classes, a decision boundary or decision surface is a hypersurface that partitions the underlying vector space into two sets, one for each class. The classifier will classify all the point ...
. For all
and
in the input space
, certain functions
can be expressed as an
inner product in another space
. The function
is often referred to as a ''kernel'' or a ''
kernel function In operator theory, a branch of mathematics, a positive-definite kernel is a generalization of a positive-definite function or a positive-definite matrix. It was first introduced by James Mercer in the early 20th century, in the context of solvi ...
''. 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
. The computation is made much simpler if the kernel can be written in the form of a "feature map"
which satisfies
:
The key restriction is that
must be a proper inner product.
On the other hand, an explicit representation for
is not necessary, as long as
is an
inner product space. The alternative follows from
Mercer's theorem In mathematics, specifically functional analysis, Mercer's theorem is a representation of a symmetric positive-definite function on a square as a sum of a convergent sequence of product functions. This theorem, presented in , is one of the most no ...
: an implicitly defined function
exists whenever the space
can be equipped with a suitable
measure ensuring the function
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 In mathematics, specifically measure theory, the counting measure is an intuitive way to put a measure on any set – the "size" of a subset is taken to be the number of elements in the subset if the subset has finitely many elements, and infini ...
for all
, 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
in
and all choices of
real-valued coefficients
(cf.
positive definite kernel), then the function
satisfies Mercer's condition.
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
. The linear interpretation gives us insight about the algorithm. Furthermore, there is often no need to compute
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 with respect to
(sometimes also called a "kernel matrix"), where
, must be
positive semi-definite (PSD). Empirically, for machine learning heuristics, choices of a function
that do not satisfy Mercer's condition may still perform reasonably if
at least approximates the intuitive idea of similarity. Regardless of whether
is a Mercer kernel,
may still be referred to as a "kernel".
If the kernel function
is also a
covariance function In probability theory and statistics, the covariance function describes how much two random variables change together (their ''covariance'') with varying spatial or temporal separation. For a random field or stochastic process ''Z''(''x'') on a doma ...
as used in
Gaussian processes
In probability theory and statistics, a Gaussian process is a stochastic process (a collection of random variables indexed by time or space), such that every finite collection of those random variables has a multivariate normal distribution, i.e. e ...
, then the Gram matrix
can also be called a
covariance matrix
In probability theory and statistics, a covariance matrix (also known as auto-covariance matrix, dispersion matrix, variance matrix, or variance–covariance matrix) is a square Matrix (mathematics), matrix giving the covariance between ea ...
.
Applications
Application areas of kernel methods are diverse and include
geostatistics
Geostatistics is a branch of statistics focusing on spatial or spatiotemporal datasets. Developed originally to predict probability distributions of ore grades for mining operations, it is currently applied in diverse disciplines including pe ...
,
kriging
In statistics, originally in geostatistics, kriging or Kriging, also known as Gaussian process regression, is a method of interpolation based on Gaussian process governed by prior covariances. Under suitable assumptions of the prior, kriging giv ...
,
inverse distance weighting
Inverse distance weighting (IDW) is a type of deterministic method for multivariate interpolation with a known scattered set of points. The assigned values to unknown points are calculated with a weighted average of the values available at the kno ...
,
3D reconstruction
In computer vision and computer graphics, 3D reconstruction is the process of capturing the shape and appearance of real objects.
This process can be accomplished either by active or passive methods. If the model is allowed to change its shape i ...
,
bioinformatics
Bioinformatics () is an interdisciplinary field that develops methods and software tools for understanding biological data, in particular when the data sets are large and complex. As an interdisciplinary field of science, bioinformatics combine ...
,
chemoinformatics
Cheminformatics (also known as chemoinformatics) refers to use of physical chemistry theory with computer and information science techniques—so called "''in silico''" techniques—in application to a range of descriptive and prescriptive proble ...
,
information extraction
Information extraction (IE) is the task of automatically extracting structured information from unstructured and/or semi-structured machine-readable documents and other electronically represented sources. In most of the cases this activity concer ...
and
handwriting recognition.
Popular kernels
*
Fisher kernel
*
Graph kernel
In structure mining, a graph kernel is a kernel function that computes an inner product on graphs.
Graph kernels can be intuitively understood as functions measuring the similarity of pairs of graphs. They allow kernelized learning algorithms su ...
s
*
Kernel smoother A kernel smoother is a statistical technique to estimate a real valued function f: \mathbb^p \to \mathbb as the weighted average of neighboring observed data. The weight is defined by the ''kernel'', such that closer points are given higher weights ...
*
Polynomial kernel
In machine learning, the polynomial kernel is a kernel function commonly used with support vector machines (SVMs) and other kernelized models, that represents the similarity of vectors (training samples) in a feature space over polynomials of th ...
*
Radial basis function kernel In machine learning, the radial basis function kernel, or RBF kernel, is a popular kernel function used in various kernelized learning algorithms. In particular, it is commonly used in support vector machine classification.
The RBF kernel on two s ...
(RBF)
*
String kernels
*
Neural tangent kernel
*
Neural network Gaussian process (NNGP) kernel
See also
*
Kernel methods for vector output
*
Kernel density estimation
*
Representer theorem
*
Similarity learning
Similarity learning is an area of supervised machine learning in artificial intelligence. It is closely related to regression and classification, but the goal is to learn a similarity function that measures how similar or related two objects are. ...
*
Cover's theorem
References
Further reading
*
*
*
External links
Kernel-Machines Org��community website
onlineprediction.net Kernel Methods Article
{{DEFAULTSORT:Kernel Methods
Kernel methods for machine learning
Geostatistics
Classification algorithms