Nystroem-Methode zur Kernel-Approximation

12

Ich habe über die Nyström-Methode für die Annäherung an Kernel mit niedrigem Rang gelesen. Diese Methode wird in scikit-learn [1] implementiert, um Datenproben auf eine niedrigrangige Näherung der Kernel-Feature-Mapping zu projizieren.

Nach meinem besten Wissen erzeugt es bei gegebenem Trainingssatz und einer Kernelfunktion eine niedrigrangige Approximation der Kernelmatrix durch Anwenden von SVD auf und .{xi}i=1nn×nKWC

K=[WK21TK21K22] C=[WK21] ,WRl×l

Aber ich verstehe nicht , wie die Low-Rang Approximation der Kernel - Matrix verwendet werden kann , neue Proben zu dem angenäherten Kernel - Feature Raum zu projizieren . Die Papiere, die ich gefunden habe (zB [2]), sind keine große Hilfe, da sie wenig didaktisch sind.

Ich bin auch neugierig auf die rechnerische Komplexität dieser Methode, sowohl in der Trainings- als auch in der Testphase.

[1] http://scikit-learn.org/stable/modules/kernel_approximation.html#nystroem-kernel-approx

[2] http://www.jmlr.org/papers/volume13/kumar12a/kumar12a.pdf

Daniel López
quelle

Antworten:

15

Lassen Sie uns die Nyström-Näherung so ableiten, dass die Antworten auf Ihre Fragen klarer werden.

