6.3 Konvexe Optimierung

Die SVM ist ein Optimierungsproblem mit Nebenbedingungen (6.2). Dieser Abschnitt klärt die Begriffe und zeigt den entscheidenden Vorteil der SVM gegenüber z.B. neuronalen Netzen: Das Problem ist konvex, jedes lokale Minimum ist also ein globales.

Optimierung unter Nebenbedingungen

📄 08_svm.pdf, Folie 18

Optimierungsproblem mit Nebenbedingungen

minimiere $\ f(\mathbf x),\quad \mathbf x\in\Omega$

unter den Nebenbedingungen (constraints):

$$\begin{aligned} g_i(\mathbf x) &\le 0, \quad i = 1,\dots,k &&\text{(Ungleichheitsbedingungen)}\\ h_i(\mathbf x) &= 0, \quad i = 1,\dots,m &&\text{(Gleichheitsbedingungen)} \end{aligned}$$

Begriffe:

• Die Funktionen $g_i$ und $h_i$ schränken die Wahl von $\mathbf x$ ein auf die Bereiche, in denen alle Bedingungen erfüllt sind.
• Eine Ungleichheitsbedingung heißt aktiv (active), wenn sie am Minimum $\mathbf x^*$ gerade noch erfüllt ist, also $g_i(\mathbf x^*) = 0$. Sonst ($g_i(\mathbf x^*) \lt 0$) heißt sie inaktiv (inactive).
• Der Bereich, in dem alle Bedingungen erfüllt sind, heißt zulässiger Bereich (feasible region), ein Punkt darin zulässig (feasible).

Anmerkung: Die Folie schreibt $\mathbf x \in \Omega$ in die Zielzeile und nennt $\Omega$ den zulässigen Bereich. Gemeint ist: $\Omega$ ist die Menge aller Punkte, die die Nebenbedingungen erfüllen.

Übertragung auf die SVM: Die Optimierungsvariablen sind $(\mathbf w, b)$. Die Nebenbedingungen $y_i(\langle\mathbf w\cdot\mathbf x_i\rangle + b)\ge 1$ bringt man in die Normalform $g_i \le 0$:

$$g_i(\mathbf w, b) = 1 - y_i(\langle\mathbf w\cdot\mathbf x_i\rangle + b) \le 0.$$

Es gibt $k = \ell$ Ungleichheitsbedingungen und keine Gleichheitsbedingungen. Aktiv sind genau die Bedingungen der Supportvektoren ($y_i f(\mathbf x_i) = 1$), alle anderen sind inaktiv. Das ist eine sehr nützliche Übersetzung: Supportvektor = Punkt mit aktiver Nebenbedingung.

Lokale und globale Optima

📄 08_svm.pdf, Folie 19

• Ein zulässiger Punkt $\mathbf x^*\in\Omega$ heißt globales Minimum, wenn für alle $\mathbf x\in\Omega$ gilt: $f(\mathbf x^*) \le f(\mathbf x)$.
• Ein zulässiger Punkt $\mathbf x^*\in\Omega$ heißt lokales Minimum, wenn es einen Radius $r \gt 0$ gibt, sodass für alle $\mathbf x\in\Omega$ mit $\lVert\mathbf x^* - \mathbf x\rVert \lt r$ gilt: $f(\mathbf x^*) \le f(\mathbf x)$.

Die Lösung des Optimierungsproblems ist ein globales Optimum.

Die Abbildung auf der Folie zeigt eine Funktion mit mehreren lokalen Minima. Wichtig: Durch die Einschränkung auf $\Omega$ können auch am Rand von $\Omega$ lokale Minima entstehen, an Stellen, an denen die Funktion ohne Nebenbedingung weiter fallen würde. Das sind genau die Fälle, in denen eine Nebenbedingung aktiv ist.

📄 08_svm.pdf, Folie 20

Das 3D-Beispiel zeigt eine unregelmäßige Funktion mit einer linearen Ungleichheitsbedingung (Halbebene) und einer linearen Gleichheitsbedingung (Gerade). Das globale Minimum mit Nebenbedingung liegt woanders als das ohne Nebenbedingung. Ein lokales Verfahren wie Gradientenabstieg würde bei so einer Funktion je nach Startpunkt in einem anderen lokalen Minimum landen.

Konvexe Mengen und konvexe Funktionen

📄 08_svm.pdf, Folie 21

Die Optimierung wird erheblich leichter, wenn das Problem konvex ist.

Konvexe Menge (convex set)

Eine Menge $X$ heißt konvex, wenn für alle $\mathbf x,\mathbf y\in X$ und beliebiges $0\le\theta\le 1$ gilt:

