Kernel Methods and Gaussian Processes — The Champions Before Neural Nets

Before deep learning took over, kernel SVMs held the crown in classification. This article builds the whole story from zero: the kernel trick that makes lifting into high dimensions free, Gaussian processes that put a probability distribution over functions, and Bayesian optimization that turns uncertainty into a weapon.

Practical Bayesian Optimization of Machine Learning Algorithms

A problem a single ruler cannot cut

Picture red and blue markers scattered on a table. The red ones cluster in the middle; the blue ones form a ring around them. Now lay down a single ruler and separate red from blue cleanly. You can't. A straight line has no way to carve out an enclosed interior.

But grab the tablecloth by its center and lift. The red markers rise; the blue ones stay low. Slide a flat board in horizontally, and a single perfectly straight cut separates the two colors.

That is where kernel methods begin. A problem that seems to demand a curved boundary becomes straight-line separable once you lift the data into a higher-dimensional space. And the real subject of this article is the second half of that sentence: how to make the lifting cost nothing.

Write the lift down explicitly and the dimensions explode

The lifting operation is a function called a feature map, written $\phi$. It takes an input $x$ and moves it into a different, higher-dimensional space.

For the ring above, mapping the 2D point $(x_1, x_2)$ to $(x_1, x_2, x_1^2 + x_2^2)$ is enough. The third coordinate is the squared distance from the origin, so the center markers sit low and the outer ring sits high — exactly the lifted tablecloth.

The trouble starts when you don't know in advance how the boundary curves. If you play it safe and lift exhaustively — "include every term up to degree three" — the dimension grows combinatorially. From $d$ features, the number of degree-three terms is $\binom{d+2}{3}$, which for $d = 1000$ is 167,167,000. Transforming a single data point would produce 167 million numbers, and holding that for tens of thousands of points is not something you do.

The trick: only the inner product matters

Here is the observation that changes everything. Most classification and regression algorithms never actually need $\phi(x)$ itself. What they need is "how similar are $\phi(x)$ and $\phi(y)$" — that is, the inner product of two vectors, and nothing more.

The inner product as a yardstick for similarity is the same idea that drives Attention from Scratch: vectors pointing in the same direction have a large dot product. That is what "similar" means mathematically.

So let's define that inner product as a function in its own right.

$k$ is called a kernel function. The left side takes $x$ and $y$ and returns a single number; the right side is "lift both into high dimensions, then take the inner product." What the equation claims is this: if you can find a convenient $k$ that makes both sides equal, you never have to compute $\phi$ at all.

Does such a convenient function exist? It does. Expand $k(x, y) = (x \cdot y + 1)^3$ and you get exactly the inner product of two vectors listing every term up to degree three. The left side costs $d$ multiplications and additions plus one cubing. The right side is a 167-million-dimensional inner product. Same value, but one of them lands instantly. That is the kernel trick.

Not every function qualifies as a kernel

For $k$ to be writable as "the inner product of some $\phi$," it must be positive definite. Pick any finite set of points $x_1, \dots, x_n$; the $n \times n$ matrix $K_{ij} = k(x_i, x_j)$ — the Gram matrix, or kernel matrix — must be positive semi-definite. If that holds, a corresponding $\phi$ is guaranteed to exist, even if it is infinite-dimensional (Mercer's theorem).

The flip side matters in practice. If you invent a similarity function off the top of your head and drop it in, this condition can break, and you get diverging optimization or a failed Cholesky factorization further downstream. The safe way to build a custom kernel is to compose known ones: sums, products, and positive scalar multiples of kernels are again kernels.

In practice, four kernels cover nearly everything.

• Linear $k(x,y) = x \cdot y$ — no lifting, just the raw inner product
• Polynomial $(x \cdot y + c)^p$ — captures interactions up to degree $p$
• RBF (Gaussian) $\exp(-\|x-y\|^2 / 2\ell^2)$ — its $\phi$ is infinite-dimensional
• Matérn — lets you dial the smoothness of the function directly via $\nu$

The intuition for RBF is "similarity that equals 1 at zero distance and falls off fast." Here $\ell$ (length_scale) is the yardstick for how far apart two points must be before they count as strangers: small $\ell$ gives a wiggly boundary, large $\ell$ a bland one. scikit-learn's SVM specifies the same quantity as its reciprocal, $\gamma = 1/(2\ell^2)$, so raising gamma makes the model more flexible while raising length_scale makes it smoother — the two run in opposite directions, which is an easy thing to get backwards.