7.2 Duale Darstellung

Bevor man den Kernel-Trick anwenden kann, muss die Lernmaschine so umgeschrieben werden, dass die Daten nur noch in Skalarprodukten vorkommen. Das leistet die duale Darstellung (dual representation): Statt den Gewichtsvektor $\mathbf{w}$ direkt zu lernen, lernt man für jeden Trainingspunkt einen Koeffizienten $\alpha_i$.

Wiederholung: duale Repräsentation beim Perzeptron

📄 10_kern.pdf, Folie 9

Der Perzeptron-Algorithmus addiert fehlklassifizierte positive Beispiele zum Gewichtsvektor und subtrahiert fehlklassifizierte negative Beispiele. Kompakt: Bei einem Fehler auf $(\mathbf{x}_i, y_i)$ mit $y_i\in\lbrace -1, +1\rbrace$ wird

$$\mathbf{w} \leftarrow \mathbf{w} + y_i\,\mathbf{x}_i .$$

Startet man mit $\mathbf{w} = 0$, so ist der resultierende Gewichtsvektor eine Linearkombination der Trainingsdaten:

$$\mathbf{w} = \sum_{i=1}^{\ell} \alpha_i\, y_i\, \mathbf{x}_i .$$

• Die nichtnegativen Koeffizienten $\alpha_i$ heißen Einbettungsstärken (embedding strengths). Beim Perzeptron ist $\alpha_i$ genau die Anzahl der Fehlklassifikationen, die Beispiel $\mathbf{x}_i$ während des Trainings verursacht hat.
• Damit ist $\alpha_i$ eine Art Maß für die Schwierigkeit oder den Informationsgehalt des Datenpunktes: Punkte, die leicht richtig klassifiziert werden, haben $\alpha_i = 0$ und tragen nichts zu $\mathbf{w}$ bei. Punkte nahe der Grenze werden oft „korrigiert“ und bekommen große $\alpha_i$.
• Für einen festen Datensatz $S$ kann man den Vektor $\boldsymbol{\alpha} = (\alpha_1, \alpha_2, \dots)^\top$ als alternative Repräsentation des Gewichtsvektors ansehen, die duale Repräsentation. Die übliche Darstellung über $\mathbf{w}$ heißt primal.

Kleines Beispiel (Ergänzung): Drei Trainingspunkte, das Perzeptron hat sich während des Trainings bei $\mathbf{x}_1$ (Klasse $+1$) zweimal und bei $\mathbf{x}_3$ (Klasse $-1$) einmal geirrt, bei $\mathbf{x}_2$ nie. Dann ist $\boldsymbol\alpha = (2, 0, 1)^\top$ und

$$\mathbf{w} = 2\cdot(+1)\,\mathbf{x}_1 + 0\cdot\mathbf{x}_2 + 1\cdot(-1)\,\mathbf{x}_3 = 2\mathbf{x}_1 - \mathbf{x}_3 .$$

Kombination von Merkmalen und linearen Lernmaschinen

📄 10_kern.pdf, Folie 10

Nun kombiniert man das mit der Merkmalsbildung aus 7.1. In der primalen Form ersetzt man einfach $\mathbf{x}$ durch $\Phi(\mathbf{x})$:

$$f(\mathbf{x}) = \langle\mathbf{w}\cdot\mathbf{x}\rangle + b,\ \ \mathbf{x},\mathbf{w}\in\mathbb{R}^d \quad\longrightarrow\quad f(\mathbf{x}) = \langle\mathbf{w}\cdot\Phi(\mathbf{x})\rangle + b,\ \ \mathbf{x}\in\mathbb{R}^d,\ \mathbf{w}\in\mathbb{R}^m .$$

Problem: $\mathbf{w}$ lebt jetzt im Merkmalsraum und hat $m$ Komponenten. Ist $m$ riesig oder unendlich, kann man $\mathbf{w}$ nicht mehr speichern.

Das Repräsentertheorem

Aufgrund des Repräsentertheorems (representer theorem) sind die Gewichtsvektoren für eine große Gruppe von Optimierungsproblemen Linearkombinationen der Trainingsdaten, sofern sie sich als Lösung eines solchen Problems ergeben (z. B. Perzeptron, SVM, regularisierte Kleinste-Quadrate-Regression):

$$\mathbf{w} = \sum_{i=1}^{\ell} \alpha_i y_i \mathbf{x}_i \qquad\text{bzw.}\qquad \mathbf{w} = X^\top\boldsymbol{\alpha} \quad\text{mit}\quad X = \begin{pmatrix} y_1\mathbf{x}_1^\top\\ y_2\mathbf{x}_2^\top\\ \vdots\end{pmatrix},\ \boldsymbol\alpha = \begin{pmatrix}\alpha_1\\ \alpha_2\\ \vdots\end{pmatrix}.$$

Im Merkmalsraum entsprechend $\mathbf{w} = \sum_i \alpha_i y_i \Phi(\mathbf{x}_i)$. Die Gewichte $\alpha_i$ werden je nach Lernalgorithmus und Aufgabenstellung gewählt (beim Perzeptron Fehlerzähler, bei der SVM Lagrange-Multiplikatoren).

