Wie funktioniert eine zufällige Küchenspüle?

17

Letztes Jahr auf der NIPS 2017 gewannen Ali Rahimi und Ben Recht den Test of Time Award für ihre Arbeit "Random Features for Large-Scale Kernel Machines", in der sie Random Features einführten, die später als Random-Kitchen-Sink-Algorithmus kodifiziert wurden. Im Rahmen der Veröffentlichung ihrer Arbeit zeigten sie, dass ihr Modell in 5 Zeilen Matlab implementiert werden kann.

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

Wie der obige Algorithmus irgendetwas lernt, ist mir unklar. Wie funktioniert eine zufällige Küchenspüle? Wie werden Gaußsche Prozesse angenähert und Vektormaschinen unterstützt?

Bearbeiten

In Rahimis Vortrag wird der Begriff "Random Features for Large-Scale Kernel Machines" nicht in der Zeitung erwähnt, für die sie den Preis gewonnen haben, sondern am Ende der Trilogie der Arbeiten, die mit "Random Features for Large-Scale Kernel Machines" beginnt. Die anderen Papiere sind:

Rahimi, Ali und Benjamin Recht. "Einheitliche Approximation von Funktionen mit zufälligen Basen." Kommunikation, Kontrolle und Datenverarbeitung, 2008 46. Allerton-Jahreskonferenz am. IEEE, 2008.

Rahimi, Ali und Benjamin Recht. "Gewichtete Summen zufälliger Küchenspülen: Minimierung durch Zufallsgenerierung beim Lernen ersetzen." Fortschritte in neuronalen Informationsverarbeitungssystemen. 2009.

Ich denke, das oben eingeführte Code-Snippet ist eine Spezialisierung von Algorithmus 1 in der letzten Veröffentlichung.

MachineEpsilon
quelle
Weder das Wort "sink" noch der Code, den Sie zitieren, erscheinen auf dem verlinkten Papier. Vermissen Sie eine Referenz?
Kodiologist
2
Sie haben völlig recht, danke. Ohne den Kontext des Vortrags von 2017 scheint die Frage etwas unzusammenhängend zu sein! Die Idee wurde im ersten Artikel entwickelt, ich denke aber der Begriff zufällige Küchenspülen wurde erst später eingeführt. Das Code-Snippet wurde anscheinend auf der Postersession 2007 für das Papier verteilt. Ich habe es aus
Rahimis

Antworten:

14

Zufällige Küchenspülen (oder zufällige Fourier-Merkmale) und andere verwandte Methoden bemühen sich nicht um Inferenz, sondern versuchen, den Engpass kernbasierter Inferenzmethoden zu verringern.

n×nÖ(n3)

Zufällige Fourier-Merkmale (Rehimi & Recht 2007) haben erwogen, Annäherungen mit niedrigem Rang für verschiebungsinvariante Kernel zu erstellen, indem nur eine zufällige Teilmenge der Fourier-Kernelkomponenten abgetastet wurde. Da der Fourier-Raum verschiebungsinvariant ist, wurde diese Eigenschaft beibehalten, aber jetzt wurde durch die Vereinigung dieser Fourier-Komponenten ein expliziter, endlichdimensionaler, reproduzierender Kernel-Hilbert-Raum gebildet. Das einst unendlich dimensionale RKHS wird durch den entarteten Näherungskern angenähert.

Hinweise zum Code-Snippet: In den 5 Zeilen sind einige Details überstrichen. Das Wichtigste ist, dass die Gauß-Funktion auch eine Gauß-Funktion im Fourier-Raum ist, nur die Varianz wird invertiert. Deshalb werden sie von randn abgetastet und dann mit der Varianz multipliziert. Dann erzeugen sie Alpha, was nur eine Unterprozedur ist, um ztest zu finden. Im Wesentlichen sieht die normale Kernelvorhersage so aus:

ztest=K(xtest,x)(K(x,x)+λich)-1y.

ztest=Φ(xtest)TΦ(x)(Φ(x)TΦ(x)+λich)-1y.

Φ()

Nebenbemerkung: Solltest du es benutzen? Die Antwort ist kein klares Ja. Es hängt ganz davon ab, was Sie modellieren. Die Verwendung des Fourier-Raums ist nicht unbedingt für nicht stationäre nicht verschiebungsinvariante Kernel geeignet. Die Jungs haben nie behauptet, dass es in dieser Umgebung funktionieren würde, aber wenn man gerade erst in diesem Bereich anfängt, sind die Nuancen manchmal nicht offensichtlich.

j__
quelle
5
Es dauerte eine Sekunde, bis mir klar wurde, dass das Berechnen von Alpha hier das Ridge-Regressionsproblem in X und Y mit dem Regularizer Lambda löst. Wenn Sie von Hausärzten kommen und sich Ihre Formeln ansehen, ist dies ein wenig offensichtlich. Von einem SVM-Standpunkt aus gesehen ist dies etwas verwirrend. Ihre "normale Kernelvorhersage" ist ein GP mit Rauschen, auch bekannt als Kernel Ridge Regression.
Andreas Müller
1
@ AndreasMüller ja sorry das ist richtig! Ich bin ursprünglich sehr stark von der GP-Community, also übersehen Sie das manchmal! Ich bin froh, dass du verstanden hast, was ich meinte :)
17.
@j__, wenn du Zeit hast, habe ich hier eine Frage zu RFFs: stats.stackexchange.com/questions/440633 . Es hört sich so an, als ob die Antwort auf meine Frage darin besteht, RKHS und den Repräsentantensatz besser zu verstehen.
GWG