6.6 Hinge-Loss und Pegasos

Die Soft Margin SVM aus 6.5 ist ein quadratisches Programm mit $2\ell$ Nebenbedingungen. Man könnte es mit einem QP-Löser angehen. Die Vorlesung geht einen anderen, sehr modernen Weg: Sie eliminiert die Nebenbedingungen, erhält so eine Zielfunktion „Regularisierer + Verlust“ und minimiert diese mit einem stochastischen Subgradientenabstieg, ganz ähnlich wie beim Perzeptron.

Umwandlung in eine Optimierung ohne Nebenbedingungen

📄 09_svm_nicht_trennbar.pdf, Folie 12

Ausgangspunkt sind die $\ell$ Nebenbedingungen

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

Schritt 1: Mit der Entscheidungsfunktion $f(\mathbf x_i) = \langle\mathbf w\cdot\mathbf x_i\rangle + b$ der SVM lautet das

$$y_if(\mathbf x_i) \ge 1 - \xi_i \quad\Longleftrightarrow\quad \xi_i \ge 1 - y_if(\mathbf x_i).$$

Schritt 2: Zusammen mit $\xi_i\ge 0$ muss $\xi_i$ größer oder gleich beiden Schranken sein, also

$$\xi_i \ge \max\bigl(0,\ 1 - y_if(\mathbf x_i)\bigr).$$

Schritt 3: Am Minimum muss hier Gleichheit gelten. Denn wäre $\xi_i$ echt größer als nötig, könnte man es verkleinern, ohne eine Nebenbedingung zu verletzen. Wegen $C \gt 0$ würde die Zielfunktion dabei sinken, man wäre also nicht im Minimum. Also

$$\xi_i = \max\bigl(0,\ 1 - y_if(\mathbf x_i)\bigr).$$

Schritt 4: Einsetzen in die Zielfunktion eliminiert die $\xi_i$ und alle Nebenbedingungen:

Soft Margin SVM ohne Nebenbedingungen

$$f(\mathbf w) = \tfrac12\langle\mathbf w\cdot\mathbf w\rangle + C\sum_{i=1}^{\ell}\max\bigl(0,\ 1 - y_if(\mathbf x_i)\bigr),\qquad \mathbf w\in\mathbb R^d.$$

(Optimiert wird natürlich weiterhin auch über $b$, das in $f(\mathbf x_i)$ steckt. Die Folie schreibt nur $\mathbf w$.)

Fallstrick: zweimal $f$

Auf der Folie bezeichnet $f$ sowohl die Zielfunktion $f(\mathbf w)$ als auch die Entscheidungsfunktion $f(\mathbf x_i)$. Gemeint ist im Summanden immer die Entscheidungsfunktion $\langle\mathbf w\cdot\mathbf x_i\rangle + b$.

Verlustfunktion

📄 09_svm_nicht_trennbar.pdf, Folie 13

Der zweite Term

$$\mathcal L(\mathbf w) = \sum_{i=1}^{\ell}\max\bigl(0,\ 1 - y_if(\mathbf x_i)\bigr)$$

ist eine Verlustfunktion (loss function). Die Größe $y_if(\mathbf x_i)$ ist positiv bei korrekter, negativ bei falscher Klassifikation und umso größer, je weiter der Punkt auf der richtigen Seite liegt. Es gibt drei Fälle:

1. $y_if(\mathbf x_i) \gt 1$: Punkt liegt außerhalb des Margins und trägt nichts zum Verlust bei.
2. $y_if(\mathbf x_i) = 1$: Punkt sitzt genau auf dem Margin (Supportvektor) und trägt ebenfalls nichts bei.
3. $y_if(\mathbf x_i) \lt 1$: Punkt verletzt den Margin (ebenfalls Supportvektor) und trägt zum Verlust bei, und zwar linear mit der Stärke der Verletzung.

Interpretation: Die SVM-Zielfunktion hat jetzt die Form

$$\underbrace{\tfrac12\lVert\mathbf w\rVert^2}_{\text{Regularisierung (großer Margin)}} + C\cdot\underbrace{\mathcal L(\mathbf w)}_{\text{Datenanpassung}}.$$

