6.5 Soft Margin SVM

Die bisherige SVM hat eine harte Voraussetzung: Die Daten müssen linear trennbar sein. Echte Daten sind verrauscht, haben Ausreißer und überlappende Klassen. Die Soft Margin SVM lockert die Nebenbedingungen, indem sie Verletzungen erlaubt, aber bestraft.

Wiederholung: Ergebnis der Hard Margin SVM

📄 09_svm_nicht_trennbar.pdf, Folie 4 📄 09_svm_nicht_trennbar.pdf, Folie 5

Zusammenfassung von 6.2 und 6.3:

• Die SVM ist ein konvexes Optimierungsproblem, jedes lokale Minimum ist eine Lösung.
• Falls das Problem linear trennbar ist, ist die Existenz einer Lösung garantiert.
• Durch das Kriterium der maximalen Trennbreite ist die SVM auch auf hochdimensionale Probleme anwendbar.
• Zur Lösung des quadratischen Programms gibt es leistungsfähige allgemeine Pakete (z.B. quadprog in Matlab). Meist ist es aber besser, spezialisierte SVM-Pakete zu verwenden (die Folie nennt „svmlib“, gemeint ist vermutlich libsvm).
• Die Lage der Trennebene wird nur durch die Supportvektoren bestimmt, alle anderen Punkte spielen keine Rolle.

„Aber: wir sind noch nicht am Ziel…“

Nicht linear trennbare Daten

📄 09_svm_nicht_trennbar.pdf, Folie 6

Problem 1: Der zulässige Bereich ist leer. Wendet man die Hard Margin SVM auf nicht linear trennbare Daten an, gibt es kein $(\mathbf w, b)$, das alle Nebenbedingungen $y_i(\langle\mathbf w\cdot\mathbf x_i\rangle + b)\ge 1$ erfüllt. Der zulässige Bereich ist die leere Menge, es kann keine Lösung gefunden werden. Ein einziger falsch beschrifteter Punkt reicht dafür.

Problem 2: Auch bei trennbaren Daten kann Härte schaden. Selbst wenn die Daten trennbar sind, kann es besser sein, einige Ausnahmen zuzulassen. Die Abbildung auf der Folie zeigt zwei Wolken, bei denen ein einzelner Ausreißer (ein schwarzer Punkt mitten zwischen den roten) die trennende Gerade stark verkippt. Ohne diesen Punkt gäbe es eine viel breitere Lücke. Das ist dieselbe Überlegung wie auf 📄 08_svm.pdf, Folie 7: Ein Klassifikator, der jeden Trainingspunkt korrekt trennt, ist nicht unbedingt der beste.

Ansatz

Man erlaubt den Datenpunkten, zur Not auch innerhalb des Margins oder sogar auf der falschen Seite der Trennebene zu liegen, solange der Abstand zur Trennebene nicht zu groß ist.

Schlupfvariablen

📄 09_svm_nicht_trennbar.pdf, Folie 7

Jede Nebenbedingung erhält eine Schlupfvariable (slack variable) $\xi_i$, die angibt, wie stark die Nebenbedingung verletzt wird:

$$\begin{aligned} y_i = +1:&\quad \langle\mathbf w\cdot\mathbf x_i\rangle + b \ge 1 - \xi_i\\ y_i = -1:&\quad \langle\mathbf w\cdot\mathbf x_i\rangle + b \le -1 + \xi_i \end{aligned} \qquad\text{mit } \xi_i \ge 0.$$

Kurz: $y_i(\langle\mathbf w\cdot\mathbf x_i\rangle + b) \ge 1 - \xi_i$, $\xi_i\ge 0$.

Geometrische Bedeutung: $\xi_i$ misst die Verletzung in Einheiten von $1/\lVert\mathbf w\rVert$. Der tatsächliche Abstand, um den ein Punkt „zu weit drin“ liegt, ist $\xi_i/\lVert\mathbf w\rVert$ (in der Abbildung die grün gestrichelten Linien vom Punkt zum Rand seines Margins).

Ergänzung, nicht auf den Folien: Je nach Wert von $\xi_i$ unterscheidet man drei Fälle.

$\xi_i$	$y_if(\mathbf x_i)$	Lage des Punkts
$\xi_i = 0$	$\ge 1$	korrekt, außerhalb oder auf dem Margin
$0 \lt \xi_i \lt 1$	zwischen 0 und 1	im Margin, aber noch auf der richtigen Seite
$\xi_i = 1$	$= 0$	genau auf der Trennebene
$\xi_i \gt 1$	$\lt 0$	auf der falschen Seite, fehlklassifiziert

