Kernel method

Mathematics: the kernel trick

The kernel trick avoids the explicit mapping that is needed to get linear learning algorithms to learn a nonlinear function or decision boundary. For all ${\displaystyle \mathbf{x}}$ and ${\displaystyle {\mathbf{x}}^{\prime }}$ in the input space ${\displaystyle \mathcal{X}}$, certain functions ${\displaystyle k(\mathbf{x},{\mathbf{x}}^{\prime })}$ can be expressed as an inner product in another space ${\displaystyle \mathcal{V}}$. The function ${\displaystyle k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}}$ is often referred to as a kernel or a kernel function. The word "kernel" is used in mathematics to denote a weighting function for a weighted sum or integral.

Certain problems in machine learning have more structure than an arbitrary weighting function ${\displaystyle k}$. The computation is made much simpler if the kernel can be written in the form of a "feature map" ${\displaystyle \phi :\mathcal{X}\to \mathcal{V}}$ which satisfies $${\displaystyle k(\mathbf{x},{\mathbf{x}}^{\prime })=⟨\phi (\mathbf{x}),\phi ({\mathbf{x}}^{\prime }){⟩}_{\mathcal{V}}.}$$The key restriction is that ${\displaystyle ⟨\cdot ,\cdot {⟩}_{\mathcal{V}}}$ must be a proper inner product. On the other hand, an explicit representation for ${\displaystyle \phi }$ is not necessary, as long as ${\displaystyle \mathcal{V}}$ is an inner product space. The alternative follows from Mercer's theorem: an implicitly defined function ${\displaystyle \phi }$ exists whenever the space ${\displaystyle \mathcal{X}}$ can be equipped with a suitable measure ensuring the function ${\displaystyle k}$ satisfies Mercer's condition.

Mercer's theorem is similar to a generalization of the result from linear algebra that associates an inner product to any positive-definite matrix. In fact, Mercer's condition can be reduced to this simpler case. If we choose as our measure the counting measure ${\displaystyle \mu (T)=|T|}$ for all ${\displaystyle T\subset X}$, which counts the number of points inside the set ${\displaystyle T}$, then the integral in Mercer's theorem reduces to a summation$${\displaystyle \sum _{i=1}^n\sum _{j=1}^{n}k({\mathbf{x}}_i,{\mathbf{x}}_j)c_i{c}_j\ge 0.}$$If this summation holds for all finite sequences of points ${\displaystyle ({\mathbf{x}}_1,\dots ,{\mathbf{x}}_n)}$ in ${\displaystyle \mathcal{X}}$ and all choices of ${\displaystyle n}$ real-valued coefficients ${\displaystyle (c_1,\dots ,c_n)}$ (cf. positive definite kernel), then the function ${\displaystyle k}$ satisfies Mercer's condition.

Some algorithms that depend on arbitrary relationships in the native space ${\displaystyle \mathcal{X}}$ would, in fact, have a linear interpretation in a different setting: the range space of ${\displaystyle \phi }$. The linear interpretation gives us insight about the algorithm. Furthermore, there is often no need to compute ${\displaystyle \phi }$ directly during computation, as is the case with support-vector machines. Some cite this running time shortcut as the primary benefit. Researchers also use it to justify the meanings and properties of existing algorithms.

Theoretically, a Gram matrix ${\displaystyle \mathbf{K}\in {\mathbb{R}}^{n\times n}}$ with respect to ${\displaystyle \{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_n\}}$ (sometimes also called a "kernel matrix"), where ${\displaystyle K_{ij}=k({\mathbf{x}}_i,{\mathbf{x}}_j)}$, must be positive semi-definite (PSD). Empirically, for machine learning heuristics, choices of a function ${\displaystyle k}$ that do not satisfy Mercer's condition may still perform reasonably if ${\displaystyle k}$ at least approximates the intuitive idea of similarity. Regardless of whether ${\displaystyle k}$ is a Mercer kernel, ${\displaystyle k}$ may still be referred to as a "kernel".

If the kernel function ${\displaystyle k}$ is also a covariance function as used in Gaussian processes, then the Gram matrix ${\displaystyle \mathbf{K}}$ can also be called a covariance matrix.

Applications

Application areas of kernel methods are diverse and include geostatistics, kriging, inverse distance weighting, 3D reconstruction, bioinformatics, cheminformatics, information extraction and handwriting recognition.

Popular kernels

• Fisher kernel
• Graph kernels
• Kernel smoother
• Polynomial kernel
• Radial basis function kernel (RBF)
• String kernels
• Neural tangent kernel
• Neural network Gaussian process (NNGP) kernel