Ergänzung, nicht auf den Folien: Das ist dasselbe Muster wie bei Ridge-Regression (quadratischer Verlust + $\lVert\mathbf w\rVert^2$) oder regularisierter logistischer Regression (logistischer Verlust $\log(1 + e^{-yf})$ + $\lVert\mathbf w\rVert^2$). Die SVM unterscheidet sich „nur“ durch die Wahl des Verlusts.

Hinge-Loss

📄 09_svm_nicht_trennbar.pdf, Folie 14

Trägt man den Verlust eines einzelnen Punkts über $z = y_if(\mathbf x_i)$ auf, erhält man den Hinge-Loss (engl. hinge, „Scharnier“, deutsch auch Scharnierverlust):

$$\ell_\text{hinge}(z) = \max(0,\ 1 - z).$$

Zum Vergleich der 0-1-Verlust (0-1 loss), der einfach Fehler zählt: 1 bei falscher Klassifikation ($z \lt 0$), sonst 0.

$z = y_if(\mathbf x_i)$	$-2$	$-1$	$0$	$0{,}5$	$1$	$2$
0-1-Verlust	1	1	1 bzw. 0*	0	0	0
Hinge-Loss	3	2	1	0,5	0	0

* Bei $z = 0$ (Punkt auf der Trennebene) ist die Konvention uneinheitlich.

Eigenschaften:

• Der Hinge-Loss ist eine obere Schranke des 0-1-Verlusts: $\ell_\text{hinge}(z) \ge \ell_{0\text{-}1}(z)$ für alle $z$. Minimiert man den Hinge-Loss, drückt man also auch die Anzahl der Fehler nach unten.
• Er ist konvex (Maximum zweier linearer Funktionen, vgl. die V-Form im Quiz in 6.3). Der 0-1-Verlust ist das nicht und außerdem fast überall flach (Gradient 0), also für Optimierung unbrauchbar.
• Er bestraft auch korrekt klassifizierte Punkte, die zu nah an der Ebene liegen ($0 \lt z \lt 1$). Das erzwingt den Margin.
• Aber: Bei $z = 1$ hat er einen Knick, er ist dort nicht differenzierbar. Gradientenabstieg im klassischen Sinn geht also nicht.

Ergänzung: Vergleich mit dem Perzeptron. Dessen Verlust ist $\max(0, -z)$: Er bestraft nur Fehlklassifikationen, nicht zu kleine Abstände. Der Hinge-Loss ist genau dieser Perzeptron-Verlust, um 1 nach rechts verschoben. Diese kleine Verschiebung und der Regularisierer machen den Unterschied zwischen „irgendeine Trennebene“ und „Trennebene mit maximalem Margin“.

Subgradienten

📄 09_svm_nicht_trennbar.pdf, Folie 15

Um konvexe, aber nicht überall differenzierbare Funktionen zu minimieren, verallgemeinert man den Gradienten.

Subgradient

Ein Subgradient einer konvexen Funktion $f$ an der Stelle $\mathbf x$ ist die Steigung $\mathbf g$ einer Geraden (oder Ebene), die $f$ in $\mathbf x$ berührt und überall unterhalb von $f$ verläuft:

$$f(\mathbf z) \ge f(\mathbf x) + \mathbf g^\top(\mathbf z - \mathbf x)\quad\text{für alle } \mathbf z.$$

• An Stellen, an denen $f$ differenzierbar ist, ist der Subgradient eindeutig und gleich der Steigung der Tangente (dem Gradienten).
• An Stellen, an denen $f$ nicht differenzierbar ist, ist der Subgradient eine Menge: die Steigungen aller Tangentialebenen durch $\mathbf x$, die unterhalb von $f$ verlaufen. Diese Menge heißt Subdifferential $\partial f(\mathbf x)$.

Anmerkung: Auf der Folie steht „für alle $z\in\mathbb R$“. Im Mehrdimensionalen ist natürlich $\mathbf z\in\mathbb R^n$ gemeint.

