https://www.microsoft.com/en-us/research/uploads/prod/2006/01/Bishop-Pattern-Recognition-and-Machine-Learning-2006.pdf

University of Michigan - Ann Arbor

Kernels are used as a computational “trick” to compute the dot product of two vectors in some new feature space. Kernels can be generally thought of as a measure of distance, and are denoted by $K(\vec{x}_1, \vec{x}_2)$. When we look at the dual formulation of the SVM problem, we see that our feature vectors are now isolated in a dot product. By switching out this dot product for the term $K(\vec{x}^i, \vec{x}^j)$, we can learn non-linear decision boundaries in our original feature space. 

For anyone studying math, notice how similar this is to the general notion of an inner-product, however be cautious because the kernel need-not be an inner product. 

We can also think of kernels as an *implicit* feature mapping. This is what is meant by a computational trick (see child node on "Proof of Quadratic Kernel" to see the relationship between one kernel and its *explicit* feature mapping). 


Kernels

One popular kernel is the Quadratic Kernel. Below we prove the kernel with a given set of parameters.

From the below proof we see what is meant by an implicit feature mapping. Instead of computing $f(\vec{x}), f(\vec{z})$, then $f(\vec{x}) \cdot f(\vec{z})$, we compute the kernel and skip 1 step of computation.

To see how the kernel and a feature mapping work together, lets prove that the feature mapping 

$f: \mathbb{R}^2 \to \mathbb{R}^5 \text{ where } f([x_1 x_2]^T) = [x_1^2 \ x_1 \ x_2 \ \sqrt{2}x_1x_2 \ x_2^2 \ 1]^2$  

corresponds to the kernel $K(\vec{x},\vec{z}) = (\vec{x} \cdot \vec{z} + 1)^2$. 

(Capture generated by myself on overleaf.com)

Proof of Quadratic Kernel

Pattern Recognition and Machine Learning, Bishop

Basic types of kernel functions include:

- **Polynomial Kernel**: $$K(x, y) = (x \cdot y + 1)^p$$
- **Radial Basis Function (RBF) Kernel**: $$K(x, y) = \exp\left(-\frac{||x - y||^2}{2\sigma^2}\right)$$
- **Sigmoid Kernel**: $$K(x, y) = \tanh(C(x \cdot y) + \delta)$$

Learn Before

Related