7.6 Kernbeispiele und nichtlineare SVM

Beispiele für Kernfunktionen

📄 10_kern.pdf, Folie 25

Kern	Formel	Parameter	Merkmalsraum
linear (Ergänzung)	$k(\mathbf{x},\mathbf{y}) = \mathbf{x}^\top\mathbf{y}$	–	Eingaberaum selbst
homogener Polynomkern	$k(\mathbf{x},\mathbf{y}) = (\mathbf{x}^\top\mathbf{y})^p$	Grad $p$	alle Monome vom Grad genau $p$
inhomogener Polynomkern	$k(\mathbf{x},\mathbf{y}) = (\mathbf{x}^\top\mathbf{y} + c)^p$	$p$, $c\ge 0$	alle Monome bis Grad $p$
Sigmoidkern	$k(\mathbf{x},\mathbf{y}) = \tanh(\kappa\,\mathbf{x}^\top\mathbf{y} + \theta)$	$\kappa$, $\theta$	nur für manche Parameter gültig
Gaußkern / RBF-Kern	$k(\mathbf{x},\mathbf{y}) = \exp\!\Big(-\dfrac{\lVert\mathbf{x}-\mathbf{y}\rVert^2}{2\sigma^2}\Big)$	Breite $\sigma$	unendlichdimensional

Die Polynomkerne wurden in 7.3 hergeleitet.

Der Sigmoidkern

Eine lineare Maschine mit Sigmoidkern,

$$f(\mathbf{x}) = \sum_{i=1}^{\ell}\alpha_iy_i\tanh(\kappa\,\mathbf{x}_i^\top\mathbf{x} + \theta) + b,$$

entspricht einem dreischichtigen Multilayer-Perzeptron (multilayer perceptron, MLP): Jeder Stützvektor $\mathbf{x}_i$ ist ein verdecktes Neuron mit Gewichtsvektor $\kappa\mathbf{x}_i$, Bias $\theta$ und $\tanh$-Aktivierung, die $\alpha_iy_i$ sind die Ausgabegewichte. Allerdings erfüllt der Sigmoidkern die Bedingung des Mercer-Theorems nur für bestimmte Werte von $\kappa$ und $\theta$.

Ergänzung – Gegenbeispiel: Für $\theta \lt 0$ ist $k(\mathbf{0},\mathbf{0}) = \tanh(\theta) \lt 0$. Ein gültiger Kern muss aber $k(\mathbf{x},\mathbf{x}) = \lVert\Phi(\mathbf{x})\rVert^2\ge 0$ erfüllen (vgl. Checkliste in 7.5). In der Praxis wird der Sigmoidkern deshalb selten verwendet.

Der Gaußkern (RBF-Kern)

$$k(\mathbf{x},\mathbf{y}) = e^{-\frac{\lVert\mathbf{x}-\mathbf{y}\rVert^2}{2\sigma^2}}$$

Eine lineare Maschine mit diesem Kern entspricht einem RBF-Netzwerk (radial basis function network): Um jeden Stützvektor sitzt eine Gauß-Glocke, die Entscheidungsfunktion ist eine gewichtete Summe dieser Glocken. Der Gaußkern ist ein sehr häufig eingesetzter Standardkern.

Ergänzung, nicht auf den Folien – Eigenschaften und Parameter:

• Wertebereich: $0 \lt k(\mathbf{x},\mathbf{y}) \le 1$, mit $k(\mathbf{x},\mathbf{x}) = 1$. Jeder Punkt hat also im Merkmalsraum die Länge 1, alle $\Phi(\mathbf{x})$ liegen auf einer Einheitskugel.
• Radial / translationsinvariant: $k$ hängt nur vom Abstand $\lVert\mathbf{x}-\mathbf{y}\rVert$ ab.
• Merkmalsraum unendlichdimensional: siehe die Herleitung in 7.4. Die Gram-Matrix ist für paarweise verschiedene Punkte sogar strikt positiv definit, d. h. man kann jede Klassenaufteilung trennen.
• Breite $\sigma$ legt fest, ab welchem Abstand zwei Punkte als „unähnlich“ gelten:

$\lVert\mathbf{x}-\mathbf{y}\rVert^2$	$k$ bei $\sigma = 0.5$	$k$ bei $\sigma = 1$	$k$ bei $\sigma = 2$
$0$	$1$	$1$	$1$
$0.5$	$e^{-1} \approx 0.37$	$e^{-0.25}\approx 0.78$	$e^{-0.0625}\approx 0.94$
$2$ (z. B. $(0,0)$ vs. $(1,1)$)	$e^{-4}\approx 0.018$	$e^{-1}\approx 0.37$	$e^{-0.25}\approx 0.78$
$8$ (z. B. $(0,0)$ vs. $(2,2)$)	$e^{-16}\approx 10^{-7}$	$e^{-4}\approx 0.018$	$e^{-1}\approx 0.37$

• $\sigma$ klein: Nur sehr nahe Punkte sind ähnlich, $K$ wird fast zur Einheitsmatrix. Jeder Trainingspunkt bekommt seine eigene schmale Glocke, die Entscheidungsgrenze wird sehr zerklüftet. Gefahr: Überanpassung (overfitting), im Extrem ein „Auswendiglernen“ der Trainingsdaten.
• $\sigma$ groß: Alle Punkte sind sich ähnlich, $K$ wird fast zur Matrix aus lauter Einsen. Die Entscheidungsfunktion wird sehr glatt, fast linear. Gefahr: Unteranpassung (underfitting).
• In scikit-learn heißt der Parameter gamma mit $k = \exp(-\gamma\lVert\mathbf{x}-\mathbf{y}\rVert^2)$, also $\gamma = 1/(2\sigma^2)$. Großes gamma = kleines $\sigma$ = komplexeres Modell.
• $\sigma$ (bzw. $\gamma$) und $C$ werden gemeinsam per Kreuzvalidierung (siehe Kapitel 5) gewählt, typischerweise mit einer Gittersuche auf logarithmischer Skala.

Fallstrick: Skalierung der Merkmale

Der Gaußkern basiert auf dem euklidischen Abstand. Hat ein Merkmal Werte in der Größenordnung 1000 und ein anderes um 1, dominiert das erste den Abstand komplett. Vor dem Einsatz des RBF-Kerns die Merkmale standardisieren. (Ergänzung)

Kerne als nichtlineare Ähnlichkeitsmaße

Da Kerne einem Skalarprodukt nach der Einbettung in den Merkmalsraum entsprechen, kann man sie sich als nichtlineares Ähnlichkeitsmaß vorstellen (vgl. Skalarprodukt als Ähnlichkeitsmaß in 7.2). Beim Gaußkern ist das besonders anschaulich: 1 bei identischen Punkten, gegen 0 bei weit entfernten.

Konstruktion von Kernen aus Kernen

📄 10_kern.pdf, Folie 26

Sind $k_1(\mathbf{x},\mathbf{y})$, $k_2(\mathbf{x},\mathbf{y})$ und $k_3(\mathbf{x},\mathbf{y})$ gültige Kernfunktionen, so sind auch folgende Funktionen gültige Kerne:

Regel	Begründung (Ergänzung, über die Gram-Matrix bzw. die Einbettung)
$a\cdot k_1$ für $a\ge 0$	$\mathbf{v}^\top(aK_1)\mathbf{v} = a\,\mathbf{v}^\top K_1\mathbf{v}\ge 0$; Einbettung $\sqrt a\,\Phi_1$
$k_1 + k_2$	$\mathbf{v}^\top(K_1+K_2)\mathbf{v} = \mathbf{v}^\top K_1\mathbf{v} + \mathbf{v}^\top K_2\mathbf{v}\ge 0$; Einbettung: $\Phi_1$ und $\Phi_2$ hintereinanderhängen
$k_1\cdot k_2$	Einbettung aus allen Produkten $\phi^{(1)}_i(\mathbf{x})\,\phi^{(2)}_j(\mathbf{x})$ (Tensorprodukt); in Matrixform: Satz von Schur
$f(\mathbf{x})\,f(\mathbf{y})$ für beliebiges $f:\mathbb{R}^d\to\mathbb{R}$	eindimensionale Einbettung $\Phi(\mathbf{x}) = f(\mathbf{x})$; $\mathbf{v}^\top K\mathbf{v} = \big(\sum_iv_if(\mathbf{x}_i)\big)^2\ge 0$
$k_3(\Phi(\mathbf{x}),\Phi(\mathbf{y}))$ für beliebige Abbildung $\Phi$	die Gram-Matrix ist die von $k_3$ auf den Punkten $\Phi(\mathbf{x}_1),\dots,\Phi(\mathbf{x}_l)$, also psd