Warum funktioniert das nur für konvexe Funktionen? Nur bei konvexen Funktionen gibt es an jeder Stelle eine solche „Stützgerade“ unterhalb des Graphen, denn konvexe Funktionen liegen immer oberhalb ihrer Tangenten.

Beispiele

📄 09_svm_nicht_trennbar.pdf, Folie 16

Betragsfunktion $f(x) = \lvert x\rvert$:

$$\partial f(x) = \begin{cases} -1 & x \lt 0\\ [-1, 1] & x = 0\\ +1 & x \gt 0 \end{cases}$$

Bei $x = 0$ passt jede Gerade durch den Ursprung mit Steigung zwischen $-1$ und $1$ unter das V. Im Graphen des Subdifferentials sieht man an dieser Stelle einen senkrechten Sprung von $-1$ auf $1$.

$f(x) = \max\bigl(0,\ \tfrac12(x^2 - 1)\bigr)$: Für $\lvert x\rvert \gt 1$ ist $f(x) = \tfrac12(x^2-1)$ mit Ableitung $x$. Für $\lvert x\rvert\lt 1$ ist $f = 0$ mit Ableitung $0$. An den Knickstellen:

$$\partial f(1) = [0, 1],\qquad \partial f(-1) = [-1, 0].$$

Links und rechts der Knickstelle haben die Ableitungen die Werte 0 und 1 (bzw. $-1$ und 0), das Subdifferential füllt das Intervall dazwischen.

Ergänzung: Ein Punkt $\mathbf x^*$ ist genau dann globales Minimum einer konvexen Funktion, wenn $\mathbf 0\in\partial f(\mathbf x^*)$. Beim Betrag: $0 \in [-1,1]$ bei $x = 0$, also ist 0 das Minimum.

Subgradient des Hinge-Loss

📄 09_svm_nicht_trennbar.pdf, Folie 17

Für einen Summanden $\max(0, 1 - y_i(\langle\mathbf w\cdot\mathbf x_i\rangle + b))$ gilt nach der Kettenregel (das Innere ist linear in $\mathbf w$ mit Ableitung $-y_i\mathbf x_i$):

$$\frac{\partial}{\partial\mathbf w}\max(0, 1 - y_if(\mathbf x_i)) = \begin{cases} -y_i\mathbf x_i & \text{falls } y_if(\mathbf x_i) \lt 1\\ \mathbf 0 & \text{falls } y_if(\mathbf x_i) \gt 1\\ \theta\cdot(-y_i\mathbf x_i),\ \theta\in[0,1] & \text{falls } y_if(\mathbf x_i) = 1. \end{cases}$$

Für den gesamten Verlust $\mathcal L(\mathbf w)$ addiert man die Beiträge. An Knickpunkten nimmt der Subgradient alle Zwischenwerte zwischen 0 und $-\sum_{i:\ y_if(\mathbf x_i)\lt 1} y_i\mathbf x_i$ an (genauer: die Beiträge der Punkte mit $y_if(\mathbf x_i) = 1$ können jeweils zwischen 0 und $-y_i\mathbf x_i$ liegen).

Ergänzung: Analog ist die Ableitung nach $b$ gleich $-y_i$ für Punkte mit $y_if(\mathbf x_i)\lt 1$ und 0 sonst.

Die Subgradientenmethode

📄 09_svm_nicht_trennbar.pdf, Folie 18

Sei $f:\mathbb R^n\to\mathbb R$ konvex. Die Subgradientenmethode (subgradient method) iteriert

$$\mathbf x^{(k+1)} = \mathbf x^{(k)} - \eta\,\mathbf g^{(k)},$$

wobei $\mathbf g^{(k)}$ ein beliebiger Subgradient von $f$ an $\mathbf x^{(k)}$ ist. Das entspricht dem normalen Gradientenabstieg, nur läuft man in Richtung des negativen Subgradienten.

