Random features (RF) are a technique used in machine learning to approximate kernel methods, introduced by Ali Rahimi and Ben Recht in their 2007 paper "Random Features for Large-Scale Kernel Machines", and extended by. RF uses a Monte Carlo approximation to kernel functions by randomly sampled feature maps. It is used for datasets that are too large for traditional kernel methods like support vector machine, kernel ridge regression, and gaussian process.
Mathematics.
Kernel method.
Given a feature map formula_1, where formula_2 is a Hilbert space (more specifically, a reproducing kernel Hilbert space), the kernel trick replaces inner products in feature space formula_3 by a kernel functionformula_4Kernel methods replaces linear operations in high-dimensional space by operations on the kernel matrix: formula_5 where formula_6 is the number of data points.
Random kernel method.
The problem with kernel methods is that the kernel matrix formula_7 has size formula_8. This becomes computationally infeasible when formula_6 reaches the order of a million. The random kernel method replaces the kernel function formula_10 by an inner product in low-dimensional feature space formula_11:formula_12 where formula_13 is a randomly sampled feature map formula_14.
This converts kernel linear regression into linear regression in feature space, kernel SVM into SVM in feature space, etc. Since we have formula_15 where formula_16, these methods no longer involve matrices of size formula_17, but only random feature matrices of size formula_18.
Random Fourier feature.
Radial basis function kernel.
The radial basis function (RBF) kernel on two samples formula_19 is defined as
 formula_20
where formula_21 is the squared Euclidean distance and formula_22 is a free parameter defining the shape of the kernel. It can be approximated by a random Fourier feature map formula_23:formula_24where formula_25 are IID samples from the multidimensional normal distribution formula_26.
(Variance bound) Since formula_25 are IID, it suffices to prove that the variance of formula_28 is finite, which is true since it is bounded within formula_29.
(Convergence) By Chebyshev's inequality.
}}Since formula_30 are bounded, there is a stronger convergence guarantee by Hoeffding's inequality.
Random Fourier features.
By Bochner's theorem, the above construction can be generalized to arbitrary positive definite shift-invariant kernel formula_31.
Define its Fourier transformformula_32then formula_25 are sampled IID from the probability distribution with probability density formula_34. This applies for other kernels like the Laplace kernel and the Cauchy kernel.
Neural network interpretation.
Given a random Fourier feature map formula_35, training the feature on a dataset by featurized linear regression is equivalent to fitting complex parameters formula_36 such thatformula_37which is a neural network with a single hidden layer, with activation function formula_38, zero bias, and the parameters in the first layer frozen.
In the overparameterized case, when formula_39, the network linearly interpolates the dataset formula_40, and the network parameters is the least-norm solution:formula_41At the limit of formula_42, the L2 norm formula_43 where formula_44 is the interpolating function obtained by the kernel regression with the original kernel, and formula_45 is the norm in the reproducing kernel Hilbert space for the kernel.
Other examples.
Random binning features.
A random binning features map partitions the input space using randomly shifted grids at randomly chosen resolutions and assigns to an input point a binary bit string that corresponds to the bins in which it falls. The grids are constructed so that the probability that two points formula_46 are assigned to the same bin is proportional to formula_47. The inner product between a pair of transformed points is proportional to the number of times the two points are binned together, and is therefore an unbiased estimate of formula_47. Since this mapping is not smooth and uses the proximity between input points, Random Binning Features works well for approximating kernels that depend only on the formula_49 distance between datapoints.
Orthogonal random features.
Orthogonal random features uses a random orthogonal matrix instead of a random Fourier matrix.
Historical context.
In NIPS 2006, deep learning had just become competitive with linear models like PCA and linear SVMs for large datasets, and people speculated about whether it could compete with kernel SVMs. However, there was no way to train kernel SVM on large datasets. The two authors developed the random feature method to train those.
It was then found that the formula_50 variance bound did not match practice: the variance bound predicts that approximation to within formula_51 requires formula_52, but in practice required only formula_53. Attempting to discover what caused this led to the subsequent two papers.