$$\theta\mathbf x + (1-\theta)\mathbf y \in X.$$

Intuitiv: Mit je zwei Punkten liegt auch die gesamte Verbindungsstrecke in der Menge. Der Ausdruck $\theta\mathbf x + (1-\theta)\mathbf y$ durchläuft für $\theta$ von 1 bis 0 genau die Strecke von $\mathbf x$ nach $\mathbf y$. Eine Menge mit „Einbuchtung“ (wie das Polygon auf der Folie) ist nicht konvex.

Konvexe Funktion (convex function)

Eine Funktion $f$ heißt konvex, wenn für alle $\mathbf x,\mathbf y$ und beliebiges $0\le\theta\le 1$ gilt:

$$f(\theta\mathbf x + (1-\theta)\mathbf y) \le \theta f(\mathbf x) + (1-\theta) f(\mathbf y).$$

Intuitiv: Die Sehne zwischen zwei Punkten des Graphen liegt nie unterhalb des Graphen. Links steht der Funktionswert an einem Zwischenpunkt, rechts der Wert der Sehne an derselben Stelle. Die Funktion „hängt durch“ wie eine Schüssel.

Ergänzung: Für zweimal differenzierbare Funktionen einer Variablen ist $f$ genau dann konvex, wenn $f''(x)\ge 0$ überall gilt. Im Mehrdimensionalen: Die Hesse-Matrix ist überall positiv semidefinit.

Quiz: Welche Mengen und Funktionen sind konvex?

📄 08_svm.pdf, Folie 22 📄 08_svm.pdf, Folie 23

Die Folien enthalten zwei Bilderquiz ohne Auflösung. Die folgenden Lösungen sind meine Lesart der Bilder, nicht von den Folien.

Lösung Mengen (Folie 22)

Bild	konvex?	Begründung
Sanddollar (Scheibe)	ja	Kreisscheibe, keine Einbuchtung
Koralle	nein	verzweigt, Verbindungsstrecken verlassen die Menge
roter Edelstein (Achteck-Schliff)	ja	konvexes Polyeder
Seestern	nein	zwischen den Armen liegen Einbuchtungen
Schneeflocke	nein	verzweigte Struktur
Kristallkugel (facettiert)	ja	konvexes Polyeder, kugelähnlich

Lösung Funktionen (Folie 23)

Position	Form	konvex?
oben 1	nach oben geöffnete Parabel	ja
oben 2	Gerade	ja (lineare Funktionen sind konvex und konkav)
oben 3	nach unten geöffnete Parabel	nein (konkav)
oben 4	geknickte Gerade, V-Form	ja (Maximum zweier linearer Funktionen, nicht differenzierbar, trotzdem konvex)
unten 1	fallende, abflachende Kurve	ja
unten 2	fallend mit Plateau und erneutem Abfall	nein (Wendepunkte, Sehne liegt teilweise darunter)
unten 3	zwei Mulden (W-Form)	nein (zwei lokale Minima)
unten 4	zwei Geradenstücke mit Sprung	nein (Sprungstelle, eine konvexe Funktion ist im Inneren ihres Definitionsbereichs stetig)

Die V-Form (oben 4) ist besonders wichtig: Der Hinge-Loss in 6.6 hat genau so einen Knick und ist trotzdem konvex.

Eigenschaften konvexer Mengen und Funktionen

📄 08_svm.pdf, Folie 24

Aussage	gilt?	Kurzbegründung (Ergänzung)
Schnittmengen konvexer Mengen sind konvex	✔	Liegen $\mathbf x,\mathbf y$ in allen Mengen, liegt auch die Strecke in jeder, also im Schnitt
Vereinigungen konvexer Mengen sind konvex	✘ (nicht immer)	Zwei getrennte Kreisscheiben: Die Strecke zwischen ihnen verlässt die Vereinigung
Summe zweier konvexer Funktionen ist konvex	✔	Ungleichungen addieren
Positives Vielfaches einer konvexen Funktion ist konvex	✔	Ungleichung mit $c \gt 0$ multiplizieren, Richtung bleibt
Differenz zweier konvexer Funktionen ist konvex	✘ (nicht immer)	$0 - x^2 = -x^2$ ist konkav
Ist $f$ konvex, so ist die Subniveaumenge $\{\mathbf x \mid f(\mathbf x)\le 0\}$ konvex	✔	siehe unten

Beweis der letzten Aussage (Ergänzung): Seien $f(\mathbf x)\le 0$ und $f(\mathbf y)\le 0$. Dann ist

$$f(\theta\mathbf x + (1-\theta)\mathbf y) \le \theta\underbrace{f(\mathbf x)}_{\le 0} + (1-\theta)\underbrace{f(\mathbf y)}_{\le 0} \le 0,$$

