Kapitel 6 – Hochdimensionale Daten & SVM

Folien: 📄 08_svm.pdf, 📄 09_svm_nicht_trennbar.pdf · Woche 5, Prof. Franz

Worum geht es?

Bisher (Perzeptron, lineare Regression, Bayes) haben wir Klassifikatoren in eher niedrigdimensionalen Räumen betrachtet. In vielen echten Anwendungen hat ein Datenpunkt aber Hunderte oder Tausende Merkmale (Pixel eines Bildes, Wörter eines Textes, Gene). Und spätestens mit dem Kernel-Trick in Kapitel 7 arbeiten wir sogar in unendlichdimensionalen Merkmalsräumen.

Das wirft eine grundsätzliche Frage auf: Wie kann man in solchen Räumen überhaupt lernen, ohne exponentiell viele Daten zu brauchen? Die Antwort dieses Kapitels:

1. Im Allgemeinen gar nicht, das ist der Fluch der Dimensionalität (curse of dimensionality).
2. Wenn die Daten aber gutartig sind, geht es doch. Für lineare Klassifikatoren heißt „gutartig“: Die Klassen lassen sich mit großer Trennbreite (margin) trennen. Die statistische Lerntheorie zeigt, dass der Generalisierungsfehler dann klein ist, unabhängig von der Dimension.
3. Die Supportvektormaschine (Support Vector Machine, SVM) sucht genau diese Trennebene mit maximaler Trennbreite. Das führt auf ein konvexes quadratisches Optimierungsproblem, das ein eindeutiges globales Optimum hat.
4. Für nicht trennbare Daten werden Schlupfvariablen (slack variables) eingeführt (Soft Margin SVM). Umgeschrieben ist das ein Problem ohne Nebenbedingungen mit Hinge-Loss, das sich mit einem stochastischen Subgradientenverfahren (Pegasos) lösen lässt.

Die Vorlesung behandelt dabei durchgehend das primale Problem. Die duale Formulierung mit Lagrange-Multiplikatoren steht nicht auf diesen Folien. Sie ist hier als Ergänzung aufbereitet, weil sie in fast jedem Lehrbuch vorkommt und erklärt, warum nur die Supportvektoren zählen. In der Vorlesung kommt die duale Darstellung in Kapitel 7 über das Representer-Theorem.

Aufbau des Kapitels

Abschnitt	Inhalt
6.1 Fluch der Dimensionalität	Exponentieller Datenbedarf, Volumen in der Kugelschale, lineare Trennbarkeit in hohen Dimensionen, gutartige Probleme
6.2 Die optimale Trennebene	Hyperebenen, kanonische Form, geometrischer Abstand, Trennbreite $2/\lVert\mathbf w\rVert$, Supportvektoren, primales SVM-Problem, Zahlenbeispiele
6.3 Konvexe Optimierung	Optimierung unter Nebenbedingungen, lokale/globale Optima, konvexe Mengen und Funktionen, warum die SVM konvex ist
6.4 Lagrange-Dualität und KKT (Ergänzung)	Lagrange-Funktion, KKT-Bedingungen, duales Problem, warum $\alpha_i \neq 0$ nur für Supportvektoren
6.5 Soft Margin SVM	Nicht trennbare Daten, Schlupfvariablen $\xi_i$, Regularisierungsparameter $C$
6.6 Hinge-Loss und Pegasos	Umformung ohne Nebenbedingungen, Hinge-Loss, Subgradienten, Subgradientenmethode, Pegasos

Der zweite Teil von Termin 10, der Kernel-Trick, folgt in Kapitel 7.

Notation

Die Folien verwenden durchgehend folgende Schreibweisen:

Symbol	Bedeutung
$\langle \mathbf w \cdot \mathbf x\rangle$	Skalarprodukt $\mathbf w^\top \mathbf x = \sum_j w_j x_j$
$S = \{(\mathbf x_1,y_1),\dots,(\mathbf x_\ell,y_\ell)\}$	Trainingsmenge mit $\ell$ Beispielen
$y_i \in \{-1,+1\}$	Klassenlabel
$d$	Dimension des Eingaberaums, $\mathbf x_i \in \mathbb R^d$
$f(\mathbf x) = \langle \mathbf w\cdot\mathbf x\rangle + b$	Entscheidungsfunktion, Klassifikation über $\operatorname{sign} f(\mathbf x)$
$\gamma$	Trennbreite (margin)
$\xi_i$	Schlupfvariable des $i$-ten Beispiels
$C$	Regularisierungsparameter der Soft Margin SVM

Prüfungsrelevant / Selbsttest

1. Was besagt der Fluch der Dimensionalität, und warum ist er für die Klassifikation ein Problem?

Antwort

Die Komplexität einer Funktion mehrerer Variablen kann exponentiell mit der Dimension wachsen. Um sie zu schätzen, braucht man entsprechend exponentiell viele Daten: Mit 10 Intervallen pro Achse braucht man in $d$ Dimensionen $10^d$ Zellen. Dasselbe gilt für eine Trennfläche zwischen zwei Klassen: Um eine beliebig komplizierte Trennfläche in hoher Dimension abzutasten, bräuchte man exponentiell viele Trainingspunkte. Im Allgemeinen ist Klassifikation in hoch- und unendlichdimensionalen Räumen daher unmöglich, es sei denn, das Problem ist gutartig.

2. Welcher Anteil des Volumens einer 20-dimensionalen Einheitskugel liegt in der äußeren Schale der Dicke $\epsilon = 0{,}1$?

Antwort

$1-(1-\epsilon)^D = 1 - 0{,}9^{20} \approx 1 - 0{,}12 = 0{,}88$. Also rund 88 % des Volumens liegen in den äußeren 10 % des Radius. Gleichverteilte Daten liegen in hohen Dimensionen fast alle „an der Oberfläche“.

3. Warum ist ein Perzeptron in hohen Dimensionen problematisch, und was macht die SVM anders?

Antwort

In hohen Dimensionen sind (fast) beliebige Trainingsmengen linear trennbar. Das Perzeptron hört auf, sobald irgendeine trennende Ebene gefunden ist. Welche das ist, hängt vom Zufall (Startwert, Reihenfolge) ab, und es gibt keinen Mechanismus, der gutartige Strukturen ausnutzt. Ergebnis: Overfitting. Die SVM wählt unter allen trennenden Ebenen diejenige mit maximaler Trennbreite. Nach der statistischen Lerntheorie ist der Generalisierungsfehler dann mit hoher Wahrscheinlichkeit klein, und zwar unabhängig von der Dimension.

4. Leite her, warum die Trennbreite einer kanonischen Trennebene $2/\lVert\mathbf w\rVert$ ist.

Antwort

Der vorzeichenbehaftete Abstand eines Punkts zur Ebene ist $\gamma_i = (\langle\mathbf w\cdot\mathbf x_i\rangle + b)/\lVert\mathbf w\rVert$. In kanonischer Form gilt für die nächstgelegenen Punkte $\lvert\langle\mathbf w\cdot\mathbf x_i\rangle + b\rvert = 1$, also $\lvert\gamma_i\rvert = 1/\lVert\mathbf w\rVert$. Die nächsten Punkte beider Klassen liegen auf den Ebenen $f(\mathbf x)=+1$ und $f(\mathbf x)=-1$, jeweils im Abstand $1/\lVert\mathbf w\rVert$ von der Trennebene. Der freie Streifen zwischen ihnen ist also $2/\lVert\mathbf w\rVert$ breit. Siehe 6.2.

5. Formuliere das primale Optimierungsproblem der Hard Margin SVM. Warum minimiert man $\langle\mathbf w\cdot\mathbf w\rangle$ statt $2/\lVert\mathbf w\rVert$ zu maximieren?

Antwort

