Support-Vektor-Maschine

Eine Support Vector Machine [səˈpɔːt ˈvektə məˈʃiːn] (SVM, die Übersetzung aus dem Englischen, „Stützvektormaschine“ oder Stützvektormethode, ist nicht gebräuchlich) ist ein Klassifikator (vgl. Klassifizierung). Eine Support Vector Machine unterteilt eine Menge von Objekten so in Klassen, dass um die Klassengrenzen herum ein möglichst breiter Bereich frei von Objekten bleibt; sie ist ein sogenannter Large Margin Classifier (engl. „Breiter-Rand-Klassifikator“). Support Vector Machines können zur Klassifizierung als auch zur Regression verwendet werden.

Support Vector Machines sind keine Maschinen im herkömmlichen Sinne, bestehen also nicht aus greifbaren Bauteilen. Es handelt sich um ein rein mathematisches Verfahren der Mustererkennung, das in Computerprogrammen umgesetzt wird. Der Namensteil machine weist dementsprechend nicht auf eine Maschine hin, sondern auf das Herkunftsgebiet der Support Vector Machines, das maschinelle Lernen.

Grundlegende Funktionsweise

Ausgangsbasis für den Bau einer Support Vector Machine ist eine Menge von Trainingsobjekten, für die jeweils bekannt ist, welcher Klasse sie zugehören. Jedes Objekt wird durch einen Vektor in einem Vektorraum repräsentiert. Aufgabe der Support Vector Machine ist es, in diesen Raum eine mehrdimensionale Hyperebene einzupassen, die als Trennfläche fungiert und die Trainingsobjekte in zwei Klassen teilt. Der Abstand derjenigen Vektoren, die der Hyperebene am nächsten liegen, wird dabei maximiert. Dieser breite, leere Rand soll später dafür sorgen, dass auch Objekte, die nicht genau den Trainingsobjekten entsprechen, möglichst zuverlässig klassifiziert werden.

Beim Einsetzen der Hyperebene ist es nicht notwendig, alle Trainingsvektoren zu beachten. Vektoren, die weiter von der Hyperebene entfernt liegen und gewissermaßen hinter einer Front anderer Vektoren „versteckt“ sind, beeinflussen Lage und Position der Trennebene nicht. Die Hyperebene ist nur von den ihr am nächsten liegenden Vektoren abhängig – und auch nur diese werden benötigt, um die Ebene mathematisch exakt zu beschreiben. Diese nächstliegenden Vektoren werden nach ihrer Funktion Stützvektoren (engl. support vectors) genannt und verhalfen den Support Vector Machines zu ihrem Namen.

Lineare Trennbarkeit

Eine Hyperebene kann nicht „verbogen“ werden, so dass eine saubere Trennung mit einer Hyperebene nur dann möglich ist, wenn die Objekte linear trennbar sind. Dies ist in realen Anwendungsfällen im Allgemeinen nicht der Fall. Support Vector Machines verwenden im Fall nicht linear trennbarer Daten den Kernel-Trick, um eine nicht lineare Klassengrenze einzuziehen.

Die Idee hinter dem Kernel-Trick ist, den Vektorraum und damit auch die darin befindlichen Trainingsvektoren in einen höherdimensionalen Raum zu überführen. In einem Raum mit genügend hoher Dimensionsanzahl – im Zweifelsfall unendlich – wird auch die verschachteltste Vektormenge linear trennbar. In diesem höherdimensionalen Raum wird nun die trennende Hyperebene bestimmt. Bei der Rücktransformation in den niedrigerdimensionalen Raum wird die lineare Hyperebene zu einer nicht linearen, unter Umständen sogar nicht zusammenhängenden Hyperfläche, die die Trainingsvektoren sauber in zwei Klassen trennt.

Bei diesem Vorgang stellen sich zwei Probleme: Die Hochtransformation ist enorm rechenlastig und die Darstellung der Trennfläche im niedrigdimensionalen Raum im Allgemeinen unwahrscheinlich komplex und damit praktisch unbrauchbar. An dieser Stelle setzt der Kernel-Trick an. Verwendet man zur Beschreibung der Trennfläche geeignete Kernelfunktionen, die im Hochdimensionalen die Hyperebene beschreiben und trotzdem im Niedrigdimensionalen „gutartig“ bleiben, so ist es möglich, die Hin- und Rücktransformation umzusetzen, ohne sie tatsächlich rechnerisch ausführen zu müssen. Auch hier genügt ein Teil der Vektoren, nämlich wiederum die Stützvektoren, um die Klassengrenze vollständig zu beschreiben.

