Zum Hauptinhalt springen

6.2 Die optimale Trennebene

In 6.1 haben wir gesehen: In hohen Dimensionen gibt es viele trennende Ebenen, und die Wahl der „richtigen“ entscheidet über die Generalisierung. Der Supportvektoralgorithmus (support vector algorithm) wählt die Trennebene, die die Trennbreite für die gegebenen Trainingsdaten maximiert.

📄 08_svm.pdf, Folie 12

Die Abbildung zeigt das Problem: Zwei Punktwolken in der Ebene lassen sich durch unendlich viele Geraden trennen („…which one?“). Intuitiv wirkt die Gerade „in der Mitte der Lücke“ am vernünftigsten. Die SVM macht diese Intuition präzise.

Wiederholung: Trennebenen​

📄 08_svm.pdf, Folie 13

Eine Hyperebene (hyperplane) im Rd\mathbb R^d ist gegeben durch einen Normalenvektor w\mathbf w und einen Achsenabschnitt (Bias) bb:

H={x∣⟨w⋅x⟩+b=0}.H = \{\mathbf x \mid \langle\mathbf w\cdot\mathbf x\rangle + b = 0\}.
  • w\mathbf w steht senkrecht auf der Ebene und zeigt in den Halbraum mit ⟨w⋅x⟩+b>0\langle\mathbf w\cdot\mathbf x\rangle + b \gt 0 (positive Klasse).
  • Auf der anderen Seite ist ⟨w⋅x⟩+b<0\langle\mathbf w\cdot\mathbf x\rangle + b \lt 0 (negative Klasse).
  • Der lineare Klassifikator ist y^=sign⁡(⟨w⋅x⟩+b)\hat y = \operatorname{sign}(\langle\mathbf w\cdot\mathbf x\rangle + b).

Skalierungsinvarianz​

Für jedes c≠0c \neq 0 beschreiben

{x∣⟨w⋅x⟩+b=0}und{x∣⟨cw⋅x⟩+cb=0}\{\mathbf x \mid \langle\mathbf w\cdot\mathbf x\rangle + b = 0\} \quad\text{und}\quad \{\mathbf x \mid \langle c\mathbf w\cdot\mathbf x\rangle + cb = 0\}

dieselbe Ebene, denn man kann die Gleichung einfach durch cc teilen. Das Paar (w,b)(\mathbf w, b) ist also nur bis auf einen Faktor festgelegt. (Für c<0c\lt 0 vertauschen sich zusätzlich die Seiten, deshalb nimmt man in der Praxis c>0c\gt 0.)

Kanonische Form​

Um die Mehrdeutigkeit zu beseitigen, legt man den Skalierungsfaktor bezüglich der Trainingsmenge fest:

Kanonische Form (canonical hyperplane)

Wähle cc so, dass für die Trainingspunkte gilt:

min⁡xi∈S∣⟨w⋅xi⟩+b∣=1.\min_{\mathbf x_i \in S} \lvert\langle\mathbf w\cdot\mathbf x_i\rangle + b\rvert = 1.

In Worten: Der nächstgelegene Trainingspunkt hat den Funktionswert ±1\pm 1. Alle anderen Punkte haben betragsmäßig größere Werte. Das ist keine Einschränkung der möglichen Ebenen, sondern nur eine Konvention, welcher Vertreter (cw,cb)(c\mathbf w, cb) gewählt wird.

Geometrischer Abstand und Trennbreite​

📄 08_svm.pdf, Folie 14

Vorzeichenbehafteter Abstand​

Der vorzeichenbehaftete Abstand eines Punkts xi\mathbf x_i zur Hyperebene (geometric margin) ist

γi=⟨w⋅xi⟩+b∥w∥.\gamma_i = \frac{\langle\mathbf w\cdot\mathbf x_i\rangle + b}{\lVert\mathbf w\rVert}.

Warum gilt diese Formel? Herleitung (Ergänzung, auf der Folie nur angegeben): Sei xp\mathbf x_p der Fußpunkt des Lots von xi\mathbf x_i auf die Ebene. Dann ist xi=xp+γiw∥w∥\mathbf x_i = \mathbf x_p + \gamma_i \frac{\mathbf w}{\lVert\mathbf w\rVert}, denn man geht vom Fußpunkt entlang der Einheitsnormalen um den Abstand γi\gamma_i. Einsetzen:

