Kernelised k Nächster Nachbar

Ich bin neu in Kerneln und habe beim Versuch, kNN zu kerneln, einen Haken bekommen.

Vorbereitungen

Ich verwende einen Polynomkern:
$K(\mathbf{x},\mathbf{y}) = (1 + \langle \mathbf{x},\mathbf{y} \rangle)^d$

Ihr typischer euklidischer kNN verwendet die folgende Abstandsmetrik:
$d(\mathbf{x}, \mathbf{y}) = \vert\vert \mathbf{x} - \mathbf{y} \vert\vert$

Lassen Sie \ mathbf {x} in einen höherdimensionalen Merkmalsraum abbilden . Dann kann das Quadrat der obigen Distanzmetrik im Hilbert-Raum durch innere Produkte ausgedrückt werden: d ^ 2 (f (x), f (y)) = K (\ mathbf {x}, \ mathbf {x}) - 2K ( \ mathbf {x}, \ mathbf {y}) + K (\ mathbf {y}, \ mathbf {y})$f(\mathbf{x})$$\mathbf{x}$$d^2(f(x), f(y)) = K(\mathbf{x},\mathbf{x}) - 2K(\mathbf{x}, \mathbf{y}) + K(\mathbf{y} ,\mathbf{y})$

Beachten Sie, dass, wenn wir $d = 1$ das Obige zu Ihrem euklidischen Standardabstand degeneriert.

Die Frage

Das Hauptproblem, das ich habe, ist, dass ich nicht sehen kann, wie das Kernelisieren von kNN zu besseren Ergebnissen führt, wie dies beispielsweise in diesem Artikel experimentell gezeigt wird (Warnung, direkter PDF-Link!).

Satz von Cover: Grob gesagt heißt es, dass bei einer zufälligen Menge endlicher Punkte (mit willkürlichen Bezeichnungen) diese Punkte mit hoher Wahrscheinlichkeit linear trennbar gemacht werden können [1], indem sie auf eine höhere Dimension abgebildet werden [2].

Implikation: Großartig, dieses Theorem sagt mir, dass ich leicht einen linearen Klassifikator finden kann, wenn ich meinen Datensatz nehme und diese Punkte einer höheren Dimension zuordne. Die meisten Klassifizierer müssen jedoch eine Ähnlichkeit wie das Punktprodukt berechnen, und dies bedeutet, dass die zeitliche Komplexität eines Klassifizierungsalgorithmus proportional zur Dimension des Datenpunkts ist. Eine höhere Dimension bedeutet also eine größere zeitliche Komplexität (ganz zu schweigen von der räumlichen Komplexität zum Speichern dieser großen dimensionalen Punkte).

Kernel-Trick: Sei die ursprüngliche Dimension von Datenpunkten und die Karte, die diese Punkte auf einen Raum der Dimension abbildet . Wenn es nun eine Funktion die Eingaben und aus dem ursprünglichen Raum nimmt und berechnet, kann ich das Punktprodukt berechnen im höherdimensionalen Raum, aber in der Komplexität anstelle von .$n$$f$$N (>> n)$$K$$x$$y$$K(x, y) = \langle f(x), f(y) \rangle$$O(n)$$O(N)$

Implikation: Wenn also der Klassifizierungsalgorithmus nur vom Punktprodukt abhängig ist und keine Abhängigkeit von der tatsächlichen Karte , kann ich den Kernel-Trick verwenden, um den Algorithmus im hochdimensionalen Raum fast ohne zusätzliche Kosten auszuführen.$f$

Bedeutet die lineare Trennbarkeit, dass Punkte derselben Klasse näher kommen als Punkte verschiedener Klassen? Nein, es gibt keine solche Garantie. Die lineare Trennbarkeit bedeutet nicht wirklich, dass der Punkt aus derselben Klasse näher gekommen ist oder dass die Punkte aus zwei verschiedenen Klassen weiter fortgeschritten sind.

Warum sollte kNN funktionieren? Es muss nicht! Wenn dies jedoch der Fall ist, liegt dies ausschließlich am Kernel.

Was bedeutet das? Betrachten Sie den booleschen Merkmalsvektor . Wenn Sie einen Polynomkern Grades verwenden, wird der Merkmalsvektor auf den Vektor abgebildet$x = (x_1, x_2)$$x$$(x_1^2, \sqrt{2} x_1x_2, x_2^2)$. Aus einem Vektor boolescher Merkmale haben wir unter Verwendung eines Polynoms zweiten Grades einen Merkmalsvektor von "Konjunktionen" erhalten. Somit erzeugen die Kernel selbst einige brillante Feature-Maps. Wenn Ihre Daten gute Originalfunktionen aufweisen und Ihre Daten von den von diesen Kerneln erstellten Funktionszuordnungen profitieren könnten. Mit Vorteil meine ich, dass die von diesen Feature-Maps erzeugten Features die Punkte derselben Klasse näher zusammenbringen und Punkte aus verschiedenen Klassen wegschieben können. Dann kann kNN von der Verwendung von Kerneln profitieren. Andernfalls unterscheiden sich die Ergebnisse nicht von denen, die Sie erhalten, wenn Sie kNN für die Originaldaten ausführen.

Warum dann Kernel kNN verwenden? Wir haben gezeigt, dass der Rechenaufwand bei der Verwendung von Kerneln nur geringfügig über dem üblichen kNN liegt. Wenn Daten von der Verwendung von Kerneln profitieren, warum sollten Sie sie dann nicht trotzdem verwenden?

Gibt es ein Papier, das untersucht hat, welche Datenklasse von Kerneln in kNN profitieren kann? Soweit ich weiß, nein.

[1] http://en.wikipedia.org/wiki/Linear_separability
[2] http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4038449&tag=1