Support Vector Machine (SVM)

Eine Support-Vektor-Maschine (SVM) ist ein Algorithmus für überwachtes Lernen, der Daten klassifiziert, indem er die Hyperebene findet, die zwei Klassen mit dem größtmöglichen Rand trennt – dem Abstand zwischen der Grenze und den nächstgelegenen Trainingspunkten jeder Klasse. Diese nächstgelegenen Punkte, die Stützvektoren, sind die einzigen Trainingsbeispiele, die die Grenze bestimmen. Mit Kernel-Funktionen können SVMs gekrümmte Grenzen lernen; Varianten eignen sich für Regression und die Erkennung von Ausreißern. Vladimir Vapnik und seine Kollegen entwickelten das Verfahren bei AT&T Bell Labs: Die Kernel-Version stammt aus dem Jahr 1992, und die heute verwendete Soft-Margin-Formulierung wurde 1995 von Cortes und Vapnik veröffentlicht. Vor dem Deep Learning gehörten SVMs zu den genauesten Klassifikatoren für Text, Bilder und biologische Daten. Auch heute liefern sie bei kleinen bis mittelgroßen Datensätzen mit vielen Merkmalen gute Ergebnisse.

So funktionieren SVMs#

Eine lineare SVM sagt die Klasse anhand des Vorzeichens von w·x + b voraus. Ihre Entscheidungsgrenze ist daher die Hyperebene w·x + b = 0. Sind die Gewichte so skaliert, dass für die nächstgelegenen Punkte |w·x + b| = 1 gilt, ist der Rand 2/‖w‖ breit. Beim Training wird der Rand maximiert, indem ‖w‖² minimiert wird, während jeder Trainingspunkt auf der richtigen Seite liegen muss. Reale Klassen überschneiden sich, deshalb erlaubt die Soft-Margin-SVM, dass Punkte den Rand überschreiten; die Kosten dafür legt der Parameter C für die Regularisierung fest. Der Hinge-Loss bestraft korrekt klassifizierte Punkte außerhalb des Rands nicht und belegt die übrigen Punkte mit einer Strafe, die linear mit der Verletzung wächst. Ein kleines C toleriert mehr Verletzungen und führt zu einem breiteren, glatteren Rand. Ein großes C passt sich stärker an die Trainingsdaten an und erhöht das Risiko des Overfittings. Im trainierten Modell haben nur Punkte auf dem Rand oder auf seiner falschen Seite ein von null verschiedenes Gewicht. Das sind die Stützvektoren; verschiebt man einen anderen Punkt, ohne dass er den Rand überschreitet, bleibt die Grenze unverändert.

Der Kernel-Trick#

Wenn keine Hyperebene die Klassen trennt, kann eine Abbildung der Daten in einen höherdimensionalen Raum sie trennbar machen: Zwei konzentrische Ringe in 2D lassen sich durch eine flache Ebene trennen, sobald ein drittes Merkmal, x₁² + x₂², den Abstand jedes Punkts vom Mittelpunkt misst. In der dualen Form verwenden SVM-Training und -Vorhersage die Daten ausschließlich über Skalarprodukte zwischen Punktepaaren. Eine Kernel-Funktion k(x, x′) kann daher direkt das Skalarprodukt im abgebildeten Raum zurückgeben, ohne die abgebildeten Koordinaten jemals zu berechnen. Das ist der Kernel-Trick. Zu den gängigen Kernels zählen der lineare Kernel, der polynomiale Kernel und die radiale Basisfunktion (RBF), exp(−γ‖x − x′‖²), wobei γ festlegt, wie weit der Einfluss jedes Stützvektors reicht. Dieses Beispiel trainiert scikit-learn's SVC mit einem linearen und einem RBF-Kernel auf zwei konzentrischen Ringen:

from sklearn.datasets import make_circles
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC

# Two concentric rings: no straight line separates the classes
X, y = make_circles(n_samples=500, factor=0.4, noise=0.1, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)

for kernel in ("linear", "rbf"):
    clf = SVC(kernel=kernel, C=1.0)
    clf.fit(X_train, y_train)
    print(f"{kernel}: test accuracy {clf.score(X_test, y_test):.2f}, support vectors {clf.n_support_.sum()}")

Der lineare Kernel erreicht bei zurückgehaltenen Punkten einen Wert von 0,43 und schneidet damit schlechter ab als Raten. Er behält 360 der 375 Trainingspunkte als Stützvektoren bei. Der RBF-Kernel trennt die Ringe perfekt (1,00) und benötigt dafür nur 42 Stützvektoren.