⟨w⋅xi⟩+b=⟨w⋅xp⟩+b⏟=0, da xp∈H+γi⟨w⋅w⟩∥w∥=γi ∥w∥.\langle\mathbf w\cdot\mathbf x_i\rangle + b = \underbrace{\langle\mathbf w\cdot\mathbf x_p\rangle + b}_{=0,\ \text{da } \mathbf x_p \in H} + \gamma_i\frac{\langle\mathbf w\cdot\mathbf w\rangle}{\lVert\mathbf w\rVert} = \gamma_i\,\lVert\mathbf w\rVert.

Auflösen nach γi\gamma_i ergibt die Formel. Das Vorzeichen sagt, auf welcher Seite der Punkt liegt. Wichtig: γi\gamma_i ändert sich nicht, wenn man (w,b)(\mathbf w, b) mit c>0c \gt 0 skaliert, Zähler und Nenner wachsen beide um cc. Der geometrische Abstand ist eine echte Eigenschaft der Ebene, nicht der Parametrisierung.

Ergänzung: Multipliziert man mit dem Label, so ist yiγi>0y_i\gamma_i \gt 0 genau dann, wenn xi\mathbf x_i korrekt klassifiziert ist. yiγiy_i\gamma_i ist dann der (positive) Abstand zur Ebene.

Die Trennbreite (margin)​

Die Trennbreite einer Hyperebene (w,b)(\mathbf w, b) bezüglich einer Trainingsmenge SS ist

γ=min⁡i=1,…,ℓ∣⟨w⋅xi⟩+b∣∥w∥,\gamma = \min_{i = 1,\dots,\ell} \frac{\lvert\langle\mathbf w\cdot\mathbf x_i\rangle + b\rvert}{\lVert\mathbf w\rVert},

also der Abstand des zur Trennebene am nächsten liegenden Datenpunkts.

Trennbreite in kanonischer Form​

Ist die Ebene kanonisch, so ist der Zähler für die nächstgelegenen Punkte genau 1. Für diese Punkte gilt also:

γi=1∥w∥falls yi=1,γi=−1∥w∥falls yi=−1.\gamma_i = \frac{1}{\lVert\mathbf w\rVert} \quad\text{falls } y_i = 1, \qquad \gamma_i = -\frac{1}{\lVert\mathbf w\rVert} \quad\text{falls } y_i = -1.
Supportvektoren (support vectors)

Die nächstliegenden Datenpunkte heißen Supportvektoren (engl. to support: halten, unterstützen), da nur sie allein die Lage der optimalen Trennebene bestimmen.

Herleitung: Die Breite des freien Streifens ist 2/∥w∥2/\lVert\mathbf w\rVert​

📄 08_svm.pdf, Folie 15

Bei der optimalen Trennebene liegen auf beiden Seiten Supportvektoren. Wäre das nicht so, z.B. nur auf der positiven Seite, könnte man die Ebene ein Stück von diesen Punkten weg schieben und den Mindestabstand vergrößern, sie wäre also nicht optimal.

  • Die positiven Supportvektoren liegen auf der Ebene ⟨w⋅x⟩+b=+1\langle\mathbf w\cdot\mathbf x\rangle + b = +1, im Abstand 1/∥w∥1/\lVert\mathbf w\rVert von der Trennebene.
  • Die negativen Supportvektoren liegen auf der Ebene ⟨w⋅x⟩+b=−1\langle\mathbf w\cdot\mathbf x\rangle + b = -1, im Abstand 1/∥w∥1/\lVert\mathbf w\rVert auf der anderen Seite.
  • Dazwischen liegt kein einziger Datenpunkt, denn in kanonischer Form gilt für alle Punkte ∣f(xi)∣≥1\lvert f(\mathbf x_i)\rvert \ge 1.

Also gibt es um die Trennebene einen Freiraum der Breite

1∥w∥+1∥w∥=2∥w∥.\frac{1}{\lVert\mathbf w\rVert} + \frac{1}{\lVert\mathbf w\rVert} = \frac{2}{\lVert\mathbf w\rVert}.