Folgerung: Jeder fehlklassifizierte Trainingspunkt hat $\xi_i \gt 1$. Daher ist $\sum_i\xi_i$ eine obere Schranke für die Anzahl der Trainingsfehler.

📄 09_svm_nicht_trennbar.pdf, Folie 8

Tradeoff: Mit Schlupfvariablen kann man den Margin beliebig breit machen, man muss nur genügend Punkte „hineinlassen“. Die zweite Abbildung zeigt genau das: ein breiter Streifen mit vielen Verletzungen. Je größer die Trennbreite, desto mehr Fehler. Das erfordert einen sinnvollen Kompromiss.

Zielfunktion bei nicht linear trennbaren Daten

📄 09_svm_nicht_trennbar.pdf, Folie 9

Die Gesamtgröße der Schlupfvariablen charakterisiert man, ähnlich wie beim Perzeptron, durch einfaches Aufaddieren:

$$\sum_{i=1}^{\ell}\xi_i.$$

Da alle $\xi_i\ge 0$ sind, können sie sich nicht gegenseitig aufheben. (Ohne die Nebenbedingung $\xi_i\ge 0$ könnte man negative $\xi_i$ bei „sehr guten“ Punkten benutzen, um Verletzungen anderswo zu kompensieren.)

Ziel: $\sum_i\xi_i$ möglichst klein und gleichzeitig die Trennbreite möglichst groß. Beides kombiniert man in einer Zielfunktion, die immer noch quadratisch und konvex ist:

$$f(\mathbf w,\boldsymbol\xi) = \tfrac12\langle\mathbf w\cdot\mathbf w\rangle + C\sum_{i}\xi_i.$$

Regularisierungsparameter $C$

Der Regularisierungsparameter (regularization parameter) $C \gt 0$ kontrolliert den relativen Einfluss beider Größen:

• Großes $C$: Verletzungen sind teuer. Die SVM versucht, möglichst alle Punkte korrekt mit Margin zu trennen, nimmt dafür einen schmalen Margin in Kauf. Gefahr: Overfitting, starke Reaktion auf Ausreißer. Für $C\to\infty$ erhält man die Hard Margin SVM.
• Kleines $C$: Verletzungen sind billig. Breiter Margin, viele Punkte im Margin, glattere Entscheidung. Gefahr: Underfitting.

Laut Folie ist bei stark verrauschten und schlecht trennbaren Klassifikationsproblemen ein kleineres $C$ tendenziell besser.

Warum ist das konvex? $\tfrac12\langle\mathbf w\cdot\mathbf w\rangle$ ist konvex, $C\sum_i\xi_i$ ist linear in $\boldsymbol\xi$ (also konvex), Summe konvexer Funktionen ist konvex (6.3). Die Nebenbedingungen sind linear in $(\mathbf w, b, \boldsymbol\xi)$.

Ergänzung: Der Name „Regularisierungsparameter“ passt eigentlich besser zu $1/C$: Der Term $\tfrac12\lVert\mathbf w\rVert^2$ ist ein Regularisierer wie bei der Ridge-Regression, und $C$ gewichtet den Datenterm dagegen. Großes $C$ heißt also wenig Regularisierung. In der Praxis wählt man $C$ per Kreuzvalidierung (Kapitel 5), typischerweise auf einem logarithmischen Gitter wie $10^{-3},\dots,10^{3}$.

Die Soft Margin SVM

📄 09_svm_nicht_trennbar.pdf, Folie 10

SVM-Optimierung (1-Norm Soft Margin)

• minimiere

$$f(\mathbf w,\boldsymbol\xi) = \tfrac12\langle\mathbf w\cdot\mathbf w\rangle + C\sum_{i=1}^{\ell}\xi_i,\qquad \mathbf w\in\mathbb R^d,\ \boldsymbol\xi\in\mathbb R^\ell$$

• unter den $2\ell$ Nebenbedingungen, $i = 1,\dots,\ell$:

$$y_i(\langle\mathbf w\cdot\mathbf x_i\rangle + b) \ge 1 - \xi_i, \qquad \xi_i \ge 0.$$

Bemerkungen:

• „1-Norm“, weil die Schlupfvariablen linear, also über ihre 1-Norm $\sum_i\lvert\xi_i\rvert = \sum_i\xi_i$, eingehen. Ergänzung: Es gibt auch die 2-Norm-Variante mit $C\sum_i\xi_i^2$.
• Es gibt jetzt $d + 1 + \ell$ Optimierungsvariablen ($\mathbf w$, $b$, $\boldsymbol\xi$) und $2\ell$ Nebenbedingungen.
• Der zulässige Bereich ist nie leer: Für jedes $(\mathbf w, b)$ kann man $\xi_i$ einfach groß genug wählen. Damit ist das Problem für beliebige Daten lösbar.

