Algorithmus im Detail
Abbildung 1: Zwei mögliche Hyperebenen[1]
Eine Support Vector Machine trennt eine Menge von Objekten mit einer Hyperebene in zwei Klassen, sodass der Abstand zwischen den Objekten der Klassen und der Hyperebene maximal wird. Sie wird daher auch als Large Margin Classifier bezeichnet. Abbildung 1 zeigt eine Menge von Objekten, die zu zwei verschiedenen Klassen gehören, sowie zwei mögliche Hyperebenen A und B. Beide teilen die Objekte in zwei Klassen auf, doch der Abstand bei Trennebene A ist wesentlich größer als bei Trennebene B. Die Trennebene A, mit dem maximalen Abstand, stellt damit einen besseren Klassifikator dar, weil sie den kleinsten Generalisierungsfehler erzeugt.[2]
Ebenendarstellung
Gegeben sei ein zweidimensionaler Raum, dann lässt sich die Hyperebene als lineare Gleichung darstellen. Sei Vektor
und
,
dann lässt sich die lineare Gleichung darstellen als
.[3]
Bedingungen
Gesucht werden zwei Hyperebenen und
, die eine Menge von Datenpunkten in zwei verschiedene Klassen trennen. Zwischen diesen Hyperebenen sollen sich keine Datenpunkte befinden.
Für jeden Datenpunkt
muss also gelten:
oder
Sei ist die zugehörige Klasse zum Datenpunkt , dann lassen sich die Bedingungen aus Formal 1 und 2 zu einer einzigen Bedingung zusammenfassen, indem sie mit
multipliziert werden.
Formel 3: &space;\geq&space;1\;\text{f\"ur}&space;1\leq&space;i&space;\leq&space;n)
In Abbildung 2 markieren die gestrichelten Linien zwei mögliche Hyperebenen, sodass die Bedingung aus Formel 3 erfüllt ist.[4]
Abbildung 2: Support Vector Machine - Hyperebene mit maximalem Abstand[1]
Abstandsberechnung
Ziel der Support Vector Machine ist es den Abstand zwischen den Hyperebenen
und
zu maximieren.
Abbildung 3: Abstandsberechnung[4]
Der Abstand lässt sich einfach als Vektor
darstellen mit:
Addiert man zu einem Punkt in der Hyperebene
den Vektor
, so erhält man den Punkt
in der Hyperebene
.
Setzt man Formel 4 in
ein, so erhält man die Formel 5 um den Abstand zu berechnen.[4]
Die Herleitung der Formel 5 ist hier aufgelistet.[4]
Optimierungsproblem
Den maximalen Abstand erhält man demnach, indem
minimiert wird.
Es wird also eine Hyperebene mit dem kleinsten
gesucht, die die Bedingung aus Formel 3 erfüllt.
Eine Möglichkeit dieses Optimierungsproblem zu lösen ist mittels Gradientenabstieg.
Genutzt wurde dazu die Implementierung des Pegasos[5] Algorithmus aus dem sklearn-Framework[6]. Der Algorithmus basiert auf der Fehlerfunktion aus Formel 6.
bezieht sich hierbei auf die hinge loss Funktion (siehe Formel 7).
Formel 6: &space;=&space;\lambda\frac{1}{2}&space;\left|&space;\vec{w}&space;\right|^2&space;+&space;\frac{1}{n}&space;\sum_{i=1}^n&space;\ell_i(\langle&space;\vec{w},\vec{x}\rangle&space;+&space;b))
Formel 7: }})
Kernel Trick
Die Support Vector Machine, wie sie bisher besprochen wurde, kann nur Daten in zwei Klassen trennen, wenn sie linear separierbar sind. Das wird erreicht, indem eine Hyperebene konstruiert wird. Linear separierbar bedeutet, dass es sich immer um eine gerade Ebene handeln muss. Im zweidimensionalen Raum ist eine Hyperebene eine Gerade. Abbildung 4 stellt das Problem gut dar. Links ist eine Menge von Datenpunkten im zweidimensionalen Raum dargestellt, die zu zwei verschiedenen Klassen gehören. Diese Daten lassen sich beispielsweise mit einem Kreis in zwei Klassen trennen. Eine Support Vector Machine könnte diese Daten nicht klassifizieren, da sich die Daten nicht mit einer Gerade trennen lassen.[7]
Doch mit dem sogenannten Kernel Trick ist dies trotzdem möglich. Die Idee dabei ist, dem Merkmalsraum eine weitere Dimension hinzuzufügen. Auf dem linken Bild befinden sich die Datenpunkte im zweidimensionalen Raum. Das rechte Bild zeigt die gleichen Datenpunkte im dreidimensionalen Raum. Gut zu erkennen ist, dass sich die Daten nach der transformation linear separieren lassen. Dadurch lässt sich auch die Support Vector Machine auf dieses Problem anwenden.[7]
Die Datenpunkte lassen sich auf verschiedene Weisen in eine höhere Dimension projizieren. In dem Beispiel aus Abbildung 4 wurden die drei neuen Dimensionen wie folgt berechnet:[7]
Ein weiterer Vorteil des Kernel Tricks ist, dass die Berechnung sehr effizient ist. Die Berechnung der Hyperebene kann in einem höherdimensionalen Raum durchgeführt werden, ohne die einzelnen Datenpunkte in diesen Raum zu projizieren.[7]
Abbildung 4: Kernel Trick grafisch dargestellt: (a) Daten im zweidimensionalen Raum, (b) Daten projiziert in den dreidimensionalen Raum[7]
1. https://de.wikipedia.org/wiki/Support_Vector_Machine ↩↩
2. Manning, C. D., Raghavan, P., & Schütze, H. Cambridge University Press; 2009. Introduction to Information Retrieval ↩
3. http://www.svm-tutorial.com/2014/11/svm-understanding-math-part-2/ ↩
4. http://www.svm-tutorial.com/2015/06/svm-understanding-math-part-3/ ↩↩↩↩
5. Shalev-Shwartz, Shai, et al. "Pegasos: Primal estimated sub-gradient solver for svm." Mathematical programming 127.1 (2011): 3-30. ↩
6. http://scikit-learn.org/stable/modules/sgd.html ↩
7. Russell, S., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach. Prentice Hall (Third edit). Pearson. ↩↩↩↩↩
Author: Daniel Beneker