Tag Info

Kernel methods are used in machine learning to generalize linear techniques to nonlinear situations, especially SVMs, PCA, and GPs. Not to be confused with [kernel-smoothing], for kernel density estimation (KDE) and kernel regression.

In machine learning, the kernel trick is a widely applied method to generalize linear techniques to non-linear cases. The most widely used applications include support vector machines (for classification, regression, and anomaly detection), Gaussian processes (for classification and regression), and principal components analysis (for dimensionality reduction). Such uses are also known as kernel methods.

A kernel is a function $$k : \mathcal X \times \mathcal X \to \mathbb R$$ that can be thought of roughly as a similarity function on the domain $$\mathcal X$$. Kernel functions exist for many domains, including $$\mathbb R^n$$ (in which case they can allow more complicated nonlinear relationships) as well as sets, graphs, strings, probability distributions, and other complicated objects. César R. Souza has cataloged many common kernel functions in Kernel Functions for Machine Learning Applications.

The kernel trick works because if $$k$$ is a positive semidefinite function, then there is a corresponding Hilbert space $$\mathcal H$$, known as the reproducing kernel Hilbert space (RKHS) of $$k$$, and a "feature map" $$\varphi : \mathcal X \to \mathcal H$$ such that $$k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$$. Thus, if an algorithm accesses the data only in the form of inner products $$x^T y$$, it can be "kernelized" by simply replacing those inner products with $$k(x, y)$$, in which case it corresponds to performing the algorithm in the Hilbert space $$\mathcal H$$. For many common kernels, $$\mathcal H$$ is very high- or even infinite-dimensional, so that actually representing the data in that space would be impossible, but by using pairwise kernel evaluations the algorithm can still be run.

For large datasets, pairwise evaluations can be too computationally expensive to be practical. In these cases approximations such as the Nyström method (which approximates the kernel function based on kernel evaluations to landmark points) or approximate embeddings (which give a function $$z : \mathcal X \to \mathbb R^D$$ such that $$z(x)^T z(y) \approx k(x, y)$$) can be used.

Note that the word "kernel" is also used to refer to the local similarity functions of kernel smoothing techniques like kernel density estimation and Nadaraya-Watson kernel regression. See for this usage.