A kernel method combines a feature transformation with
a linear model for transformed feature vectors.
The transformation is constructed from a kernel:
each feature vector is mapped to a function
with domain equal to the original feature space, and
inner products between transformed feature vectors reduce to
evaluations of a kernel. Kernel methods offer great
flexibility in the choice of the feature space, which can
consist of text documents or discrete structures such as
graphs.
Definition
A kernel method is a machine learning (ML) method that
applies a linear method, such as a linear model for regression or
a linear classifier for classification, to transformed
feature vectors that are constructed from a kernel
(Lampert, 2009; Schölkopf and Smola, 2002). Kernel
methods are used in computer vision, e.g., to decide whether an image
shows a specific object (Lampert, 2009), and for categorizing
text documents by topic (Cristianini and Shawe-Taylor, 2000).
Linear methods learn a hypothesis that combines the
features of a data point linearly, e.g.,
$\hypothesis(\featurevec) = \weights^{\top} \featurevec$ for the
feature space $\featurespace = \reals^{\nrfeatures}$. Such a
hypothesis predicts well only if the relation between the
feature vectors and the labels of data points is
approximately linear. Fig. 1 shows a
binary classification problem where this fails: no straight line separates the
two classes in the original feature space. Moreover, a linear
method requires numeric feature vectors and is not directly
applicable to data points from an arbitrary feature space
$\featurespace$, such as text documents or graphs.
Both limitations can be mitigated by a feature map
$\featuremap: \featurespace \rightarrow \hilbertspace$ from the original
feature space $\featurespace$ to a transformed feature space
$\hilbertspace$, chosen as a Hilbert space. A suitable
feature map makes a dataset "more linear": the relation
between the transformed feature vectors $\featuremap(\featurevec)$
and the labels is closer to linear than in $\featurespace$
(see Fig. 1).
Figure 1: Five data points characterized by feature vectors $\featurevec^{(\sampleidx)}$
and labels $\truelabel^{(\sampleidx)} \in \{ \circ, \square \}$ for $\sampleidx=1, \,\ldots, \,5$.
With these feature vectors, there is no way to separate the two classes
by a straight line (representing the decision boundary of a linear classifier).
In contrast, the transformed feature vectors $\vz^{(\sampleidx)} = \featuremap\big(\featurevec^{(\sampleidx)}\big)$
allow the data points to be separated using a linear classifier
A useful feature map $\featuremap$ often delivers transformed
feature vectors in a high-dimensional (possibly
infinite-dimensional) Hilbert space $\hilbertspace$
(Schölkopf and Smola, 2002). Computing and
storing the transformed feature vectors $\featuremap(\featurevec)$
explicitly can then be infeasible. However, linear methods access the
feature vectors of data points only through
inner products between pairs of feature vectors (see
linear model). For example, the prediction delivered by a
trained support vector machine (SVM) is a weighted sum of inner products between the
feature vector of a new data point and the feature vectors in
the training set. To apply a linear method to the transformed
feature vectors, it is therefore enough to know the
inner products
$\innerprod{\featuremap(\featurevec)}{\featuremap(\featurevec')}$ for
every possible pair of feature vectors
$\featurevec, \featurevec' \in \featurespace$. These
inner products are captured by a single function of two
arguments, the kernel
\[
\kernelmap{\featurevec}{\featurevec'}
\defeq \innerprod{\featuremap(\featurevec)}{\featuremap(\featurevec')}
\text{, for } \featurevec, \featurevec' \in \featurespace \text{.}
\]
A linear method that is applied to the transformed feature vectors
requires only the kernel $\kernel$; the feature map
$\featuremap$ itself is never evaluated.
Kernel methods turn this observation around: they start from a
kernel $\kernel: \featurespace \times \featurespace \rightarrow \reals$
and construct the feature map from it. The
feature map sends a feature vector $\featurevec \in \featurespace$
to the function $\kernelmap{\featurevec}{\cdot}$, i.e., the
transformed feature vector
$\vz \defeq \featuremap(\featurevec) = \kernelmap{\featurevec}{\cdot}$
is itself a function with domain $\featurespace$. These
functions belong to the reproducing kernel Hilbert space (RKHS) $\hilbertspace_{\kernel}$
associated with the kernel $\kernel$ (Aronszajn, 1950). The
inner product between the transformed feature vectors of two
original feature vectors $\featurevec, \featurevec' \in \featurespace$
is a single kernel evaluation,
\[
\innerprod{\kernelmap{\featurevec}{\cdot}}{\kernelmap{\featurevec'}{\cdot}}
= \kernelmap{\featurevec}{\featurevec'} \text{.}
\]
More generally, the inner product between the transformed
feature vector $\kernelmap{\featurevec}{\cdot}$ and any function
$\hypothesis \in \hilbertspace_{\kernel}$ is a point evaluation,
\[
\innerprod{\hypothesis}{\kernelmap{\featurevec}{\cdot}} = \hypothesis(\featurevec) \text{,}
\]
which is referred to as the reproducing property of the RKHS
$\hilbertspace_{\kernel}$ (Aronszajn, 1950). The preceding identity
is the special case $\hypothesis = \kernelmap{\featurevec'}{\cdot}$.
The (possibly infinite-dimensional) transformed feature vectors
therefore never need to be computed explicitly.
Fig. 2 depicts the RKHS
$\hilbertspace_{\kernel}$ for a training set with two
data points: a hypothesis $\hypothesis$ is a single
vector in $\hilbertspace_{\kernel}$, while the map
$\featurevec \mapsto \innerprod{\hypothesis}{\kernelmap{\featurevec}{\cdot}} = \hypothesis(\featurevec)$
it induces on the original feature space $\featurespace$ is
nonlinear in general. Indeed, the original feature space
$\featurespace$ might not be a vector space at all, e.g., if it
consists of text documents or graphs.
Figure 2: The RKHS $\hilbertspace_{\kernel}$ for a training set
with two data points having feature vectors
$\featurevec^{(1)}, \featurevec^{(2)}$. Their transformed
feature vectors $\kernelmap{\featurevec^{(1)}}{\cdot}$ and
$\kernelmap{\featurevec^{(2)}}{\cdot}$ span a two-dimensional
subspace (shaded). A hypothesis $\hypothesis$ is a
vector in $\hilbertspace_{\kernel}$; its prediction
for a data point with feature vector $\featurevec$ is the
inner product $\innerprod{\hypothesis}{\kernelmap{\featurevec}{\cdot}} = \hypothesis(\featurevec)$,
which is a nonlinear function of $\featurevec$ in general.
Replacing $\hypothesis$ by its orthogonal projection
$\widehat{\hypothesis}$ (dashed) onto the shaded subspace
leaves the predictions for both data points in the
training set unchanged and never increases
$\normgeneric{\hypothesis}{\hilbertspace_{\kernel}}$
Kernel methods can be formulated as regularized empirical risk minimization (RERM) over the RKHS
$\hilbertspace_{\kernel}$,
\[
\min_{\hypothesis \in \hilbertspace_{\kernel}} \frac{1}{\samplesize}
\sum_{\sampleidx=1}^{\samplesize}
\lossfunc{\big(\featurevec^{(\sampleidx)}, \truelabel^{(\sampleidx)}\big)}{\hypothesis}
+ \regparam \normgeneric{\hypothesis}{\hilbertspace_{\kernel}}^{2}
\text{,}
\]
over a training set with feature vectors $\featurevec^{(\sampleidx)}$
and labels $\truelabel^{(\sampleidx)}$, for
$\sampleidx = 1, \ldots, \samplesize$. The loss function
$\lossfunc{\big(\featurevec^{(\sampleidx)}, \truelabel^{(\sampleidx)}\big)}{\hypothesis}$
depends on $\hypothesis$ only through the prediction
$\hypothesis\big(\featurevec^{(\sampleidx)}\big)$, i.e., it is a function
of the prediction $\hypothesis\big(\featurevec^{(\sampleidx)}\big)$ and the
label $\truelabel^{(\sampleidx)}$ only. Since
$\hypothesis \in \hilbertspace_{\kernel}$, the reproducing property
delivers this prediction as an inner product,
$\hypothesis\big(\featurevec^{(\sampleidx)}\big) = \innerprod{\hypothesis}{\kernelmap{\featurevec^{(\sampleidx)}}{\cdot}}$.
By the representer theorem, this optimization problem has a minimizer
of the form $\widehat{\hypothesis} = \sum_{\sampleidx=1}^{\samplesize} \expcoeff_{\sampleidx} \kernelmap{\featurevec^{(\sampleidx)}}{\cdot}$
with expansion coefficients
$\expcoeff_{1}, \ldots, \expcoeff_{\samplesize} \in \reals$
(Schölkopf and Smola, 2002). Training thus reduces to a
convex optimization problem in these $\samplesize$ coefficients, and
the prediction $\widehat{\hypothesis}(\featurevec) = \sum_{\sampleidx=1}^{\samplesize} \expcoeff_{\sampleidx} \kernelmap{\featurevec^{(\sampleidx)}}{\featurevec}$
requires only kernel evaluations. Examples include the
kernel SVM and kernel ridge regression
(Cristianini and Shawe-Taylor, 2000; Hastie et al., 2009, Ch. 12).
For $\featurespace = \reals^{\nrfeatures}$, a widely used choice is the
Gaussian kernel
$\kernelmap{\featurevec}{\featurevec'} = \exp\big(- \normgeneric{\featurevec - \featurevec'}{2}^{2} / (2 \sigma^{2}) \big)$
with bandwidth $\sigma > 0$; kernels are also available for
data points without numeric features, such as strings and
graphs (Schölkopf and Smola, 2002).
Fig. 3 shows the resulting nonlinear
decision boundary $\widehat{\hypothesis}(\featurevec) = 0$ for a
Gaussian-kernel method with squared error loss (kernel
ridge regression on the labels $\truelabel^{(\sampleidx)} \in \{-1, +1\}$),
learned from a training set of two concentric rings that no
linear classifier separates.
Figure 3: A Gaussian-kernel method (kernel
ridge regression with $\sigma = 0.8$,
$\regparam = 10^{-3}$) learned from a training set of two
concentric rings. Data points with label
$\truelabel = +1$ are drawn as filled circles, those with
$\truelabel = -1$ as open squares. The learned decision boundary
$\widehat{\hypothesis}(\featurevec) = 0$ (solid) encircles the
inner ring. Note that the dataset is not linearly separable
in the original feature space. Data generated by
pythondemos/kernelmethod.py
Kernel methods are the most direct operationalization of the
smoothness assumption. The RKHS norm
$\normgeneric{\hypothesis}{\hilbertspace_{\kernel}}$ quantifies the smoothness of
a hypothesis $\hypothesis$: large for rapidly varying $\hypothesis$, small for smooth
$\hypothesis$. Different kernels encode different flavors of smoothness.
The Gaussian kernel gives infinitely differentiable
functions and penalizes high-frequency components, while
Mat\'ern kernels with parameter $\nu$ give Sobolev spaces of
$\nu$-times weakly differentiable functions
(Rasmussen and Williams, 2006, Ch. 4). The penalty term
$\regparam \normgeneric{\hypothesis}{\hilbertspace_{\kernel}}^{2}$ in the above
RERM therefore picks the smoothest hypothesis (in the
RKHS sense) that fits the training set. For localized
kernels, such as the Gaussian kernel, the prediction
at $\featurevec$ is dominated by the data points in the
training set that are close to $\featurevec$. Kernel methods are the
smoothness assumption in algorithmic form and the soft-weighted
analogue of $k$-nearest neighbors ($k$-NN) (Hastie et al., 2009, Ch. 6).
Synonyms: kernel machine.
See also: kernel, feature map, Hilbert space,
reproducing kernel Hilbert space, linear model, linear classifier, support vector machine,
kernel ridge regression, ridge regression,
smoothness assumption, $k$-nearest neighbors.