also liegt auch der Zwischenpunkt in der Menge.

Warum ist das wichtig? Ist jede Ungleichheitsbedingung $g_i(\mathbf x)\le 0$ mit konvexem $g_i$ gegeben, so ist jede einzelne zulässige Menge konvex und damit auch ihr Schnitt, der gesamte zulässige Bereich.

Beispiele für konvexe Funktionen

📄 08_svm.pdf, Folie 25

Lineare Funktionen $\langle\mathbf w\cdot\mathbf x\rangle + b$ sind konvex

Man rechnet die Differenz „linke Seite minus rechte Seite“ der Definition aus:

$$\begin{aligned} &f(\theta\mathbf x + (1-\theta)\mathbf y) - \bigl(\theta f(\mathbf x) + (1-\theta) f(\mathbf y)\bigr)\\ &= \langle\mathbf w\cdot(\theta\mathbf x + (1-\theta)\mathbf y)\rangle + b - \bigl(\theta(\langle\mathbf w\cdot\mathbf x\rangle + b) + (1-\theta)(\langle\mathbf w\cdot\mathbf y\rangle + b)\bigr)\\ &= \langle\mathbf w\cdot(\theta\mathbf x + (1-\theta)\mathbf y)\rangle + b - \bigl(\langle\mathbf w\cdot(\theta\mathbf x + (1-\theta)\mathbf y)\rangle + b\bigr) = 0. \end{aligned}$$

Im zweiten Schritt wurde die Linearität des Skalarprodukts benutzt und $\theta b + (1-\theta)b = b$. Die Differenz ist $0 \le 0$, also gilt die Konvexitätsungleichung (sogar mit Gleichheit).

$f(x) = x^2$ ist konvex

$$\begin{aligned} &f(\theta x + (1-\theta) y) - \bigl(\theta f(x) + (1-\theta) f(y)\bigr)\\ &= (\theta x + (1-\theta)y)^2 - \bigl(\theta x^2 + (1-\theta)y^2\bigr)\\ &= -\theta(1-\theta)(x^2 - 2xy + y^2) = -\theta(1-\theta)(x-y)^2 \le 0. \end{aligned}$$

Zwischenschritt (auf der Folie übersprungen): Ausmultiplizieren ergibt $\theta^2x^2 + 2\theta(1-\theta)xy + (1-\theta)^2y^2 - \theta x^2 - (1-\theta)y^2$. Wegen $\theta^2 - \theta = -\theta(1-\theta)$ und $(1-\theta)^2 - (1-\theta) = -\theta(1-\theta)$ fasst sich das zu $-\theta(1-\theta)(x^2 - 2xy + y^2)$ zusammen. Da $\theta(1-\theta)\ge 0$ für $\theta\in[0,1]$ und $(x-y)^2\ge 0$, ist das Ergebnis $\le 0$.

$f(\mathbf x) = \langle\mathbf x\cdot\mathbf x\rangle$ ist konvex

Folgt aus der Konvexität von $x^2$ und $\langle\mathbf x\cdot\mathbf x\rangle = x_1^2 + x_2^2 + \dots$: Jeder Summand $x_j^2$ ist konvex (als Funktion von $\mathbf x$, die nur von einer Koordinate abhängt), und Summen konvexer Funktionen sind konvex.

Konvexe Optimierungsprobleme

📄 08_svm.pdf, Folie 26

Satz

Wenn $\Omega$ eine konvexe Menge und $f$ eine konvexe Funktion ist, dann ist jedes lokale Minimum von $f$ ein globales Minimum über $\Omega$.

Beweisidee (Ergänzung, nicht auf den Folien): Angenommen, $\mathbf x^*$ ist lokales, aber nicht globales Minimum. Dann gibt es ein $\mathbf y\in\Omega$ mit $f(\mathbf y) \lt f(\mathbf x^*)$. Wegen der Konvexität von $\Omega$ liegt die ganze Strecke von $\mathbf x^*$ nach $\mathbf y$ in $\Omega$. Wegen der Konvexität von $f$ gilt auf der Strecke

$$f(\theta\mathbf y + (1-\theta)\mathbf x^*) \le \theta f(\mathbf y) + (1-\theta) f(\mathbf x^*) \lt f(\mathbf x^*) \quad\text{für } 0\lt\theta\le 1.$$

Für beliebig kleines $\theta$ gibt es also Punkte beliebig nahe an $\mathbf x^*$ mit kleinerem Funktionswert. Widerspruch zur lokalen Minimalität.

Konsequenzen:

• Bei konvexen Problemen kann die Lösung mit lokalen Methoden (z.B. Gradientenabstieg) gefunden werden, ohne ganz $\Omega$ absuchen zu müssen.
• Achtung: Der Satz sagt nicht, dass für jede konvexe Menge und jede konvexe Funktion ein Minimum existiert. Beispiel (Ergänzung): $f(x) = e^x$ auf $\Omega = \mathbb R$ ist konvex, hat aber kein Minimum, die Funktion nähert sich nur der 0 an.
• Unter bestimmten Bedingungen ist die Existenz garantiert, z.B. wenn $\Omega$ nichtleer und kompakt (abgeschlossen und beschränkt) und $f$ stetig ist (Satz von Weierstraß).

Ergänzung: Ist $f$ sogar strikt konvex (Ungleichung strikt für $\mathbf x\neq\mathbf y$ und $0\lt\theta\lt 1$), ist das globale Minimum außerdem eindeutig. $\langle\mathbf w\cdot\mathbf w\rangle$ ist strikt konvex, deshalb ist das optimale $\mathbf w$ der SVM eindeutig.

Ist die SVM-Optimierung konvex?

📄 08_svm.pdf, Folie 27

Zur Erinnerung: minimiere $f(\mathbf w) = \langle\mathbf w\cdot\mathbf w\rangle$ unter $y_i(\langle\mathbf w\cdot\mathbf x_i\rangle + b)\ge 1$, $i = 1,\dots,\ell$.

Schritt für Schritt:

1. Die Zielfunktion $\mathbf w\mapsto\langle\mathbf w\cdot\mathbf w\rangle$ ist konvex (s.o.) und stetig.
2. Die Nebenbedingungen $y_i(\langle\mathbf w\cdot\mathbf x_i\rangle + b) - 1$ sind lineare Funktionen in $(\mathbf w, b)$ und damit ebenfalls konvex.
3. Der durch jede Nebenbedingung definierte zulässige Bereich ist daher eine konvexe Menge, hier ein Halbraum im Parameterraum.
4. Der gesamte zulässige Bereich ist eine Schnittmenge konvexer Mengen und damit selbst konvex.

Also: Die SVM ist ein konvexes Optimierungsproblem.

Fallstrick: In welchem Raum lebt der Halbraum?

Die Halbräume aus Schritt 3 liegen im Parameterraum der $(\mathbf w, b)$, nicht im Datenraum der $\mathbf x$! Jeder Trainingspunkt $\mathbf x_i$ schneidet einen Halbraum aus dem Raum aller möglichen Trennebenen heraus: die Menge der Ebenen, die $\mathbf x_i$ mit ausreichendem Abstand richtig klassifizieren.

Merkmale der SVM

📄 08_svm.pdf, Folie 28

• Der SVM-Algorithmus ist ein konvexes Optimierungsproblem, d.h. jedes lokale Minimum ist eine Lösung.
• Die Zielfunktion ist stetig, und (falls das Problem linear trennbar ist, der zulässige Bereich also nichtleer) ist die Existenz einer Lösung garantiert.
• Im Vergleich zu traditionelleren konnektionistischen Ansätzen (z.B. MLPs, also mehrschichtigen neuronalen Netzen) ist die Konvexität ein entscheidender Vorteil: Man bleibt bei der Optimierung nicht in lokalen Minima hängen und findet immer das globale Minimum („Off-the-shelf“-Algorithmus: funktioniert ohne viel Feintuning).
• Durch das Kriterium der maximalen Trennbreite ist die Wahrscheinlichkeit für Überanpassung gering, unabhängig von der Dimensionalität der Eingangsdaten. Die SVM ist daher auch auf hochdimensionale und (mit Kernen, Kapitel 7) nichtlineare Probleme anwendbar.

Anmerkung zur Existenzaussage

Die Folie begründet die Existenz damit, dass der zulässige Bereich „kompakt“ sei. Streng genommen ist der zulässige Bereich (ein Schnitt von Halbräumen) unbeschränkt und damit nicht kompakt: Man kann $\mathbf w$ beliebig groß machen und bleibt zulässig. Die Existenz folgt trotzdem: Wählt man einen zulässigen Punkt $\mathbf w_0$, so muss das Minimum in der Menge $\{\mathbf w \text{ zulässig} \mid \langle\mathbf w\cdot\mathbf w\rangle \le \langle\mathbf w_0\cdot\mathbf w_0\rangle\}$ liegen, und die ist beschränkt und abgeschlossen. (Für $b$ braucht man ein ähnliches Argument, solange beide Klassen vorkommen.) Für die Prüfung reicht: konvex, stetig, nichtleer zulässig ⇒ Lösung existiert und ist global.