Unterschied zum Gradientenabstieg: Es ist nicht garantiert, dass die Zielfunktion bei jedem Schritt kleiner wird. Ein negativer Subgradient ist nicht unbedingt eine Abstiegsrichtung (Beispiel: $f(x_1,x_2) = \lvert x_1\rvert + 2\lvert x_2\rvert$ an einem Knick). Dennoch kann man beweisen, dass die Methode zum Minimum hin konvergiert, wenn die Schrittweite asymptotisch gegen 0 geht.

Ergänzung: Die genaue Bedingung ist $\eta_k \to 0$ und $\sum_k\eta_k = \infty$. Die zweite Bedingung sorgt dafür, dass man trotz kleiner werdender Schritte noch beliebig weit kommt. $\eta_k = 1/k$ erfüllt beides (harmonische Reihe divergiert). Weil die Funktionswerte nicht monoton fallen, merkt man sich in der Praxis oft den bisher besten Punkt.

Subgradientenmethode für die SVM

📄 09_svm_nicht_trennbar.pdf, Folie 19

Für die SVM-Zielfunktion $\tfrac12\langle\mathbf w\cdot\mathbf w\rangle + C\,\mathcal L(\mathbf w)$ wählt man an Knickpunkten ($y_if(\mathbf x_i) = 1$) einfach den Subgradienten 0 für diesen Summanden. Der Subgradient des Regularisierers ist $\mathbf w$. Damit ergibt sich die Iteration

$$\mathbf w_{t+1} = \mathbf w_t - \eta\Bigl(\mathbf w_t - C\sum_{i:\ y_if(\mathbf x_i)\lt 1} y_i\mathbf x_i\Bigr).$$

Das ist ein Batch-Update über den gesamten Datensatz. Statt dessen macht man wie beim Perzeptron eine Einzelbeispielkorrektur, d.h. einen stochastischen (Sub-)Gradientenabstieg (stochastic subgradient descent): In jedem Schritt wird nur ein (zufällig gezogenes) Beispiel $(\mathbf x_i, y_i)$ betrachtet.

Pegasos: Primal Estimated sub-GrAdient SOlver for SVM

$$\mathbf w_{t+1} = \begin{cases} \mathbf w_t - \eta_t(\mathbf w_t - Cy_i\mathbf x_i) & \text{falls } y_if(\mathbf x_i) \lt 1\\ \mathbf w_t - \eta_t\mathbf w_t & \text{sonst} \end{cases}$$

mit der zeitabhängigen Lernrate $\eta_t = 1/t$.

Die zwei Fälle verstehen:

• Sonst-Fall ($y_if(\mathbf x_i)\ge 1$, Punkt gut klassifiziert): $\mathbf w_{t+1} = (1 - \eta_t)\mathbf w_t$. Der Gewichtsvektor wird nur geschrumpft. Das ist der Effekt des Regularisierers: kleineres $\lVert\mathbf w\rVert$, also breiterer Margin.
• Verletzungs-Fall ($y_if(\mathbf x_i)\lt 1$): $\mathbf w_{t+1} = (1-\eta_t)\mathbf w_t + \eta_tCy_i\mathbf x_i$. Zusätzlich zum Schrumpfen wird $\mathbf w$ in Richtung des Beispiels korrigiert, genau wie beim Perzeptron ($\mathbf w \leftarrow \mathbf w + y_i\mathbf x_i$), nur dass das Perzeptron bloß bei echter Fehlklassifikation korrigiert, Pegasos schon bei einer Margin-Verletzung.

Vergleich Perzeptron und Pegasos (Ergänzung):

	Perzeptron	Pegasos
Korrektur, wenn	$y_if(\mathbf x_i) \le 0$ (falsch)	$y_if(\mathbf x_i) \lt 1$ (Margin verletzt)
Schrumpfen von $\mathbf w$	nie	in jedem Schritt
Lernrate	konstant	$\eta_t = 1/t$
Ziel	irgendeine Trennebene	Minimum der konvexen SVM-Zielfunktion
Ende	sobald alles getrennt ist	Konvergenz gegen das globale Optimum

Zahlenbeispiel: Pegasos von Hand

