Jak działa przypadkowy zlew kuchenny?

W ubiegłym roku na targach NIPS 2017 Ali Rahimi i Ben Recht wygrali próbę czasową za swój artykuł „Random Features for Large Scale Kernel Machines”, w którym wprowadzili losowe funkcje, później skodyfikowane jako algorytm losowych zlewów kuchennych. W ramach publikacji artykułu wykazali, że ich model można zaimplementować w 5 liniach Matlaba.

% 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);

To, jak powyższy algorytm uczy się czegokolwiek, jest dla mnie niejasne. Jak działa przypadkowy zlew kuchenny? Jak przybliża procesy Gaussa i obsługuje maszyny wektorowe?

Edytować

Odnosząc się do przemówienia Rahimi, termin przypadkowe zlewozmywaki kuchenne nie został wprowadzony w artykule, za który zdobyli nagrodę, ale na końcu trylogii artykułów rozpoczynającej się od „Losowych funkcji dla dużych maszyn jądra”. Pozostałe dokumenty to:

Rahimi, Ali i Benjamin Recht. „Jednolite przybliżenie funkcji z losowymi zasadami”. Komunikacja, kontrola i przetwarzanie danych, 46. doroczna konferencja Allerton 2008. IEEE, 2008.

Rahimi, Ali i Benjamin Recht. „Ważone sumy przypadkowych zlewozmywaków kuchennych: zamiana minimalizacji na randomizację w nauce”. Postępy w systemach przetwarzania informacji neuronowych. 2009.

Myślę, że fragment kodu wprowadzony powyżej jest specjalizacją algorytmu 1 w ostatnim artykule.

Losowe zlewozmywaki kuchenne (lub losowe funkcje Fouriera) i inne powiązane metody nie starają się wykonywać wnioskowania, ale raczej starają się zmniejszyć wąskie gardło metod wnioskowania opartych na jądrze.

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

Losowe cechy Fouriera (Rehimi i Recht 2007) rozważyły ​​utworzenie przybliżeń niskiego rzędu niezmienników przesunięcia poprzez próbkowanie tylko losowego podzbioru składników Fouriera w jądrze. Ponieważ przestrzeń Fouriera jest niezmienna przesunięciem, ta właściwość została zachowana, ale teraz połączenie elementów składowych Fouriera utworzyło jawne, skończone wymiarowo jądro przestrzeni Hilberta. Raz nieskończone wymiarowo RKHS jest aproksymowane przez zdegenerowane przybliżone jądro.

Uwagi na temat fragmentu kodu: W 5 wierszach omówiono kilka szczegółów. Najważniejsze jest to, że funkcja Gaussa jest również funkcją Gaussa w przestrzeni Fouriera, tylko wariancja jest odwrócona. Dlatego pobierają próbki z randn, a następnie mnożą przez wariancję. Następnie produkują alfa, co jest tylko podprocedurą znalezienia ztest. Zasadniczo wygląda normalna prognoza jądra,

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

Komentarz boczny: Czy powinieneś go użyć? Odpowiedź nie jest jednoznaczna tak. Zależy to całkowicie od tego, co modelujesz. Wykorzystanie przestrzeni Fouriera niekoniecznie jest odpowiednie dla niestacjonarnych niezmiennych jąder niezmiennych. Chłopaki nigdy nie twierdzili, że to zadziała w tym otoczeniu, ale jeśli dopiero zaczynasz w tym obszarze, czasami niuanse nie są oczywiste.