Ergänzung, alternative Herleitung: Seien x+\mathbf x_+ und x−\mathbf x_- Punkte auf den beiden Randebenen. Subtrahiert man ⟨w⋅x+⟩+b=1\langle\mathbf w\cdot\mathbf x_+\rangle + b = 1 und ⟨w⋅x−⟩+b=−1\langle\mathbf w\cdot\mathbf x_-\rangle + b = -1, erhält man ⟨w⋅(x+−x−)⟩=2\langle\mathbf w\cdot(\mathbf x_+ - \mathbf x_-)\rangle = 2. Projiziert man x+−x−\mathbf x_+ - \mathbf x_- auf die Einheitsnormale w/∥w∥\mathbf w/\lVert\mathbf w\rVert, ergibt sich die Streifenbreite 2/∥w∥2/\lVert\mathbf w\rVert.

Fallstrick: Trennbreite γ\gamma vs. Streifenbreite

Die Folien nennen γ=1/∥w∥\gamma = 1/\lVert\mathbf w\rVert (Abstand der nächsten Punkte zur Ebene) die Trennbreite und 2/∥w∥2/\lVert\mathbf w\rVert die Breite des Freiraums. In der Literatur wird manchmal auch 2/∥w∥2/\lVert\mathbf w\rVert „Margin“ genannt. Für die Optimierung ist das egal, der Faktor 2 ändert das Optimum nicht. In der Prüfung sauber sagen, welche Größe gemeint ist.

Vom geometrischen Ziel zum Optimierungsproblem​

Um die optimale Trennebene zu finden, muss 2∥w∥\frac{2}{\lVert\mathbf w\rVert} möglichst groß werden, also

∥w∥=w12+w22+⋯+wd2=⟨w⋅w⟩\lVert\mathbf w\rVert = \sqrt{w_1^2 + w_2^2 + \dots + w_d^2} = \sqrt{\langle\mathbf w\cdot\mathbf w\rangle}

möglichst klein. Zwei Vereinfachungen:

  1. Die Wurzel weglassen: Da ⋅\sqrt{\cdot} monoton steigend ist, hat ⟨w⋅w⟩\langle\mathbf w\cdot\mathbf w\rangle dieselbe Minimalstelle wie ∥w∥\lVert\mathbf w\rVert. ⟨w⋅w⟩\langle\mathbf w\cdot\mathbf w\rangle ist mathematisch einfacher: eine glatte quadratische Funktion, überall differenzierbar (die Wurzel ist bei w=0\mathbf w = 0 nicht differenzierbar).
  2. Die Trennung als Nebenbedingung: Gleichzeitig muss sichergestellt sein, dass die Trainingsmenge korrekt getrennt wird, und zwar in kanonischer Form, also mit ∣f(xi)∣≥1\lvert f(\mathbf x_i)\rvert \ge 1. Das wird als Nebenbedingung (constraint) der Minimierung formuliert.

Warum braucht man die Nebenbedingung überhaupt? Ohne sie wäre w=0\mathbf w = 0 trivialerweise optimal. Erst die Forderung yif(xi)≥1y_i f(\mathbf x_i) \ge 1 verhindert, dass w\mathbf w beliebig klein wird: Sie fixiert die Skalierung (kanonische Form) und erzwingt korrekte Klassifikation.

Der Supportvektoralgorithmus als Optimierungsproblem​

📄 08_svm.pdf, Folie 16
SVM-Optimierung (Hard Margin, primales Problem)

Für einen gegebenen Trainingsdatensatz S={(x1,y1),…,(xℓ,yℓ)}⊆(X×Y)ℓS = \{(\mathbf x_1,y_1),\dots,(\mathbf x_\ell,y_\ell)\} \subseteq (X\times Y)^\ell:

  • minimiere f(w)=⟨w⋅w⟩,w∈Rd\quad f(\mathbf w) = \langle\mathbf w\cdot\mathbf w\rangle,\quad \mathbf w\in\mathbb R^d
  • unter ℓ\ell Nebenbedingungen, i=1,…,ℓi = 1,\dots,\ell:
⟨w⋅xi⟩+b≥1fu¨r yi=1⟨w⋅xi⟩+b≤−1fu¨r yi=−1\begin{aligned} \langle\mathbf w\cdot\mathbf x_i\rangle + b &\ge 1 &&\text{für } y_i = 1\\ \langle\mathbf w\cdot\mathbf x_i\rangle + b &\le -1 &&\text{für } y_i = -1 \end{aligned}

oder kürzer

yi(⟨w⋅xi⟩+b)≥1.y_i\left(\langle\mathbf w\cdot\mathbf x_i\rangle + b\right) \ge 1.

