kernel trick

Topics

• ml paradigm
• kernel methods

Kernel Trick is a technique used in machine learning algorithms. Allows algorithms designed for linear data to handle non-linear data. This is done by implicitly mapping data into a higher-dimensional “feature space” where it becomes linearly separable.

Explicitly computing this mapping $\varphi (x)$ and working in the high-dimensional space can be computationally expensive or impossible, especially if the space is very high or infinite dimensional. Let’s illustrate this with an example: suppose $x\in {\mathbb{R}}^d$ , and let $\varphi (x)$ be the vector that contains all the monomials of x with degree $\le 3$:

$$\varphi (x)=\left[\begin{array}{c}1\\ x_1\\ ⋮\\ x_1^2\\ x_1{x}_2\\ ⋮\\ x_2{x}_1\\ x_1^3\\ x_1^2{x}_2\\ ⋮\end{array}\right]$$

The “trick” is that many linear machine learning algorithms (such as the SVM dual formulation and PCA) only require calculating dot products (inner product) between data points. The kernel trick defines a function, called a kernel function $K(x,z)$, that directly computes (we don’t need to transform $x\to \varphi (x)$) the dot product of the data points after they have been mapped to the higher-dimensional space, i.e.,

$$K(x,z)=\varphi (x{)}^T\varphi (z)$$

By replacing the original dot product $x^{T}z$ with $K(x,z)$ in the algorithm, the model behaves as if it is operating in the high-dimensional feature space without ever needing to explicitly compute the coordinates in that space or the mapping function $\varphi$. This avoids the computational burden of explicit feature mapping.

Note

A function $K$ is a valid kernel if it corresponds to a dot product in some feature space (satisfies mercer’s condition).

Related

• popular kernels used in ml