7.3 Der Kernel-Trick

Zentrale Beobachtung

📄 10_kern.pdf, Folie 15

In der dualen Form (siehe 7.2) kommen Trainings- und Testdatenpunkte nur in Form von Skalarprodukten vor:

$$\langle\mathbf{x}_i\cdot\mathbf{x}\rangle \qquad\text{bzw.}\qquad \langle\Phi(\mathbf{x}_i)\cdot\Phi(\mathbf{x})\rangle .$$

Man kann beweisen, dass das nicht nur für Kleinste-Quadrate-Regression und Perzeptron gilt, sondern für eine große Klasse von Optimierungsproblemen (Repräsentertheorem, siehe Schölkopf & Smola, 2002).

In all diesen Problemen kann man das Skalarprodukt $\langle\Phi(\mathbf{x})\cdot\Phi(\mathbf{z})\rangle$ durch eine Kernfunktion (kernel function, kurz Kern) ersetzen:

$$k : \mathbb{R}^d\times\mathbb{R}^d\to\mathbb{R} \qquad\text{mit}\qquad k_\Phi(\mathbf{x},\mathbf{y}) = \langle\Phi(\mathbf{x})\cdot\Phi(\mathbf{y})\rangle .$$

Das heißt: Merkmalsbildung und Skalarprodukt werden durch eine einzige Funktionsberechnung ersetzt. Man berechnet $\Phi$ nie explizit, sondern nur $k$. Das ist der Kernel-Trick (kernel trick).

Die duale Entscheidungsfunktion lautet damit

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

Der Kernel-Trick in drei Schritten

1. Schreibe den Algorithmus so um, dass die Daten nur in Skalarprodukten vorkommen (duale Form).
2. Ersetze jedes Skalarprodukt $\langle\mathbf{x}_i\cdot\mathbf{x}_j\rangle$ durch $k(\mathbf{x}_i,\mathbf{x}_j)$.
3. Fertig: Der Algorithmus arbeitet jetzt implizit linear im Merkmalsraum von $k$, also nichtlinear im Eingaberaum, ohne dass $\Phi$ je ausgerechnet wird.

Konstruktion einer Kernfunktion aus der Einbettung

📄 10_kern.pdf, Folie 16

Kennt man die Einbettung $\Phi$, kann man den zugehörigen Kern direkt nach der Definition

$$k_\Phi(\mathbf{x},\mathbf{y}) = \langle\Phi(\mathbf{x})\cdot\Phi(\mathbf{y})\rangle$$

konstruieren. Interessant wird es, wenn sich das Ergebnis viel einfacher ausdrücken lässt als über $\Phi$.

Beispiel: Monome 2. Grades in 2D, Schritt für Schritt

Mit $\Phi(\mathbf{x}) = (x_1^2,\ \sqrt2\,x_1x_2,\ x_2^2)^\top$ aus 7.1 und $\mathbf{z} = (z_1, z_2)^\top$:

$$\begin{aligned} \langle\Phi(\mathbf{x})\cdot\Phi(\mathbf{z})\rangle &= (x_1^2,\ \sqrt2\,x_1x_2,\ x_2^2)\,(z_1^2,\ \sqrt2\,z_1z_2,\ z_2^2)^\top \\ &= x_1^2z_1^2 + \sqrt2\cdot\sqrt2\; x_1x_2z_1z_2 + x_2^2z_2^2 \\ &= x_1^2z_1^2 + 2\,x_1z_1\,x_2z_2 + x_2^2z_2^2 \\ &= (x_1z_1 + x_2z_2)^2 \qquad\text{(binomische Formel } a^2+2ab+b^2 = (a+b)^2\text{)} \\ &= \langle\mathbf{x}\cdot\mathbf{z}\rangle^2 . \end{aligned}$$

Das Skalarprodukt im 3-dimensionalen Merkmalsraum ist also einfach das Quadrat des Skalarprodukts im Eingaberaum. Man muss $\Phi$ gar nicht ausrechnen.

Zahlenbeispiel: $\mathbf{x} = (1, 2)^\top$, $\mathbf{z} = (3, 1)^\top$.

• Über den Merkmalsraum: $\Phi(\mathbf{x}) = (1,\ 2\sqrt2,\ 4)$, $\Phi(\mathbf{z}) = (9,\ 3\sqrt2,\ 1)$, also $\langle\Phi(\mathbf{x})\cdot\Phi(\mathbf{z})\rangle = 1\cdot 9 + 2\sqrt2\cdot3\sqrt2 + 4\cdot1 = 9 + 12 + 4 = 25$.
• Über den Kern: $\langle\mathbf{x}\cdot\mathbf{z}\rangle = 1\cdot3 + 2\cdot1 = 5$, also $k(\mathbf{x},\mathbf{z}) = 5^2 = 25$. ✔

Gleiches Ergebnis, aber der zweite Weg braucht 2 Multiplikationen, 1 Addition und 1 Quadrierung, statt erst zweimal 3 Merkmale zu berechnen und dann deren Skalarprodukt.

Allgemein: Polynomkern vom Grad $p$

Nimmt man als Merkmale alle Produkte von $p$ Eingabekomponenten,

$$\phi_{j_1\dots j_p}(\mathbf{x}) = x_{j_1}x_{j_2}\cdots x_{j_p}\qquad\text{für alle } j_1,\dots,j_p\in\lbrace 1,\dots,d\rbrace,$$

so ergibt sich

