Kernel method

A kernel method is a class of algorithms for pattern analysis in which observations enter calculations through evaluations of a kernel function. The kernel represents an inner product in a possibly high-dimensional feature space, allowing linear constructions in that space to induce nonlinear relations in the original input domain. This substitution is commonly called the kernel trick.

Kernel methods include the support-vector machine, kernel principal component analysis, kernel ridge regression, and several forms of spectral clustering. They also share mathematical structure with Gaussian processes, although the two traditions assign different interpretations to the same kernel matrix. Kernel methods are therefore characterized less by a single statistical model than by a common representation of similarity and function space geometry.

Mathematical formulation

Let (\mathcal X) be an input set and let

[ k:\mathcal X\times\mathcal X\rightarrow\mathbb R ]

be a symmetric function. A positive-semidefinite kernel satisfies

[ \sum_{i=1}^{n}\sum_{j=1}^{n}c_i c_j k(x_i,x_j)\geq 0 ]

for every finite collection (x_1,\ldots,x_n\in\mathcal X) and every set of real coefficients (c_1,\ldots,c_n). Equivalently, the Gram matrix (K), whose entries are (K_{ij}=k(x_i,x_j)), is positive semidefinite for every finite sample.

Such a kernel determines a reproducing kernel Hilbert space (\mathcal H). There exists a feature map

[ \phi:\mathcal X\rightarrow\mathcal H ]

for which

[ k(x,z)=\langle\phi(x),\phi(z)\rangle_{\mathcal H}. ]

The feature map need not be unique, and its coordinates need not be constructed explicitly. An algorithm whose dependence on the data occurs only through inner products can replace (\langle x,z\rangle) with (k(x,z)), thereby operating on (\phi(x)) through kernel evaluations alone.

For a finite data set, the Gram matrix contains all pairwise inner products among the mapped observations. Distances in feature space follow from

[ |\phi(x)-\phi(z)|_{\mathcal H}^{2}

k(x,x)+k(z,z)-2k(x,z). ]

Consequently, many geometric operations can be stated entirely in terms of kernel values. The resulting geometry depends on the chosen kernel and its parameters rather than solely on the original coordinate representation.

Historical development

The mathematical basis of kernel methods developed before their use in modern statistical learning. In 1909, James Mercer established the spectral expansion now associated with Mercer’s theorem. Under its standard assumptions, a continuous symmetric positive-semidefinite kernel on a compact domain admits an expansion in orthogonal eigenfunctions with nonnegative eigenvalues. This result connected integral operators, inner products, and kernel representations.

In 1950, Nachman Aronszajn gave a systematic theory of reproducing kernels and their associated Hilbert spaces. His formulation established that every positive-semidefinite kernel determines a unique reproducing kernel Hilbert space, while every such space has a corresponding reproducing kernel. This equivalence later supplied the functional-analytic interpretation of regularized kernel estimators.

The use of kernel-like similarity functions in pattern recognition became explicit during the twentieth century. In 1964, Mikhail Aizerman, Emmanuil Braverman, and Lev Rozonoer described the potential-function method, which transformed pattern-classification problems through functions of pairwise similarity. Their construction anticipated the later kernel-trick formulation, although it was developed within a different terminology and computational setting.

In 1992, Bernhard Boser, Isabelle Guyon, and Vladimir Vapnik presented the support-vector classifier in a form that used positive-semidefinite kernels to construct nonlinear decision boundaries. Their formulation combined the kernel representation with maximum-margin classification, reducing model fitting to a convex quadratic programming problem. The subsequent development of soft margins incorporated nonseparable training data through explicit penalties on margin violations.

In 1998, Bernhard Schölkopf, Alexander Smola, Klaus-Robert Müller, and You Watanabe formulated kernel principal component analysis as the eigendecomposition of a centered Gram matrix. Their treatment showed that ordinary principal component analysis in a feature space could be expressed without constructing feature coordinates. The resulting components describe orthogonal directions of variance in that space and generally correspond to nonlinear structures in the original input domain.

The representer theorem

A central structural result for kernel methods is the representer theorem. Consider an objective of the form

[ J(f)=L\bigl(f(x_1),\ldots,f(x_n)\bigr) +\lambda,\Omega\bigl(|f|_{\mathcal H}\bigr), ]

where (L) is a loss depending on evaluations at the training observations and (\Omega) is a strictly increasing function of the reproducing-kernel Hilbert-space norm. Any minimizer has a representation

[ f(\cdot)=\sum_{i=1}^{n}\alpha_i k(x_i,\cdot). ]

This expression converts optimization over an infinite-dimensional function space into optimization over the finite coefficient vector (\alpha). The theorem does not assert that the feature space itself is finite-dimensional; instead, it establishes that the component of a minimizer orthogonal to the span of the training kernel sections cannot improve the data-dependent loss and increases the norm penalty.

For squared-error loss, the theorem produces kernel ridge regression. Given target vector (y), regularization parameter (\lambda>0), and Gram matrix (K), its coefficient vector satisfies

[ (K+\lambda I)\alpha=y. ]

Predictions at a new input (x) are then given by

[ f(x)=\sum_{i=1}^{n}\alpha_i k(x_i,x). ]

The regularization term controls the Hilbert-space norm of the fitted function. Its effect depends jointly on the kernel spectrum and the scale of (\lambda), since directions associated with smaller Gram-matrix eigenvalues undergo greater relative attenuation.

