KernelTrick

The kernel trick is a technique in machine learning and statistics that enables linear learning algorithms to model nonlinear relationships by implicitly mapping data into a high-dimensional feature space without computing the map explicitly.

It relies on a kernel function k(x, y) that computes the inner product φ(x)·φ(y) in the feature space, where φ maps input vectors x to a feature representation. The trick avoids explicit φ by evaluating k directly on inputs. For this to correspond to a dot product in some feature space, the kernel must be positive semi-definite (Mercer condition).

Common kernels include linear (k(x, y) = x·y), polynomial (k(x, y) = (α x·y + c)^d), radial basis function (Gaussian) k(x, y) = exp(-||x−y||^2/(2σ^2)), and sigmoid. The Gaussian kernel corresponds to an infinite-dimensional feature space.

The kernel trick is central to kernel methods such as support vector machines for classification and regression, kernel ridge regression, and kernel principal component analysis. The computational bottleneck is forming and operating on the kernel (Gram) matrix of size n×n, where n is the number of samples.

Limitations include choosing an appropriate kernel and hyperparameters, possible overfitting, and reduced interpretability. Practical concerns also include scaling, numerical stability, and computational cost for large data sets.