Ergänzung, nicht auf den Folien. Zwei Punkte, $C = 1$, ohne Bias ($b = 0$), abwechselnd präsentiert: $\mathbf x_A = (2,1)$, $y_A = +1$ und $\mathbf x_B = (-1,-2)$, $y_B = -1$. Start $\mathbf w_1 = (0,0)$.

$t$	$\eta_t$	Beispiel	$y_if(\mathbf x_i)$	Fall	$\mathbf w_{t+1}$
1	$1$	A	$0$	verletzt	$(0,0) - 1\cdot\bigl((0,0) - (2,1)\bigr) = (2,\ 1)$
2	$\tfrac12$	B	$4$	sonst	$\tfrac12(2,1) = (1,\ 0{,}5)$
3	$\tfrac13$	A	$2{,}5$	sonst	$\tfrac23(1, 0{,}5) = (0{,}67,\ 0{,}33)$
4	$\tfrac14$	B	$1{,}33$	sonst	$\tfrac34(0{,}67, 0{,}33) = (0{,}5,\ 0{,}25)$
5	$\tfrac15$	A	$1{,}25$	sonst	$\tfrac45(0{,}5, 0{,}25) = (0{,}4,\ 0{,}2)$
6	$\tfrac16$	B	$0{,}8$	verletzt	$(0{,}4, 0{,}2) - \tfrac16\bigl((0{,}4,0{,}2) - (1,2)\bigr) = (0{,}5,\ 0{,}5)$

Man sieht das typische Verhalten: Solange alle Punkte den Margin einhalten, schrumpft $\mathbf w$ (der Margin wächst). Sobald ein Punkt in den Margin rutscht ($t = 6$), zieht die Korrektur $\mathbf w$ wieder in seine Richtung. Mit kleiner werdendem $\eta_t$ pendelt sich das auf das Optimum ein.

Beispiel aus der Vorlesung

📄 09_svm_nicht_trennbar.pdf, Folie 20

Links: Die „Energie“ (Wert der Zielfunktion) über ca. 300 Iterationen auf logarithmischer Skala. Sie fällt anfangs schnell, ist nicht monoton (Zacken, typisch für stochastische Subgradientenverfahren) und stabilisiert sich dann. Rechts: zwei überlappende Punktwolken mit der gefundenen Trennebene (blau) und den Margin-Rändern (gestrichelt). Einige Punkte liegen im Margin oder auf der falschen Seite, das ist bei nicht trennbaren Daten unvermeidlich.

Anmerkungen zur Pegasos-Folie

• Die Folie lässt offen, wie $b$ behandelt wird. Üblich ist, $b$ analog mit $\eta_tCy_i$ zu aktualisieren (ohne Schrumpfen), oder eine konstante 1 als zusätzliches Merkmal an $\mathbf x$ anzuhängen.
• Im Originalpaper (Shalev-Shwartz et al., 2007) steht die Zielfunktion in der Form $\tfrac\lambda2\lVert\mathbf w\rVert^2 + \tfrac1\ell\sum_i\ell_\text{hinge}$ mit Lernrate $\eta_t = 1/(\lambda t)$. Die Folie verwendet die $C$-Form. Streng genommen ist ein stochastischer Schritt mit einem einzigen Beispiel eine Schätzung von $C\sum_i(\dots)$ erst nach Multiplikation mit $\ell$. Für das Verständnis ist das unerheblich, es verschiebt nur die Bedeutung von $C$ um den Faktor $\ell$.

Typische Fallstricke

• Hinge-Loss ist nicht differenzierbar, aber konvex. Nicht verwechseln: Konvexität garantiert das globale Optimum, Differenzierbarkeit ist nur für klassischen Gradientenabstieg nötig.
• Subgradientenverfahren sind keine Abstiegsverfahren. Die Zielfunktion darf zwischendurch steigen.
• Punkte mit $0 \lt y_if(\mathbf x_i) \lt 1$ verursachen Verlust, obwohl sie korrekt klassifiziert sind.
• $\eta_t = 1/t$ ist wichtig. Bei konstanter Lernrate springt der stochastische Subgradientenabstieg dauerhaft um das Optimum herum.