SVM

Was ist SVM? Einfach erklärt!

Im Kern des maschinellen Lernens geht es darum, Mustern in Daten auf die Spur zu kommen. Eine der elegantesten und leistungsfähigsten Methoden hierfür sind die Support Vector Machines, kurz SVMs. Vielleicht begegnet einem diese Bezeichnung und man fragt sich, was sich hinter diesen geheimnisvollen „Stützvektormaschinen“ verbirgt. Im Grunde ist die Idee verblüffend einfach: Es geht um die Kunst der optimalen Trennung.

Angenommen, man hat einen Datensatz mit Objekten, die zu zwei verschiedenen Gruppen oder Klassen gehören – wie Äpfel und Birnen auf einem Tisch. Die Absicht des SVM-Algorithmus ist es, die bestmögliche Trennlinie zwischen diesen beiden Gruppen zu finden. Diese Linie soll nicht nur irgendwie trennen, sondern den größtmöglichen Abstand zu den nächstgelegenen Früchten beider Sorten haben.

Dieser größtmögliche Abstand, auch „Margin“ genannt, ist das Herzstück der SVM-Methode. Man kann es sich wie eine möglichst breite Straße vorstellen, die zwischen den beiden Gruppen von Datenpunkten verläuft. Die Punkte, die direkt am Straßenrand liegen und die Position der Straße definieren, sind die namensgebenden „Support Vectors“ oder Stützvektoren. Sie stützen sozusagen die Entscheidungsgrenze. 

Alle anderen Punkte, die weiter von der Grenze entfernt liegen, sind für die genaue Position dieser Trennlinie unerheblich. Diese Konzentration auf die kritischen Punkte macht SVMs zu einer sehr effizienten Methode, um Klassifizierungsprobleme zu lösen und ein robustes Modell für die Vorhersage zu erstellen.

Das Konzept der optimalen Hyperebene

Die eben beschriebene Trennungsgerade ist in einem zweidimensionalen Raum leicht vorstellbar. Doch was passiert, wenn Daten mehr als zwei Merkmale haben? In diesem Fall bewegen wir uns in einem mehrdimensionalen Raum. Die Trennlinie wird dann zu einer Trennebene oder, ganz allgemein gesprochen, zu einer Hyperebene. 

Das Ziel des SVM-Algorithmus bleibt identisch: Er sucht jene Hyperebene, die den maximalen Abstand zu den nächstgelegenen Datenpunkten jeder Klasse aufweist. Diese optimale Hyperebene stellt die robusteste Entscheidungsgrenze dar, da sie am unempfindlichsten gegenüber leichten Verschiebungen der Punkte ist. Die Maximierung dieses Abstands ist das zentrale Optimierungsproblem, das eine SVM löst.

Die Rolle der Support Vectors

Die Stützvektoren sind jene Datenpunkte oder Vektoren, die auf den Rändern des „Margins“ liegen, also die minimale Distanz zur Hyperebene haben. Der Name „Support Vector Machines“ leitet sich direkt von diesen Vektoren ab, weil sie allein die Position und Ausrichtung der Entscheidungsgrenze „stützen“. Würde man alle anderen Trainingsdaten aus dem Datensatz entfernen, die keine Trägervektoren sind, würde sich die gefundene Hyperebene nicht ändern. 

Diese Eigenschaft macht den SVM-Algorithmus besonders speichereffizient, da das trainierte Modell nur die Informationen über diese wenigen, kritischen Punkte speichern muss. Es sind genau diese Vektoren, die das Modell definieren. Der Name Support Vector Machines unterstreicht, dass es sich um einen algorithmischen Apparat handelt, bei dem die Stützvektoren den entscheidenden Support für die Position der optimalen Hyperplane liefern.

Harte und weiche Trennung (Hard vs. Soft Margin)

In einem idealen Szenario sind die Daten perfekt linear trennbar. Das bedeutet, es existiert eine Hyperebene, die alle Datenpunkte einer Klasse sauber von den Datenpunkten der anderen Klasse trennt. In diesem Fall spricht man von einer „Hard Margin“ Klassifizierung. Die Realität sieht oft anders aus: Datensätze können verrauscht sein oder sich überlappen. Hier kommt die „Soft Margin“ Klassifizierung ins Spiel. 

Diese Methode erlaubt es dem Algorithmus, einige Datenpunkte falsch zu klassifizieren oder innerhalb des Margins zu platzieren. Dafür wird ein Strafterm in das Optimierungsproblem eingeführt, der durch einen Parameter (oft als „C“ bezeichnet) gesteuert wird. So findet der Algorithmus einen Kompromiss zwischen einem möglichst breiten Abstand und einer möglichst geringen Anzahl an Fehlklassifikationen.

