The kernel trick
The kernel trick lets a straight-line model learn curved boundaries by comparing points in a richer space it never has to build.
- 7 min read
- 3 reading levels
- Published
Read these first
On this page 5
One lesson, three depths. Pick the one that fits you today — you can switch any time.
Beginner — No maths. Plain English.
The kernel trick lets a straight-line model draw curved boundaries, without ever paying for the extra dimensions it pretends to use.
Picture red and white carrom coins scattered on the board, whites clustered in the middle, reds around them. No ruler placed flat on the board can separate them — any straight line traps reds on both sides. Now slap the board from below, right under the centre. The middle coins jump higher than the edge ones. In mid-air, a flat sheet of paper slides neatly between high whites and low reds.
Lifting the coins into the air is adding a new dimension. A problem that was impossible flat becomes easy lifted.
Why it exists
Support vector machines draw straight boundaries. Real data is often not straight — think of the ring of coins.
The honest fix is to add features until the data straightens out. But useful liftings can need enormous numbers of new features, too many to compute or store.
The trick: an SVM never needs each lifted point on its own. It only needs similarity scores between pairs of points in the lifted space. A kernel is a shortcut formula that returns that score directly from the original coordinates. You get the lifted answer without doing the lifting. That shortcut is the whole trick.
How it works
flat board: reds ● around whites ○ → no straight separator exists
lift step: height = distance from centre (a new, third dimension)
in the air: whites high, reds low → a flat sheet separates them
kernel trick: skip the lift — a formula gives "similarity as if lifted"A real example you have seen
Early camera face detectors and handwriting readers used kernel SVMs to learn wiggly boundaries between "face" and "not face". Closer to daily life: think of a small clinic model separating "healthy" from "at risk". The boundary is curved and there are only a few hundred patients. That is kernel territory. Deep learning starves on data that small.
Remember this
- Straight-line models fail on ring-shaped data — no flat cut works.
- Adding the right feature can make the data straight again in a higher dimension.
- A kernel delivers the higher-dimensional answer while skipping the higher-dimensional work.
What to learn next
- Gaussian process regression — kernels reused as covariance, with uncertainty for free.
- Support vector machines — the margin machinery the trick plugs into.
- Embeddings — the deep-learning answer to "learn the lifting from data".
Developer — Code and libraries.
Setup
pip install scikit-learnOutputs verified with scikit-learn 1.7.2 on CPU.
Rings that defeat a straight line
import numpy as np
from sklearn.datasets import make_circles
from sklearn.svm import SVC
# an inner ring of one class inside an outer ring of the other
X, y = make_circles(n_samples=200, factor=0.4, noise=0.08, random_state=0)
for kernel in ("linear", "rbf"):
acc = SVC(kernel=kernel).fit(X, y).score(X, y)
print(f"{kernel:>6} kernel: training accuracy {acc:.2f}")
r2 = (X ** 2).sum(axis=1, keepdims=True) # handmade feature: distance from centre, squared
X3 = np.hstack([X, r2])
acc3 = SVC(kernel="linear").fit(X3, y).score(X3, y)
print(f"linear kernel + handmade feature: training accuracy {acc3:.2f}")linear kernel: training accuracy 0.62 rbf kernel: training accuracy 1.00 linear kernel + handmade feature: training accuracy 1.00
The walkthrough
The linear kernel scores 0.62 — barely above coin-flipping. No straight line separates a ring from its centre, and 200 training points cannot change geometry.
The handmade lift is the carrom slap. The new column r2 is each point's squared distance from the centre — exactly the "height" from the analogy. Inner points get small heights, outer points large ones. In this 3-feature space one flat cut succeeds, and the linear kernel jumps to 1.00.
The RBF kernel found that lift on its own. The RBF (radial basis function) kernel scores two points by how near they sit: the score decays smoothly from 1 (identical) toward 0 (far apart). Training with it is equivalent to lifting into an infinitely rich feature space — one you could never build column by column. That is the trick earning its keep: we handcrafted one clever feature; RBF shipped with the cleverness built in.
Two knobs control RBF behaviour. C prices mistakes, as in any SVM. gamma sets how fast similarity dies with distance — how far each training point's influence reaches. Big gamma means tiny islands of influence around each point: the boundary wraps every example, which is overfitting in its purest visual form.
Common mistakes
Reading training accuracy as success. The 1.00 scores above are on the training data, kept honest here only because rings are genuinely separable. On noisy data an RBF with large gamma also prints 1.00 — memorised, not learned. Always confirm with cross-validation.
Leaving gamma and C at defaults. The defaults (gamma="scale", C=1) are sensible starting points, nothing more. Grid-search both on a log scale; the two interact.
Forgetting to scale features. Kernels are built on distances. One big-unit feature warps every similarity score. Scale first, as with KNN.
Kernel SVMs on massive datasets. Kernel training cost grows roughly quadratically with rows. For 500k rows, approximate the kernel instead: RBFSampler or Nystroem builds explicit random features, then a fast linear model finishes the job.
Try it yourself
Fit SVC(kernel="rbf", gamma=100) on the rings and print training accuracy — then evaluate honestly with cross_val_score. Explain the gap. Then retry the handmade-feature approach using un-squared distance np.sqrt(r2) and check whether the linear model still succeeds.
What to learn next
- Gaussian process regression — kernels reused as covariance, with uncertainty for free.
- Support vector machines — the margin machinery the trick plugs into.
- Embeddings — the deep-learning answer to "learn the lifting from data".
Researcher — Mathematics and papers.
Kernels as inner products
A feature map $\phi: \mathcal{X} \to \mathcal{H}$ sends inputs into a Hilbert space $\mathcal{H}$. A kernel computes the inner product there without materialising $\phi$:
$$ k(x, x') = \langle \phi(x), \phi(x') \rangle_{\mathcal{H}} $$
Where:
- $x, x' \in \mathcal{X}$ — two inputs in the original space.
- $\phi$ — the (possibly infinite-dimensional) lifting; $\mathcal{H}$ — its target space.
- $\langle \cdot, \cdot \rangle_{\mathcal{H}}$ — the inner product in that space.
Mercer's condition: $k$ corresponds to some $\phi$ iff it is symmetric and positive semi-definite — every Gram matrix $K_{ij} = k(x_i, x_j)$ has non-negative eigenvalues.
Common kernels:
| Kernel | Formula | Feature space |
|---|---|---|
| Linear | $x^\top x'$ | the input space itself |
| Polynomial | $(\gamma x^\top x' + r)^p$ | all monomials up to degree $p$ |
| RBF | $\exp(-\gamma \lVert x - x' \rVert^2)$ | infinite-dimensional |
For the polynomial case with $d$ inputs and degree $p$, the explicit space has $\binom{d+p}{p}$ dimensions — the kernel evaluates the inner product in $O(d)$ regardless.
Why the SVM dual admits the trick
The dual objective and the decision function touch data only through inner products:
$$ f(x) = \sum_{i=1}^{n} \alpha_i y_i \, k(x_i, x) + b $$
with $\alpha_i$ the dual coefficients (non-zero only for support vectors). Replace every $x_i^\top x_j$ with $k(x_i, x_j)$ and the optimisation is unchanged. Any algorithm expressible purely in inner products kernelises the same way: ridge regression (kernel ridge), PCA (kernel PCA; Schölkopf et al., 1998), and Gaussian processes, where the kernel reappears as a covariance function.
Representer theorem
For minimisers of regularised empirical risk over the RKHS (reproducing kernel Hilbert space) induced by $k$, the solution has the finite form $f(\cdot) = \sum_i \alpha_i k(x_i, \cdot)$ (Kimeldorf and Wahba, 1971; general form Schölkopf, Herbrich, Smola, 2001). Infinite-dimensional learning collapses to $n$ coefficients — the theorem that makes the trick a method rather than a hope.
Cost and scaling out
Gram matrix construction is $O(n^2 d)$ and solvers add up to $O(n^3)$; memory is $O(n^2)$. Beyond ~$10^5$ points, approximations take over:
- Random Fourier features (Rahimi and Recht, 2007): sample $D$ frequencies from the kernel's spectral density; a shift-invariant kernel becomes an explicit $D$-dimensional map with error $O(1/\sqrt{D})$.
- Nyström (Williams and Seeger, 2001): low-rank Gram approximation from $m \ll n$ landmark points.
Historical anchor: Boser, Guyon and Vapnik (1992) introduced kernels into max-margin training; Aizerman et al. (1964) had the core idea decades earlier. Neural networks later absorbed the lifting role — a learned representation is a trainable $\phi$ — and the neural tangent kernel (Jacot et al., 2018) closed the circle by describing infinitely wide networks as kernel machines.
What to learn next
- Gaussian process regression — kernels reused as covariance, with uncertainty for free.
- Support vector machines — the margin machinery the trick plugs into.
- Embeddings — the deep-learning answer to "learn the lifting from data".