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(xn,x1)…⋱…k(x1,xn)⋮k(xn,xn)⎤⎦⎥⎥,
mmKK=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=[K11K21KT21K22],
K11m×mK21(n−m)×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ΛUT1U2ΛUT1U1ΛUT2U2ΛUT2],
U1m×mU2(n−m)×mK11=U1ΛUT1U1Λ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ΛUT1U2(ΛUT1)−1=U1Λ−1
U2=K21U1Λ−1.
K22K22=U2ΛUT2=(K21U1Λ−1)Λ(K21U1Λ−1)T=K21U1(Λ−1Λ)Λ−1UT1KT21=K21U1Λ−1UT1KT21=K21K−111KT21=(K21K−1211)(K21K−1211)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:
K21K−1211(n−m)×mK1211mm
Φ=⎡⎣⎢K1211K21K−1211⎤⎦⎥.
ΦΦΦT=⎡⎣⎢K1211K21K−1211⎤⎦⎥⎡⎣⎢K1211K21K−1211⎤⎦⎥T=⎡⎣⎢K1211K1211K21K−1211K1211K1211K−1211KT21K21K−1211K−1211KT21⎤⎦⎥=[K11K21KT21K21K−111KT21]=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)]K−1211.
x[k(x,x1)…k(x,xm)]K21K21K−1211ϕ(x)K11K11K−1211=K1211Φ. 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,1K−1211.
m[KtrainKtest,trainKtrain,testKtest]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 Rekonstruktionen
KmKnmK21Ktest,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 .K11K21K21K†11K11
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,10−12)