Zahlenbeispiel

Ergänzung, nicht auf den Folien.

Wir nehmen die Trennebene aus 6.2, Beispiel 1: $\mathbf w = (\tfrac12,\tfrac12)$, $b = -1$, also $f(\mathbf x) = \tfrac12(x_1 + x_2) - 1$. Für eine feste Ebene ist die kleinste zulässige Schlupfvariable $\xi_i = \max(0, 1 - y_if(\mathbf x_i))$ (warum, siehe 6.6).

Punkt	$y_i$	$f(\mathbf x_i)$	$y_if(\mathbf x_i)$	$\xi_i$	Lage
$(0,0)$	$-1$	$-1$	$1$	$0$	auf dem Margin (Supportvektor)
$(4,4)$	$+1$	$3$	$3$	$0$	weit außerhalb
$(1{,}5;\ 1{,}5)$	$+1$	$0{,}5$	$0{,}5$	$0{,}5$	im Margin, richtige Seite
$(1;\ 1)$	$-1$	$0$	$0$	$1$	genau auf der Trennebene
$(1{,}5;\ 1{,}5)$	$-1$	$0{,}5$	$-0{,}5$	$1{,}5$	falsche Seite, fehlklassifiziert

Mit $\lVert\mathbf w\rVert^2 = \tfrac12$ und $\sum_i\xi_i = 3$ ergibt sich für $C = 1$ der Zielfunktionswert $\tfrac12\cdot\tfrac12 + 1\cdot 3 = 3{,}25$. Ob eine andere Ebene besser ist, hängt von $C$ ab: Bei großem $C$ lohnt es, $\mathbf w$ zu vergrößern (schmalerer Margin), um die $\xi_i$ zu verkleinern.

Supportvektoren bei Soft Margin

Ergänzung, nicht auf den Folien (siehe aber 📄 09_svm_nicht_trennbar.pdf, Folie 13, Fälle 2 und 3).

Bei der Soft Margin SVM sind alle Punkte mit $y_if(\mathbf x_i) \le 1$ Supportvektoren: die auf dem Margin und alle, die den Margin verletzen. Im dualen Problem (vgl. 6.4) ändert sich nur eine Nebenbedingung: Aus $\alpha_i\ge 0$ wird die Box-Bedingung $0\le\alpha_i\le C$. Die KKT-Bedingungen ergeben dann:

$\alpha_i$	Bedeutung
$\alpha_i = 0$	$y_if(\mathbf x_i) \ge 1$: kein Supportvektor
$0 \lt \alpha_i \lt C$	$y_if(\mathbf x_i) = 1$, $\xi_i = 0$: Supportvektor genau auf dem Margin
$\alpha_i = C$	$y_if(\mathbf x_i) \le 1$, $\xi_i \ge 0$: Supportvektor im Margin oder fehlklassifiziert

Der Einfluss jedes einzelnen Punkts auf $\mathbf w = \sum_i\alpha_iy_i\mathbf x_i$ ist also auf $C$ begrenzt. Das erklärt, warum kleines $C$ robust gegen Ausreißer macht: Ein Ausreißer kann die Ebene nicht beliebig stark verziehen.

Kurz in scikit-learn

Ergänzung: Der Effekt von $C$ lässt sich direkt ausprobieren. Kleines $C$ führt typischerweise zu mehr Supportvektoren (breiter Margin, viele Punkte darin):

from sklearn.svm import SVC

for C in [0.01, 1, 100]:
    clf = SVC(kernel="linear", C=C).fit(X_train, y_train)
    print(C, len(clf.support_), clf.score(X_test, y_test))

Typische Fallstricke

• $C$ ist kein Margin-Parameter, sondern ein Strafgewicht. Großes $C$ bedeutet kleinen Margin, nicht großen.
• „Soft Margin heißt, die Daten werden nichtlinear getrennt.“ Nein. Die Trennebene bleibt linear, sie darf nur Fehler machen. Nichtlinearität kommt erst mit Kernen (Kapitel 7).
• $\xi_i \gt 0$ heißt nicht fehlklassifiziert. Für $0\lt\xi_i\le 1$ liegt der Punkt noch auf der richtigen Seite (bzw. auf der Ebene).
• Skalierung der Merkmale: Da $C$ gegen $\lVert\mathbf w\rVert^2$ abwägt und Abstände eingehen, hängt das Ergebnis von der Skalierung der Merkmale ab. Ergänzung: In der Praxis vorher standardisieren.