Ergänzung, nicht auf den Folien – Intuition: Ein Anteil von $\mathbf{w}$, der senkrecht auf allen Trainingspunkten steht, ändert keine einzige Vorhersage $\langle\mathbf{w}\cdot\mathbf{x}_i\rangle$ auf den Trainingsdaten, macht aber $\lVert\mathbf{w}\rVert$ größer. Bei einem Verfahren, das $\lVert\mathbf{w}\rVert$ klein halten will (Regularisierung, Margin-Maximierung), lohnt sich so ein Anteil nie. Also liegt das optimale $\mathbf{w}$ im Aufspann der Trainingspunkte.

Die duale Form

Setzt man $\mathbf{w} = \sum_i \alpha_i y_i \mathbf{x}_i$ in $f$ ein, bekommt man die duale Form (die Anzahl der Gewichte bleibt gleich: $\ell$ Stück, eines pro Trainingspunkt):

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

Herleitung in einem Schritt, nur mit Bilinearität des Skalarprodukts:

$$\langle\mathbf{w}\cdot\mathbf{x}\rangle = \Big\langle \sum_i \alpha_i y_i\mathbf{x}_i \cdot \mathbf{x}\Big\rangle = \sum_i \alpha_i y_i \langle\mathbf{x}_i\cdot\mathbf{x}\rangle .$$

Primal vs. dual

	primal	dual
Parameter	$\mathbf{w}\in\mathbb{R}^m$ (Dimension des Merkmalsraums)	$\boldsymbol\alpha\in\mathbb{R}^\ell$ (Anzahl Trainingspunkte)
Daten kommen vor als	$\Phi(\mathbf{x})$ explizit	nur in Skalarprodukten $\langle\Phi(\mathbf{x}_i)\cdot\Phi(\mathbf{x})\rangle$
günstig, wenn	$m$ klein, $\ell$ groß	$m$ groß oder unendlich, $\ell$ moderat

Ergänzung: Dieselbe Idee kam schon bei der kernalisierten linearen Regression in Kapitel 4 vor. Auch dort lässt sich die Lösung als $\mathbf{w} = X^\top\boldsymbol\alpha$ schreiben, und die Vorhersage braucht nur Skalarprodukte zwischen Datenpunkten.

Skalarprodukt als Ähnlichkeitsmaß

📄 10_kern.pdf, Folie 11

Warum ist das Skalarprodukt eine natürliche Größe? Beispiel Gesichtserkennung: Man sucht ein Gesicht, indem man eine Schablone (template) $y_i$ über das Bild schiebt und für jedes Suchfenster mit Pixeln $x_i$ die Korrelation

$$\sum_{i=1}^{d} y_i x_i$$

berechnet. Das kanonische Skalarprodukt zweier Muster ist also ihre Korrelation: Es ist groß, wenn die Muster ähnlich aussehen.

Damit bekommt die duale Form eine anschauliche Interpretation:

$$f(\mathbf{x}) = \sum_{i=1}^{\ell}\alpha_i y_i\, \underbrace{\langle\Phi(\mathbf{x}_i)\cdot\Phi(\mathbf{x})\rangle}_{\text{Ähnlichkeit zu } \mathbf{x}_i} + b .$$

Die Maschine vergleicht den Input mit allen Trainingsbeispielen. Jedes Trainingsbeispiel „stimmt ab“ für seine Klasse $y_i$, gewichtet mit seiner Wichtigkeit $\alpha_i$ und seiner Ähnlichkeit zum Input. (Ergänzung: Das erinnert an einen gewichteten Nächste-Nachbarn-Klassifikator, nur dass die Gewichte gelernt werden und meist nur wenige $\alpha_i$ ungleich null sind.)

Anwendung auf die SVM

📄 10_kern.pdf, Folie 12

Das Repräsentertheorem gilt auch für die SVM: Der Gewichtsvektor einer trainierten SVM hat die Form $\mathbf{w} = \sum_{i=1}^{\ell}\alpha_i y_i\mathbf{x}_i$. Setzt man das in die Soft-Margin-Zielfunktion $\tfrac12\langle\mathbf{w}\cdot\mathbf{w}\rangle + C\sum_i\xi_i$ ein (siehe Kapitel 6), so wird

$$\langle\mathbf{w}\cdot\mathbf{w}\rangle = \Big\langle \sum_i\alpha_i y_i\mathbf{x}_i \cdot \sum_j \alpha_j y_j \mathbf{x}_j\Big\rangle = \sum_{i,j=1}^{\ell} y_i y_j \alpha_i\alpha_j \langle\mathbf{x}_i\cdot\mathbf{x}_j\rangle .$$

Zusammen mit der dualen Entscheidungsfunktion $f(\mathbf{x}) = \sum_i \alpha_i y_i \langle\mathbf{x}_i\cdot\mathbf{x}\rangle + b$ erhält man ein Problem, das nur von Skalarprodukten abhängt:

