Kernel Methods

Kernel methods compute inner products in a high-dimensional space implicitly, letting linear algorithms learn nonlinear patterns.

Nonlinearity without coordinates

Many algorithms depend on the data only through inner products between points. A kernel function K(x, x') computes the inner product of x and x' in some high-dimensional feature space, without ever mapping the points into that space or storing their coordinates. This is the kernel trick: it gives a linear method nonlinear power at the cost of a single function evaluation per pair.

Common kernels

• Linear: K(x,x') = x . x'; recovers the original linear method.
• Polynomial: K(x,x') = (x . x' + c)^d; boundaries of degree d.
• RBF (Gaussian): K(x,x') = exp(-gamma ||x - x'||^2); flexible, local, the common default.
• A valid kernel must be symmetric and positive semi-definite (Mercer's condition).

Where it is used

Support vector machines are the best-known kernel method: the maximum-margin boundary depends only on inner products, so swapping in a kernel yields nonlinear boundaries. Kernel PCA, Gaussian processes, and kernel ridge regression apply the same idea to dimensionality reduction, probabilistic regression, and regularized least squares.

import numpy as np
def rbf(X, Y, gamma):
    d = np.sum(X**2,1)[:,None] + np.sum(Y**2,1) - 2*X@Y.T
    return np.exp(-gamma*d)

Strengths and limits

Kernels handle nonlinearity elegantly and work well on modest datasets. Their weakness is scale: computing and storing the kernel matrix costs on the order of n-squared, so plain kernel methods struggle beyond tens of thousands of points. Random Fourier features and other approximations restore scalability by approximating the kernel with an explicit low-dimensional map.