Support Vector Machine

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) dient als Klassifikator (vgl. Klassifizierung) und Regressor (vgl. Regressionsanalyse). 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 (dt. „Breiter-Rand-Klassifikator“).

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

Zwei mögliche Trenngeraden mit verschiedenen Randgrößen

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 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, sodass eine saubere Trennung mit einer Hyperebene nur dann möglich ist, wenn die Objekte linear trennbar sind. Diese Bedingung ist für reale Trainingsobjektmengen im Allgemeinen nicht erfüllt. Support Vector Machines verwenden im Fall nichtlinear trennbarer Daten den Kernel-Trick, um eine nichtlineare 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 nichtlinearen, unter Umständen sogar nicht zusammenhängenden Hyperfläche, welche 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 nichtlineare 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} _{i},y_{i})\mid i=1,\dotsc ,m;\ y_{i}\in \{-1,1\}\}$

eine Hyperebene, die beide Klassen möglichst eindeutig voneinander trennt.

Anschaulich bedeutet das Folgendes: Ein Normalenvektor $\mathbf {w}$ beschreibt eine Gerade durch den Koordinatenursprung. Senkrecht zu dieser Geraden verlaufen Hyperebenen. Jede schneidet die Gerade in einer bestimmten Entfernung ${\tfrac {b}{\|\mathbf {w} \|_{2}}}$ vom Ursprung (gemessen in der Gegenrichtung zu $\mathbf {w}$). Diese Entfernung nennt man Bias. Gemeinsam bestimmen der Normalenvektor und der Bias eindeutig eine Hyperebene, und für die zu ihr gehörenden Punkte $\mathbf {x}$ gilt:

$\langle \mathbf {w} ,\mathbf {x} \rangle +b=0$.

Für Punkte, die nicht auf der Hyperebene liegen, ist der Wert nicht Null, sondern positiv (auf der Seite, zu der $\mathbf {w}$ zeigt) bzw. negativ (auf der anderen Seite). Durch das Vorzeichen kann man die Seite benennen, auf der der Punkt liegt.

Wenn die Hyperebene die beiden Klassen voneinander trennt, dann ist das Vorzeichen für alle Punkte der einen Klasse positiv und für alle Punkte der anderen Klasse negativ. Ziel ist nun, eine solche Hyperebene zu finden.

Drückt man in den Trainingsbeispielen die Klassenzugehörigkeit durch $y_{i}=\pm 1$ aus, dann ergibt das eine formelmäßige Bedingung

$y_{i}=\operatorname {sgn}(\langle \mathbf {w} ,\mathbf {x} _{i}\rangle +b)$

Wenn überhaupt eine solche Hyperebene existiert, dann gibt es gleich unendlich viele, die sich nur minimal unterscheiden und teilweise sehr dicht an der einen oder anderen Klasse liegen. Dann besteht aber die Gefahr, dass Datenpunkte, denen man zukünftig begegnet, auf der „falschen“ Seite der Hyperebene liegen und somit falsch interpretiert werden.

Die Hyperebene soll daher so liegen, dass der kleinste Abstand der Trainingspunkte zur Hyperebene, das sogenannte Margin (von englisch margin, Marge), maximiert wird, um eine möglichst gute Generalisierbarkeit des Klassifikators zu garantieren.

Das sogenannte Training hat das Ziel, die Parameter $\mathbf {w}$ und $b$ dieser „besten“ Hyperebene zu berechnen.

Die Hyperebene wird dann als Entscheidungsfunktion benutzt. Das heißt: man geht davon aus, dass auch für zukünftige Datenpunkte das berechnete Vorzeichen die Klassenzugehörigkeit richtig wiedergeben wird. Insbesondere kann ein Computer die Klassifikation leicht und automatisch ausführen, indem er einfach das Vorzeichen berechnet.

Linear separierbare Daten

Viele Lernalgorithmen arbeiten mit einer Hyperebene, die im Zweidimensionalen durch eine lineare Funktion dargestellt werden kann. Sind zwei Klassen von Beispielen durch eine Hyperebene voneinander trennbar, d. h. linear separierbar, 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 +b)\geq 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 den Term ${\frac {1}{2}}\|\mathbf {w} \|_{2}^{2}$ durch Anpassung der Variablen $\mathbf {w} ,b$,

