¿Cómo funciona un fregadero de cocina al azar?

El año pasado, en NIPS 2017, Ali Rahimi y Ben Recht ganaron el premio de la prueba del tiempo por su trabajo "Características aleatorias para máquinas de grano a gran escala", donde introdujeron características aleatorias, que luego se codificaron como el algoritmo de fregaderos de cocina aleatorios. Como parte de la publicidad de su trabajo, mostraron que su modelo podría implementarse en 5 líneas de 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);

Cómo el algoritmo anterior aprende algo no está claro para mí. ¿Cómo funciona un fregadero de cocina al azar? ¿Cómo aproxima los procesos gaussianos y admite máquinas de vectores?

Editar

Al volver a observar la charla de Rahimi, el término fregaderos de cocina al azar no se introduce en el documento por el que ganaron el premio, sino al final de la trilogía de documentos que comienzan con "Características aleatorias para máquinas de grano a gran escala". Los otros documentos son:

Rahimi, Ali y Benjamin Recht. "Aproximación uniforme de funciones con bases aleatorias". Comunicación, control e informática, 2008 46a Conferencia anual de Allerton sobre. IEEE, 2008.

Rahimi, Ali y Benjamin Recht. "Sumas ponderadas de fregaderos de cocina aleatorios: Reemplazar la minimización por aleatorización en el aprendizaje". Avances en sistemas de procesamiento de información neuronal. 2009

Creo que el fragmento de código presentado anteriormente es una especialización del Algoritmo 1 en el último artículo.

Los sumideros de cocina aleatorios (o características de Fourier aleatorias) y otros métodos relacionados no se esfuerzan por realizar inferencia, sino que intentan reducir el cuello de botella de los métodos de inferencia basados ​​en el núcleo.

Los métodos de kernel son excelentes en muchos entornos, pero generalmente dependen de la manipulación de matrices, por ejemplo, para resolver sistemas lineales de ecuaciones y encontrar determinantes de matrices. Si la matriz es entonces ingenuamente estos cálculos generalmente cuestan que limita las aplicaciones que pueden aplicarse a problemas con solo unos pocos miles de observaciones. La forma más popular de evitar este cuello de botella tiende a ser los métodos de bajo rango (aunque existen otros enfoques, como los métodos basados ​​en Kronecker, las matrices H y las máquinas de comités bayesianos, por nombrar solo algunos).$n \times n$$O(n^3)$

Las características aleatorias de Fourier (Rehimi y Recht 2007) consideraron la creación de aproximaciones de bajo rango de núcleos invariantes de cambio al muestrear solo un subconjunto aleatorio de los componentes de Fourier de los núcleos. Como el espacio de Fourier es invariante al cambio, esta propiedad se conservó pero ahora se formó un núcleo de reproducción de dimensiones finitas explícito del espacio de Hilbert por la unión de estos componentes de Fourier. El RKHS dimensional una vez infinito es aproximado por el núcleo aproximado degenerado.

Notas sobre el fragmento de código: hay algunos detalles cepillados en las 5 líneas. Lo más importante es que la función gaussiana también es una función gaussiana en el espacio de Fourier, solo la varianza se invierte. Es por eso que están tomando muestras de randn y luego multiplicando por varianza. Luego producen alfa, que es solo un subprocedimiento para encontrar ztest. Esencialmente, la predicción normal del núcleo se ve así,

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

$\Phi(\cdot)$

Comentario lateral: ¿Deberías usarlo? La respuesta no es un sí claro. Depende completamente de lo que estés modelando. El uso del espacio de Fourier no es necesariamente apropiado para los núcleos invariantes no estacionarios y sin desplazamiento. Los chicos nunca afirmaron que funcionaría en este entorno, pero si recién estás comenzando en esa área, a veces los matices no son obvios.