# How does a random kitchen sink work?

Last year at NIPS 2017 Ali Rahimi and Ben Recht won the test of time award for their paper "Random Features for Large-Scale Kernel Machines" where they introduced random features, later codified as the random kitchen sinks algorithm. As part of publicising their paper, they showed that their model could be implemented in 5 lines of matlab.

% Approximates Gaussian Process regression
%     with Gaussian kernel of variance gamma^2
% lambda: regularization parameter
% dataset: X is dxN, y is 1xN
% test: xtest is dx1
% D: dimensionality of random feature

% training
w = randn(D,d);
b = 2 * pi * rand(D, 1);
Z = cos(gamma * w * X + b * ones(1,N));

alpha = (lambda * eye(D) +Z * Z') \ (Z * y);

% testing
ztest = alpha' * cos(gamma * w * xtest + b);


How the above algorithm learns anything is unclear to me. How does a random kitchen sink work? How does it approximate Gaussian processes and support vector machines?

Edit

Rewatching Rahimi's talk, the term random kitchen sinks is not introduced in the paper for which they won the award but rather at the end of the trilogy of papers beginning with "Random Features for Large-Scale Kernel Machines". The other papers are:

Rahimi, Ali, and Benjamin Recht. "Uniform approximation of functions with random bases." Communication, Control, and Computing, 2008 46th Annual Allerton Conference on. IEEE, 2008.

Rahimi, Ali, and Benjamin Recht. "Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning." Advances in neural information processing systems. 2009.

I think the code snippet introduced above is a specialisation of Algorithm 1 in last paper.

• Neither the word "sink" nor the code you quote appears in the linked paper. Are you missing a reference? – Kodiologist Feb 9 '18 at 0:57
• You're quite right, thank you. Without the context of the 2017 talk, the question seems a bit disjointed! The idea was developed in the first paper, I think but the term random kitchen sinks was only introduced later. The code snippet was distributed at the 2007 poster session for the paper apparently. I transcribed it from Rahimi's talk at NIPS 2017. – MachineEpsilon Feb 9 '18 at 2:17

Random kitchen sinks (or random Fourier features) and other related methods don't endeavour to perform inference but rather they try to reduce the bottleneck of kernel based inference methods.

Kernel methods are great in many settings but they usually rely on the manipulation of matrices, for example solving linear systems of equations and finding matrix determinants. If the matrix is $n \times n$ then naively these computations generally cost $O(n^3)$ which limits the applications they can be applied to problems with only a few thousand observations. The most popular way around this bottleneck tends to be low rank methods (although other approaches exist such as Kronecker based methods, H-matrices and Bayesian committee machines to name but a few).

Random Fourier features (Rehimi & Recht 2007) considered creating low rank approximations of shift invariant kernels by sampling only a random subset of the kernels Fourier components. As Fourier space is shift invariant, this property was preserved but now an explicit finite dimensional reproducing kernel Hilbert space was formed by the union of these Fourier components. The once infinite dimensional RKHS is approximated by the degenerate approximate kernel.

Notes on code snippet: There are a few details brushed over in the 5 lines. The most important is that the Gaussian function is also a Gaussian function in Fourier space, just the variance is inverted. That is why they are sampling from randn and then multiplying by variance. Then they produce alpha which is only a sub-procedure to find ztest. Essentially the normal kernel prediction looks like,

$z_{test} = K(x_{test}, x)(K(x, x) + \lambda I)^{-1} y.$

$z_{test} = \Phi(x_{test})^T\Phi(x)(\Phi(x)^T\Phi(x) + \lambda I)^{-1} y.$

Where $\Phi(\cdot)$ is the evaluated random Fourier feature vector.

Side comment: Should you use it? The answer isn't a clear yes. It depends completely on what you are modelling. The use of the Fourier space is not necessarily appropriate for non-stationary non-shift invariant kernels. The guys never claimed it would work in this setting but if you are just starting out in that area sometimes the nuances aren't obvious.

• Took me a second to realize that computing alpha here is solving the ridge regression problem in X and y with regularizer lambda. If you come from GPs then looking at your formulas this is somewhat obvious, coming from an SVM angle it's slightly confusing. Your "normal kernel prediction" is a GP with noise added, aka kernel ridge regression. – Andreas Mueller Apr 17 '19 at 23:05
• @AndreasMueller yes sorry that is correct! I am very much from the GP community originally so sometimes overlook that! Glad you got what I meant though :) – j__ Sep 17 '19 at 4:14
• @j__, if you have time, I have a question about RFFs over here: stats.stackexchange.com/questions/440633. It sounds like the answer to my question is in better understand RKHS and the representer theorem. – gwg Dec 13 '19 at 21:33