In
machine learning
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
, 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,
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 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
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 ...
without ever computing the coordinates of the data in that space, but rather by simply computing the
inner product
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 ...
s between the
images
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
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, support-vector machines (SVM),
Gaussian processes,
principal components analysis (PCA),
canonical correlation analysis,
ridge regression,
spectral clustering
In multivariate statistics, spectral clustering techniques make use of the spectrum (eigenvalues) of the similarity matrix of the data to perform dimensionality reduction before clustering in fewer dimensions. The similarity matrix is provided as ...
,
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
Statistical learning theory is a framework for machine learning drawing from the fields of statistics and functional analysis. Statistical learning theory deals with the statistical inference problem of finding a predictive function based on dat ...
(for example, using
Rademacher complexity).
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 , called a kernel, between the unlabeled input
and each of the training inputs
. For instance, a kernelized
binary classifier 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 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. 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
Handwriting recognition (HWR), also known as handwritten text recognition (HTR), is the ability of a computer to receive and interpret intelligible handwritten input from sources such as paper documents, photographs, touch-screens and other de ...
.
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. For all
and
in the input space
, certain functions
can be expressed as an
inner product
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 ...
in another space
. The function
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
In mathematics, an integral assigns numbers to functions in a way that describes displacement, area, volume, and other concepts that arise by combining infinitesimal data. The process of finding integrals is called integration. Along wit ...
.
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 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 ...
.
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 infinity ...
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
In linear algebra, the Gram matrix (or Gramian matrix, Gramian) of a set of vectors v_1,\dots, v_n in an inner product space is the Hermitian matrix of inner products, whose entries are given by the inner product G_ = \left\langle v_i, v_j \right\r ...
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 as used in
Gaussian processes, then the Gram matrix
can also be called a
covariance matrix.
Applications
Application areas of kernel methods are diverse and include
geostatistics,
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 kn ...
,
3D reconstruction,
bioinformatics,
chemoinformatics,
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
Handwriting recognition (HWR), also known as handwritten text recognition (HTR), is the ability of a computer to receive and interpret intelligible handwritten input from sources such as paper documents, photographs, touch-screens and other de ...
.
Popular kernels
*
Fisher kernel In statistical classification, the Fisher kernel, named after Ronald Fisher, is a function that measures the similarity of two objects on the basis of sets of measurements for each object and a statistical model. In a classification procedure, the ...
*
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 s ...
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 ...
(RBF)
*
String kernels
*
Neural tangent kernel
In the study of artificial neural networks (ANNs), the neural tangent kernel (NTK) is a kernel that describes the evolution of deep artificial neural networks during their training by gradient descent. It allows ANNs to be studied using theoretica ...
*
Neural network Gaussian process (NNGP) kernel
See also
*
Kernel methods for vector output Kernel methods are a well-established tool to analyze the relationship between input data and the corresponding output of a function. Kernels encapsulate the properties of functions in a Kernel trick, computationally efficient way and allow algorith ...
*
Kernel density estimation
In statistics, kernel density estimation (KDE) is the application of kernel smoothing for probability density estimation, i.e., a non-parametric method to estimate the probability density function of a random variable based on '' kernels'' as ...
*
Representer theorem
*
Similarity learning
*
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