Was sind Support Vector Machines und wie funktionieren sie?

Autor*in:
Till
Schulz

Support Vector Machines (SVM) sind überwachte Lernverfahren, welche vornehmlich bei Klassifikationsproblemen zum Einsatz kommen. Ihre Aufgabe ist es, auf Basis einer Menge von Datenpunkten und deren Klassenzugehörigkeit ein Model zu erzeugen, welches die Klasse neuer Datenpunkte möglichst korrekt bestimmt. SVMs sind vielseitig einsetzbar und finden unter anderem Anwendung in der Text- und Bildklassifikation.

Für einen Einstieg in das Thema Klassifikation empfiehlt sich der Beitrag Klassifikation im Maschinellen Lernen von Sebastian Müller. Während SVMs mit beliebig dimensionalen Daten umgehen können, beschränken sich die folgenden Beispiele zur vereinfachten Visualisierung auf Daten aus dem 2-dimensionalen bzw. 3-dimensionalen Raum.

Funktionsweise

Das grundlegende Prinzip von SVMs verfolgt einen verblüffend einfachen Ansatz: Es besteht darin, eine Ebene – die sogenannte trennende Hyperebene – zu bestimmen, welche Datenpunkte bezüglich ihrer Klassenzugehörigkeit voneinander trennt. Im Folgenden 2-dimensionalen Beispiel (Abb. 1) entspricht die Hyperebene einer einfachen Geraden, welche die roten und blauen Punkte voneinander trennen soll. Um die Klasse eines neuen Datenpunktes zu ermitteln, reicht es dann aus, zu prüfen, auf welcher Seite der Hyperebene der Punkt liegt. Da theoretisch unendlich viele solcher Hyperebenen existieren, stellt sich die Frage, wie genau diese gewählt werden sollte.

© Till Schulz
Abbildung 1: Hyperebenen \(h_1\) und \(h_2\) klassifizieren den neuen Punkt (abgebildet in schwarz) nachvollziehbar als blauen Punkt, wohingegen \(h_3\) den Punkt der roten Klasse zuordnet.

Um die Klassen möglichst sauber voneinander zu trennen, wählen SVMs diejenige Hyperebene, welche die Distanzen zu den am nächsten gelegenen Punkten beider Klassen maximieren. Anders formuliert liegt die optimale Hyperebene in der Mitte eines maximal breiten Streifens, genannt Margin, welche die zwei Klassen voneinander trennt. Es handelt sich daher um ein klassisches Optimierungsproblem, das sich mit herkömmlichen Methoden wie zum Beispiel dem Gradientenverfahren lösen lässt

© Till Schulz
Abbildung 2: Die von der SVM gewählte optimale Hyperebene maximiert den Abstand zu den beiden Klassengrenzen (Margin).

Soft Margin SVM

In den allermeisten Fällen sind die Daten allerdings nicht linear separierbar wie bisher angenommen. Das heißt, aufgrund von ungünstigen Datenverteilungen mag der Fall eintreten, dass keine Hyperebene existiert, welche die Klassen perfekt voneinander trennt. Für solche Fälle lässt sich das Prinzip der SVMs etwas erweitern. Die sogenannte Soft Margin SVM erlaubt einen gewissen Grad an Fehlern bei der Klassifikation der Trainingsdaten. Datenpunkte dürfen dabei in die Margin oder gar auf die falsche Seite der Hyperebene fallen. Anstatt nur eine maximal breite Margin zu ermitteln, wählen Soft Margin SVMs die Klassengrenzen zusätzlich so, dass die Summe der Distanzen zu allen in oder jenseits der Margin gelegenen Punkte minimiert wird (Abb. 3). Soft Margin SVMs verfolgen also gleich zwei Ziele: Die Margin soll maximiert werden, während der Fehler durch falsche Klassifikationen minimiert wird. Dieser Trade-off zwischen beiden Zielen wird durch einen Parameter (üblicherweise C genannt) bestimmt. Kleine Werte für C vergrößern tendenziell die Margin. Gleichzeitig werden dadurch mehr Klassifikationsfehler der Trainingsbeispiele toleriert. Üblicherweise ist das Ermitteln eines geeigneten Wertes für C Teil des Lernverfahrens.

© Till Schulz
Abbildung 3: Um ein gewisses Maß an Fehlern zu erlauben, versuchen Soft Margin SVMs die Distanzen zu falsch klassifizierten oder innerhalb der Margin gelegenen Punkten zu minimieren.

Kernel Trick

Leider löst auch die Soft Margin SVM nicht alle Probleme. Um mit kniffligen Fällen wie im folgenden Beispiel (Abb. 4) abgebildet umzugehen, muss etwas nachgeholfen werden, um die Daten linear separierbar zu machen.

© Till Schulz
Abbildung 4: Beispiel für eine Menge von Punkten, welche sich im 2-dimensionalen Raum (auch unter Verwendung der Soft Margin SVM) kaum zufriedenstellend voneinander trennen lassen.

Die Lösungsidee besteht darin, die Punkte in einen höher dimensionalen Raum zu transformieren, in dem sie durch eine Hyperebene voneinander trennbar sind. Die folgende Illustration zeigt, wie dies für das Beispiel (Abb. 5) aussehen könnte. Die ursprünglich 2-dimensionalen Punkte werden jeweils um eine dritte Dimension erweitert. In diesem neuen 3-dimensionalen Raum entspricht die trennende Hyperebene einer 2-dimensionalen Ebene, welche die beiden Klassen nun sauber voneinander trennt.

© Till Schulz
Abbildung 5: Durch den Kernel Trick, d.h. der Transformation in einen höherdimensionalen Raum, lassen sich die Punkte nun voneinander trennen.

Leider bekommen wir eine solche Transformation nicht geschenkt. Ganz im Gegenteil: Besonders für hoch-dimensionale Daten ist das Finden einer geeigneten Transformation im Allgemeinen mit einem nicht vertretbaren Rechenaufwand verbunden. Woher nehmen wir also stattdessen eine geeignete Transformation? Nun, eigentlich wird sie gar nicht explizit benötigt. Stattdessen lässt sich das Problem durch eine geschickte Umformulierung umgehen. Tatsächlich genügt es, paarweise Ähnlichkeiten zwischen den Datenpunkten mithilfe einer Kernel Funktion zu berechnen. Mit diesem sogenannten Kernel Trick wird die Notwendigkeit einer expliziten und aufwendigen Transformation von Datenpunkten in einem höher-dimensionalen Raum vollständig umgangen.

Verwandte Beiträge zum Thema SVM:

Das intelligente Regal: Der Weg zu intelligenten Mensch-Maschine-Schnittstellen in der Industrie

Computer Vision: Wie lernen Maschinen zu sehen?

Krankheitsverläufe besser einschätzen mit Ranking SVM

Autor*in

Till
Schulz

Till Schulz ist wissenschaftlicher Mitarbeiter am Lamarr-Standort der Universität Bonn. Er beschäftigt sich dort mit Lernverfahren auf Graphdaten, insbesondere der Klassifikation von Graphen.