Random feature explained

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",^[1] and extended by.^{[2] [3]} 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

See main article: Kernel method. Given a feature map $\backslash phi:\; \backslash R^d\; \backslash to\; V$, where $V$ is a Hilbert space (more specifically, a reproducing kernel Hilbert space), the kernel trick replaces inner products in feature space $$\backslash langle\; \backslash phi(x\_i),\; \backslash phi(x\_j)\backslash rangle\_V$$ by a kernel function$$k(x\_i,\; x\_j):\; \backslash R^d\; \backslash times\; \backslash R^d\; \backslash to\; \backslash R$$Kernel methods replaces linear operations in high-dimensional space by operations on the kernel matrix: $$K\_X\; :=\; [k(x\_i,\; x\_j)]\_$$ where $N$ is the number of data points.

Random kernel method

The problem with kernel methods is that the kernel matrix $K\_X$ has size $N\; \backslash times\; N$. This becomes computationally infeasible when $N$ reaches the order of a million. The random kernel method replaces the kernel function $k$ by an inner product in low-dimensional feature space $\backslash R^D$:$$k(x,y)\; \backslash approx\; \backslash langle\; z(x),\; z(y)\backslash rangle$$ where $z$ is a randomly sampled feature map $z\; :\; \backslash R^d\; \backslash to\; \backslash R^D$.

This converts kernel linear regression into linear regression in feature space, kernel SVM into SVM in feature space, etc. Since we have

where , these methods no longer involve matrices of size $O(N^2)$, but only random feature matrices of size $O(DN)$.

Random Fourier feature

Radial basis function kernel

See main article: Radial basis function kernel. The radial basis function (RBF) kernel on two samples

is defined as^[4]

where

is the squared Euclidean distance and is a free parameter defining the shape of the kernel. It can be approximated by a random Fourier feature map :$$z(x)\; :=\; \backslash frac[\backslash cos\backslash langle\; \backslash omega\_1,\; x\backslash rangle,\; \backslash sin\backslash langle\; \backslash omega\_1,\; x\backslash rangle,\; \backslash ldots,\; \backslash cos\backslash langle\; \backslash omega\_D,\; x\backslash rangle,\; \backslash sin\backslash langle\; \backslash omega\_D,\; x\backslash rangle]^T$$where are IID samples from the multidimensional normal distribution .

Since

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

.

Define its Fourier transform$$p(\backslash omega)=\backslash frac\; \backslash int\_\; e^\; k(\backslash Delta)\; d\; \backslash Delta$$then

are sampled IID from the probability distribution with probability density . This applies for other kernels like the Laplace kernel and the Cauchy kernel.

Neural network interpretation

See also: Neural tangent kernel. Given a random Fourier feature map

, training the feature on a dataset by featurized linear regression is equivalent to fitting complex parameters such that$$f\_\backslash theta(x)\; =\; \backslash mathrm\backslash left(\backslash sum\_k\; \backslash theta\_k\; e^\; \backslash right)$$which is a neural network with a single hidden layer, with activation function , zero bias, and the parameters in the first layer frozen.

In the overparameterized case, when

, the network linearly interpolates the dataset , and the network parameters is the least-norm solution:$$\backslash hat\; \backslash theta\; =\; \backslash arg\backslash min\_\; \backslash |\backslash theta\backslash |$$At the limit of , the L2 norm where is the interpolating function obtained by the kernel regression with the original kernel, and is the norm in the reproducing kernel Hilbert space for the kernel.^[5]

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

are assigned to the same bin is proportional to . 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 . 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

L₁

distance between datapoints.

Orthogonal random features

Orthogonal random features^[6] 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

variance bound did not match practice: the variance bound predicts that approximation to within requires , but in practice required only . Attempting to discover what caused this led to the subsequent two papers.^[7]

See also

• Kernel method
• Support vector machine
• Fourier transform
• Monte Carlo method

External links

• Random Walks - Random Fourier features

Notes and References

1. Rahimi . Ali . Recht . Benjamin . 2007 . Random Features for Large-Scale Kernel Machines . Advances in Neural Information Processing Systems . 20.
2. Book: Rahimi . Ali . Recht . Benjamin . Uniform approximation of functions with random bases . September 2008 . 2008 46th Annual Allerton Conference on Communication, Control, and Computing . http://dx.doi.org/10.1109/allerton.2008.4797607 . 555–561 . IEEE . 10.1109/allerton.2008.4797607. 978-1-4244-2925-7 .
3. Rahimi . Ali . Recht . Benjamin . 2008 . Weighted Sums of Random Kitchen Sinks: Replacing minimization with randomization in learning . Advances in Neural Information Processing Systems . Curran Associates, Inc. . 21.
4. Jean-Philippe Vert, Koji Tsuda, and Bernhard Schölkopf (2004). "A primer on kernel methods". Kernel Methods in Computational Biology.
5. Belkin . Mikhail . May 2021 . Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation . Acta Numerica . en . 30 . 203–248 . 10.1017/S0962492921000039 . 2105.14368 . 0962-4929.
6. Yu . Felix Xinnan X . Suresh . Ananda Theertha . Choromanski . Krzysztof M . Holtmann-Rice . Daniel N . Kumar . Sanjiv . 2016 . Orthogonal Random Features . Advances in Neural Information Processing Systems . Curran Associates, Inc. . 29.
7. Web site: Recht . Benjamin . Reflections on Random Kitchen Sinks . 2024-09-29 . arg min blog.