Support Vector Machine

Kernidee und Zweck

Eine Support Vector Machine (SVM) ist ein mathematisches Verfahren des maschinellen Lernens. Sie dient als Klassifikator, also zur Einteilung von Objekten in Klassen, und auch als Regressor in der Regressionsanalyse. Der Begriff „Machine“ bedeutet hier keine Maschine mit Bauteilen, sondern verweist auf das Gebiet des maschinellen Lernens.

Die Grundidee lautet: Eine SVM trennt eine Menge von Objekten so in Klassen, dass um die Klassengrenze herum ein möglichst breiter Bereich ohne Objekte bleibt. Deshalb ist sie ein Large Margin Classifier, also ein „Breiter-Rand-Klassifikator“. Dieser breite Rand soll dazu beitragen, dass auch neue, bisher unbekannte Objekte zuverlässig klassifiziert werden.

Ausgangspunkt sind Trainingsobjekte, bei denen die Klassenzugehörigkeit bereits bekannt ist. Jedes Objekt wird als Vektor in einem Vektorraum dargestellt. Die SVM sucht in diesem Raum eine Hyperebene, die als Trennfläche zwischen zwei Klassen dient. Eine Hyperebene ist die Verallgemeinerung einer Geraden oder Ebene auf beliebig viele Dimensionen. Die SVM wählt die Hyperebene so, dass der Abstand zu den nächstliegenden Trainingsvektoren möglichst groß wird.

Stützvektoren und Margin

Für die Lage der Trennfläche sind nicht alle Trainingsvektoren gleich wichtig. Vektoren, die weit von der Hyperebene entfernt liegen und hinter anderen Vektoren „versteckt“ sind, beeinflussen die Lage der Hyperebene nicht. Entscheidend sind nur die Vektoren, die der Hyperebene am nächsten liegen.

Diese nächstliegenden Vektoren heißen Stützvektoren oder support vectors. Sie beschreiben die Trennebene mathematisch exakt und geben der Support Vector Machine ihren Namen. Der Abstand der nächstliegenden Vektoren zur Hyperebene heißt Margin. Die SVM versucht, diesen kleinsten Abstand zu maximieren.

Eine saubere Trennung durch eine unveränderte Hyperebene ist nur möglich, wenn die Daten linear trennbar sind. Das bedeutet, dass es eine Gerade, Ebene oder höherdimensionale Hyperebene gibt, die die Klassen vollständig trennt. Reale Daten erfüllen diese Bedingung oft nicht. Deshalb können SVMs durch Schlupfvariablen flexibler gemacht werden: Sie erlauben einzelne falsche Klassifikationen, bestrafen diese aber. Dadurch soll Überanpassung vermieden und die Zahl der benötigten Stützvektoren gesenkt werden.

Mathematische Beschreibung

Die SVM arbeitet mit Trainingsbeispielen der Form { (x_i, y_i) | i = 1, …, m; y_i ∈ {−1, 1} }. Dabei ist x_i ein Datenpunkt als Vektor, und y_i gibt die Klasse an, entweder −1 oder 1.

Eine Hyperebene wird durch einen Normalenvektor w und einen Bias b beschrieben. Für Punkte x auf der Hyperebene gilt die Gleichung ⟨w, x⟩ + b = 0. Das Symbol ⟨w, x⟩ bezeichnet ein Skalarprodukt. Punkte auf der einen Seite der Hyperebene liefern einen positiven Wert, Punkte auf der anderen Seite einen negativen Wert. Das Vorzeichen kann daher zur Klassifikation verwendet werden.

Für korrekt getrennte Trainingspunkte gilt formal y_i = sgn(⟨w, x_i⟩ + b). Das Training besteht darin, die Parameter w und b der „besten“ Hyperebene zu berechnen. „Beste“ bedeutet hier: Der kleinste Abstand der Trainingspunkte zur Hyperebene, also der Margin, soll möglichst groß sein. Die berechnete Hyperebene wird anschließend als Entscheidungsfunktion benutzt. Ein Computer muss für neue Datenpunkte nur das Vorzeichen von ⟨w, x⟩ + b bestimmen, um die Klassenzugehörigkeit vorherzusagen.

Lineare und nichtlineare Daten

Sind die Daten linear separierbar, gibt es meist unendlich viele Hyperebenen, die die beiden Klassen trennen. Die SVM wählt unter ihnen diejenige mit minimaler quadratischer Norm ||w||_2^2, während für jedes Trainingsbeispiel x_i die Bedingung y_i(⟨w, x_i⟩ + b) ≥ 1 gilt. Dies entspricht der Maximierung des Margins. Das Optimierungsproblem lautet: Minimiere 1/2 ||w||_2^2 durch Anpassung von w und b, sodass y_i(⟨w, x_i⟩ + b) ≥ 1 für alle 1 ≤ i ≤ m gilt.

