Como funciona uma pia de cozinha aleatória?

No ano passado, no NIPS 2017, Ali Rahimi e Ben Recht ganharam o prêmio do teste do tempo por seu artigo "Recursos Aleatórios para Máquinas de Kernel em Grande Escala", onde introduziram recursos aleatórios, posteriormente codificados como o algoritmo de pias de cozinha aleatórias. Como parte da divulgação de seu trabalho, eles mostraram que seu modelo poderia ser implementado em 5 linhas do 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);

Como o algoritmo acima aprende algo não está claro para mim. Como funciona uma pia de cozinha aleatória? Como ele aproxima os processos gaussianos e suporta máquinas vetoriais?

Editar

Relembrando a palestra de Rahimi, o termo pias de cozinha aleatórias não é introduzido no artigo pelo qual eles ganharam o prêmio, mas no final da trilogia de artigos que começam com "Recursos aleatórios para máquinas de kernel em grande escala". Os outros trabalhos são:

Rahimi, Ali e Benjamin Recht. "Aproximação uniforme de funções com bases aleatórias." Comunicação, Controle e Computação, 2008 46ª Conferência Anual da Allerton em. IEEE, 2008.

Rahimi, Ali e Benjamin Recht. "Soma ponderada de pias de cozinha aleatórias: substituindo minimização por randomização na aprendizagem." Avanços nos sistemas de processamento de informações neurais. 2009.

Eu acho que o trecho de código introduzido acima é uma especialização do Algoritmo 1 no último artigo.

Pias de cozinha aleatórias (ou recursos aleatórios de Fourier) e outros métodos relacionados não se esforçam para realizar inferência, mas tentam reduzir o gargalo dos métodos de inferência baseados em kernel.

$n \times n$$O(n^3)$

Os recursos aleatórios de Fourier (Rehimi & Recht 2007) consideraram a criação de aproximações de baixa classificação dos núcleos invariantes por deslocamento, amostrando apenas um subconjunto aleatório dos componentes de Fourier dos núcleos. Como o espaço de Fourier é invariável ao deslocamento, essa propriedade foi preservada, mas agora um espaço Hilbert explícito e dimensional explícito do núcleo de reprodução foi formado pela união desses componentes de Fourier. O RKHS dimensional uma vez infinito é aproximado pelo kernel degenerado aproximado.

Notas sobre o snippet de código: existem alguns detalhes detalhados nas 5 linhas. O mais importante é que a função gaussiana também é uma função gaussiana no espaço de Fourier, apenas a variação é invertida. É por isso que eles estão amostrando a partir de randn e depois multiplicando por variação. Então eles produzem alfa, que é apenas um subprocedimento para encontrar o ztest. Basicamente, a previsão normal do kernel se parece,

$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.$

Onde $\Phi(\cdot)$ é o vetor de característica de Fourier aleatório avaliado.

Comentário lateral: Você deve usá-lo? A resposta não é clara, sim. Depende completamente do que você está modelando. O uso do espaço de Fourier não é necessariamente apropriado para núcleos invariantes não estacionários e sem deslocamento. Os caras nunca afirmaram que funcionaria nesse cenário, mas se você está apenas começando nessa área, às vezes as nuances não são óbvias.