The Kernel Trick, Drawn

Lift two-dimensional data into a feature space where a plane separates it.

Ch 6 6.4

Animator

Supervised Learning

20 mindifficulty 4/5

Training the kernel machine…

Predict before you look

On concentric circles, which kernel needs the fewest support vectors to separate the classes well?

Scenarios

Teacher-ready starting points.

Documentation

What this shows

A kernel support vector machine trained by a simplified sequential minimal optimization (SMO) dual coordinate ascent, on four two-dimensional datasets of increasing nonlinearity. The input-space panel draws the decision boundary as a raster with a shaded margin band and rings the support vectors; the feature-space panel morphs ('lifts') the same points toward an explicit low-dimensional feature map so you can see, concretely, what a kernel is standing in for.

Dual SVM, kernels, and the kernel matrix

The soft-margin SVM dual maximizes Σᵢαᵢ − ½ΣᵢΣⱼαᵢαⱼyᵢyⱼK(xᵢ,xⱼ) subject to 0 ≤ αᵢ ≤ C and Σᵢαᵢyᵢ = 0. Only inner products K(xᵢ,xⱼ) ever appear — never the coordinates of any lifted feature vector φ(x).

A kernel is valid (Mercer) precisely when it equals ⟨φ(xᵢ),φ(xⱼ)⟩ for some feature map φ, possibly infinite-dimensional. The polynomial kernel (x·y + c)ᵈ corresponds to an explicit, finite feature map of all monomials up to degree d; the RBF kernel exp(−γ‖x−y‖²) corresponds to an infinite-dimensional map (its Taylor expansion has a term for every degree).

The optimizer here is Platt's simplified SMO: repeatedly pick two dual variables, solve the resulting 1-D constrained quadratic in closed form, and clip to the box. Points with αᵢ = 0 never influence the boundary; points with 0 < αᵢ < C sit exactly on the margin; points with αᵢ = C are inside the margin or misclassified. The margin width 2/‖w‖ is computed as 2/√(ΣᵢΣⱼαᵢαⱼyᵢyⱼK(xᵢ,xⱼ)) — entirely from kernel evaluations, never from ‖w‖ in an explicit feature space.

max_α Σαᵢ − ½ΣΣ αᵢαⱼ yᵢyⱼ K(xᵢ,xⱼ),  0≤αᵢ≤C,  Σαᵢyᵢ=0

f(x) = Σᵢ αᵢ yᵢ K(xᵢ,x) + b

‖w‖² = ΣΣ αᵢαⱼ yᵢyⱼ K(xᵢ,xⱼ)  ⟹  margin = 2/‖w‖

poly: K(x,y)=(x·y+c)^d  ↔  φ = all monomials up to degree d, dim = C(d+2, d)

Try this

On concentric circles, compare the linear and RBF kernels: the linear boundary is a straight line through both rings; RBF wraps a closed curve around the inner class.
On XOR with the polynomial kernel (degree 2), drag Lift from 0 to 1 and watch the four clusters rearrange along the √2·x₁x₂ axis into two linearly separable halves.
Raise C from 0.1 to 20 on the moons dataset with RBF: more points collapse to α=C (inside the margin), the margin narrows, and training accuracy rises while test accuracy can fall.
Raise the polynomial degree from 2 to 5 and watch the 'explicit feature dimension' readout grow much faster than the 'kernel-matrix cost' readout — the gap is the entire point of the trick.
Increase label noise on the linearly separable dataset and watch the number of support vectors grow as more points sit inside or across the margin.

Common misconception

“A kernel like RBF works by first computing the coordinates of each point in a high-dimensional feature space.”

It never does. The dual SVM only needs inner products K(xᵢ,xⱼ), and the kernel function computes that scalar directly from the two low-dimensional inputs — for RBF, exp(−γ‖x−y‖²) is one exponential of one distance, not a dot product taken after mapping to an infinite-dimensional space. The 'explicit feature dimension' readout in this lab shows what you would need to compute by hand if you insisted on doing it the slow way; the kernel-matrix cost readout shows what the SVM actually pays, and it never depends on that dimension.

DSPA3, Chapter 6.4