6.4 Lagrange-Dualität und KKT (Ergänzung)

Ergänzung, nicht auf den Folien

Die Folien von Vorlesung 8 und 9 behandeln die SVM ausschließlich in der primalen Form und lösen sie in 6.6 mit einem Subgradientenverfahren. Lagrange-Multiplikatoren, KKT-Bedingungen und das duale Problem kommen dort nicht vor. Diese Seite fasst den Standardweg aus der Literatur (z.B. Bishop, Kap. 7; Schölkopf und Smola) zusammen, weil er

• präzise begründet, warum nur die Supportvektoren die Lösung bestimmen,
• zur dualen Darstellung $\mathbf w = \sum_i \alpha_i y_i\mathbf x_i$ führt, die in Kapitel 7 (dort über das Representer-Theorem) die Grundlage des Kernel-Tricks ist.

Ob diese Herleitung prüfungsrelevant ist, solltest du in der Vorlesung klären.

Ausgangspunkt

Wir verwenden das primale Problem aus 6.2 in der üblichen Form mit Faktor $\tfrac12$:

$$\min_{\mathbf w, b}\ \tfrac12\langle\mathbf w\cdot\mathbf w\rangle \quad\text{u.d.N.}\quad y_i(\langle\mathbf w\cdot\mathbf x_i\rangle + b) \ge 1,\quad i = 1,\dots,\ell.$$

Der Faktor $\tfrac12$ ändert das optimale $(\mathbf w, b)$ nicht, nur die Lagrange-Multiplikatoren werden halb so groß.

Die Lagrange-Funktion

Idee: Statt die Nebenbedingungen „hart“ einzuhalten, bestraft man ihre Verletzung in der Zielfunktion. Für jede Nebenbedingung führt man einen Lagrange-Multiplikator (Lagrange multiplier) $\alpha_i \ge 0$ ein:

$$L(\mathbf w, b, \boldsymbol\alpha) = \tfrac12\langle\mathbf w\cdot\mathbf w\rangle - \sum_{i=1}^{\ell}\alpha_i\bigl[y_i(\langle\mathbf w\cdot\mathbf x_i\rangle + b) - 1\bigr].$$

Warum Minus und $\alpha_i\ge 0$? Die eckige Klammer ist $\ge 0$, wenn die Bedingung erfüllt ist, und $\lt 0$, wenn sie verletzt ist. Bei Verletzung wird $-\alpha_i[\dots]$ positiv, die Zielfunktion steigt. Maximiert man über $\boldsymbol\alpha \ge 0$, so gilt:

$$\max_{\boldsymbol\alpha\ge 0} L(\mathbf w, b, \boldsymbol\alpha) = \begin{cases} \tfrac12\langle\mathbf w\cdot\mathbf w\rangle & \text{falls alle Bedingungen erfüllt}\\ +\infty & \text{sonst.} \end{cases}$$

Das primale Problem ist also $\min_{\mathbf w,b}\max_{\boldsymbol\alpha\ge0} L$. Das duale Problem vertauscht die Reihenfolge: $\max_{\boldsymbol\alpha\ge0}\min_{\mathbf w,b} L$. Für konvexe Probleme mit (streng) erfüllbaren Nebenbedingungen (Slater-Bedingung, bei trennbaren Daten erfüllt) haben beide denselben Optimalwert (starke Dualität).

Die KKT-Bedingungen

Für ein konvexes Problem wie die SVM sind die Karush-Kuhn-Tucker-Bedingungen (KKT conditions) notwendig und hinreichend für Optimalität. Ein Punkt $(\mathbf w^*, b^*, \boldsymbol\alpha^*)$ ist genau dann optimal, wenn gilt:

Bedingung	Formel	Bedeutung
Stationarität in $\mathbf w$	$\mathbf w = \sum_i \alpha_i y_i \mathbf x_i$	$\nabla_{\mathbf w} L = 0$
Stationarität in $b$	$\sum_i \alpha_i y_i = 0$	$\partial L/\partial b = 0$
Primale Zulässigkeit	$y_i(\langle\mathbf w\cdot\mathbf x_i\rangle + b) \ge 1$	alle Punkte richtig mit Margin
Duale Zulässigkeit	$\alpha_i \ge 0$
Komplementärer Schlupf	$\alpha_i\bigl[y_i(\langle\mathbf w\cdot\mathbf x_i\rangle + b) - 1\bigr] = 0$	$\alpha_i = 0$ oder Bedingung aktiv

Herleitung der Stationarität:

$$\nabla_{\mathbf w} L = \mathbf w - \sum_i \alpha_i y_i \mathbf x_i \overset{!}{=} 0, \qquad \frac{\partial L}{\partial b} = -\sum_i \alpha_i y_i \overset{!}{=} 0.$$

Was der komplementäre Schlupf bedeutet

Das ist die wichtigste Bedingung für das Verständnis. Für jeden Trainingspunkt gibt es nur zwei Möglichkeiten:

• $y_i f(\mathbf x_i) \gt 1$ (Punkt liegt außerhalb des Margins, Bedingung inaktiv): Dann muss $\alpha_i = 0$ sein.
• $\alpha_i \gt 0$: Dann muss $y_i f(\mathbf x_i) = 1$ sein, der Punkt liegt genau auf dem Rand des Margins (Bedingung aktiv). Das ist ein Supportvektor.

Zusammen mit $\mathbf w = \sum_i \alpha_i y_i\mathbf x_i$ heißt das:

Warum nur die Supportvektoren zählen

$$\mathbf w = \sum_{i\,:\,\alpha_i \gt 0} \alpha_i y_i\mathbf x_i.$$

$\mathbf w$ ist eine Linearkombination nur der Supportvektoren. Alle anderen Punkte haben $\alpha_i = 0$ und tragen nichts bei. Man kann sie löschen, ohne dass sich die Lösung ändert. Das ist die exakte Fassung der Folienaussage „nur sie allein bestimmen die Lage der optimalen Trennebene“ (📄 08_svm.pdf, Folie 14).

Bestimmung von $b$: Für einen beliebigen Supportvektor $\mathbf x_s$ gilt $y_s(\langle\mathbf w\cdot\mathbf x_s\rangle + b) = 1$. Wegen $y_s^2 = 1$ folgt

$$b = y_s - \langle\mathbf w\cdot\mathbf x_s\rangle.$$

Numerisch stabiler ist der Mittelwert über alle Supportvektoren.

Das duale Problem

Setzt man die Stationaritätsbedingungen in $L$ ein, verschwinden $\mathbf w$ und $b$:

$$\begin{aligned} L &= \tfrac12\Bigl\langle\sum_i\alpha_i y_i\mathbf x_i \cdot \sum_j\alpha_j y_j\mathbf x_j\Bigr\rangle - \sum_i\alpha_i y_i\Bigl\langle\sum_j\alpha_j y_j\mathbf x_j\cdot\mathbf x_i\Bigr\rangle - b\underbrace{\sum_i\alpha_i y_i}_{=0} + \sum_i\alpha_i\\ &= \tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j\langle\mathbf x_i\cdot\mathbf x_j\rangle - \sum_{i,j}\alpha_i\alpha_j y_i y_j\langle\mathbf x_i\cdot\mathbf x_j\rangle + \sum_i\alpha_i\\ &= \sum_i\alpha_i - \tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j\langle\mathbf x_i\cdot\mathbf x_j\rangle. \end{aligned}$$

Duales SVM-Problem (Hard Margin)

$$\max_{\boldsymbol\alpha}\ W(\boldsymbol\alpha) = \sum_{i=1}^{\ell}\alpha_i - \frac12\sum_{i,j=1}^{\ell}\alpha_i\alpha_j y_i y_j\langle\mathbf x_i\cdot\mathbf x_j\rangle$$

unter den Nebenbedingungen $\alpha_i \ge 0$ und $\sum_i\alpha_i y_i = 0$.

Entscheidungsfunktion:

$$f(\mathbf x) = \sum_{i=1}^{\ell}\alpha_i y_i\langle\mathbf x_i\cdot\mathbf x\rangle + b.$$

Was hat man gewonnen?

1. Die Daten kommen nur noch in Skalarprodukten $\langle\mathbf x_i\cdot\mathbf x_j\rangle$ vor, im Training und in der Vorhersage. Ersetzt man das Skalarprodukt durch eine Kernfunktion, erhält man eine nichtlineare SVM, ohne den Merkmalsraum je explizit zu berechnen. Das ist der Kernel-Trick aus Kapitel 7.
2. Die Anzahl der Variablen ist $\ell$ (eine pro Trainingspunkt) statt $d+1$. Bei sehr hoher oder unendlicher Dimension $d$ ist das ein großer Vorteil.
3. Dünnbesetzte Lösung (sparse): Die meisten $\alpha_i$ sind 0.