Es gibt eine Reihe weiterer erlaubter Operationen, z. B. Tensorprodukte von Kernen, Faltungen, direkte Summen (siehe Schölkopf & Smola, 2002).

Achtung

Differenzen $k_1 - k_2$ und negative Vielfache sind im Allgemeinen keine Kerne. Beispiel: $-k_1$ hat $-k_1(\mathbf{x},\mathbf{x}) \lt 0$, sobald $k_1(\mathbf{x},\mathbf{x}) \gt 0$.

Anwendungsbeispiel (Ergänzung): Damit lässt sich zeigen, dass die Kerne von Folie 25 gültig sind, ohne $\Phi$ auszurechnen.

• Polynomkern: $\mathbf{x}^\top\mathbf{y}$ ist ein Kern (Einbettung = Identität). Nach der Produktregel ist $(\mathbf{x}^\top\mathbf{y})^p$ ein Kern. Die Konstante $c\ge 0$ ist ein Kern (Regel $f(\mathbf{x})f(\mathbf{y})$ mit $f\equiv\sqrt c$), also ist $\mathbf{x}^\top\mathbf{y}+c$ ein Kern, und damit auch $(\mathbf{x}^\top\mathbf{y}+c)^p$.
• Gaußkern: Zerlege

$$e^{-\frac{\lVert\mathbf{x}-\mathbf{y}\rVert^2}{2\sigma^2}} = \underbrace{e^{-\frac{\lVert\mathbf{x}\rVert^2}{2\sigma^2}}\ e^{-\frac{\lVert\mathbf{y}\rVert^2}{2\sigma^2}}}_{f(\mathbf{x})f(\mathbf{y})}\cdot \underbrace{e^{\frac{\mathbf{x}^\top\mathbf{y}}{\sigma^2}}}_{\text{Kern?}} .$$

Der zweite Faktor ist $\sum_{n}\frac{1}{n!}\big(\mathbf{x}^\top\mathbf{y}/\sigma^2\big)^n$, eine Summe von Polynomkernen mit nichtnegativen Vorfaktoren, also (als Grenzwert) ein Kern. Mit der Produktregel ist der Gaußkern ein Kern.

Kerne für nichtvektorielle Daten

📄 10_kern.pdf, Folie 27

Oft lassen sich die Daten nicht sinnvoll als Vektoren darstellen, z. B. bei der Klassifikation von Texten oder Genomsequenzen (unterschiedliche Länge, keine natürliche Koordinatenzuordnung). Man kann aber Ähnlichkeitsmaße für solche Objekte definieren. Diese müssen natürlich die Bedingungen des Mercer-Theorems erfüllen, damit man sie sinnvoll in einer linearen Lernmaschine einsetzen kann.

Der Charme dabei: Der Algorithmus (z. B. die SVM) braucht nur die Kernwerte $k(\mathbf{x}_i,\mathbf{x}_j)$. Ob die $\mathbf{x}_i$ Vektoren, Strings oder Graphen sind, ist ihm egal.

Beispiele:

• Stringkern (string kernel): Die Ähnlichkeit zweier Zeichenketten wird über die Häufigkeit und Länge aller gemeinsamen Teilstrings gemessen. Sie lässt sich rekursiv in linearer Zeit berechnen.
• Ähnlichkeit von Gesten: Das Produkt der Gelenkwinkel stellt ebenfalls einen Kern dar.