Der Trick mit dem Label: Für yi=+1y_i = +1 ist die Kurzform direkt die erste Zeile. Für yi=−1y_i = -1 multipliziert man ⟨w⋅xi⟩+b≤−1\langle\mathbf w\cdot\mathbf x_i\rangle + b \le -1 mit −1-1, dabei dreht sich das Ungleichheitszeichen um: −(⟨w⋅xi⟩+b)≥1-(\langle\mathbf w\cdot\mathbf x_i\rangle + b) \ge 1, also wieder yi(… )≥1y_i(\dots)\ge 1.

Es handelt sich um ein quadratisches Optimierungsproblem (quadratic program, QP) mit linearen Ungleichheitsbedingungen: Die Zielfunktion ist quadratisch in w\mathbf w, die Nebenbedingungen sind linear in (w,b)(\mathbf w, b).

Bemerkungen:

  • Optimiert wird über w\mathbf w und bb, obwohl bb in der Zielfunktion nicht vorkommt. bb taucht nur in den Nebenbedingungen auf.
  • Ergänzung: In Lehrbüchern steht oft 12⟨w⋅w⟩\tfrac12\langle\mathbf w\cdot\mathbf w\rangle. Der Faktor 12\tfrac12 ändert das Optimum nicht, er macht nur die Ableitung schöner (∇12∥w∥2=w\nabla \tfrac12\lVert\mathbf w\rVert^2 = \mathbf w). In der Soft Margin Version (6.5) verwenden auch die Folien 12\tfrac12.
  • Die Nebenbedingung ist nur erfüllbar, wenn die Daten linear trennbar sind. Sonst ist der zulässige Bereich leer, siehe 6.5.

Zahlenbeispiele​

Ergänzung, nicht auf den Folien.

Beispiel 1: Zwei Punkte​

Gegeben: x1=(0,0)\mathbf x_1 = (0,0) mit y1=−1y_1 = -1 und x2=(2,2)\mathbf x_2 = (2,2) mit y2=+1y_2 = +1.

Intuition: Die optimale Trennebene ist die Mittelsenkrechte der Verbindungsstrecke. w\mathbf w zeigt also in Richtung (1,1)(1,1), d.h. w=(a,a)\mathbf w = (a,a) mit a>0a\gt 0. Beide Punkte sind Supportvektoren, die Nebenbedingungen gelten mit Gleichheit:

y1f(x1)=−(0+b)=1⇒ b=−1,y2f(x2)=2a+2a+b=1⇒ 4a=2 ⇒ a=12.\begin{aligned} y_1 f(\mathbf x_1) = -(0 + b) &= 1 &&\Rightarrow\ b = -1,\\ y_2 f(\mathbf x_2) = 2a + 2a + b &= 1 &&\Rightarrow\ 4a = 2 \ \Rightarrow\ a = \tfrac12. \end{aligned}

Ergebnis: w=(12,12)\mathbf w = (\tfrac12,\tfrac12), b=−1b = -1, Trennebene 12x1+12x2−1=0\tfrac12 x_1 + \tfrac12 x_2 - 1 = 0, also x1+x2=2x_1 + x_2 = 2.

Margin: ∥w∥=14+14=12\lVert\mathbf w\rVert = \sqrt{\tfrac14 + \tfrac14} = \tfrac{1}{\sqrt 2}, also

2∥w∥=22≈2,83.\frac{2}{\lVert\mathbf w\rVert} = 2\sqrt 2 \approx 2{,}83.

Probe: Der Abstand der beiden Punkte ist ∥(2,2)∥=8=22\lVert(2,2)\rVert = \sqrt 8 = 2\sqrt 2. Bei zwei Punkten ist der freie Streifen genau die Verbindungsstrecke. ✔

Beispiel 2: Ein dritter Punkt, der keine Rolle spielt​

Füge x3=(4,4)\mathbf x_3 = (4,4) mit y3=+1y_3 = +1 hinzu. Mit der Lösung aus Beispiel 1:

y3f(x3)=12⋅4+12⋅4−1=3≥1.y_3 f(\mathbf x_3) = \tfrac12\cdot 4 + \tfrac12 \cdot 4 - 1 = 3 \ge 1.

Die Nebenbedingung ist erfüllt, und zwar strikt (inaktiv, siehe 6.3). Der Punkt liegt außerhalb des Margins, ist kein Supportvektor, und die Lösung ändert sich nicht. Genau das meinen die Folien mit „nur die Supportvektoren bestimmen die Trennebene“.

