Kann Support Vector Machine in großen Datenmengen verwendet werden?

Mit dem begrenzten Wissen, das ich über SVM habe, ist es gut für eine kurze und fette Datenmatrix (viele Funktionen und nicht zu viele Instanzen), aber nicht für Big Data.$X$

Ich verstehe einen Grund dafür, dass die Kernel-Matrix eine n × n- Matrix ist, wobei n die Anzahl der Instanzen in den Daten ist. Wenn wir sagen, 100K Daten, die Kernmatrix K wird 10 10 Elemente und kann ~ 80G Erinnerungen nehmen.$K$$n \times n$$n$$K$$10^{10}$

Gibt es eine Modifikation von SVM, die in großen Datenmengen verwendet werden kann? (Sagen wir auf der Skala von 100K bis 1M Datenpunkten?)

Wie Sie bereits erwähnt haben, erfordert das Speichern der Kernelmatrix einen Speicher, der quadratisch mit der Anzahl der Datenpunkte skaliert. Die Trainingszeit für herkömmliche SVM-Algorithmen skaliert auch superlinear mit der Anzahl der Datenpunkte. Daher sind diese Algorithmen für große Datenmengen nicht durchführbar.

$K_{ij}$$x_i$$x_j$$K_{ij} = \Phi(x_i) \cdot \Phi(x_j)$$\Phi$wird implizit durch die Kernelfunktion definiert, und kernelisierte SVMs berechnen Feature-Space-Darstellungen nicht explizit. Dies ist für kleine bis mittlere Datensätze rechnerisch effizient, da der Merkmalsraum sehr hochdimensional oder sogar unendlich dimensioniert sein kann. Wie oben wird dies jedoch für große Datenmengen nicht mehr möglich. Stattdessen können wir die Daten explizit nichtlinear in den Merkmalsraum abbilden und dann effizient eine lineare SVM auf die Merkmalsraumdarstellungen trainieren. Die Feature-Space-Zuordnung kann so erstellt werden, dass sie sich einer bestimmten Kernelfunktion annähert, jedoch weniger Dimensionen verwendet als die vollständige Feature-Space-Zuordnung. Bei großen Datenmengen können wir immer noch umfangreiche Darstellungen des Funktionsbereichs erhalten, jedoch mit viel weniger Dimensionen als Datenpunkte.

Ein Ansatz zur Kernnäherung verwendet die Nyström-Näherung (Williams und Seeger 2001). Dies ist eine Möglichkeit, die Eigenwerte / Eigenvektoren einer großen Matrix unter Verwendung einer kleineren Submatrix zu approximieren. Ein anderer Ansatz verwendet zufällige Merkmale und wird manchmal als "zufällige Küchenspülen" bezeichnet (Rahimi und Recht 2007).

Ein weiterer Trick zum Trainieren von SVMs für große Datenmengen besteht darin, das Optimierungsproblem mit einer Reihe kleinerer Teilprobleme zu approximieren. Zum Beispiel ist die Verwendung eines stochastischen Gradientenabfalls für das ursprüngliche Problem ein Ansatz (unter vielen anderen). An der Optimierungsfront wurde viel Arbeit geleistet. Menon (2009) gibt eine gute Umfrage.

Verweise

Williams und Seeger (2001). Verwenden der Nystroem-Methode zum Beschleunigen von Kernel-Computern.

Rahimi und Recht (2007). Zufällige Funktionen für große Kernelmaschinen.

Menon (2009) . Große Support-Vektor-Maschinen: Algorithmen und Theorie.