Random Fourier Kernel Features

Worked Example

Let length scale ℓ = 1. The RBF kernel between points x and y is k(x,y) = exp(-(x-y)² / (2ℓ²)). Consider x = 0.5 and y = 0.

1. The exact kernel is exp(-0.5² / 2) = exp(-0.125) ≈ 0.8824969.
2. For the random feature map with D frequencies, we draw \omega_j ~ N(0, 1/ℓ²).
3. The approximated kernel is 1/D \sum_(j=1)^D cos(\omega_j (x-y) / ℓ).
4. With a specific random sample of frequencies, this average approaches the exact expected value.

Experiment

Explore how the number of frequencies affects the approximation quality in the interactive module:
Random Fourier Kernel Features

1. Set the Length scale to 1 and compare the exact and approximate curves.
2. Increase the Frequency count to observe the approximate kernel converging toward the exact Gaussian shape.
3. Observe that at x = y, the approximated kernel is always exactly 1, preserving the self-similarity property.

Limitations

The finite sample approximation provides an unbiased estimate of the true kernel, but any specific set of frequencies has non-zero variance. This means the approximate kernel can sometimes evaluate to small negative values, unlike the true RBF kernel which is strictly positive. Additionally, increasing the number of frequencies reduces variance but does not guarantee a monotone decrease in error for every specific pair of points.

References

The original formulation of Random Fourier Features demonstrates that a relatively small number of random frequencies can approximate the RBF kernel well enough to achieve similar generalization performance as exact kernel methods.

• Rahimi, A., & Recht, B. (2007). Random Features for Large-Scale Kernel Machines. Advances in Neural Information Processing Systems (NIPS).