Mit den richtigen Features $\phi(x)$ kann ein linearer Classifier auch nichtlineare Vorhersagen machen.

Wie finden wir ein gutes mapping $\phi$? Was machen wir wenn $\phi(x)$ sehr viele Dimensionen hat.

https://commons.wikimedia.org/wiki/File:Kernel_trick_idea.svg

Annahme (vorerst): Alle unsere Daten lassen sich linear trennen.

Wir wollen möglichst viel Abstand von der Decision Boundary

Wir verwenden hier eine andere Notation:

\[ y \in \{{\color{red}-1}, 1\} \]

\[ h_{w,{\color{red}b}}(x) = g(w \cdot x{\color{red} + b})\\[3mm] g(z) = \begin{cases} 1 & \text{if } z \geq 0 \\ {\color{red} -1} & \text{else} \end{cases} \]

Großer Abstand zur Decision Boundary:

• Wenn $y=1$, wollen wir $w \cdot x + b \gg 0$
• Wenn $y=-1$, wollen wir $w \cdot x + b \ll 0$

Definiere $\hat \gamma(x,y) = y (w \cdot x + b)$
(functional margin)

Wollen $\hat \gamma(x,y) = y (w \cdot x + b) \gg 0$

Function margin der Trainingsdaten ist:

\[ \hat \gamma = \min_{(x,y) \in \mathcal{D}_\text{train}} \hat\gamma(x,y) \]

(worst case)

Die functional margin kann man leicht austricksen:

\[ w \gets 2 w \qquad b \gets 2 b \\[3mm] \Rightarrow y(w \cdot x + b) \text{ verdoppelt sich} \]

Lösung: Wir suchen den echten (euklidischen) Abstand von der Decision Boundary (in Einheitsgrößen)

Geometric margin: \[ \gamma(x,y) = \frac{\hat\gamma(x,y)}{||w||} = \frac{y (w \cdot x + b)}{||w||} \]

Die geometric margin auf den Trainingsdaten ist analog: \[ \gamma = \min_{(x,y) \in \mathcal{D}_\text{train}} \gamma(x,y) \] (kleinster Abstand)

Ein "optimal margin classifier" findet $w$ und $b$ mit maximalem $\gamma$

\[ \begin{align*} \max_{\gamma, w, b} \quad & \gamma \\ \text{s.t.}\quad & \frac{y(w \cdot x + b)}{||w||} \geq \gamma & \forall (x,y) \in \mathcal{D}_\text{train} \end{align*} \]

Das ist ein nicht konvexes Problem und schwer direkt zu lösen.

Äquivalente Formulierung:

\[ \begin{align*} \min_{w,b} \quad & \frac{1}{2} ||w||^2 \\ \text{s.t.} \quad & y(w \cdot x + b) \geq 1 & \forall (x,y) \in \mathcal{D}_\text{train} \end{align*} \]

Diese Formulierung ist konvex und kann effizient gelöst werden.

Kernels

Wir starten mit einem Feature Mapping $\phi(x)$.

$k(x, z) = \phi(x) \cdot \phi(z)$ nennen wir Kernel.

Kernel Trick

• Schreibe Algorithmus, der niemals Feature $x$ direkt verwendet, sondern alles als Skalarprodukt $x \cdot x'$ ausdrückt
• Wähle ein Feature Mapping $\phi(x)$, dass $x$ in einen nützlichen hochdimensionalen Feature Space abbildet
• Finde einen effizienten weg um den Kernel $k$ von $\phi$ zu berechnen.
• Ersetze im Algorithmus $x \cdot x'$ durch $k(x, x')$

Beispiel

\[ x = \left[ {\begin{array}{c} x^{(1)} \\ x^{(2)} \\ x^{(3)} \end{array}} \right] \qquad \phi(x) = \left[ {\begin{array}{c} x^{(1)} x^{(1)} \\ x^{(1)} x^{(2)} \\ x^{(1)} x^{(3)} \\ x^{(2)} x^{(1)} \\ x^{(2)} x^{(2)} \\ x^{(2)} x^{(3)} \\ x^{(3)} x^{(1)} \\ x^{(3)} x^{(2)} \\ x^{(3)} x^{(3)} \end{array}} \right] \]

Wenn $x \in \mathbb{R}^n$, dann ist $\phi(x) \in \mathbb{R}^{n^2}$

Bei $n = 10000$ wären das $100$ Millionen Features

Brauchen $O(n^2)$ Zeit um $\phi(x)$ oder $\phi(x) \cdot \phi(z)$ direkt zu berechnen

$k(x, z) = (x \cdot z)^2$ können wir in $O(n)$ Zeit ausrechnen.
Implizit berechnen wir aber $\phi(x) \cdot \phi(z)$.

Funktioniert auch mit $k(x, z) = (x \cdot z + c)^d$

Dann hat $\phi(x)$ alle Kombinations-Produkte bis zur Ordnung $d$.