Die Hauptannahme in Nyström ist, dass die Kernelfunktion den Rang . (Wir gehen wirklich davon aus, dass es ungefähr Rang , aber der Einfachheit halber tun wir einfach so, als wäre es genau Rang .) Das bedeutet, dass jede Kernelmatrix höchstens Rang haben wird , insbesondere ist Rang . Daher gibt es Eigenwerte ungleich Null, und wir können die Eigenzerlegung von als schreibenm m m K = [ k ( x 1 , x 1 ) k ( x 1 , x n ) ( k ( x n , x 1 ) k ( x n , x n ) ] , m m K K. = U Λ U T U n × m ×mmmm

K=[k(x1,x1)k(x1,xn)k(xn,x1)k(xn,xn)],
mmK
K=UΛUT
mit in gespeicherten Eigenvektoren mit der Form und Eigenwerten, die in angeordnet sind , einer Diagonalmatrix.Un×mmΛm×m

Wählen wir also Elemente aus, normalerweise gleichmäßig zufällig, aber möglicherweise nach anderen Schemata - alles, was in dieser vereinfachten Version zählt, ist, dass den vollen Rang hat. Sobald wir dies getan haben, beschriften Sie die Punkte einfach neu, sodass wir die Kernelmatrix in Blöcken erhalten: wo wir jeden Eintrag in (das ist ) und ( ) auswerten, aber keine Einträge in auswerten wollen .K 11 K = [ K 11 K T 21 K 21 K 22 ] , K 11 m × m K 21 ( n - m ) × m K 22mK11

K=[K11K21TK21K22],
K11m×mK21(nm)×mK22

Jetzt können wir die Eigendekomposition auch nach dieser Blockstruktur aufteilen: wo ist und ist . Beachten Sie jedoch, dass wir jetzt . Wir können also und indem wir die bekannte Matrix .

K=UΛUT=[U1U2]Λ[U1U2]T=[U1ΛU1TU1ΛU2TU2ΛU1TU2ΛU2T],
U1m×mU2(nm)×mK11=U1ΛU1TU1ΛK11

Wir wissen auch , dass . Hier wissen wir alles in dieser Gleichung außer , damit wir können, welche Eigenwerte dies implizieren: Multiplizieren Sie beide Seiten mit , um zu erhalten Jetzt haben wir alles, was wir brauchen, um zu bewerten : K21=U2ΛU1TU2(ΛU1T)1=U1Λ1

U2=K21U1Λ1.
K22
K22=U2ΛU2T=(K21U1Λ1)Λ(K21U1Λ1)T=K21U1(Λ1Λ)Λ1U1TK21T=K21U1Λ1U1TK21T(*)=K21K111K21T(**)=(K21K1112)(K21K1112)T.

In (*) haben wir eine Version der Nyström-Einbettung gefunden, die Sie möglicherweise einfach als Definition gesehen haben. Dies sagt uns die effektiven Kernelwerte, die wir für den Block .K22

In (**) sehen wir, dass die Merkmalsmatrix , die Form ist, diesen unterstellten Kernelwerten entspricht. Wenn wir für die Punkte verwenden, haben wir eine Reihe von dimensionalen Merkmalen Wir können nur schnell überprüfen, ob der richtigen Kernelmatrix entspricht: K21K1112(nm)×mK1112mm

Φ=[K1112K21K1112].
Φ
ΦΦT=[K1112K21K1112][K1112K21K1112]T=[K1112K1112K1112K1112K21TK21K1112K1112K21K1112K1112K21T]=[K11K21TK21K21K111K21T]=K.

Alles was wir tun müssen, ist unser reguläres Lernmodell mit den dimensionalen Merkmalen trainieren . Dies wird genau das gleiche (unter den Annahmen , die wir gemacht haben) als kernelized Version des Lernproblem mit .mΦK

Nun, für einen einzelnen Datenpunkt , die Merkmale in entsprechen Für einen Punkt in Partition 2 ist der Vektor nur die relevante Zeile von , so dass das Stapeln diese geben uns - also stimmt für Punkte in Partition 2 überein. Es funktioniert auch in Partition 1: Dort ist der Vektor eine Reihe von , also erhält das Stapeln und stimmt erneut mitxΦ

ϕ(x)=[k(x,x1)k(x,xm)]K1112.
x[k(x,x1)k(x,xm)]K21K21K1112ϕ(x)K11K11K1112=K1112Φ. Also ... es gilt immer noch für einen Testpunkt Zeitpunkt des Trainings nicht . Sie machen einfach das Gleiche: Da wir angenommen haben, dass der Kernel Rang , ist die Matrix hat ebenfalls den Rang , und die Rekonstruktion von ist nach genau derselben Logik wie bei immer noch genau .xnew
Φtest=Ktest,1K1112.
m[KtrainKtrain,testKtest,trainKtest]mKtestK22


Oben, gingen wir davon aus, dass die Kernmatrix war genau Rang . Dies wird normalerweise nicht der Fall sein; für einen Gauß - Kern, beispielsweise ist immer Rang , aber die letztere Eigenwert normalerweise ziemlich schnell abfallen, so dass es sein wird nahe an eine Matrix von Rang , und unsere Rekonstruktionen von oder werden nahe an den wahren Werten liegen, aber nicht genau gleich. Je näher der Eigenraum von dem von kommt, besser sind die RekonstruktionenKmKnmK21Ktest,1K11KInsgesamt ist die Auswahl der richtigen Punkte in der Praxis daher wichtig.m

Beachten Sie auch, dass Sie, wenn Null-Eigenwerte hat, Inversen durch Pseudoinverse ersetzen können und alles immer noch funktioniert. Sie ersetzen einfach in der Rekonstruktion durch .K11K21K21K11K11

Sie können die SVD anstelle der Eigendekomposition verwenden, wenn Sie möchten. Da psd ist, sind sie dasselbe, aber die SVD ist möglicherweise etwas robuster gegenüber geringfügigen numerischen Fehlern in der Kernel-Matrix und dergleichen. Genau das macht Scikit-Learn. Die eigentliche Implementierung von scikit-learn tut dies, obwohl sie in der Inversen anstelle der Pseudoinverse verwendet.Kmax(λi,1012)

Dougal
quelle
1
Wenn positiv semidefinit ist, stimmt die Eigenzerlegung mit der SVD überein. Scikit-Learn, weil aufgrund numerischer Fehler könnte leicht nicht-psd sein, berechnet statt und verwendet , so dass ‚s Funktionen werden . Im Grunde ist es dasselbe. AUΛUTAUΣVTA12=VΣ12VTAAVΣ12VT=UΣVTVΣ12VT=UΣ12VT=A12
Dougal
1
Hoppla, sorry, ja, sie benutzen . Es ist nicht wirklich wichtig, seit , aber da sie die Transponierung durchführen, enden die Funktionen für als . UΣ12VT=K12UVK11UΣVTVΣ12UT=UΣ12UT
Dougal
1
Das Erhöhen einer Diagonalmatrix auf eine Potenz entspricht dem Erhöhen jedes Elements auf eine Potenz und . In der Numpy-Broadcast-Notation entspricht die elementweise Multiplikation mit einem Vektor der rechten Multiplikation mit einer Diagonalmatrix. Außerdem verwendet dieser Code zu bedeuten, was ich . VVT.x12=1/xVVT
Dougal
1
Hoppla, sorry, das sollte nur bis zu (in der neu beschrifteten Reihenfolge, damit das die Nyström-Basispunkte sind). Wird behoben. xm
Dougal
1
x R d x X k : X × XR ϕ : XR m k ( x , x i ) mx ist ein Datenpunkt, dessen Dimension hier nicht angegeben ist. könnte in , oder es könnte eine Zeichenfolge oder etwas sein; einfach sagen , dass , so dass . Dann stapelt nur für verschiedene Eingaben. xRdxXk:X×XRϕ:XRmk(x,xi)m
Dougal