Auch das duale Problem ist ein konvexes QP (die Matrix mit Einträgen $y_iy_j\langle\mathbf x_i\cdot\mathbf x_j\rangle$ ist positiv semidefinit). Klassische SVM-Pakete wie libsvm (auf 📄 09_svm_nicht_trennbar.pdf, Folie 5 als „svmlib“ erwähnt) lösen dieses duale Problem.

Nützliche Identität: Im Optimum gilt $\langle\mathbf w\cdot\mathbf w\rangle = \sum_i\alpha_i$. Begründung: $\langle\mathbf w\cdot\mathbf w\rangle = \sum_i\alpha_i y_i\langle\mathbf w\cdot\mathbf x_i\rangle$, und für Supportvektoren ist $\langle\mathbf w\cdot\mathbf x_i\rangle = y_i - b$. Also $\sum_i\alpha_i y_i(y_i - b) = \sum_i\alpha_i - b\sum_i\alpha_iy_i = \sum_i\alpha_i$. Damit ist die Streifenbreite $2/\sqrt{\sum_i\alpha_i}$.

Zahlenbeispiel: KKT-Check

Wir prüfen die Lösung aus Beispiel 3 in 6.2: $\mathbf x_1 = (0,0)$, $y_1 = -1$; $\mathbf x_2 = (2,2)$, $y_2 = +1$; $\mathbf x_3 = (3,0)$, $y_3 = +1$, mit $\mathbf w = (\tfrac23,\tfrac13)$, $b = -1$.

Gesucht: $\alpha_1,\alpha_2,\alpha_3 \ge 0$ mit $\mathbf w = \sum_i\alpha_i y_i\mathbf x_i$ und $\sum_i\alpha_i y_i = 0$.

$$\mathbf w = -\alpha_1(0,0) + \alpha_2(2,2) + \alpha_3(3,0) = (2\alpha_2 + 3\alpha_3,\ 2\alpha_2) \overset{!}{=} (\tfrac23,\tfrac13).$$

• Zweite Komponente: $2\alpha_2 = \tfrac13 \Rightarrow \alpha_2 = \tfrac16$.
• Erste Komponente: $\tfrac13 + 3\alpha_3 = \tfrac23 \Rightarrow \alpha_3 = \tfrac19$.
• Summenbedingung: $-\alpha_1 + \alpha_2 + \alpha_3 = 0 \Rightarrow \alpha_1 = \tfrac16 + \tfrac19 = \tfrac{5}{18}$.

Check aller KKT-Bedingungen:

Bedingung	erfüllt?
Stationarität	✔ nach Konstruktion
Primale Zulässigkeit	✔ alle $y_if(\mathbf x_i) = 1$
Duale Zulässigkeit	✔ alle $\alpha_i \gt 0$
Komplementärer Schlupf	✔ alle Bedingungen aktiv

Da das Problem konvex ist, sind die KKT-Bedingungen hinreichend: Die Lösung ist optimal. Probe der Identität: $\sum_i\alpha_i = \tfrac{5}{18} + \tfrac{3}{18} + \tfrac{2}{18} = \tfrac59 = \lVert\mathbf w\rVert^2$. ✔

Gegenprobe mit Versuch 1 ($\mathbf w = (\tfrac12,\tfrac12)$, $b = -1$): Diese Lösung verletzt die primale Zulässigkeit für $\mathbf x_3$ und ist daher nicht optimal, egal welche $\alpha_i$ man wählt.

Beispiel 2 aus 6.2 (Punkte $(0,0)$, $(2,2)$, $(4,4)$): Hier ist $y_3f(\mathbf x_3) = 3 \gt 1$, also $\alpha_3 = 0$. Aus $\mathbf w = \alpha_2(2,2) = (\tfrac12,\tfrac12)$ folgt $\alpha_2 = \tfrac14$ und mit der Summenbedingung $\alpha_1 = \tfrac14$. Probe: $\sum\alpha_i = \tfrac12 = \lVert\mathbf w\rVert^2$. ✔

Typische Fallstricke

• Vorzeichen der Lagrange-Multiplikatoren: Bei Ungleichungen müssen sie $\ge 0$ sein, bei Gleichungen sind sie frei. Wer das vergisst, bekommt keine korrekte Dualität.
• $\alpha_i \gt 0$ impliziert Supportvektor, aber nicht umgekehrt. In Spezialfällen kann ein Punkt genau auf dem Margin liegen und trotzdem $\alpha_i = 0$ haben (degenerierter Fall).
• Faktor $\tfrac12$: Ohne ihn (wie auf 📄 08_svm.pdf, Folie 16) werden alle $\alpha_i$ doppelt so groß, die Trennebene bleibt dieselbe.