SVMs als überwachtes Lernen

Support Vector Machines gehören zur Familie der Algorithmen des überwachten Lernens (Supervised Learning). „Überwacht“ bedeutet in diesem Kontext, dass der Algorithmus aus einem Datensatz lernt, bei dem die korrekte Klassenzugehörigkeit für jeden Datenpunkt bereits bekannt ist. Man gibt der Maschine also Trainingsdaten mit Beispielen und den richtigen „Antworten“. 

Die Absicht des Lernprozesses ist es, ein Modell zu erstellen, das von diesen Beispielen generalisiert. Nach dem Training soll das SVM-Modell in der Lage sein, die Klasse für neue, bisher ungesehene Objekte korrekt vorherzusagen. Es ist somit eine leistungsstarke Methode für diverse Klassifikationsprobleme. Die Absicht ist, für jeden neuen Support Vector die korrekte Klasse vorherzusagen, nachdem die Klassifizierung anhand zahlreicher Trainingsbeispiele gelernt wurde.

Die Grundlagen der linearen Klassifikation mit SVMs

Um die Funktionsweise von Support Vector Machines zu verstehen, beginnt man am besten bei der linearen Klassifikation. Dies ist der grundlegendste Anwendungsfall. Hier geht es um ein Problem, bei dem ein Datensatz in zwei Klassen unterteilt werden soll, die durch eine gerade Hyperebene (in 2D) oder eine flache Hyperebene (in 3D und höher) getrennt werden können. Solche Daten nennt man „linear trennbar“. Der SVM-Algorithmus sucht nicht irgendeine Trennlinie, sondern die eine, optimale Linie.

Diese optimale Trennlinie ist die bereits erwähnte Hyperebene. Mathematisch wird sie durch eine Gleichung wie w ⋅ x – b = 0 beschrieben, wobei w ein Gewichtsvektor (der Normalenvektor zur Hyperebene), x ein Datenpunkt und b ein Schwellenwert ist. Die Ausrichtung der Hyperebene im Raum wird durch den Vektor w bestimmt. Die Schreibweise als fettgedruckter Buchstabe (boldsymbol)  ist dabei eine übliche Konvention in der Mathematik. Sie signalisiert, dass es sich bei w nicht um eine einzelne Zahl, sondern um einen Vektor handelt, der mehrere Werte oder Dimensionen repräsentiert.

Alle Punkte auf der einen Seite der Ebene führen zu einem positiven Ergebnis, alle Punkte auf der anderen Seite zu einem negativen. Die Absicht des Lernens ist es, die perfekten Werte für w und b zu finden. Die Stärke der Support Vector Machines liegt darin, dass die gefundene Entscheidungsgrenze den maximalen „Margin“ oder Pufferbereich zu den Datenpunkten beider Klassen hat. Dieser Fokus auf den maximalen Abstand macht das Modell besonders robust gegenüber neuen, unbekannten Daten. Die Datenpunkte, die diesen Abstand definieren, sind die einzigen, die für das finale Modell von Belang sind.

Der Kernel-Trick: Von der Linie zur komplexen Form

Die Welt ist selten so geordnet, dass alle Datenpunkte sich brav durch eine gerade Linie trennen lassen. Was geschieht, wenn die Daten ineinander verschlungen sind, zum Beispiel eine Gruppe von Punkten, die von einer anderen Gruppe ringförmig umschlossen wird? Ein linearer Klassifikator würde hier scheitern. An dieser Stelle kommt eine der genialsten Ideen im Machine Learning zum Einsatz: der Kernel-Trick. Dieser Trick ist das, was eine SVM so unglaublich flexibel macht und ihr erlaubt, auch hochkomplexe Klassifikationsprobleme zu lösen.

Die Kernidee ist, die Daten aus ihrem ursprünglichen Merkmalsraum in einen neuen, höherdimensionalen Raum zu transformieren. In diesem neuen, hochdimensionalen Raum könnten die Daten plötzlich linear trennbar sein. Der „Trick“ besteht darin, dass der SVM-Algorithmus diese Transformation nicht explizit durchführen muss. Statt die Koordinaten jedes Datenpunktes im neuen Raum aufwendig zu berechnen, verwenden SVMs eine Kernel-Funktion. 

