ML//kernel methods

Kernel methods are the family of learning methods that predict from a similarity between examples, a kernel \(k(x,x')\), instead of from parameters attached to the inputs one by one, and they are used where data are few and resemblance is the natural question: which past operating points look like this one, which compressor cycles resemble the one just recorded. (A kernel here has nothing to do with an operating system kernel, a GPU kernel or the kernel of a matrix, its null space.) The oldest idea in ML is behind them: to know what will happen to a new case, look at what happened to the cases that resembled it.

Kernel methods are the family of learning methods that predict from a similarity between examples, a kernel k(x,x′)k(x,x')k(x,x′), instead of from parameters attached to the inputs one by one, and they are used where data are few and resemblance is the natural question: which past operating points look like this one, which compressor cycles resemble the one just recorded. (A kernel here has nothing to do with an operating system kernel, a GPU kernel or the kernel of a matrix, its null space.) The oldest idea in ML is behind them: to know what will happen to a new case, look at what happened to the cases that resembled it.

A kernel is a similarity that equals an inner product ⟨φ(x),φ(x′)⟩\langle\varphi(x),\varphi(x')\rangle⟨φ(x),φ(x′)⟩ in some feature space, so it behaves like geometry even when that space is never built. The most used one is the Gaussian kernel,

k(x,x′)=exp⁡ ⁣(−∥x−x′∥22ℓ2)k(x,x')=\exp\!\left(-\frac{\lVert x-x'\rVert^{2}}{2\ell^{2}}\right)k(x,x′)=exp(−2ℓ2∥x−x′∥2​)

where ℓ\ellℓ is the distance at which two points stop resembling each other. Choosing the kernel and its width is the main modelling decision, the statement of what similar means.

The kernel trick buys a curved boundary without building curved features.

When an algorithm touches the data only through inner products xi⊤xjx_i^{\top}x_jxi⊤​xj​, replacing them by a kernel makes it work implicitly in another feature space, possibly infinite-dimensional, at the cost of evaluating a similarity for every pair of examples.

The members differ in what they do with the similarities. k-nearest neighbors averages the labels of the closest examples and needs no training, the simplest tool for show me similar cases in a few dimensions. Kernel regression lets every example vote with a weight that falls with distance, and returns in transformers as attention. A support vector machine finds the widest-margin boundary and keeps only the examples on it. A Gaussian process adds an explicit variance at every point, which makes it the model of choice for tuning expensive parameters such as a controller's gains on a test bench (Bayesian optimization).

Kernel method scaling is their limit: the cost grows between the square and the cube of the number of examples, O(N2)O(N^2)O(N2) to O(N3)O(N^3)O(N3), so past a few tens of thousands they become impractical, and on tables gradient boosting has displaced them. They also carry their data wherever they run, a poor fit for a microcontroller at the edge.

Every member depends on the scale of the inputs: if one variable spans 0 to 10,000 and another 0 to 1, the distance sees only the first, so inputs are standardized first (variable scaling). In many dimensions all distances look alike and nearest loses its meaning (curse of dimensionality).