Sowohl lineare als auch nicht lineare Support Vector Machines lassen sich durch zusätzliche Schlupfvariablen flexibler gestalten. Die Schlupfvariablen erlauben es dem Klassifikator, einzelne Objekte falsch zu klassifizieren, „bestrafen“ aber gleichzeitig jede derartige Fehleinordnung. Auf diese Weise wird zum einen Überanpassung vermieden, zum anderen wird die benötigte Anzahl an Stützvektoren gesenkt.

Mathematische Umsetzung

Die SVM bestimmt anhand einer Menge von Trainingsbeispielen

$\{( \mathbf x_1, y_1),..., ( \mathbf x_m, y_m )\}, \mathbf x_i\in \mathcal X, y_i \in \{-1,1\}$

eine Hyperebene, die beide Klassen so voneinander trennt, dass der kleinste Abstand zur Hyperebene, dem sogenannten Margin, für die Beispiele beider Klassen maximiert wird, um eine möglichst gute Generalisierbarkeit des Klassifikators zu garantieren. Dabei gibt y_i die Klassenzugehörigkeit für das Trainingsbeispiel $\mathbf x_i$ an. Das sogenannte Training berechnet die Hyperebene, die die Trainingsbeispiele beider Klassen bestmöglich teilt. Sie wird dann als Entscheidungsfunktion benutzt. Sie ist gegeben durch einen Normalenvektor $\mathbf w$ und einen sogenanntes Bias $\mathbf b$. Einem Trainingsbeispiel $\mathbf x_i$ wird dabei das Vorzeichen der Entscheidungsfunktion als Klasse zugeordnet:

$y_i = sgn(\langle \mathbf w, \mathbf x_i \rangle + \mathbf b )$.

Je nachdem wo sich die Beispiele relativ zur Hyperebene befinden (oberhalb oder unterhalb), errechnet sich ein positiver oder negativer Wert, wo nach Anwendung der sgn-Funktion nur noch +/- 1 verbleibt. Für Beispiele, die genau auf der Trennebene liegen, wird dieser Wert zu 0.

Linear separierbare Daten

Viele Lernalgorithmen arbeiten mit einer linearen Funktion in Form einer Hyperebene. Sind zwei Klassen von Beispielen durch eine Hyperebene voneinander trennbar, d.h. linear separierbar, dann gibt es jedoch in der Regel unendlich viele Hyperebenen, die die beiden Klassen voneinander trennen. Die SVM unterscheidet sich von anderen Lernalgorithmen dadurch, dass sie von allen möglichen trennenden Hyperebenen diejenige mit minimaler quadratischer Norm $||\mathbf w||_2^2$ auswählt, so dass gleichzeitig $y_i ( \langle \mathbf w , \mathbf x_i \rangle + \mathbf b ) \ge 1$ für jedes Trainingsbeispiel $\mathbf x_i$ gilt. Dies ist mit der Maximierung des kleinsten Abstands zur Hyperebene (dem Margin) äquivalent. Nach der statistischen Lerntheorie ist die Komplexität der Klasse aller Hyperebenen mit einem bestimmten Margin geringer als die der Klasse aller Hyperebenen mit einem kleineren Margin. Daraus lassen sich obere Schranken für den erwarteten Generalisierungsfehler der SVM ableiten.

Das Optimierungsproblem kann dann geschrieben werden als:

minimiere bezüglich $\mathbf{w,b}$: $\frac{1}{2} ||\mathbf w||_2^2$,

so dass die Nebenbedingung $y_i ( \langle \mathbf w, \mathbf x_i \rangle + \mathbf b) \ge 1$ für alle $1\le i\le m$ gilt.

Nicht-linear separierbare Daten

In der Regel sind die Trainingsbeispiele nicht streng linear separierbar. Dies kann u.a. an Messfehlern in den Daten liegen, oder daran, dass die Verteilungen der beiden Klassen natürlicherweise überlappen. Für diesen Fall wird das Optimierungsproblem derart verändert, dass Verletzungen der m Nebenbedingungen möglich sind, die Verletzungen aber so klein wie möglich gehalten werden sollen. Zu diesem Zweck wird eine positive Schlupfvariable ξ_i für jede Nebenbedingung eingeführt, deren Wert gerade die Verletzung der Nebenbedingungen ist. ξ_i > 0 bedeutet also, dass die Nebenbedingung verletzt ist. Da in der Summe die Verletzungen möglichst klein gehalten werden sollen, wird die Summe der Fehler der Zielfunktionen hinzugefügt und somit ebenso minimiert. Zusätzlich wird diese Summe mit einer positiven Konstante C multipliziert, die den Ausgleich zwischen der Minimierung von $\frac{1}{2} ||\mathbf w||_2^2$ und der korrekten Klassifizierung der Trainingsbeispiele regelt. Das Optimierungsproblem besitzt dann folgende Form:

minimiere bezüglich $\mathbf{w,b}$: $\frac{1}{2} ||\mathbf w||_2^2 + C \sum_{i=1}^m \xi_i$,

so dass die Nebenbedingung $y_i(\langle \mathbf{w,x_i}\rangle+\mathbf b) \ge 1 - \xi_i$ für alle $1\le i\le m$ gilt.

Duales Problem

Beide Optimierungskriterien sind konvex und können mit modernen Verfahren effizient gelöst werden. Diese einfache Optimierung und die Eigenschaft, dass Support-Vector-Machines eine Überanpassung an die zum Entwurf des Klassifikators verwendeten Testdaten großteils vermeiden, haben der Methode zu großer Beliebtheit und einem breiten Anwendungsgebiet verholfen.

Beispiel für eine Klassifizierung mit einer SVM. Zu sehen ist die in den Eingangsraum abgebildete trennende Hyperebene (schwarze Linie) und die Support-Vektoren (blau umkreist).

Das oben beschriebene Optimierungsproblem wird normalerweise in seiner dualen Form gelöst. Diese Formulierung ist äquivalent zu dem primalen Problem, in dem Sinne, dass alle Lösungen des dualen auch Lösungen des primalen Problems sind. Die Umrechnung ergibt sich dadurch, dass der Normalenvektor $\mathbf w$ als Linearkombination aus Trainingsbeispielen geschrieben werden kann:

$\mathbf w = \sum_{i=1}^m \alpha_i y_i \mathbf x_i$

Die duale Form wird mit Hilfe der Lagrange-Multiplikatoren und der Karush-Kuhn-Tucker-Bedingungen hergeleitet. Sie lautet:

maximiere für $\mathbf \alpha$: $\sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{j=1}^m \alpha_i \alpha_j y_i y_j \langle \mathbf x_i, \mathbf x_j \rangle$,

so dass die Nebenbedingungen $0 \le \alpha_i \le C$ und $\sum_{i=1}^m \alpha_i y_i = 0$ gelten.

Damit ergibt sich als Klassifikationsregel:

$f(\mathbf x)= sgn (\langle \mathbf{w,x}\rangle +\mathbf b) = sgn\left(\sum_{i=1}^m \alpha_i y_i \langle \mathbf{x_i, x}\rangle +\mathbf b \right)$

Ihren Namen hat die SVM von einer speziellen Untermenge der Trainingspunkte, deren Lagrangevariablen $\alpha_i \neq 0$. Diese heißen Support-Vektoren und liegen entweder auf dem Margin (falls $y_i(\langle \mathbf{w,x}\rangle+\mathbf b) = 1$) oder innerhalb des Margin (ξ_i > 0).

Nichtlineare Erweiterung mit Kernelfunktionen

Der oben beschriebene Algorithmus klassifiziert die Daten mit Hilfe einer linearen Funktion. Diese ist jedoch nur optimal, wenn auch das zu Grunde liegende Klassifikationsproblem linear ist. In vielen Anwendungen ist dies aber nicht der Fall. Ein möglicher Ausweg ist, die Daten in einen Raum höherer Dimension abzubilden.

$\phi: \mathbb{R}^{d_1} \rightarrow \mathbb{R}^{d_2}, \mathbf x\mapsto \phi(\mathbf x)$

Dabei gilt d₁ < d₂. Durch diese Abbildung wird die Anzahl möglicher linearer Trennungen erhöht (Theorem von Cover ^[1]). SVMs zeichnen sich dadurch aus, dass sich diese Erweiterung sehr elegant einbauen lässt. In das dem Algorithmus zu Grunde liegende Optimierungsproblem in der zuletzt dargestellten Formulierung gehen die Datenpunkte $\mathbf x_i$ nur in Skalarprodukten ein. Daher ist es möglich, das Skalarprodukt $\langle \mathbf x_i,\mathbf x_j\rangle$ im Eingaberaum $\mathbb{R}^{d_1}$ durch ein Skalarprodukt im $\mathbb{R}^{d_2}$ zu ersetzen und $\langle \phi(\mathbf x_i),\phi(\mathbf x_j)\rangle$ stattdessen direkt zu berechnen. Die Kosten dieser Berechnung lassen sich sehr stark reduzieren, wenn eine positiv definite Kernelfunktion stattdessen benutzt wird:

$k(\mathbf x_i,\mathbf x_j)=\langle \phi(\mathbf x_i),\phi(\mathbf x_j)\rangle$

Durch dieses Verfahren kann eine Hyperebene (d.h. eine lineare Funktion) in einem hochdimensionalen Raum implizit berechnet werden. Der resultierende Klassifikator hat die Form

