Kernel Trick

This is mainly about how we deal with nonlinear classification.

The idea is that we want to do a non-linear transformation $\mathbf{z}=\varphi (\mathbf{x})$ such that the nonlinear input space becomes a linearly separable feature space.

Let’s say we want to model a 2nd order polynomial (quadratic) decision function, we have to do transformation $X\to Z$, where $X\subset {\mathbb{R}}^D$ and $Z\subset {\mathbb{R}}^D$, where $D=\frac{d(d+3)}{2}$.

We would have to do mapping for three different terms:

1. Linear → $z^1=x^1,\dots ,z^d=x^d$ (total of $d$ coordinates): to model straight lines
2. Square → $z^{d+1}=(x^1{)}^2,\dots ,(z^d{)}^2$ (total of $d$ coordinates): to model circles / ellipses
3. Cross → $z^{2d+1}=x^1{x}^2,\dots ,z^D$ (total of $\frac{d(d-1)}{2}$ coordinates): to model curves

This is bad because (1) A lot of compute is needed, (2) Dimensionality increasing.

So we have the kernel trick. Following Optimal Hyperplane solution, we have:

$$f(\mathbf{x})=\text{sgn}\left\{\sum _{i=1}^n{\alpha }^{\ast }{y}_i({\mathbf{x}}_i\cdot \mathbf{x})+b^{\ast }\right\}$$

Notice that we are only using the inner-products of the transformed vector. We can just define $\mathbf{x}\to \varphi (\mathbf{x})$ and then $(\varphi (x_i)\cdot \varphi ({\mathbf{x}}_j))=K({\mathbf{x}}_i,{\mathbf{x}}_j)$. In this way, we don’t have to store each of the mapping, just take the inner product!

Dual Problem with Kernel Trick

$$\underset{\alpha }{\max }Q(\alpha )=\sum _{i=1}^l{\alpha }_i-{\frac{1}{2}}_{i,j=1}^l{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j)$$

We transform the decision function into:

$$f(\mathbf{x})=\text{sgn}\left\{\sum _{i=1}^l{\alpha }_i^{\ast }{y}_{i}K({\mathbf{x}}_i,\mathbf{x})+b^{\ast }\right\}$$

To determine whether the Kernel $K$ is a proper kernel, we have to fulfill the Mercer Theorem. And Here is a list of Commonly Used Kernels.