Jak działa przypadkowy zlew kuchenny?

18

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.

MachineEpsilon
źródło
Ani słowo „zatopienie”, ani cytowany kod nie pojawia się w powiązanym dokumencie. Czy brakuje Ci referencji?
Kodiolog,
2
Masz rację, dziękuję. Bez kontekstu dyskusji w 2017 r. Pytanie wydaje się nieco rozłączne! Myślę, że pomysł został opracowany w pierwszym artykule, ale termin przypadkowe zlewozmywaki kuchenne został wprowadzony dopiero później. Fragment kodu został prawdopodobnie rozprowadzony na sesji plakatowej w 2007 roku.
Zapisałem

Odpowiedzi:

15

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×nO(n3))

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,

ztmist=K.(xtmist,x)(K.(x,x)+λja)-1y.

ztmist=Φ(xtmist)T.Φ(x)(Φ(x)T.Φ(x)+λja)-1y.

Φ()

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.

jot__
źródło
5
Zajęło mi sekundę uświadomienie sobie, że obliczenie alfa rozwiązuje problem regresji grzbietu w X i y za pomocą regulizatora lambda. Jeśli pochodzisz z lekarzy ogólnych, to patrząc na twoje formuły jest to nieco oczywiste, ponieważ pod kątem SVM jest to nieco mylące. Twoje „normalne przewidywanie jądra” to GP z dodanym szumem, czyli regresją grzbietu jądra.
Andreas Mueller
1
@AndreasMueller tak przepraszam, że to prawda! Pochodzę ze społeczności GP, więc czasami przeoczam to! Cieszę się, że rozumiesz, co miałem na myśli :)
j__
1
@j__, jeśli masz czas, mam pytanie dotyczące RFF tutaj: stats.stackexchange.com/questions/440633 . Wygląda na to, że odpowiedź na moje pytanie jest w lepszym rozumieniu RKHS i twierdzenia o reprezentatorze.
gwg