$$\langle\Phi(\mathbf{x})\cdot\Phi(\mathbf{z})\rangle = \sum_{j_1,\dots,j_p=1}^{d} x_{j_1}\cdots x_{j_p}\, z_{j_1}\cdots z_{j_p} = \sum_{j_1,\dots,j_p=1}^{d} (x_{j_1}z_{j_1})\cdots(x_{j_p}z_{j_p}) = \Big(\sum_{j=1}^{d}x_jz_j\Big)^{p} = \langle\mathbf{x}\cdot\mathbf{z}\rangle^{p} .$$

Der vorletzte Schritt ist einfach das Ausmultiplizieren rückwärts: $(a_1+\dots+a_d)^p$ ausmultipliziert ergibt genau die Summe über alle Produkte $a_{j_1}\cdots a_{j_p}$ mit $a_j = x_jz_j$.

Ergänzung zum Zusammenhang mit dem 2D-Beispiel: Die Folie spricht von „allen Permutationen“, gemeint sind alle geordneten Index-Tupel $(j_1,\dots,j_p)$ (mit Wiederholung). Für $d = p = 2$ sind das die vier Merkmale $x_1x_1,\ x_1x_2,\ x_2x_1,\ x_2x_2$. Die beiden mittleren sind gleich. Fasst man sie zu einem Merkmal zusammen, muss es mit $\sqrt2$ gewichtet werden, damit das Skalarprodukt gleich bleibt: $x_1x_2z_1z_2 + x_2x_1z_2z_1 = (\sqrt2 x_1x_2)(\sqrt2 z_1z_2)$. Genau daher kommt der Faktor $\sqrt2$ in 7.1.

Merke

Ein und derselbe Kern kann zu verschiedenen Einbettungen gehören ($\mathbb{R}^4$ mit vier geordneten Produkten oder $\mathbb{R}^3$ mit $\sqrt2$-Gewichtung). Der Kern legt die Geometrie (Skalarprodukte, Abstände, Winkel) fest, nicht die konkrete Darstellung von $\Phi$.

Warum ist das ein „Trick“? Rechenaufwand

Ergänzung, nicht auf den Folien. Die Anzahl der verschiedenen Monome vom Grad genau $p$ in $d$ Variablen ist

$$\binom{d+p-1}{p}.$$

Beispiel: Bilder mit $16\times16 = 256$ Pixeln, Monome vom Grad $p=5$ (Produkte von je 5 Pixeln):

$$\binom{260}{5} = \frac{260\cdot259\cdot258\cdot257\cdot256}{120} \approx 9{,}5\cdot 10^{9}$$

Merkmale. Ein einziger Merkmalsvektor wären rund 76 GB (als double). Der Kern $\langle\mathbf{x}\cdot\mathbf{z}\rangle^5$ kostet dagegen nur ein Skalarprodukt mit 256 Multiplikationen und eine Potenz.

	explizit über $\Phi$	Kernel-Trick
Aufwand pro Skalarprodukt	$O\big(\binom{d+p-1}{p}\big)$, praktisch $O(d^p)$	$O(d)$
Speicher pro Punkt	$\binom{d+p-1}{p}$ Zahlen	$d$ Zahlen
unendlich viele Merkmale	unmöglich	möglich (z. B. Gaußkern)

Der Preis: Man braucht alle paarweisen Kernwerte $k(\mathbf{x}_i,\mathbf{x}_j)$ der Trainingsdaten, die Gram-Matrix mit $\ell^2$ Einträgen (siehe 7.5). Bei sehr vielen Trainingspunkten wird das teuer. Außerdem muss man zur Vorhersage $k(\mathbf{x}_i,\mathbf{x})$ für alle Trainingspunkte mit $\alpha_i \ne 0$ auswerten, bei der SVM also für alle Stützvektoren.

Der inhomogene Polynomkern als Beispiel

Ergänzung, nicht auf den Folien (der Kern selbst steht auf 📄 10_kern.pdf, Folie 25 ). Für $k(\mathbf{x},\mathbf{z}) = (\langle\mathbf{x}\cdot\mathbf{z}\rangle + c)^2$ mit $c\ge 0$ in 2D rechnet man aus:

$$\begin{aligned} (x_1z_1 + x_2z_2 + c)^2 &= x_1^2z_1^2 + x_2^2z_2^2 + 2x_1x_2z_1z_2 + 2c\,x_1z_1 + 2c\,x_2z_2 + c^2 \\ &= \big\langle \Phi(\mathbf{x})\cdot\Phi(\mathbf{z})\big\rangle \quad\text{mit}\quad \Phi(\mathbf{x}) = \big(x_1^2,\ x_2^2,\ \sqrt2\,x_1x_2,\ \sqrt{2c}\,x_1,\ \sqrt{2c}\,x_2,\ c\big)^\top . \end{aligned}$$

Der Merkmalsraum enthält jetzt alle Monome bis Grad 2 (inklusive linearer Terme und Konstante). Damit lassen sich auch verschobene Ellipsen, Parabeln und Hyperbeln trennen. $c$ steuert, wie stark die niedrigen Grade gegenüber den hohen gewichtet werden.

Fallstrick

Der homogene Kern $\langle\mathbf{x}\cdot\mathbf{z}\rangle^2$ kennt nur Monome vom Grad genau 2. Eine Ellipse, die nicht um den Ursprung zentriert ist, braucht aber auch lineare Terme $x_1, x_2$. Dafür nimmt man den inhomogenen Kern mit $c \gt 0$.