Kernel Methods

Definition

A feature map $\Phi :\mathcal{X}\to {\mathbb{R}}^D$ turns objects into vectors; a linear model $w^{\top }\Phi (x)$ is non-linear in $x$. A kernel is $k(x,y)=⟨\Phi (x),\Phi (y)⟩$; the kernel trick uses $k$ directly whenever the algorithm only needs scalar products.

Formula

$$\begin{array}{rl}& \text{polynomial: }(1,x,\dots ,x^p)\\ & \text{Fourier: }(1,\cos x,\sin x,\dots )\\ & \text{RBF: }{\phi }_j(x)=\exp (-\frac{\Vert x-c_j{\Vert }^2}{2{\sigma }^2})\end{array}$$

Example: $k(x,y)=(x^{\top }y{)}^2$ on ${\mathbb{R}}^2$ has $\Phi (x)=(x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2)$.

The SVM is a large-margin linear classifier in the feature space. Kernels avoid designing and computing representations; modern deep learning instead learns them (representation learning).

Appears in

• Lecture 7, explicit features
• Lecture 7, basis functions
• Lecture 7, kernel trick
• Lecture 7, exam-style task
• Lecture 8, neural tangent kernel

Related concepts

• Random Features