Kernels

In the dual form, the data appears only through inner products ${\mathbf{x}}_i^{\top }{\mathbf{x}}_j$. The kernel trick replaces each inner product with a kernel $k({\mathbf{x}}_i,{\mathbf{x}}_j)=\varphi ({\mathbf{x}}_i{)}^{\top }\varphi ({\mathbf{x}}_j)$ — an inner product in some feature space — without ever computing $\varphi$.

This lets SVMs work in very high-dimensional, even infinite-dimensional, feature spaces at the cost of computing a kernel between pairs of points.

• Linear: $k={\mathbf{x}}^{\top }\mathbf{z}$.
• Polynomial: $k=({\mathbf{x}}^{\top }\mathbf{z}+c{)}^p$ — all feature products up to degree $p$.
• RBF (Gaussian): $k=\exp (-\gamma \Vert \mathbf{x}-\mathbf{z}{\Vert }^2)$ — similarity that decays with distance; corresponds to an infinite-dimensional space.