Ergänzung – ein einfacher Stringkern zum Nachrechnen (Spektrumkern): Für ein festes $q$ sei $\phi_u(s)$ die Anzahl, wie oft das Wort $u$ der Länge $q$ in $s$ vorkommt, und $k(s,t) = \sum_u\phi_u(s)\phi_u(t)$. Das ist nach Konstruktion ein Skalarprodukt, also ein gültiger Kern. Für $q = 2$, $s =$ ABAB, $t =$ BABA: $s$ enthält AB zweimal und BA einmal, $t$ enthält AB einmal und BA zweimal. Also $k(s,t) = 2\cdot1 + 1\cdot2 = 4$, während $k(s,s) = 2^2 + 1^2 = 5$.

Nichtlineare SVM mit Kernfunktion

📄 10_kern.pdf, Folie 28

Mit dem Kernel-Trick lässt sich die SVM (und Pegasos) auf einfache Weise in eine nichtlineare Lernmaschine umwandeln. Man ersetzt in der dualen Formulierung aus 7.2 einfach jedes Skalarprodukt $\langle\mathbf{x}_i\cdot\mathbf{x}_j\rangle$ durch $k(\mathbf{x}_i,\mathbf{x}_j)$:

SVM-Optimierung (nichtlinear, Folie 28)

Minimiere

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

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

$$y_i\Big(\sum_{j=1}^{\ell}\alpha_jy_j\,k(\mathbf{x}_j,\mathbf{x}_i) + b\Big)\ \ge\ 1-\xi_i\qquad\text{und}\qquad\xi_i\ge 0 .$$

Entscheidungsfunktion: $f(\mathbf{x}) = \sum_{i=1}^{\ell}\alpha_iy_i\,k(\mathbf{x}_i,\mathbf{x}) + b$.

(Auf der Folie fehlen der Faktor $\tfrac12$ vor der Doppelsumme und der Faktor $y_i$ in der Nebenbedingung; hier ist die zu Folie 12 konsistente Form angegeben. Die $2\ell$ Nebenbedingungen sind die $\ell$ Margin-Bedingungen plus die $\ell$ Bedingungen $\xi_i\ge 0$.)

Für Pegasos dual (Folie 13) gilt dasselbe: $f(\mathbf{x}_i) = C\eta_t\sum_j\alpha_jy_j\,k(\mathbf{x}_j,\mathbf{x}_i)$.

Aufgrund der Maximierung der Trennbreite funktioniert die nichtlineare SVM auch in unendlichdimensionalen Merkmalsräumen!

Ergänzung – warum? Die Kapazität einer linearen Maschine mit großem Margin hängt nicht von der Dimension des Raumes ab, sondern vom Verhältnis zwischen Datenradius und Margin. Die SVM wählt unter allen Trennebenen die mit größtem Margin, also die „einfachste“. Deshalb passt sie sich trotz unendlich vieler Merkmale nicht beliebig an die Trainingsdaten an (sofern $C$ und die Kernparameter sinnvoll gewählt sind).

Kurzes Beispiel in scikit-learn

Ergänzung, nicht auf den Folien. Zwei konzentrische Kreise, das Paradebeispiel aus 7.1:

from sklearn.datasets import make_circles
from sklearn.svm import SVC

X, y = make_circles(n_samples=200, factor=0.4, noise=0.1, random_state=0)

for clf in [SVC(kernel="linear", C=1),
            SVC(kernel="poly", degree=2, coef0=1, C=1),   # (gamma*x'y + coef0)^2
            SVC(kernel="rbf", gamma=1.0, C=1)]:           # exp(-gamma*||x-y||^2)
    clf.fit(X, y)
    print(clf.kernel, clf.score(X, y), "Stützvektoren:", clf.n_support_.sum())

Der lineare Kern bleibt bei etwa Ratewahrscheinlichkeit, Polynom- (Grad 2) und RBF-Kern trennen die Kreise nahezu perfekt. Eigene Kerne übergibt man als Funktion (kernel=meine_funktion, liefert die Gram-Matrix) oder als vorberechnete Gram-Matrix (kernel="precomputed").