Random Features

Definition

Draw ${\theta }_1,\dots ,{\theta }_D$ from a distribution $\mu$, keep them fixed, map $x\mapsto (b_{{\theta }_1}(x),\dots ,b_{{\theta }_D}(x))$ and learn only $f(x)={\sum }_j{a}_j{b}_{{\theta }_j}(x)$. Random Fourier features: $\cos ({\omega }_j^{\top }x+b_j)$ with ${\omega }_j\sim \mathcal{N}(0,{\sigma }^{-2}I)$, $b_j\sim U[0,2\pi ]$. Random ReLU features: $(w_j^{\top }x+b_j{)}_{+}$.

Formula

$$k_{emp}(x,x^{\prime })=\frac{1}{D}\sum _{j=1}^D{b}_{{\theta }_j}(x)b_{{\theta }_j}(x^{\prime })\stackrel{D\to \infty }{\to }\int b_{\theta }(x)b_{\theta }(x^{\prime })d\mu (\theta )$$

Random Fourier features approximate the Gaussian kernel (Rahimi and Recht 2007); ReLU features the ReLU (NNGP) kernel.

A random feature model is a one-hidden-layer network with a frozen random first layer: a bridge between neural networks and kernels, and the model in which double descent is shown (Lecture 8). Representation learning instead trains all layers.

Appears in

• Lecture 7, random Fourier and ReLU features, link to kernels
• Lecture 7, representation learning
• Lecture 8, double descent with random ReLU features
• Lecture 8, the NTK regime behaves like random features

Related concepts

• Kernel Methods