Diese Funktion berechnet das Skalarprodukt (eine Art Ähnlichkeitsmaß) zwischen den Vektoren von zwei Instanzen, als ob sie im hochdimensionalen Raum wären. Das Ergebnis ist dasselbe, aber der Rechenaufwand ist ungleich geringer. Durch diesen mathematischen Kniff kann eine SVM eine lineare Trennung in einem hochdimensionalen Raum durchführen, was im ursprünglichen Raum einer komplexen, nicht-linearen Entscheidungsgrenze entspricht. Dieser Mechanismus macht den Einsatz von SVMs für eine breite Palette von Problemen möglich.

Die wichtigsten Kernel-Funktionen im Überblick

Die Wahl der richtigen Kernel-Funktion ist für den Erfolg einer SVM-Anwendung ausschlaggebend, da sie die Form der Entscheidungsgrenze bestimmt. Es gibt verschiedene etablierte Kernel-Funktionen, die für unterschiedliche Arten von Daten und Herausforderungen geeignet sind. Die Auswahl der passenden Funktion und ihrer Parameter ist ein Teil der Modelloptimierung.

*   Linearer Kernel: Dies ist die einfachste Form. Er wird verwendet, wenn die Trainingsdaten bereits weitgehend linear trennbar sind. Er berechnet das Standardskalarprodukt im ursprünglichen Raum und führt keine Transformation durch. Seine Anwendung ist recheneffizient und ein guter Ausgangspunkt für viele Klassifizierungsprobleme.

*   Polynomieller Kernel: Dieser Kernel erzeugt Entscheidungsgrenzen, die auf Polynomen basieren. Er kann gekrümmte Linien im ursprünglichen Datenraum erzeugen. Ein Parameter dieses Kernels ist der Grad des Polynoms, der die Flexibilität der Trennlinie steuert. Ein höherer Grad erlaubt komplexere Formen, birgt aber auch die Gefahr der Überanpassung an die Trainingsdaten.

*   Radial Basis Function (RBF) Kernel: Dies ist oft die Standardwahl und eine der leistungsfähigsten und beliebtesten Kernel-Funktionen. Der RBF-Kernel unterstellt, dass die Klassenzugehörigkeit eines Punktes vor allem von den nahegelegenen Punkten beeinflusst wird. Er erzeugt eine Entscheidungsgrenze, die auf der Distanz zu den Vektoren basiert. Man kann sich seine Funktionsweise wie eine Überlagerung von „Hügeln“ um jeden Support Vector vorstellen. Ein wichtiger Parameter ist hier Gamma, der die Reichweite des Einflusses eines einzelnen Trainingsbeispiels steuert. Ein kleiner Gamma-Wert führt zu einer glatteren, allgemeineren Entscheidungsgrenze, ein hoher Gamma-Wert zu einer komplexeren, die sich stärker an die Daten „anschmiegt“.

*   Sigmoid Kernel: Dieser Kernel verwendet eine Funktion, die der Aktivierungsfunktion in neuronalen Netzen ähnelt. Unter bestimmten Parametern verhält er sich ähnlich wie ein neuronales Netz mit zwei Schichten. In der Praxis wird er seltener verwendet als der RBF- oder der lineare Kernel, kann aber für bestimmte Anwendungen nützlich sein.

Das Optimierungsproblem: Wie SVMs lernen

Der Prozess, bei dem eine Support Vector Machine die optimale Hyperebene findet, ist im Kern ein mathematisches Optimierungsproblem. Das Ziel ist klar definiert: Finde jene Hyperebene, die den Margin maximiert und gleichzeitig die Datenpunkte korrekt klassifiziert. Bei einer Soft-Margin-SVM kommt eine weitere Bedingung hinzu: Halte die Anzahl der Fehlklassifikationen so gering wie möglich. Dieser Lernprozess ist kein zufälliges Ausprobieren, sondern ein strukturierter Algorithmus, der nach einer global optimalen Lösung sucht.

Dieses Problem wird als quadratisches Optimierungsproblem mit linearen Nebenbedingungen formuliert. Das klingt kompliziert, hat aber eine sehr angenehme Eigenschaft: Es gibt nur eine einzige, beste Lösung (das Problem ist konvex). Das bedeutet, dass der Algorithmus nicht in lokalen Minima stecken bleiben kann, wie es bei anderen Algorithmen, beispielsweise in neuronalen Netzen, vorkommen kann. Man erhält also bei gleichen Trainingsdaten und Parametern immer dasselbe, reproduzierbare Modell. 

Der bereits erwähnte Parameter C steuert den Kompromiss bei der Soft-Margin-Optimierung: Ein hoher C-Wert bestraft Fehlklassifikationen stark und führt zu einem Modell, das versucht, so viele Trainingsdaten wie möglich korrekt zu trennen, selbst wenn der Margin dadurch schmaler wird. Ein niedriger C-Wert erlaubt mehr Fehler für einen potenziell breiteren Margin. Das eigentliche Lernen der Maschine besteht also darin, dieses wohldefinierte mathematische Problem zu lösen.

