Kernel Trick

Linear methods draw straight lines. To get curves, you could invent new features, for example add $x_1^2$, $x_2^2$ and $x_1 x_2$, and run the linear method on those. That is feature engineering, and it gets expensive fast: with many inputs the number of combinations explodes.

The kernel trick notices that some algorithms, notably support vector machines, never need the features themselves. They only need the dot product between pairs of examples, a measure of similarity. So replace that dot product with a kernel function that returns the similarity as if the points had been mapped to the bigger space.

The math

A kernel is a function $k(x, x') = \langle \varphi(x), \varphi(x') \rangle$. Common choices:

• Polynomial: $k(x, x') = (x \cdot x' + c)^d$, all feature products up to degree $d$.
• RBF (Gaussian): $k(x, x') = \exp(-\gamma \lVert x - x' \rVert^2)$. Its feature map $\varphi$ is infinite-dimensional, yet each similarity costs one distance.

Any symmetric function whose similarity matrix is always positive semi-definite (Mercer’s condition) is a valid kernel.

The catch is scale: you need a similarity for every pair of training examples, so millions of examples become impractical. That limit is one reason neural networks, which learn their own features, took over on large datasets. The trick lives on in the wider kernel methods family.