Die Support Vector Machine (SVM) ist ein leistungsstarker Algorithmus im Bereich des maschinellen Lernens, der insbesondere für Klassifikations- und Regressionsprobleme verwendet wird. Der Hauptansatz der SVM besteht darin, eine optimale Trennlinie (oder Hyperebene) zu finden, die zwei Klassen in einem Datensatz maximal voneinander trennt. Die Methode zielt darauf ab, den Abstand zwischen dieser Trennlinie und den nächsten Datenpunkten jeder Klasse – den sogenannten Support-Vektoren – zu maximieren. In diesem Blogartikel versuche ich die SVM von Grund auf erklären.

Die Kernidee hinter der SVM

Die Grundidee der Support Vector Machine besteht darin, eine optimale Trennlinie (bzw. eine Hyperplane in höheren Dimensionen) zu finden, die zwei Klassen von Datenpunkten maximal trennt. Diese Trennlinie wird so gewählt, dass der Abstand (die sogenannte Marge) zwischen der Trennlinie und den nächstgelegenen Datenpunkten beider Klassen maximiert wird. Die Punkte, die der Trennlinie am nächsten liegen und die Marge definieren, werden als Support-Vektoren bezeichnet.

Einsatzmöglichkeiten

Die SVM gehört zu den überwachten Lernverfahren und wird vor allem in folgenden Bereichen angewendet:

Bild- und Texterkennung: SVMs werden häufig in der Muster- und Spracherkennung eingesetzt, zum Beispiel für die Handschriftenerkennung oder die Gesichtserkennung.
Klassifikation von biologischen Daten: In der Genomforschung wird SVM genutzt, um zwischen unterschiedlichen Genexpressionsmustern zu unterscheiden.
Finanzwesen: SVMs helfen bei der Betrugserkennung und der Analyse von Kreditrisiken.

SVMs eignen sich besonders für Probleme, bei denen die Trennung der Klassen nicht immer offensichtlich ist, oder für hochdimensionale Daten, bei denen andere Algorithmen überfordert wären.

Mathematische Herleitung

Um die SVM mathematisch zu verstehen, starten wir mit der Definition der Entscheidungsgrenze. Gegeben sei ein Datensatz mit \( n \) Trainingsbeispielen \( \{x_1, x_2, …, x_n\} \), wobei jedes Beispiel einer Klasse \( y_i \in \{-1, +1\} \) zugeordnet ist. Die Entscheidungsgrenze (in zwei Dimensionen eine Linie, in höheren Dimensionen eine Hyperebene) wird durch die Gleichung
\[
w^T x + b = 0
\]
beschrieben, wobei \( w \) der Vektor der Gewichte und \( b \) der Bias ist.

Die Bedingung für korrekt klassifizierte Datenpunkte lautet:
\[
y_i (w^T x_i + b) \geq 1 \quad \text{für alle } i.
\]
Das Ziel ist es, die Marge \( \frac{2}{||w||} \) zu maximieren. Dies entspricht der Minimierung von \( ||w||^2 \) unter der Nebenbedingung, dass die oben genannte Ungleichung für alle Datenpunkte erfüllt ist. Diese Optimierungsaufgabe kann mit der Methode der Lagrange-Multiplikatoren gelöst werden. Das führt zu dem sogenannten Primal-Problem:
\[
\min \frac{1}{2} ||w||^2 \quad \text{unter der Nebenbedingung } y_i (w^T x_i + b) \geq 1.
\]

Mit Hilfe der Lagrange-Dualität wird dieses Problem weiter vereinfacht und kann effizient gelöst werden. Im Dual-Problem werden die Lagrange-Multiplikatoren \( \alpha_i \) eingeführt, um die Randbedingungen zu berücksichtigen. Die Dual-Formulierung lautet:
\[
\max \sum_{i=1}^{n} \alpha_i – \frac{1}{2} \sum_{i,j=1}^{n} \alpha_i \alpha_j y_i y_j x_i^T x_j
\]
unter den Nebenbedingungen
\[
\sum_{i=1}^{n} \alpha_i y_i = 0 \quad \text{und} \quad \alpha_i \geq 0.
\]

Die optimale Lösung wird durch die Support-Vektoren gefunden, also die Datenpunkte, für die \( \alpha_i > 0 \).

Kernel-Tricks: Nicht-lineare Trennungen

In der Praxis sind viele Klassifikationsprobleme nicht linear trennbar. Um auch solche Probleme zu lösen, verwendet die SVM den Kernel-Trick. Dieser Trick erlaubt es, die Daten in einen höherdimensionalen Raum zu projizieren, wo eine lineare Trennung möglich wird, ohne die Daten tatsächlich explizit zu transformieren. Stattdessen wird eine sogenannte Kernel-Funktion \( K(x_i, x_j) \) verwendet, die das innere Produkt der Datenpunkte in diesem höheren Raum berechnet.
Gängige Kernel-Funktionen sind:

Lineare Kernel: \( K(x_i, x_j) = x_i^T x_j \)
Polynomieller Kernel: \( K(x_i, x_j) = (x_i^T x_j + 1)^d \)
Radial-Basis-Funktion (RBF) Kernel: \( K(x_i, x_j) = \exp(-\gamma ||x_i – x_j||^2) \)

Beispiel: SVM im realen Einsatz

Stellen wir uns ein Beispiel aus der Biomedizin vor. Angenommen, wir wollen einen Klassifikator entwickeln, der anhand von Genexpressionsdaten zwischen gesunden und erkrankten Proben unterscheiden kann. Diese Daten sind in der Regel hochdimensional, da die Genexpressionswerte von Tausenden von Genen analysiert werden. Hier kommt die SVM ins Spiel.

Vorverarbeitung der Daten: Zunächst werden die Genexpressionsdaten normalisiert.
Modellwahl: Eine SVM mit einem RBF-Kernel könnte ausgewählt werden, um nicht-lineare Beziehungen zwischen den Genen und den Krankheitslabels zu modellieren.
Training des Modells: Der SVM-Algorithmus wird auf einem Teil des Datensatzes trainiert, um die optimale Trennlinie zu finden.
Modellbewertung: Anschließend wird das Modell auf einem Testdatensatz validiert, um die Klassifikationsgenauigkeit zu bewerten.

Das Ergebnis könnte eine präzise Vorhersage darüber sein, ob eine neue Probe zur Klasse der gesunden oder erkrankten Proben gehört.

Referenzen

[R1]: C. Cortes, V. Vapnik, Support-vector networks. Mach Learn 20, 273–297 (1995): DOI Link
[R2]: Scikit-learn SVM Dokumentation: Link zur Dokumentation
[R3]: Wikipedia – Support Vector Machine: Link zu Wikipedia