$f(\mathbf x)= sgn (\langle \mathbf{w,x}\rangle +\mathbf b) = sgn\left(\sum_{i=1}^m \alpha_i y_i k(\mathbf x_i, \mathbf x) +\mathbf b \right)$

mit $\mathbf w=\sum_{i=1}^m \alpha_i \phi(\mathbf x_i)$. Durch die Benutzung von Kernelfunktionen können SVMs auch auf allgemeinen Strukturen wie Graphen oder Strings operieren und sind daher sehr vielseitig einsetzbar. Obwohl durch die Abbildung φ implizit ein möglicherweise unendlich-dimensionaler Raum benutzt wird, generalisieren SVM immer noch sehr gut. Es lässt sich zeigen, dass für Maximum-Margin-Klassifizierer der erwartete Testfehler beschränkt ist und nicht von der Dimensionalität des Raumes abhängt.

Geschichte

Die Idee der Trennung durch eine Hyperebene wurde erstmals 1958 von Frank Rosenblatt veröffentlicht ^[2]. Die Idee der Support-Vector-Machines geht auf die Arbeit von Wladimir Wapnik und Aleksei Chervonenkis^[3] zurück. Auf theoretischer Ebene ist der Algorithmus vom Prinzip der strukturellen Risikominimierung motiviert, welches besagt, dass nicht nur der Trainingsfehler, sondern auch die Komplexität des verwendeten Modells die Generalisierungsfähigkeit eines Klassifizierers bestimmen. In der Mitte der 1990er Jahre gelang den SVMs der Durchbruch, und zahlreiche Weiterentwicklungen und Modifikationen wurden in den letzten Jahren veröffentlicht.

Literatur

• Bernhard Schölkopf, Alex Smola: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond (Adaptive Computation and Machine Learning), MIT Press, Cambridge, MA, 2002, ISBN 0262194759.
• Nello Cristianini, John Shawe-Taylor: Kernel Methods for Pattern Analysis, Cambridge University Press, Cambridge, 2004, ISBN 0521813972
• Christopher J. C. Burges: A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 2(2):121-167, 1998.
• Wladimir Wapnik: Statistical Learning Theory, Wiley, Chichester, GB, 1998.
• Wladimir Wapnik: The Nature of Statistical Learning Theory, Springer Verlag, New York, NY, USA, 1995.

Weblinks

• http://www.learning-with-kernels.org/ (6 Kapitel aus Learning with Kernels)
• http://research.microsoft.com/~cburges/papers/SVMTutorial.pdf (Chris Burges Tutorial)
• http://lectures.molgen.mpg.de/statistik/docs/Kapitel_16.pdf
• http://www.kernel-machines.org/
• http://www.kyb.tuebingen.mpg.de/bu/people/bs/svm.html (B. Schölkopfs Seite über SVMs)
• http://lcn.epfl.ch/tutorial/english/svm/html/index.html

Software

• libSVM Häufig benutzte SVM-Implementierung mit vielen Extras
• RapidMiner (früher YALE) Ein einfach zu bedienendes und frei erhältliches Tool für Maschinelles Lernen und Data-Mining. Auswahl zwischen verschiedenen SVM-Implementierungen. Unter anderem libsvm, sowie eine in Java implementierte SVM.
• SVMlight Implementation einer SVM in C (Bindings für Perl und Java verfügbar)
• Torch Machine Learning Bibliothek in C++
• kernlab Machine Learning Bibliothek in R mit SVM-Implementierung
• Shogun Machine Learning Toolbox für große Datenmengen mit generischen Anbindungen zu vielen SVM-Implementierungen, wie zB. libSVM, SVMlight (mit Interfaces zu Octave, Matlab, Python, R)
• Spider Machine Learning Toolbox für MATLAB, in der auch die SVM implementiert ist
• Lush Eine Lisp-ähnliche interpretierte/compilierte Sprache mit C/C++/Fortran Interfaces und Paketen für verschiedene SVM-Implementierungen (LASVM, LIBSVM, mySVM, SVQP, SVQP2), sowie u.A. Hidden Markov Modellen.
• Weka Eine freie, plattformunabhängige Software mit einer großen Sammlung von verschiedenen Klassifikations- und Regressionsalgorithmen und Methoden
• OpenCV Die OpenCV Machine Learning Library enthält ebenfalls eine SVM-Implementierung.

Quellen

1. ↑ Schölkopf, Smola: Learning with Kernels, MIT Press, 2001
2. ↑ Rosenblatt, F. (1958), "The Perceptron, a Probabilistic Model for Information Storage and Organisation in the Brain", in Psychological Review, 62/386
3. ↑ Vapnik und Chervonenkis, Theory of Pattern Recognition,1974 (dt. Übersetzung: Wapnik und Tschervonenkis, Theorie der Mustererkennung, 1979)