Der Hyperparameter $c$ bestimmt wie groß der Einfluss von Termen hoher vs niedriger Ordnung ist.

Visualisierung Quadratischer Kernel

In einem höherdimensionalem Raum können wir eine bessere decision boundary finden, die im Original Raum nicht linear ist.

Radial basis function (RBF) Kernel

\[ k(x, z) = e^{-\frac{||x - z||^2}{2 \sigma^2}} \]

Das passende $\phi(x)$ enthält jede Kombination an Produkten der Features mit allen (!!!) möglichen Exponenten.

$\phi(x) \in \mathbb{R}^\infty$

Problem: $w$ muss genauso viele Dimensionen wie $\phi(x)$ haben.

Um den Kernel Trick zu verwenden müssen wir $w$ loswerden.

Representer Theorem

Wir können unser optimales $w$ als lineare Kombination unserer Trainingsdaten darstellen.

\[ w = \sum_{(x,y) \in \mathcal{D}_\text{train}} \alpha_{(x,y)} \cdot y \cdot x \\[3mm] \alpha \geq 0 \]

Intuition 1:

Unser SGD Update Schritt bei GLMs sah immer so aus: \[ w \gets w - \nu (h_w(x)-y) x \]

Nach jedem Schritt bleibt $w$ eine lineare Kombination der x

Intuition 2:

Wenn wir nur 2 Punkte haben ist die Normale auf der Verbindung von diesen:

Bei 3 Punkten ist die Normale auf einer Verbindung zwischen $\color{red}x$ und einem Punkt zwischen $\color{blue} o_1$ und $\color{blue} o_2$:

Beobachtung: Nur Punkte auf der Margin sind für die Bestimmung des Classifiers relevant

In \[ w = \sum_{(x,y) \in \mathcal{D}_\text{train}} \alpha_{(x,y)} \cdot y \cdot x \\[3mm] \alpha \geq 0 \] können potentiell viele $\alpha_{(x,y)} = 0$ sein.

Die $(x,y,\alpha_{(x,y)})$ mit $\alpha_{(x,y)} > 0$ müssen wir speichern um unser $w$ so darzustellen.

Das sind die "Support Vektoren"

Nächster Schritt: Unser Optimierungsproblem auf Kernels umstellen:

\[ \begin{align*} \min_{w,b} \quad & \frac{1}{2} ||w||^2 \\ \text{s.t.} \quad & y(w \cdot x + b) \geq 1 & \forall (x,y) \in \mathcal{D}_\text{train} \end{align*} \]

\[ \frac{1}{2} ||w||^2 = \frac{1}{2} w \cdot w \]

\[ = \frac{1}{2} (\sum_{(x,y) \in \mathcal{D}_\text{train}} \alpha_{(x,y)} y x) \cdot (\sum_{(x',y') \in \mathcal{D}_\text{train}} \alpha_{(x',y')} y' x') \]

\[ = \frac{1}{2} \sum_{(x,y) \in \mathcal{D}_\text{train}} \sum_{(x',y') \in \mathcal{D}_\text{train}} \alpha_{(x,y)} \alpha_{(x',y')} y y' {\color{red} x \cdot x'} \]

\[ y (w \cdot x + b) \geq 1 \]

\[ \Rightarrow y ( (\sum_{(x',y') \in \mathcal{D}_\text{train}} \alpha_{(x',y')} y' x') \cdot x + b) \geq 1 \]

\[ \Rightarrow y ((\sum_{(x',y') \in \mathcal{D}_\text{train}} \alpha_{(x', y')} y' {\color{red} x' \cdot x}) + b) \geq 1 \]

\[ \begin{align*} \min_{\alpha,b} \quad & \frac{1}{2} \sum_{(x,y) \in \mathcal{D}_\text{train}} \sum_{(x',y') \in \mathcal{D}_\text{train}} \alpha_{(x,y)} \alpha_{(x',y')} y y' {\color{red} x \cdot x'} \\ \text{s.t.} \quad & y ((\sum_{(x',y') \in \mathcal{D}_\text{train}} \alpha_{(x', y')} y' {\color{red} x' \cdot x}) + b) \geq 1 & \forall (x,y) \in \mathcal{D}_\text{train} \\ & \alpha \geq 0 \end{align*} \]

Feature Vektor $x$ tritt nur noch im Skalarprodukt auf.

Ersetze $x$ durch $\phi(x)$:

\[ \begin{align*} \min_{\alpha,b} \quad & \frac{1}{2} \sum_{(x,y) \in \mathcal{D}_\text{train}} \sum_{(x',y') \in \mathcal{D}_\text{train}} \alpha_{(x,y)} \alpha_{(x',y')} y y' {\color{red} \phi(x) \cdot \phi(x')} \\ \text{s.t.} \quad & y ((\sum_{(x',y') \in \mathcal{D}_\text{train}} \alpha_{(x', y')} y' {\color{red} \phi(x') \cdot \phi(x)}) + b) \geq 1 & \forall (x,y) \in \mathcal{D}_\text{train} \\ & \alpha \geq 0 \end{align*} \]

