In applied mathematics, a kernel function is a real-valued function that implicitly maps input data from a lower-dimensional space into a higher-dimensional (often infinite-dimensional) feature space, enabling the application of linear algorithms to nonlinear problems. It is central to kernel methods such as support vector machines, kernel principal component analysis, and Gaussian processes. Formally, for a set of points, a kernel corresponds to an inner product in the feature space, and must satisfy certain conditions (e.g., symmetry and positive definiteness) to ensure the existence of such a mapping.
1.1 Definition
1.1.1 Mathematical form
A kernel function \( k: \mathcal{X} \times \mathcal{X} \to \mathbb{R} \) is defined such that there exists a feature map \( \phi: \mathcal{X} \to \mathcal{H} \) into a Hilbert space \( \mathcal{H} \) with the property \( k(x, x') = \langle \phi(x), \phi(x') \rangle_{\mathcal{H}} \). This representation allows the kernel to compute inner products in the feature space without explicitly constructing the mapping.
1.1.2 Positive definiteness and Mercer's theorem
A kernel is said to be positive definite if for any finite set of points \( \{x_1, \dots, x_n\} \subset \mathcal{X} \) and any real coefficients \( c_1, \dots, c_n \), the quadratic form \( \sum_{i,j} c_i c_j k(x_i, x_j) \geq 0 \). Mercer's theorem characterizes such kernels: a continuous, symmetric, positive definite kernel on a compact domain can be expressed as a uniformly convergent series of eigenfunctions and eigenvalues.
1.1.2.1 Mercer condition
The Mercer condition requires that the kernel matrix \( K_{ij} = k(x_i, x_j) \) be positive semi-definite for all finite sets of input points. This condition is both necessary and sufficient for the existence of a reproducing kernel Hilbert space (RKHS) and is the standard criterion for kernel admissibility.
1.1.3 Reproducing kernel Hilbert space (RKHS)
Associated with each positive definite kernel \( k \) is a unique Hilbert space \( \mathcal{H}_k \) of functions on \( \mathcal{X} \) with the reproducing property: \( f(x) = \langle f, k(\cdot, x) \rangle_{\mathcal{H}_k} \) for all \( f \in \mathcal{H}_k \). The RKHS provides a theoretical framework for many kernel methods, allowing linear operations in the feature space.
1.2 Types of kernels
1.2.1 Linear kernel
The linear kernel is defined as \( k(x, x') = x^\top x' \). It corresponds to the identity feature mapping and yields a linear decision boundary in the input space. It is computationally efficient but limited in expressiveness.
1.2.2 Polynomial kernel
Given by \( k(x, x') = (x^\top x' + c)^d \) where \( c \geq 0 \) and \( d \in \mathbb{N} \) is the degree, the polynomial kernel maps data into a feature space of monomials up to degree \( d \). It introduces nonlinear interactions among input features.
1.2.3 Gaussian (radial basis function) kernel
| The Gaussian kernel, also known as the radial basis function (RBF) kernel, is \( k(x, x') = \exp(-\frac{\|x - x'\|^2}{2\sigma^2}) \), with bandwidth parameter \( \sigma > 0 \). It corresponds to an infinite-dimensional feature space and is widely used due to its universal approximation property. |
|---|
1.2.4 Sigmoid kernel
Defined as \( k(x, x') = \tanh(\alpha x^\top x' + c) \), the sigmoid kernel is inspired by neural networks. It is not positive definite for all parameter choices but is used in practice, particularly in support vector machines.
1.2.5 Laplace kernel
| The Laplace kernel is \( k(x, x') = \exp(-\frac{\|x - x'\|_1}{\sigma}) \), using the L1 norm. It is less smooth than the Gaussian kernel and can be more robust to outliers. |
|---|
1.2.6 Exponential kernel
| The exponential kernel is \( k(x, x') = \exp(-\frac{\|x - x'\|}{\sigma}) \) for any norm. It is a special case of the Laplace kernel when using the L2 norm? Actually the Laplace uses L1; the exponential kernel typically uses L2 norm so is same as Gaussian? No, Gaussian has squared norm. The exponential kernel uses unsquared norm: \(\exp(-\gamma \|x-x'\|)\). It yields non-smooth (continuous but not differentiable) functions. |
|---|
1.2.6.1 Matern kernel
| The Matern kernel is a generalization given by \( k(x, x') = \frac{2^{1-\nu}}{\Gamma(\nu)} \left( \frac{\sqrt{2\nu}\|x-x'\|}{\rho} \right)^\nu K_\nu \left( \frac{\sqrt{2\nu}\|x-x'\|}{\rho} \right) \), where \( \nu > 0 \) controls smoothness, \( \rho > 0 \) is a length scale, and \( K_\nu \) is the modified Bessel function. It includes the exponential kernel (\( \nu = 0.5 \)) and the Gaussian kernel (\( \nu \to \infty \)) as limiting cases. |
|---|
1.3 Properties
1.3.1 Symmetry
For all \( x, x' \in \mathcal{X} \), \( k(x, x') = k(x', x) \). This follows from the symmetry of the inner product in the feature space.
1.3.2 Positive semi-definiteness
A kernel must be positive semi-definite: for any finite set of points, the Gram matrix \( K \) is positive semi-definite. This ensures the existence of an RKHS and a valid inner product interpretation.
1.3.3 Closure properties (sum, product, scaling)
Kernels are closed under several operations: if \( k_1 \) and \( k_2 \) are kernels, then so are \( k_1 + k_2 \), \( k_1 \cdot k_2 \), and \( c \cdot k_1 \) for any \( c \geq 0 \). Additionally, if \( f \) is any function, then \( k(f(x), f(x')) \) is a kernel. These properties allow construction of complex kernels from simple ones.
1.4 Kernel trick
1.4.1 Implicit feature mapping
The kernel trick refers to the use of a kernel function to replace inner products in a high-dimensional feature space without explicitly computing the feature vectors. Many linear algorithms (e.g., SVM, PCA) depend only on inner products, so they can be "kernelized" by substituting a suitable kernel.
1.4.2 Computational advantage
The kernel trick avoids the computational cost of explicitly mapping data to a high- or infinite-dimensional space. Instead, the kernel function is evaluated directly on input pairs, often at \( O(d) \) or \( O(n^2) \) cost, making large-scale applications feasible.
2.1 Support vector machines (SVM)
Support vector machines use kernels to construct nonlinear decision boundaries. By mapping data into a higher-dimensional feature space, SVM finds a maximum-margin hyperplane. The kernel trick allows this separation to correspond to a nonlinear decision function in the input space.
2.1.1 Soft-margin SVM
In the presence of noise or non-separable data, soft-margin SVM introduces slack variables to allow misclassifications. The kernel still applies, and the optimization problem seeks a trade-off between margin maximization and error minimization, controlled by a regularization parameter \( C \).
2.1.2 Kernel selection strategies
Choosing a kernel often depends on domain knowledge and data properties. Common strategies include cross-validation over kernel parameters (e.g., \( \sigma \) for RBF, degree for polynomial), using multiple kernels, or employing automatic relevance determination.
2.2 Kernel principal component analysis (KPCA)
Kernel PCA applies PCA in a feature space induced by a kernel. Instead of linear principal components, it finds directions that maximize variance in that space. The eigenvectors of the kernel matrix give the principal component projections without explicit mapping.
2.3 Kernel ridge regression
Kernel ridge regression combines ridge regression (L2 regularization) with the kernel trick. The solution is given by \( \alpha = (K + \lambda I)^{-1} y \), where \( K \) is the kernel matrix and \( \lambda > 0 \) is a regularization parameter. It provides a nonlinear regression method with a closed-form solution.
2.4 Gaussian processes
2.4.1 Covariance functions as kernels
In Gaussian processes (GPs), the kernel function defines the covariance between function values at different input points. Every positive definite kernel corresponds to a valid covariance function for a GP, determining properties such as smoothness and periodicity.
2.4.1.1 Automatic relevance determination (ARD)
ARD kernels extend standard kernels by assigning a separate length-scale parameter to each input dimension. This allows the GP to automatically learn which features are most relevant, effectively performing feature selection during training.
2.5 Kernel density estimation
Kernel density estimation (KDE) is a nonparametric method for estimating probability density functions. It uses a kernel (often a symmetric probability density) to smooth the empirical distribution. Common kernels in KDE include Gaussian, Epanechnikov, and triangular kernels.
2.6 Kernel mean embedding of distributions
2.6.1 Maximum mean discrepancy (MMD)
| The kernel mean embedding maps a probability distribution \( P \) to an element \( \mu_P = \mathbb{E}_{x \sim P}[k(\cdot, x)] \) in the RKHS. The maximum mean discrepancy between two distributions is the distance between their embeddings: \( \text{MMD}(P, Q) = \|\mu_P - \mu_Q\|_{\mathcal{H}} \). It is used in two-sample testing, domain adaptation, and generative modeling. |
|---|
3.1 Deep kernels and neural tangent kernels (NTK)
Deep kernels combine deep neural network architectures with kernel methods, often by learning a kernel from data. The neural tangent kernel (NTK) describes the training dynamics of infinitely wide neural networks under gradient descent, relating them to kernel regression.
3.1.1 Infinite-width limit
In the limit of infinite width, a neural network with random initialization becomes equivalent to a Gaussian process with a specific kernel (the NTK). This connection provides theoretical insights into generalization and optimization in deep learning.
3.2 Multiple kernel learning (MKL)
3.2.1 Convex combinations
Multiple kernel learning seeks to combine several base kernels to improve performance or interpretability. A common approach is to learn convex coefficients \( \theta_m \geq 0 \) with \( \sum_m \theta_m = 1 \) such that the combined kernel \( k = \sum_m \theta_m k_m \) is used in a kernel method.
3.2.2 Non-convex combinations
Non-convex combinations, such as product or exponentiated combinations of kernels, can capture more complex interactions. These are harder to optimize but may yield better performance on structured data.
3.3 Approximate kernel methods
3.3.1 Random Fourier features
Random Fourier features approximate shift-invariant kernels (e.g., Gaussian) by randomly sampling from the Fourier transform of the kernel. This yields an explicit low-dimensional feature map, enabling linear algorithms to achieve near-kernel accuracy with reduced computational cost.
3.3.2 Nyström approximation
The Nyström method approximates the kernel matrix using a low-rank factorization based on a subset of columns. It selects \( m \) landmarks and computes the kernel between all points and those landmarks, then reconstructs the full matrix, reducing complexity from \( O(n^3) \) to \( O(nm^2) \).
3.4 Graph kernels
3.4.1 Weisfeiler–Lehman kernel
The Weisfeiler–Lehman (WL) kernel compares graphs based on iterative color refinement. It assigns colors to nodes based on neighborhood structure, then counts color sequences across iterations. The kernel is efficient and expressive for graph classification.
3.4.2 Random walk kernel
The random walk kernel counts the number of common walks in two graphs. It is defined as \( k(G, G') = \sum_{i,j} \sum_{t=0}^\infty \lambda_t (A^t)_{ij} \), where \( A \) is a product adjacency matrix. Variants include the graphlet kernel and the shortest-path kernel.