Kernel construction and interpretation

The linear kernel,

[ k(x,z)=x^\mathsf Tz, ]

recovers ordinary inner-product methods. It does not introduce a nonlinear feature representation, although regularization and loss choice can still distinguish the resulting estimators from unregularized linear models.

The polynomial kernel has the form

[ k(x,z)=(\gamma x^\mathsf Tz+r)^d ]

under parameter values that preserve positive semidefiniteness. Its feature space contains monomials whose degrees are determined by (d), with coefficients controlled by (\gamma) and (r). The kernel therefore represents interactions among input coordinates without separately storing every monomial feature.

The Gaussian radial-basis kernel is

[ k(x,z)=\exp\left(-\frac{|x-z|^2}{2\sigma^2}\right). ]

It corresponds to an infinite-dimensional feature space and assigns kernel values according to Euclidean separation. The scale parameter (\sigma) determines how rapidly similarity decreases with distance, thereby changing both the spectrum of the Gram matrix and the smoothness properties of functions in the associated Hilbert space.

New positive-semidefinite kernels can be obtained from established kernels through operations that preserve positive semidefiniteness. Nonnegative weighted sums correspond to direct combinations of feature representations, while products correspond to tensor-product feature spaces. Kernels can also be defined on nonvectorial domains when a positive-semidefinite comparison exists, including structured objects represented by strings, graphs, probability distributions, or sets.

The kernel is part of the model rather than a neutral preprocessing device. Two kernels applied to the same observations generally encode different invariances and different notions of regularity. Within a reproducing-kernel Hilbert space, the norm penalizes variation according to directions determined by the kernel, so kernel selection specifies both similarity and the functional behavior favored by regularization.

Support-vector classification

For binary labels (y_i\in{-1,+1}), the soft-margin support-vector machine minimizes a regularized hinge-loss objective in the feature space. Its dual form depends on the observations through products

[ y_i y_j k(x_i,x_j). ]

The learned decision function has the expansion

[ f(x)=\sum_{i=1}^{n}\alpha_i y_i k(x_i,x)+b. ]

Only observations with nonzero coefficients contribute directly to the expansion. These observations are called support vectors, and they determine the position of the decision boundary in feature space. Their number depends on the data distribution, the regularization level, and the kernel rather than on the nominal dimensionality of the feature representation.

Convexity follows from the positive semidefiniteness of the Gram matrix and the form of the margin objective. This distinguishes the optimization problem from many nonlinear parameterizations in which the objective contains multiple local minima. The classifier itself remains nonlinear in the original input coordinates whenever the chosen kernel induces a nonlinear feature map.

Kernel principal component analysis

Ordinary principal component analysis diagonalizes a covariance matrix formed from centered observations. Kernel principal component analysis instead diagonalizes a centered Gram matrix. If (K) is the uncentered matrix and

[ H=I-\frac{1}{n}\mathbf 1\mathbf 1^\mathsf T, ]

then the centered feature-space Gram matrix is

[ K_c=HKH. ]

Centering is necessary because the feature-space mean is generally nonzero even when the original coordinates have zero mean. The eigenvectors of (K_c) provide coefficients for principal directions in the span of the centered feature vectors. Projection of a new observation requires kernel evaluations against the training sample together with the corresponding centering correction.

The method performs a linear spectral decomposition in the reproducing-kernel Hilbert space, but the resulting coordinates can trace nonlinear variation in the input domain. This distinction accounts for both its relation to principal component analysis and its classification as a nonlinear dimensionality-reduction method.

Statistical and probabilistic relations

Kernel ridge regression and Gaussian-process regression produce closely related predictive means. If a Gaussian process has covariance function (k) and independent Gaussian observation noise with variance (\lambda), its posterior mean at (x) is

[ k_x^\mathsf T(K+\lambda I)^{-1}y, ]

where (k_x) contains kernel evaluations between (x) and the training observations. This is the same point prediction obtained from kernel ridge regression under matching parameters.

Their interpretations remain distinct. Kernel ridge regression treats the reproducing-kernel Hilbert-space norm as a regularizer in an optimization problem, whereas Gaussian-process regression treats the kernel as a covariance function defining a probability distribution over functions. The probabilistic formulation additionally produces posterior variances and joint predictive distributions.

The two function spaces also differ in a technical sense. For many infinite-dimensional kernels, a sample drawn from the corresponding Gaussian process lies outside the kernel’s reproducing-kernel Hilbert space with probability one. The shared kernel nevertheless determines both the covariance structure of the stochastic process and the geometry of the regularized estimator.

Computational structure

For (n) observations, storing a dense Gram matrix requires memory proportional to (n^2). Direct matrix factorization or eigendecomposition commonly requires time proportional to (n^3), although the exact cost depends on the solver and the required output. These scaling properties arise because the standard formulation represents pairwise relations among all training observations.

Low-rank approximations replace the full Gram matrix with a representation based on a smaller subspace. The Nyström method constructs such an approximation from selected columns, while random-feature methods approximate certain shift-invariant kernels through explicit finite-dimensional maps. These approaches alter the original kernel computation by introducing a controlled finite representation.

Numerical behavior depends on the spectrum of the Gram matrix. Nearly dependent feature-space observations produce small eigenvalues, which can make unregularized systems ill-conditioned. Regularization shifts the spectrum away from zero, while centering and normalization change the matrix according to the geometric quantity represented by the analysis.