What Are Kernel Machines?

Kernel machines are a family of machine learning algorithms that operate on data through a kernel function, a similarity measure that computes inner products in a high-dimensional feature space without ever constructing coordinates in that space. A function k(x, x') qualifies as a kernel when it is symmetric and positive semi-definite, conditions that by Mercer's theorem guarantee the existence of a feature map into a Hilbert space where k(x, x') equals the inner product of the mapped points. Replacing every inner product in a linear algorithm with a kernel evaluation converts that algorithm into a nonlinear one at no change in the optimization structure, a substitution known as the kernel trick.

The approach grew out of statistical learning theory in the 1960s through 1990s, combining Aronszajn's theory of reproducing kernel Hilbert spaces with Vapnik and Chervonenkis's work on generalization bounds. Kernel machines dominated applied machine learning through the 2000s because they gave convex training problems, principled capacity control, and strong empirical accuracy on datasets of modest size. They remain the standard tool wherever data are scarce, structured, or non-vectorial.

Reproducing Kernel Hilbert Spaces

The mathematical foundation is the reproducing kernel Hilbert space, or RKHS, a function space in which evaluation at a point is a bounded linear functional and every function can be written as a combination of kernel evaluations. The Moore-Aronszajn theorem establishes a one-to-one correspondence between positive-definite kernels and such spaces, so choosing a kernel is equivalent to choosing the hypothesis class. The representer theorem then guarantees that the solution to a regularized empirical risk minimization problem over an RKHS lies in the span of the kernels centered on the training points, which reduces an infinite-dimensional optimization to a finite one in n coefficients. A tutorial on RKHS, Mercer's theorem, and the use of kernels in machine learning develops these results together with the construction rules that let practitioners build valid kernels by summing, scaling, or composing simpler ones.

Algorithms and Kernel Design

The support vector machine is the best known kernel machine, fitting a maximum-margin separating hyperplane in feature space and expressing the solution through a sparse subset of training points. The same substitution produces kernel ridge regression, kernel principal component analysis, support vector regression, Gaussian process regression, and kernel-based two-sample tests such as maximum mean discrepancy. Kernel choice encodes the assumed structure of the problem. Radial basis function kernels impose smoothness at a length scale set by their bandwidth, polynomial kernels capture bounded-order feature interactions, and specialized string, graph, and tree kernels apply the machinery to objects that have no natural vector representation, which is why the methods took hold in bioinformatics and text classification.

Scalability and Links to Neural Networks

The main practical limit is cost. Training requires forming and factoring an n by n Gram matrix, giving quadratic memory and roughly cubic time in the number of examples. Approximation methods address this by replacing exact kernel evaluation with a low-dimensional explicit feature map, most influentially the random Fourier features introduced for large-scale kernel machines, which sample frequencies from the Fourier transform of a shift-invariant kernel and then apply fast linear solvers. Nystrom subsampling and hierarchical matrix factorizations pursue the same goal differently. Kernel theory has also returned as an analytical tool for deep learning: the neural tangent kernel shows that infinitely wide networks trained by gradient descent evolve as kernel regression under a fixed limiting kernel.

Applications

Kernel machines have applications in a wide range of fields, including:

• Bioinformatics, including protein classification and gene expression analysis
• Text categorization and information retrieval
• Image and handwritten character recognition
• Fault detection and condition monitoring in industrial systems
• Financial time series modeling and credit scoring
• Geostatistics and surrogate modeling for engineering simulation