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 ${\displaystyle \|\mathbf {w} \|_{2}^{2}}$ auswählt, so dass gleichzeitig ${\displaystyle y_{i}(\langle \mathbf {w} ,\mathbf {x} _{i}\rangle +b)\geq 1}$ für jedes Trainingsbeispiel ${\displaystyle \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 ${\displaystyle {\frac {1}{2}}\|\mathbf {w} \|_{2}^{2}}$ durch Anpassung der Variablen ${\displaystyle \mathbf {w} ,b}$,

so dass die Nebenbedingung ${\displaystyle y_{i}(\langle \mathbf {w} ,\mathbf {x} _{i}\rangle +b)\geq 1}$ für alle ${\displaystyle 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 ${\displaystyle m}$ Nebenbedingungen möglich sind, die Verletzungen aber so klein wie möglich gehalten werden sollen. Zu diesem Zweck wird eine positive Schlupfvariable ${\displaystyle \xi _{i}}$ für jede Nebenbedingung eingeführt, deren Wert gerade die Verletzung der Nebenbedingungen ist. ${\displaystyle \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 ${\displaystyle C}$ multipliziert, die den Ausgleich zwischen der Minimierung von ${\displaystyle {\frac {1}{2}}\|\mathbf {w} \|_{2}^{2}}$ und der korrekten Klassifizierung der Trainingsbeispiele regelt. Das Optimierungsproblem besitzt dann folgende Form:

Minimiere den Term ${\displaystyle {\frac {1}{2}}\|\mathbf {w} \|_{2}^{2}+C\sum _{i=1}^{m}\xi _{i}}$ durch Anpassung der Variablen ${\displaystyle \mathbf {w} ,b,\xi _{i}}$,

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

Lösung

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.

${\displaystyle \phi \colon \mathbb {R} ^{d_{1}}\rightarrow \mathbb {R} ^{d_{2}},\mathbf {x} \mapsto \phi (\mathbf {x} )}$

Dabei gilt ${\displaystyle 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 ${\displaystyle \mathbf {x} _{i}}$ nur in Skalarprodukten ein. Daher ist es möglich, das Skalarprodukt ${\displaystyle \langle \mathbf {x} _{i},\mathbf {x} _{j}\rangle }$ im Eingaberaum ${\displaystyle \mathbb {R} ^{d_{1}}}$ durch ein Skalarprodukt im ${\displaystyle \mathbb {R} ^{d_{2}}}$ zu ersetzen und ${\displaystyle \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:

${\displaystyle 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

${\displaystyle 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 ${\displaystyle \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 ${\displaystyle \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.