so dass die Nebenbedingung $y_{i}(\langle \mathbf {w} ,\mathbf {x} _{i}\rangle +b)\geq 1$ für alle $1\leq i\leq 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 $\xi _{i}$ für jede Nebenbedingung eingeführt, deren Wert gerade die Verletzung der Nebenbedingungen ist. $\xi _{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 Zielfunktion 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 den Term ${\frac {1}{2}}\|\mathbf {w} \|_{2}^{2}+C\sum _{i=1}^{m}\xi _{i}$ durch Anpassung der Variablen $\mathbf {w} ,b,\xi _{i}$,

sodass die Nebenbedingung $y_{i}(\langle \mathbf {w,x_{i}} \rangle +b)\geq 1-\xi _{i}$ für alle $1\leq i\leq m$ gilt.

Lösung

Klassische Lösung: Überführung in ein duales Problem

Siehe auch: Lagrange-Dualität

Beide Optimierungsprobleme sind konvex und können mit modernen Verfahren der konvexen Optimierung 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 (dünn türkis 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 den Karush-Kuhn-Tucker-Bedingungen hergeleitet. Sie lautet:

Maximiere für $\mathbf {\alpha } \colon$ $\sum _{i=1}^{m}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{m}\sum _{j=1}^{m}\alpha _{i}\alpha _{j}y_{i}y_{j}\langle \mathbf {x} _{i},\mathbf {x} _{j}\rangle$,

sodass die Nebenbedingungen $0\leq \alpha _{i}\leq C$ und $\sum _{i=1}^{m}\alpha _{i}y_{i}=0$ gelten.

Damit ergibt sich als Klassifikationsregel:

$f(\mathbf {x} )=\operatorname {sgn}(\langle \mathbf {w,x} \rangle +b)=\operatorname {sgn} \left(\sum _{i=1}^{m}\alpha _{i}y_{i}\langle \mathbf {x_{i},x} \rangle +b\right)$

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

Lösung mittels stochastischen Gradientenabstiegs

SVMs können mit stochastischem Gradientenabstieg trainiert werden.

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 \colon \mathbb {R} ^{d_{1}}\rightarrow \mathbb {R} ^{d_{2}},\mathbf {x} \mapsto \phi (\mathbf {x} )$

Dabei gilt $d_{1}<d_{2}$. Durch diese Abbildung wird die Anzahl möglicher linearer Trennungen erhöht (Theorem von Cover). 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 stattdessen eine positiv definite Kernelfunktion 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} )=\operatorname {sgn}(\langle \mathbf {w} ,\mathbf {\phi (x)} \rangle +b)=\operatorname {sgn} \left(\sum _{i=1}^{m}\alpha _{i}y_{i}k(\mathbf {x} _{i},\mathbf {x} )+b\right)$

mit $\textstyle \mathbf {w} =\sum _{i=1}^{m}\alpha _{i}y_{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 $\phi$ 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 hatte bereits 1936 Ronald A. Fisher. Wieder aufgegriffen wurde sie 1958 von Frank Rosenblatt in seinem Beitrag zur Theorie künstlicher neuronaler Netze. Die Idee der Support Vector Machines geht auf die Arbeit von Wladimir Wapnik und Alexei Jakowlewitsch Tscherwonenkis zurück. Auf theoretischer Ebene ist der Algorithmus vom Prinzip der strukturellen Risikominimierung motiviert, das besagt, dass nicht nur der Trainingsfehler, sondern auch die Komplexität des verwendeten Modells die Generalisierungsfähigkeit eines Klassifizierers bestimmen. Der eigentliche Durchbruch gelang Wapnik mit Bernhard Boser und Isabelle Guyon 1992 (Verwendung des Kernel-Tricks). Ebenfalls zu den Pionieren gehört eine weitere Mitarbeiterin von Wapnik bei den Bell Labs Anfang der 1990er Jahre, Corinna Cortes. In der Mitte der 1990er Jahre gelang den SVMs der Durchbruch, und zahlreiche Weiterentwicklungen und Modifikationen wurden in den letzten Jahren veröffentlicht.

Software

Bibliotheken für SVMs

• libsvm, implementiert in C++ und portiert nach Java
• liblinear, implementiert in C++ und portiert nach Java
• SVMlight, basiert auf C

Software für Maschinelles Lernen und Data-Mining, die SVMs enthalten

• GNU Octave verwendet SVMlight
• KNIME
• Matlab verwendet libsvm, SVMlight und Spider
• RapidMiner verwendet libsvm und eine in Java implementierte SVM
• Scikit-learn verwendet libsvm und liblinear.
• Shogun verwendet libsvm und SVMlight
• WEKA verwendet libsvm und Spider

SVM-Module für Programmiersprachen (Auswahl)

• Perl hat Module für libsvm und SVMlight
• R, hat Pakete basierend auf libsvm (Paket e1071), SVMlight (Paket klaR) und hat das Paket kernlab für Kernel-Lernen mit SVMs
• Ruby hat Module für libsvm und SVMlight

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 0-262-19475-9.
• Ingo Steinwart, Andreas Christmann: Support Vector Machines, Springer, New York, 2008. ISBN 978-0-387-77241-7. 602 pp.
• Nello Cristianini, John Shawe-Taylor: Kernel Methods for Pattern Analysis, Cambridge University Press, Cambridge, 2004, ISBN 0-521-81397-2
• Christopher J. C. Burges: A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 2(2):121–167, 1998.
• Vladimir Vapnik: Statistical Learning Theory, Wiley, Chichester, GB, 1998.
• Vladimir Vapnik: The Nature of Statistical Learning Theory, Springer Verlag, New York, NY, USA, 1995.