¿Cómo funciona un fregadero aleatorio?

Question

El año pasado en NIPS 2017 Ali Rahimi y Ben Recht ganan el premio a la prueba del tiempo por su papel "Características aleatorias para máquinas de núcleo a gran escala" donde introdujeron características aleatorias, más tarde codificadas como algoritmo de fregaderos aleatorios. Como parte de la publicidad de su artículo, mostraron que su modelo podí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);

No me queda claro cómo aprende algo el algoritmo anterior. ¿Cómo funciona un fregadero aleatorio? ¿Cómo se aproxima a los procesos gaussianos y a las máquinas de vectores soporte?

Editar

Volviendo a ver la charla de Rahimi, el término fregaderos aleatorios no se introduce en el artículo por el que ganaron el premio, sino al final de la trilogía de artículos que comienza con "Random Features for Large-Scale Kernel Machines". Los otros artículos son:

Rahimi, Ali, y Benjamin Recht. "Aproximación uniforme de funciones con bases aleatorias". Communication, Control, and Computing, 2008 46th Annual Allerton Conference on. IEEE, 2008.

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

Creo que el fragmento de código introducido más arriba es una especialización del Algoritmo 1 del último artículo.

Answer 1

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

Los métodos kernel son excelentes en muchos entornos, pero suelen basarse en la manipulación de matrices, por ejemplo, para resolver sistemas lineales de ecuaciones y hallar determinantes matriciales. Si la matriz es $n \times n$ entonces, ingenuamente, estos cálculos suelen costar $O(n^3)$ lo que limita su aplicación a problemas con unos pocos miles de observaciones. La forma más popular de sortear este cuello de botella suelen 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é bayesiano, por citar sólo algunos).

Las características aleatorias de Fourier (Rehimi & Recht 2007) consideraron la creación de aproximaciones de bajo rango de núcleos invariantes de desplazamiento mediante el muestreo de sólo un subconjunto aleatorio de los componentes de Fourier de los núcleos. Como el espacio de Fourier es invariante respecto al desplazamiento, se conservó esta propiedad, pero ahora se formó un espacio de Hilbert explícito de dimensión finita que reproduce el núcleo mediante la unión de estos componentes de Fourier. El antiguo RKHS de dimensión infinita se aproxima mediante el núcleo aproximado degenerado.

Notas sobre el fragmento de código: Hay algunos detalles que se pasan por alto en las 5 líneas. El más importante es que la función gaussiana es también una función gaussiana en el espacio de Fourier, sólo que la varianza está invertida. Por eso están muestreando desde randn y luego multiplicando por la varianza. Luego producen alfa que es sólo un sub-procedimiento para encontrar ztest. Esencialmente la predicción normal del kernel se parece a,

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

Dónde $\Phi(\cdot)$ es el vector aleatorio de características de Fourier evaluado.

Comentario al margen: ¿Debería utilizarlo? La respuesta no es un sí rotundo. Depende totalmente de lo que se esté modelizando. El uso del espacio de Fourier no es necesariamente apropiado para los núcleos no estacionarios no invariantes por desplazamiento. Los chicos nunca afirmaron que funcionaría en este entorno, pero si estás empezando en esa área a veces los matices no son obvios.