\( \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

ML02.8 · The kernel trick

A free, illustrated module of 4 lessons and one interactive in ML02 Supervised Learning: Trees, Ensembles and Kernels: Lifting data until a line works; Kernels: dot products without the map; Kernel SVMs; Kernels beyond the SVM.

ML02.8 L2 · Intermediate 4 lessons · about 110 min Live · in review

Part of ML02 Supervised Learning: Trees, Ensembles and Kernels in the Machine Learning track.

A linear model draws straight boundaries, yet a ring of points needs a circle. Lift the data into more dimensions and a flat plane can do what no line could. These four lessons build that picture, then find the shortcut that makes it practical: a kernel computes the dot product in the lifted space without ever going there. The trick turns the SVM of ML02.7 into a classifier that bends, carries over to ridge regression, and meets its limit in the n-by-n kernel matrix, which random features and the Nystroem method cut down to size.

What you need first. The support vector machine, its dual problem and the hinge loss (ML02.7), dot products and positive semidefinite matrices (M02.3, M03.4), ridge regression (ML01.9.1) and cross-validation (ML01.9.3).

Lessons

1. Lifting data until a line works ML02.8.1 25 min

   Four points inside a ring of eight cannot be split by any line. Add one coordinate, the squared distance from the origin, and a flat plane splits them. See why, what that plane is back in the plane, and what lifting by hand costs.

2. Kernels: dot products without the map ML02.8.2 25 min

   The dot product of two lifted points can often be computed in the original space, at a fraction of the cost. Derive it for the quadratic map, meet the polynomial and RBF kernels and their Gram matrices, and learn the test that tells a true kernel from an impostor.

3. Kernel SVMs ML02.8.3 30 min

   Swap the dot product in the SVM’s dual for a kernel and the boundary bends. Solve the quadratic-kernel SVM on the rings by hand, build a kernel SVM from scratch and match scikit-learn’s SVC, and learn how gamma and C shape an RBF boundary.

4. Kernels beyond the SVM ML02.8.4 30 min

   Any method written in dot products can be kernelised. Rewrite ridge regression with one weight per example, fit kernel ridge regression on the eight-point set, count what an exact kernel method costs, and cut that cost with random Fourier features and the Nystroem method.

The interactive

ML02.8-X1 · Kernel lift. Turn the rings lifted onto the bowl z = x1^2 + x2^2 and slide a flat plane through them to see the circle it cuts back in the plane. Then switch to an RBF kernel SVM and slide gamma: the boundary goes from one smooth loop to small islands round each point. It lives in Kernel SVMs.