Sind Daten nicht streng linear separierbar, etwa wegen Messfehlern oder überlappender Klassenverteilungen, werden positive Schlupfvariablen ξ_i eingeführt. Eine Variable ξ_i misst die Verletzung einer Nebenbedingung; ξ_i > 0 bedeutet, dass eine Bedingung verletzt ist. Die Summe dieser Fehler wird in die Zielfunktion aufgenommen. Eine positive Konstante C steuert den Ausgleich zwischen großem Margin und korrekter Klassifikation der Trainingsbeispiele. Dann wird 1/2 ||w||2^2 + C∑{i=1}^m ξ_i minimiert, unter der Bedingung y_i(⟨w, x_i⟩ + b) ≥ 1 − ξ_i für alle 1 ≤ i ≤ m.

Die Optimierungsprobleme sind konvex und können effizient gelöst werden. Häufig wird das Problem in eine duale Form überführt. Dabei wird w als Linearkombination der Trainingsbeispiele geschrieben: w = ∑{i=1}^m α_i y_i x_i. Die Lagrange-Multiplikatoren α_i erfüllen unter anderem 0 ≤ α_i ≤ C und ∑{i=1}^m α_i y_i = 0. Die Trainingspunkte mit α_i ≠ 0 heißen Support-Vektoren. Sie liegen entweder auf dem Margin oder innerhalb des Margins. SVMs können außerdem mit stochastischem Gradientenabstieg trainiert werden.

Kernel-Trick

Viele Klassifikationsprobleme sind nicht linear. Ein Ausweg besteht darin, die Daten in einen Raum höherer Dimension abzubilden: φ: R^{d_1} → R^{d_2}, x ↦ φ(x), wobei d_1 < d_2 gilt. In einem höherdimensionalen Raum gibt es mehr mögliche lineare Trennungen; nach dem Theorem von Cover kann dadurch eine Trennung möglich werden, die im ursprünglichen Raum nicht linear war.

Die direkte Abbildung in sehr hohe oder sogar unendlichdimensionale Räume wäre rechnerisch aufwendig. Hier setzt der Kernel-Trick an. In der dualen Form der SVM kommen Datenpunkte nur in Skalarprodukten vor. Daher kann man das Skalarprodukt ⟨x_i, x_j⟩ im Eingaberaum durch ein Skalarprodukt ⟨φ(x_i), φ(x_j)⟩ im höherdimensionalen Raum ersetzen. Mit einer positiv definiten Kernelfunktion k(x_i, x_j) = ⟨φ(x_i), φ(x_j)⟩ lässt sich dieses Skalarprodukt berechnen, ohne die Abbildung φ ausdrücklich auszuführen.

Der resultierende Klassifikator hat die Form f(x) = sgn(∑_{i=1}^m α_i y_i k(x_i, x) + b). Dadurch kann eine lineare Hyperebene in einem hochdimensionalen Raum implizit einer nichtlinearen Trennfläche im ursprünglichen Raum entsprechen. SVMs können mit Kernelfunktionen auch auf allgemeineren Strukturen wie Graphen oder Strings arbeiten. Trotz möglicherweise unendlichdimensionaler Räume können SVMs gut generalisieren; für Maximum-Margin-Klassifizierer ist der erwartete Testfehler beschränkt und hängt nicht von der Dimensionalität des Raumes ab.

Entwicklung und Software

Die Idee, Daten durch eine Hyperebene zu trennen, geht bereits auf Ronald A. Fisher im Jahr 1936 zurück. Frank Rosenblatt griff sie 1958 im Zusammenhang mit künstlichen neuronalen Netzen wieder auf. Die Idee der Support Vector Machines geht auf Wladimir Wapnik und Alexei Jakowlewitsch Tscherwonenkis zurück. Theoretisch ist der Algorithmus durch das Prinzip der strukturellen Risikominimierung motiviert: Nicht nur der Trainingsfehler, sondern auch die Komplexität des Modells beeinflusst die Generalisierungsfähigkeit eines Klassifizierers.

Der Durchbruch gelang Wapnik zusammen mit Bernhard Boser und Isabelle Guyon 1992 durch die Verwendung des Kernel-Tricks. Corinna Cortes gehörte ebenfalls zu den Pionieren bei den Bell Labs Anfang der 1990er Jahre. In der Mitte der 1990er Jahre setzten sich SVMs stärker durch, danach erschienen zahlreiche Weiterentwicklungen und Modifikationen.

Für SVMs gibt es verschiedene Softwarebibliotheken, darunter libsvm, liblinear und SVMlight. Auch Software für maschinelles Lernen und Data-Mining enthält SVMs, zum Beispiel GNU Octave, KNIME, Matlab, RapidMiner, Scikit-learn, Shogun und WEKA. Außerdem existieren Module oder Pakete für Programmiersprachen wie Perl, R und Ruby.