Here is the idea that turned a linear classifier into one of the most powerful tools in machine learning. A linear SVM can only draw straight boundaries — useless for data shaped like rings or spirals. The kernel trick lets the very same algorithm draw arbitrarily curved boundaries, by computing inner products in a high-dimensional space without ever going there. It is built directly on the dual form of the previous chapter.

Lifting data into feature space

If data is not linearly separable in its original space, map it with a feature map \(\Phimap:\R^p\to\R^D\) (with \(D\) large) into a space where it is linearly separable, then run a linear SVM there. The boundary is linear in the lifted space but nonlinear back in the original space.

The trick: kernels replace inner products

A kernel is a function \(k(\vx,\vx')=\Phimap(\vx)^\top\Phimap(\vx')\) that computes the inner product in feature space directly from the inputs, without forming \(\Phimap\). The kernel trick is the observation that the SVM dual and prediction use data only through inner products, so we may replace every \(\vxi^\top\vx_j\) with \(k(\vxi,\vx_j)\).

Let \(k(\vx,\vx')=(\vx^\top\vx')^2\) in \(\R^2\). Expanding, \[(x_1x_1'+x_2x_2')^2 = (x_1^2)(x_1'^2)+(x_2^2)(x_2'^2)+2(x_1x_2)(x_1'x_2'),\] which is the inner product of \(\Phimap(\vx)=(x_1^2,\,x_2^2,\,\sqrt2\,x_1x_2)\) with \(\Phimap(\vx')\). So computing one scalar product and squaring it secretly evaluates a dot product in a 3-D feature space — and for degree \(d\) in \(p\) dimensions, in a space of dimension \(\binom{p+d}{d}\), which can be astronomically large. The RBF kernel corresponds to an infinite-dimensional feature space.

The kernelized SVM

Replacing inner products with \(k\), the dual becomes \(\max_\alpha \sum_i\alpha_i-\tfrac12\sum_{i,j}\alpha_i\alpha_j y_iy_j\,k(\vxi,\vx_j)\), and prediction is \[\hat y(\vx) = \sgn\!\Big(\sum_{i\in\text{SV}}\alpha_i y_i\,k(\vxi,\vx) + b\Big).\] The model never stores \(\vw\) (it may be infinite-dimensional) — it stores the support vectors and their \(\alpha_i\), and classifies new points by comparing them, via \(k\), to the support vectors.

What makes a valid kernel?

By Mercer’s theorem, \(k\) is a valid kernel (corresponds to some feature map) if and only if it is symmetric and positive semi-definite: for any points, the Gram matrix \(\Kmat_{ij}=k(\vxi,\vx_j)\) has no negative eigenvalues. Such kernels define a Reproducing Kernel Hilbert Space (RKHS) — the (possibly infinite-dimensional) feature space in which the SVM is linear.

Think of a kernel as a similarity measure: \(k(\vx,\vx')\) is large when \(\vx,\vx'\) are “alike” in the relevant sense. The positive-semidefinite requirement is what guarantees this similarity is a genuine geometry (an inner product), so the optimization stays convex. A bonus of the RKHS view is the representer theorem: the optimal function is always a finite sum \(\sum_i\alpha_i k(\vxi,\cdot)\) over the training points — even in infinite dimensions, the solution lives in the span of the data.

The kernel trick is powerful enough to overfit spectacularly. An RBF kernel with too-large \(\gamma\) (tiny bandwidth) makes every point its own island — perfect training accuracy, useless generalization. Other traps: forgetting to standardize (RBF distances become meaningless across mismatched scales); using a non-PSD “kernel” (e.g. a tuned sigmoid kernel), which breaks convexity and may not converge; and applying kernels to huge \(n\), where the \(n\times n\) Gram matrix exhausts memory. Tune \(C\) and the kernel parameters together by cross-validation (Chapters [ch:kernels], [ch:practical]).

The kernel trick launched an entire paradigm — kernel methods — spanning Gaussian processes, kernel ridge regression, kernel PCA, and one-class SVMs. Its modern echo is the deepest result connecting SVMs to deep learning: an infinitely wide neural network is governed by the Neural Tangent Kernel, so training such a network by a margin loss is provably equivalent to a kernel SVM (Chapter [ch:svmmlai]). The “compute similarities, not coordinates” idea also prefigures attention in transformers, where outputs depend on learned similarities (dot products) between tokens. Kernels are everywhere once you know to look.

import numpy as np
from sklearn.svm import SVC
from sklearn.datasets import make_circles
X, y = make_circles(n_samples=300, factor=0.4, noise=0.1, random_state=0)
lin = SVC(kernel="linear").fit(X, y)
rbf = SVC(kernel="rbf", gamma=1.0, C=1.0).fit(X, y)
print("linear kernel accuracy:", round(lin.score(X, y), 3))   # ~0.5, can't separate rings
print("RBF kernel accuracy:   ", round(rbf.score(X, y), 3))   # ~1.0, curved boundary

Chapter summary

  • A feature map \(\Phimap\) lifts data to a space where it is linearly separable; the boundary is nonlinear back home.

  • A kernel \(k(\vx,\vx')=\Phimap(\vx)^\top\Phimap(\vx')\) computes feature-space inner products without forming \(\Phimap\).

  • The kernelized prediction \(\sgn(\sum_{\text{SV}}\alpha_i y_i k(\vxi,\vx)+b)\) uses only support vectors and the kernel.

  • Valid kernels are symmetric positive semi-definite (Mercer); they define an RKHS, and the representer theorem keeps solutions finite.

  • Kernels can overfit (watch \(\gamma\)), need scaled features, and scale poorly with \(n\); they seeded all of kernel methods and the NTK link to deep nets.