Beispiel 3: Drei Supportvektoren​

Jetzt x1=(0,0)\mathbf x_1 = (0,0), y1=−1y_1=-1; x2=(2,2)\mathbf x_2 = (2,2), y2=+1y_2=+1; x3=(3,0)\mathbf x_3 = (3,0), y3=+1y_3=+1.

Versuch 1: Lösung aus Beispiel 1 übernehmen. Dann ist y3f(x3)=32−1=12<1y_3 f(\mathbf x_3) = \tfrac32 - 1 = \tfrac12 \lt 1, Nebenbedingung verletzt. Der neue Punkt liegt im Margin.

Versuch 2: Nur x1,x3\mathbf x_1, \mathbf x_3 als Supportvektoren, w=(a,0)\mathbf w = (a, 0): b=−1b = -1, 3a−1=13a - 1 = 1, a=23a = \tfrac23. Dann ist y2f(x2)=43−1=13<1y_2 f(\mathbf x_2) = \tfrac43 - 1 = \tfrac13 \lt 1, wieder verletzt.

Versuch 3: Alle drei Punkte sind Supportvektoren, alle drei Gleichungen gelten mit Gleichheit:

−(0⋅w1+0⋅w2+b)=1⇒ b=−12w1+2w2−1=1⇒ w1+w2=13w1−1=1⇒ w1=23, w2=13\begin{aligned} -(0\cdot w_1 + 0\cdot w_2 + b) &= 1 &&\Rightarrow\ b = -1\\ 2w_1 + 2w_2 - 1 &= 1 &&\Rightarrow\ w_1 + w_2 = 1\\ 3w_1 - 1 &= 1 &&\Rightarrow\ w_1 = \tfrac23,\ w_2 = \tfrac13 \end{aligned}

Margin: ∥w∥2=49+19=59\lVert\mathbf w\rVert^2 = \tfrac49 + \tfrac19 = \tfrac59, also ∥w∥=53\lVert\mathbf w\rVert = \tfrac{\sqrt 5}{3} und

2∥w∥=65≈2,68.\frac{2}{\lVert\mathbf w\rVert} = \frac{6}{\sqrt 5} \approx 2{,}68.

Der Margin ist kleiner als in Beispiel 1 (2,832{,}83). Das muss so sein: Eine zusätzliche Nebenbedingung kann den zulässigen Bereich nur verkleinern, das Optimum also nur verschlechtern oder gleich lassen. Dass Versuch 3 tatsächlich das Optimum ist (und nicht nur zulässig), lässt sich mit den KKT-Bedingungen nachprüfen, siehe 6.4.

Kurz in scikit-learn​

Ergänzung: Eine Hard Margin SVM erhält man in scikit-learn näherungsweise mit einem sehr großen CC (siehe 6.5):

import numpy as np
from sklearn.svm import SVC

X = np.array([[0, 0], [2, 2], [3, 0]])
y = np.array([-1, 1, 1])

clf = SVC(kernel="linear", C=1e6).fit(X, y)
print(clf.coef_, clf.intercept_)   # ≈ [[0.667 0.333]] [-1.]
print(clf.support_)                # Indizes der Supportvektoren: [0 1 2]

Typische Fallstricke​

  • Funktionswert ist nicht Abstand. f(xi)=⟨w⋅xi⟩+bf(\mathbf x_i) = \langle\mathbf w\cdot\mathbf x_i\rangle + b hängt von der Skalierung von w\mathbf w ab, erst nach Division durch ∥w∥\lVert\mathbf w\rVert erhält man den geometrischen Abstand. Deshalb braucht man die kanonische Form, um „Abstand maximieren“ als „∥w∥\lVert\mathbf w\rVert minimieren“ schreiben zu können.
  • Supportvektoren sind keine Vektoren im Sinne von Richtungen, sondern einfach ausgewählte Trainingspunkte.
  • „Es gibt genau zwei Supportvektoren.“ Falsch. Es gibt mindestens einen pro Klasse, aber es können beliebig viele sein (Beispiel 3: drei). Im Rd\mathbb R^d sind es typischerweise höchstens d+1d+1, wenn die Punkte in allgemeiner Lage sind.
  • bb nicht vergessen. bb ist eine Optimierungsvariable, auch wenn es in der Zielfunktion fehlt.