Praktische Anwendungsbereiche von Support Vector Machines

Die theoretischen Grundlagen von SVMs sind beeindruckend, doch ihre wahre Stärke zeigt sich in den vielfältigen praktischen Anwendungen. Überall dort, wo Objekte oder Daten in verschiedene Kategorien eingeteilt werden müssen, können Support Vector Machines eine robuste Lösung bieten. Die Fähigkeit, mit hochdimensionalen Daten umzugehen, macht sie für moderne Datensätze besonders geeignet.

Ein klassisches Beispiel für den Einsatz von SVMs ist die Bilderkennung und -klassifikation. Hierbei können SVMs lernen, Bilder basierend auf ihren visuellen Merkmalen zu klassifizieren, etwa um Katzen von Hunden zu unterscheiden oder um auf Satellitenbildern verschiedene Landnutzungstypen zu identifizieren. Ein weiteres prominentes Feld ist die Textklassifikation. SVMs werden erfolgreich eingesetzt, um Dokumente thematisch zuzuordnen, die Stimmung in Kundenrezensionen zu analysieren (Sentiment Analysis) oder E-Mails als Spam oder Nicht-Spam zu filtern. 

Die Datenpunkte sind hierbei Vektoren, die die Worthäufigkeiten im Text repräsentieren. In der Bioinformatik leisten SVMs wertvolle Dienste, zum Beispiel bei der Klassifikation von Proteinen oder bei der Diagnose von Krankheiten anhand von Genexpressionsdaten. Hier hat man es oft mit einem Datensatz zu tun, der sehr viele Merkmale (Gene), aber nur wenige Beispiele (Patienten) hat – ein Szenario, in dem SVMs ihre Stärken ausspielen können. 

Auch in der Handschrifterkennung, etwa zur Digitalisierung von Postleitzahlen, haben sich SVM-Algorithmen bewährt. Populäre Machine-Learning-Bibliotheken wie scikit-learn machen die Anwendung von SVMs auch für Datensätze mit sehr vielen Dimensionen unkompliziert und für Einsteiger zugänglich.

Stärken, Schwächen und Alternativen im Vergleich

Wie jede Methode im Machine Learning haben auch Support Vector Machines ein spezifisches Profil aus Stärken und Schwächen. Eine bewusste Entscheidung für oder gegen den Einsatz von SVMs erfordert die Kenntnis dieser Eigenschaften.

Zu den klaren Stärken gehört ihre hohe Effektivität in hochdimensionalen Räumen. Sie funktionieren auch dann gut, wenn die Anzahl der Dimensionen (Merkmale) größer ist als die Anzahl der Messwerte, was in Feldern wie der Genetik häufig vorkommt. Zudem sind sie speichereffizient, da sie für das finale Modell nur die Stützvektoren benötigen. Die Flexibilität durch verschiedene Kernel-Funktionen ermöglicht die Anpassung an eine große Bandbreite von Klassifizierungsproblemen. 

Auf der anderen Seite skaliert die Trainingszeit von SVMs nicht gut mit der Größe des Datensatzes. Bei sehr großen Mengen an Trainingsdaten (Hunderttausende oder Millionen von Beispielen) können andere Algorithmen wie neuronale Netze oder Entscheidungsbäume deutlich schneller sein. 

Die Performanz eines SVM-Modells hängt zudem stark von der richtigen Wahl des Kernels und seiner Parameter ab. Dieser Prozess der Parameter-Optimierung kann zeitaufwendig sein. Ein weiterer Punkt ist, dass SVMs von Haus aus keine Wahrscheinlichkeitsabschätzungen für die Klassenzugehörigkeit liefern, was für manche Anwendungen wünschenswert wäre.

Als Alternativen zu SVMs existieren andere leistungsfähige Klassifizierungsalgorithmen. Die logistische Regression ist ein einfacherer, linearer Klassifikator, der schneller ist und Wahrscheinlichkeiten ausgibt. Entscheidungsbäume und ihre Weiterentwicklung, die Random Forests, sind leicht zu interpretieren und gut für tabellarische Daten geeignet. Für sehr komplexe Aufgaben, insbesondere in der Bild- und Sprachverarbeitung mit riesigen Datensätzen, haben sich neuronale Netze und Deep Learning als extrem leistungsfähig erwiesen. Die Wahl des richtigen Algorithmus hängt letztlich immer vom spezifischen Problem, der Art und Menge der verfügbaren Daten und dem verfolgten Ziel ab.