SVM-Optimierung in dualen Variablen (Folie 12)

Minimiere

$$f(\boldsymbol\alpha) = \frac12\sum_{i,j=1}^{\ell} y_i y_j\alpha_i\alpha_j\langle\mathbf{x}_i\cdot\mathbf{x}_j\rangle + C\sum_{i=1}^{\ell}\xi_i,\qquad \boldsymbol\alpha\in\mathbb{R}^\ell,$$

unter den $\ell$ Nebenbedingungen ($i = 1,\dots,\ell$)

$$\sum_{j=1}^{\ell}\alpha_j y_j\langle\mathbf{x}_j\cdot\mathbf{x}_i\rangle + b \ \ge\ 1 - \xi_i .$$

Die Nebenbedingung ist die bekannte Soft-Margin-Bedingung $y_i f(\mathbf{x}_i) \ge 1-\xi_i$, nur mit eingesetztem $\mathbf{w}$. (Auf der Folie fehlt der Faktor $y_i$ vor der linken Seite; gemeint ist $y_i\big(\sum_j \alpha_j y_j\langle\mathbf{x}_j\cdot\mathbf{x}_i\rangle + b\big)\ge 1-\xi_i$, sowie $\xi_i\ge 0$.)

Ergänzung, nicht auf den Folien – Bezug zum Lagrange-Dual aus Kapitel 6: Die Folie setzt die Darstellung $\mathbf{w}=\sum\alpha_i y_i\mathbf{x}_i$ direkt ins primale Problem ein. Das in Kapitel 6 hergeleitete Lagrange-duale Problem der Soft-Margin-SVM hat dieselbe entscheidende Eigenschaft und wird in der Praxis (z. B. von libsvm/scikit-learn) gelöst:

$$\max_{\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 \quad\text{u. d. N.}\quad 0\le\alpha_i\le C,\ \ \sum_{i=1}^{\ell}\alpha_i y_i = 0 .$$

Auch hier kommen die Daten nur über Skalarprodukte $\langle\mathbf{x}_i\cdot\mathbf{x}_j\rangle$ vor. Nur darauf kommt es für den Kernel-Trick an.

Pegasos für die duale Repräsentation

📄 10_kern.pdf, Folie 13

Pegasos (der stochastische Subgradienten-Löser für die SVM aus Kapitel 6) lässt sich ebenfalls dual formulieren.

• Ähnlich wie das Perzeptron ist Pegasos ein Fehlerkorrekturverfahren: Ein Beispiel $\mathbf{x}_i$ wird nur dann auf den Gewichtsvektor addiert, wenn es die Fehlerbedingung $y_i f(\mathbf{x}_i) \lt 1$ verletzt, also innerhalb des Margins liegt oder falsch klassifiziert ist. In dualen Variablen: $y_i\, C\eta_t\sum_{j}\alpha_j y_j\langle\mathbf{x}_j\cdot\mathbf{x}_i\rangle \lt 1$.
• Daraus ergibt sich eine einfache Updateregel: Bei jedem Beispiel, das die Bedingung verletzt, wird die duale Variable um 1 hochgezählt. Die Schrumpfung durch die Regularisierung und die Lernrate stecken nicht in den $\alpha_i$, sondern werden am Ende pauschal durch den Faktor $C\cdot\eta_t$ berücksichtigt.

Pegasos dual (Folie 13)

$$\alpha_{i,t+1} = \begin{cases} \alpha_{i,t} + 1 & \text{falls } y_i f(\mathbf{x}_i) \lt 1\\ \alpha_{i,t} & \text{sonst} \end{cases} \qquad\text{mit}\quad f(\mathbf{x}_i) = C\eta_t\sum_{j=1}^{\ell}\alpha_j y_j\langle\mathbf{x}_j\cdot\mathbf{x}_i\rangle .$$

Ergänzung – warum genügt ein Zähler? Im primalen Pegasos wird $\mathbf{w}$ in jedem Schritt mit einem Faktor geschrumpft und bei Verletzung um ein Vielfaches von $y_i\mathbf{x}_i$ erhöht. Bei der Lernrate $\eta_t \propto 1/t$ heben sich diese Faktoren so auf, dass jeder Verletzungs-Schritt am Ende gleich stark in $\mathbf{w}_t$ eingeht und nur ein gemeinsamer, von $t$ abhängiger Vorfaktor übrig bleibt. Darum reicht es, pro Beispiel mitzuzählen, wie oft es die Bedingung verletzt hat, genau wie beim Perzeptron. Die genaue Konstante hängt von der Parametrisierung (mit $C$ oder $\lambda$) aus Kapitel 6 ab.

Kernaussage dieses Abschnitts

Perzeptron, SVM und Pegasos lassen sich alle so umschreiben, dass die Daten ausschließlich in Skalarprodukten auftauchen, beim Training $\langle\mathbf{x}_i\cdot\mathbf{x}_j\rangle$ und bei der Vorhersage $\langle\mathbf{x}_i\cdot\mathbf{x}\rangle$. Das ist die Eintrittskarte für den Kernel-Trick.