Kernel method

A kernel method is a technique in machine learning and statistics that represents relationships between inputs through a kernel function. In its standard form, the kernel evaluates an inner product in an implicit feature space, allowing algorithms to model nonlinear patterns without explicitly constructing the transformed features. Kernel methods include classification, regression, and dimensionality-reduction techniques; the support vector machine is a prominent example. Their mathematical foundations connect finite matrix computations with spaces of functions that may be infinite-dimensional. (stat154.berkeley.edu)

Kernels and implicit feature spaces

For an input domain $\mathcal X$, a real-valued kernel is a function $k:\mathcal X\times\mathcal X\to\mathbb R$. Standard kernel methods require symmetry and positive semidefiniteness: for every finite collection $x_1,\ldots,x_n$ and real coefficients $c_1,\ldots,c_n$,

Equivalently, the Gram matrix $K$, whose entries are $K_{ij}=k(x_i,x_j)$, must be positive semidefinite. Although such functions are often called positive-definite kernels, strict positivity is not required. An arbitrary similarity score need not satisfy this condition. (gaussianprocess.org)

A valid kernel admits a representation

where $\phi$ maps inputs into a Hilbert space, a complete inner-product vector space. The kernel trick replaces inner products in an algorithm with kernel evaluations. Computation can therefore depend on pairs of original inputs rather than on all coordinates of $\phi(x)$. A model linear in feature space can be nonlinear in the original variables. This does not mean that every algorithm can be kernelized merely by substituting a similarity function. (stat154.berkeley.edu)

Common kernel functions

For vectors $x,z\in\mathbb R^d$, several kernels are widely used:

• Linear kernel: $k(x,z)=x^\top z$, retaining the original inner-product representation.
• Polynomial kernel: $k(x,z)=(\gamma x^\top z+c)^p$, with nonnegative $\gamma,c$ and positive integer $p$. It represents weighted combinations of polynomial features.
• Gaussian radial basis function kernel: $k(x,z)=\exp(-\gamma\|x-z\|^2)$, with $\gamma>0$. Similarity decreases with squared Euclidean distance, and its exact feature representation is infinite-dimensional. (gaussianprocess.org)

Kernels can also compare strings, trees, and other structured objects. Their design specifies which shared structures count as similarity, making kernel selection a form of feature engineering. Nonnegative weighted sums and pointwise products of valid kernels remain valid, enabling composite representations. Kernel parameters encode assumptions about relevant scales, smoothness, and interactions rather than serving only as numerical settings. (gaussianprocess.org)

Function spaces and regularization

Every positive-semidefinite kernel determines a reproducing kernel Hilbert space (RKHS), whose functions satisfy

Thus evaluation at a point is itself an inner-product operation. In supervised learning, a common regularized objective is

where $L$ is a loss function and $(x_i,y_i)$ are training data. The norm penalty controls complexity relative to the chosen kernel. (stat154.berkeley.edu)

The representer theorem states, under suitable conditions, that a minimizer has the finite expansion

An infinite-dimensional search consequently reduces to finding finitely many coefficients. The theorem provides a representation, not a guarantee of low computational cost or good predictive performance. With convex loss and a squared RKHS-norm penalty, this formulation yields a convex optimization problem. (stat154.berkeley.edu)

Principal applications

Kernel support vector classification fits a separating hyperplane in feature space while balancing margin width against classification errors. Its prediction function uses kernel evaluations against support vectors, typically a subset of the training examples. Support vector regression applies related principles to continuous outputs. (scikit-learn.org)

Kernel ridge regression extends ridge regression to an RKHS. For the objective $\sum_i(y_i-f(x_i))^2+\lambda\|f\|_{\mathcal H}^2$, coefficients can be chosen as

with the system normally solved numerically rather than by explicitly forming an inverse. (stat.berkeley.edu)

Kernel principal component analysis performs dimensionality reduction using the eigenstructure of a centered kernel matrix. In Gaussian process models, a kernel instead specifies covariance between function values. These approaches share kernel mathematics but differ in their objectives and interpretations. (scikit-learn.org)

Model selection and computational limits

Kernel choice, scale parameters, and regularization strength affect flexibility and overfitting. They are often selected through cross-validation. Feature scaling changes distance-based kernels substantially; for an RBF kernel, a large $\gamma$ produces highly localized similarity, whereas a small value produces broader similarity. Kernelization does not remove sensitivity to input representation. (scikit-learn.org)

Explicit storage of a dense $n\times n$ kernel matrix requires $O(n^2)$ memory. Standard dense factorizations used in exact kernel ridge regression require approximately $O(n^3)$ operations, although iterative solvers and specialized structure can change these costs. Avoiding explicit feature coordinates therefore does not eliminate dependence on sample size. (gaussianprocess.org)

The Nyström method approximates a kernel representation using selected training examples as a basis. Random Fourier features approximate suitable shift-invariant kernels through randomized explicit features. Both permit subsequent training with linear algorithms, trading approximation error against memory and computation; their feature dimension becomes an additional model-design parameter. (scikit-learn.org)