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$

"Hinge Loss"

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$

• SVMs lassen sich mit dem Kernel Trick implementieren.
• Der Hinge Loss bietet ein gewisses Maß an Regularisierung.
• Overfitting ist für SVMs weniger ein Problem als man mit unendlich vielen Features erwartet.
• Performance ist ein Problem bei großen Daten.
• Mit dem richtigen Kernel können SVMs sehr mächtig sein.
• Wenig Interpretierbarkeit.

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

Idee: Erlaube Fehlklassifikationen auf Traingsdaten zum Preis $C$

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.

In sklearn: sklearn.svm.SVC