Minimiere $\langle\mathbf w\cdot\mathbf w\rangle$ unter den $\ell$ Nebenbedingungen $y_i(\langle\mathbf w\cdot\mathbf x_i\rangle + b)\ge 1$. Die Trennbreite $2/\lVert\mathbf w\rVert$ zu maximieren ist äquivalent dazu, $\lVert\mathbf w\rVert$ zu minimieren. Da die Wurzel monoton steigt, hat $\lVert\mathbf w\rVert^2 = \langle\mathbf w\cdot\mathbf w\rangle$ dasselbe Minimum, ist aber eine glatte, konvexe quadratische Funktion. Damit ist das Problem ein quadratisches Programm mit linearen Ungleichungsnebenbedingungen.

6. Warum ist das SVM-Problem konvex, und was folgt daraus?

Antwort

$\langle\mathbf w\cdot\mathbf w\rangle$ ist eine konvexe Funktion (Summe von Quadraten). Jede Nebenbedingung $y_i(\langle\mathbf w\cdot\mathbf x_i\rangle+b)-1 \ge 0$ ist linear und definiert einen Halbraum, also eine konvexe Menge. Der zulässige Bereich ist der Schnitt dieser Halbräume und damit konvex. Für ein konvexes Problem ist jedes lokale Minimum ein globales: Man kann nicht in lokalen Minima hängen bleiben (anders als z.B. bei MLPs).

7. Was sind Supportvektoren, und warum heißen sie so?

Antwort

Die Trainingspunkte, die am nächsten an der Trennebene liegen, also genau auf dem Rand des Margins mit $y_i f(\mathbf x_i) = 1$ (bei Soft Margin zusätzlich alle Punkte mit $y_i f(\mathbf x_i) \lt 1$). Nur sie bestimmen die Lage der optimalen Trennebene („stützen“ sie, engl. to support). Alle anderen Punkte könnte man weglassen oder verschieben, solange sie außerhalb des Margins bleiben, ohne dass sich die Lösung ändert.

8. Welche Rolle spielt die Schlupfvariable $\xi_i$? Was bedeuten $\xi_i = 0$, $0 \lt \xi_i \le 1$ und $\xi_i \gt 1$?

Antwort

$\xi_i$ misst, wie stark die Nebenbedingung $y_i f(\mathbf x_i)\ge 1$ verletzt wird: $y_i f(\mathbf x_i) \ge 1-\xi_i$. Bei $\xi_i=0$ liegt der Punkt korrekt und außerhalb oder auf dem Margin. Bei $0\lt\xi_i\le 1$ liegt er innerhalb des Margins, aber noch auf der richtigen Seite (bzw. bei $\xi_i = 1$ genau auf der Trennebene). Bei $\xi_i \gt 1$ liegt er auf der falschen Seite der Trennebene und ist fehlklassifiziert.

9. Wie wirkt sich der Parameter $C$ aus? Was passiert für $C\to\infty$?

Antwort

$C$ gewichtet die Summe der Schlupfvariablen gegen die Trennbreite. Großes $C$ bestraft Verletzungen stark: schmaler Margin, wenige Fehler auf den Trainingsdaten, Gefahr von Overfitting. Für $C\to\infty$ erhält man die Hard Margin SVM (sofern die Daten trennbar sind). Kleines $C$ erlaubt mehr Verletzungen zugunsten eines breiten Margins, das ist laut Folie bei stark verrauschten, schlecht trennbaren Daten tendenziell besser.

10. Was ist der Hinge-Loss, und warum braucht man zur Optimierung Subgradienten?

Antwort

$\max(0, 1 - y_i f(\mathbf x_i))$. Er ist null für Punkte mit $y_i f(\mathbf x_i)\ge 1$ und wächst linear, je stärker der Margin verletzt wird. Er ist eine konvexe obere Schranke des 0-1-Verlusts, aber bei $y_i f(\mathbf x_i)=1$ nicht differenzierbar (Knick). Dort gibt es keinen Gradienten, aber eine Menge von Subgradienten. Die Subgradientenmethode läuft in Richtung eines beliebigen negativen Subgradienten. Pegasos ist die stochastische Variante davon mit Lernrate $\eta_t = 1/t$.