Jetzt können wir unseren Kernel verwenden:

\[ \begin{align*} \min_{\alpha,b} \quad & \frac{1}{2} \sum_{(x,y) \in \mathcal{D}_\text{train}} \sum_{(x',y') \in \mathcal{D}_\text{train}} \alpha_{(x,y)} \alpha_{(x',y')} y y' {\color{red} k(x, x')} \\ \text{s.t.} \quad & y ((\sum_{(x',y') \in \mathcal{D}_\text{train}} \alpha_{(x', y')} y' {\color{red} k(x', x)}) + b) \geq 1 & \forall (x,y) \in \mathcal{D}_\text{train} \\ & \alpha \geq 0 \end{align*} \]

Die neue Problemformulierung löst das optimal margin Problem auf dem Feature Raum $\phi(x)$, ohne $\phi(x)$ jemals explizit zu berechnen.

Training: Suche optimale $\alpha_{(x, y)}$ und $b$.

Wir merken uns die $x$, $y$ und $\alpha_{(x, y)}$, wo $\alpha_{(x, y)} > 0$.

Prediction:

\[ h_{w,b}(x) = g(w \cdot \phi(x) + b) \]

\[ = g((\sum_{(x',y') \in \mathcal{D}_\text{train}} \alpha_{(x',y')} y' \phi(x')) \phi(x) + b) \]

\[ = g((\sum_{(x',y') \in \mathcal{D}_\text{train}} \alpha_{(x',y')} y' {\color{red} k(x', x)}) + b) \]

Achtung: Der Kernel Trick funktioniert nur mit echten Kernels.

Es muss also ein Feature Mapping $\phi$ geben, so dass $k(x,z) = \phi(x) \cdot \phi(z)$ ist.

Was ist mit Overfitting?

Zielfunktion $\min \frac{1}{2} ||w||^2$ erledigt bereits die Regularisierung

Exkurs: String Sequences

Unser Input sind Sequenzen von Symbolen:
$x = \text{"GATTACA"}$

• Genom Sequenzen
• Proteine
• Sätze

Es lässt sich ein Kernel $k(x,z)$ finden, so dass $\phi(x)$ einen Eintrag für z.B. jedes 4-Tupel hat und zählt, wie oft dieses vorkommt.

\[ \phi(\text{"GATTACATTAG"})^{(\text{"ATTA"})} = 2 \]

Lodhi, et.al. (2002): Text Classification using String Kernels

Für strukturierte Daten wurden schon einige nützliche Kernel gefunden.

Leider nicht in sklearn verfügbar. Alternativen existieren: Shogun Toolbox

Was, wenn unsere Daten nicht linear separierbar sind?

Selbst wenn es geht wollen wir das vielleicht nicht

Oulier sollten ignoriert werden

Soft margin SVM

\[ \begin{align*} \min_{w,b} \quad & \frac{1}{2} ||w||^2 {\color{red} + C \sum_{(x,y) \in \mathcal{D}_\text{train}} \xi_{(x,y)}}\\ \text{s.t.} \quad & y(w \cdot x + b) \geq 1 {\color{red}- \xi_{(x,y)}} & \forall (x,y) \in \mathcal{D}_\text{train}\\ & {\color{red} \xi \geq 0} \end{align*} \]

\[ \begin{align*} \min_{w,b} \quad & \frac{1}{2} ||w||^2 {\color{red} + C \sum_{(x,y) \in \mathcal{D}_\text{train}} \xi_{(x,y)}}\\ \text{s.t.} \quad & y(w \cdot x + b) \geq 1 {\color{red}- \xi_{(x,y)}} & \forall (x,y) \in \mathcal{D}_\text{train}\\ & {\color{red} \xi \geq 0} \end{align*} \]

Der Hyperparameter $C$ bestimmt, wie teuer ein Outlier ist.

Bei SVMs gehen wir davon aus, dass die Input Daten eine saubere Trennung (in fast allen Fällen) ermöglichen.

Vorteile

• Wenige Parameter einzustellen.
• Sehr mächtig (mit richtigem Kernel).

Nachteile

• Wenig Interpretierbarkeit.
• Sehr hochdimensionale Input Features machen oft Probleme.
• Sehr große Datensätze können Probleme machen.

SVMs haben in den späten 90ern Neuronale Netze bei der Handschrifterkennung abgelöst.

Heutzutage haben da die Neuronalen Netze wieder die Nase vorne (aber viel mehr fine tuning erforderlich).

Anwendungsgebiete:

• Text Klassifizierung
• Bild Klassifizierung
• Protein Klassifizierung
• Analyse von Satellitendaten

Erweiterung: Support Vector Regression

Suche Lineare Funktion und kleine Margin, so dass möglichst alle Punkte innerhalb der Margin liegen.

In sklearn: SVC