Kernel und Hyperparameter auswählen#

Abstände und Skalarprodukte hängen von der Skalierung der Merkmale ab. Deshalb werden SVM-Eingaben zunächst standardisiert. Der praxisorientierte Leitfaden der Autoren von LIBSVM, der Bibliothek hinter scikit-learn's SVC, empfiehlt, die Merkmale zu skalieren, mit dem RBF-Kernel zu beginnen und C und γ per Rastersuche mit Kreuzvalidierung auszuwählen. Wenn es sehr viel mehr Merkmale als Stichproben gibt, wie bei Text, liefert ein linearer Kernel etwa gleich gute Ergebnisse und lässt sich deutlich schneller trainieren. Die Trainingszeit von Kernel-SVMs wächst mindestens quadratisch mit der Anzahl der Stichproben. Bei mehr als Zehntausenden von Stichproben ersetzen daher lineare SVMs oder approximierte Kernel-Merkmale das exakte Kernel-Modell.

SVMs in der Computer Vision#

Die klassische Computer Vision kombinierte von Hand entwickelte Merkmale mit linearen SVMs. Dalal und Triggs' Fußgängerdetektor von 2005 klassifizierte Histogramme orientierter Gradienten (HOG) mit einer linearen SVM. Der Objektdetektor R-CNN von 2014 klassifizierte CNN-Merkmale aus jedem Regionenvorschlag mit einer linearen SVM pro Klasse, bis Fast R-CNN diese 2015 durch eine Softmax-Schicht ersetzte, die gemeinsam mit dem Netzwerk trainiert wurde. Moderne Detektoren lernen Merkmale und Klassifikator gemeinsam; SVMs kommen weiterhin als schnelle Klassifikatoren für feste Merkmale zum Einsatz. Eine lineare SVM, die auf den Vektoren trainiert wird, die YOLO26 aus model.embed() zurückgibt – ein Embedding pro Bild –, ist ein linearer Probe-Klassifikator, mit dem sich eine neue Bildkategorie hinzufügen lässt, ohne das Netzwerk erneut zu trainieren.

Anwendungen#

• Textklassifizierung: Wortzählvektoren haben Zehntausende dünn besetzte Dimensionen. Lineare SVMs trennen darin Themen, Spam und Stimmungen präzise – ein Vorteil, den Thorsten Joachims 1998 für die Textkategorisierung nachwies.
• Bioinformatik: Bei Genexpressionsstudien werden Tumore anhand von Tausenden gemessenen Genen und nur Dutzenden oder Hunderten von Patienten klassifiziert. In solchen Fällen begrenzt der Rand das Overfitting; String-Kernels vergleichen außerdem Proteinsequenzen direkt.
• Anomalieerkennung: Eine One-Class-SVM lernt eine Grenze ausschließlich um normale Daten und kennzeichnet Punkte außerhalb dieser Grenze. Das eignet sich für Betrugserkennung und die Maschinenüberwachung, wenn Fehler zu selten auftreten, um sie zu labeln.
• Regression: Die Support-Vektor-Regression passt eine Funktion innerhalb eines Schlauchs der Breite ε an, ignoriert Fehler unter ε und behält nur Punkte auf oder außerhalb des Schlauchs als Stützvektoren bei.

SVM im Vergleich zu verwandten Algorithmen#

• K-nächste Nachbarn (KNN): Speichert den gesamten Trainingsdatensatz und vergleicht bei der Vorhersage jeden neuen Punkt mit seinen Nachbarn. Eine SVM behält dagegen nur ihre Stützvektoren.
• Entscheidungsbäume und Random Forests: Treffen Entscheidungen anhand jeweils eines Merkmals, benötigen keine Skalierung der Merkmale und verarbeiten gemischte numerische und kategoriale Spalten. SVMs benötigen dagegen numerische, skalierte Eingaben.
• Neuronale Netze: Lernen die Merkmalsabbildung aus den Daten, statt sie mit einem Kernel festzulegen. So lassen sie sich auf Millionen von Bildern skalieren, während Kernel-SVMs dafür zu langsam werden.
• Logistische Regression: Lernt ebenfalls eine lineare Grenze, minimiert aber den Log-Loss über alle Trainingspunkte und gibt Wahrscheinlichkeiten aus. Eine SVM gibt vorzeichenbehaftete Abstände zur Grenze aus. scikit-learn's SVC erzeugt Wahrscheinlichkeiten nur mit probability=True; dafür wird die Platt-Skalierung mittels interner fünffacher Kreuzvalidierung angepasst.