Support Vector Machine

Eine Support-Vector-Machine (SVM, von engl. support vector machine, „Stützvektormaschine“, die dt. Übersetzung ist nicht gebräuchlich) ist ein Klassifikator. Eine Support-Vector-Machine teilt Objekte so in zwei Klassen auf, dass die Klassengrenze möglichst weit von allen Objekten entfernt liegt. Es entsteht ein leerer Rand um die Klassengrenze herum, dessen Breite maximiert wird; man spricht daher auch von einem large-margin-Klassifikationsverfahren (engl. „großer Rand“).

Die zum Verständnis notwendigen Grundbegriffe dieses Artikels werden im Artikel Klassifizierung erläutert.

Grundlegende Funktionsweise

Die Support-Vektor-Maschine (SVM) ist ein Lernalgorithmus zur Klassifizierung von Objekten. Die SVM bestimmt anhand einer Menge von Trainingsbeispielen $\{(x_{1},y_{1}),...,(x_{m},y_{m})\},x_{i}\in {\mathcal {X}},y_{i}\in \{-1,1\}$ eine Hyperebene, die beide Klassen so voneinander trennt, daß der kleinste Abstand zur Hyperebene, dem sog. margin, für die Beispiele beider Klassen maximiert wird. Das sog. label $y_{i}$ gibt dabei die Klassenzugehörigkeit für das Beispiel $x_{i}$ an. Die Hyperebene wird nach dem sog. Training, d.h. der Berechnung der Hyperebene zwischen den Trainingsbeispielen, als Entscheidungsfunktion benutzt. Sie ist gegeben durch einen Normalenvektor $\mathbf {w}$ und einen sog. Bias $b$. Einem Beispiel $x$ wird dabei das Vorzeichen der Entscheidungsfunktion als Label zugeordnet:

$y=sgn(\langle \mathbf {w} ,x\rangle +b)$.

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, daß sie von allen möglichen trennenden Hyperebenen diejenige mit minimaler quadratischer Norm $||\mathbf {w} ||_{2}^{2}$ auswählt, so daß gleichzeitig $y_{i}(\langle \mathbf {w} ,x\rangle +b)\geq 1$ für jedes Trainingsbeispiel $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${}_{\mathbf {w} ,b}{\frac {1}{2}}||w||_{2}^{2}$ so daß $y_{i}(\langle \mathbf {w} ,x\rangle +b)\geq 1$ für alle $1\leq i\leq m$

In der Regel sind die Trainingsbeispiele nicht streng linear separierbar. Dies kann u.a. an Meßfehlern in den Daten liegen, oder daran, daß die Verteilungen der beiden Klassen natürlicherweise überlappen. Für diesen Fall wird das Optimierungsproblem derart verändert, daß Verletzungen der 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 Nebenbedingungen eingeführt, deren Wert gerade die Verletzung der Nebenbedingungen ist. $\xi _{i}>0$ bedeutet also, daß 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}}||w||_{2}^{2}$ und der korrekten Klassifizierung der Trainingsbeispiele regelt. Das Optimierungsproblem besitzt dann folgende Form:

minimiere${}_{\mathbf {w} ,b}{\frac {1}{2}}||w||_{2}^{2}+C\sum _{i=1}^{m}\xi _{i}$ so daß $y_{i}(\langle \mathbf {w} ,x\rangle +b)\geq 1-\xi _{i}$ für alle $1\leq i\leq m$

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

Abb. 1. Beispiel für eine Klassifizierung mit einer SVM. Zu sehen ist die trennende gekrümmte Hyperfläche (schwarze Linie) und die Support-Vektoren (blau umkreist).

Das oben beschriebene Optimierungsproblem wird normalerweise in seiner dualen Form gelößt. Diese wird mit Hilfe der Langrange-Multiplikatoren und der Karush-Kuhn-Tucker-Bedingungen hergeleitet. Sie lautet:

minimiere${}_{\mathbf {\alpha } }\sum _{i=1}^{m}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{m}\alpha _{i}\alpha _{j}y_{i}y_{j}\langle x_{i},x_{j}\rangle$ so daß $0\leq \alpha _{i}\leq C$ und $\sum _{i=1}^{m}\alpha _{i}y_{i}=0$

Diese Formulierung ist äquvivalent zu dem primalen Problem, in dem Sinne, dass alle Lösungen des dualen auch Lösungen des primalen Problems sind. Der Normalenvektor $w$ kann dann als Linearkombination aus Trainingsbeispielen geschrieben werden:

$w=\sum _{i=1}^{m}\alpha _{i}y_{i}x_{i}$

Damit ergibt sich als Klassifikationsregel:

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

Ihren Namen hat die SVM von einer speziellen Untermenge der Trainingspunkte, deren Langrangevariablen $\alpha _{i}\neq 0$. Diese heissen 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$).

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}},x\rightarrow \phi (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äßt. In das dem Algorithmus zu Grunde liegende Optimierungsproblem in der zu letzt dargestellten Formulierung gehen die Datenpunkte $x_{i}$ nur in Skalarprodukten ein. Daher ist es möglich, das Skalarprodukt $\langle x_{i},x_{j}\rangle$ im Eingaberaum $\mathbb {R} ^{d_{1}}$ durch ein Skalarprodukt im $\mathbb {R} ^{d_{2}}$ zu ersetzen und $\langle \phi (x_{i}),\phi (x_{j})\rangle$ stattdessen direkt zu berechnen. Die Kosten dieser Berechnung lassen sich sehr stark reduzieren, wenn eine positiv definiter Kernelfunktion stattdessen benutzt wird:

$k(x_{i},x_{j})=\langle \phi (x_{i}),\phi (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(x)=sgn(\langle w,x\rangle +b)=sgn\left(\sum _{i=1}^{m}\alpha _{i}y_{i}k(x_{i},x)+b\right)$

mit $w=\sum _{i=1}^{m}\alpha _{i}\phi (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äßt 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 . Die Idee der Support-Vector-Machines geht auf die Arbeit von Vladimir Vapnik und Aleksei Chervonenkis 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 Klassifizieres 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.

Weblinks

• http://www.learning-with-kernels.org/ (3 Kapitel aus Learning with Kernels)
• http://research.microsoft.com/copyright/accept.asp?path=http://research.microsoft.com/~cburges/papers/SVMTutorial.pdf&pub=1 (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://diwww.epfl.ch/mantra/tutorial/english/svm/html/index.html

Software

• http://www.kyb.tuebingen.mpg.de/bs/people/spider/main.html - Machine Learning Toolbox für Matlab, in der auch die SVM implementiert ist
• YALE ist ein einfach zu bedienenes und frei erhältliches Tool für Maschinelles Lernen und Data Mining, in der auch die SVM implementiert ist
• SVMlight Implementation einer SVM in C (Bindings für Perl und Java verfügbar)