Kapitel 7 – Kernel-Trick

Folien: 📄 10_kern.pdf · Woche 5, Prof. Franz

Worum geht es?

Lineare Lernmaschinen (Perzeptron, lineare SVM, lineare Regression) sind einfach und gut verstanden, können aber nur lineare Zusammenhänge darstellen. Die Folien heißen „Kerninduzierte Merkmalsräume“ und zeigen, wie man diese Grenze überwindet, ohne den linearen Rahmen zu verlassen:

1. Bilde die Daten mit einer Einbettung $\Phi$ in einen (oft sehr hoch- oder unendlichdimensionalen) Merkmalsraum ab und lerne dort linear.
2. Schreibe den Lernalgorithmus in der dualen Form, in der die Daten nur in Skalarprodukten $\langle\Phi(\mathbf{x}_i)\cdot\Phi(\mathbf{x}_j)\rangle$ vorkommen.
3. Ersetze diese Skalarprodukte durch eine Kernfunktion $k(\mathbf{x}_i,\mathbf{x}_j)$, die man direkt im Eingaberaum ausrechnet. $\Phi$ wird nie explizit gebraucht. Das ist der Kernel-Trick.

Das Mercer-Theorem beantwortet schließlich die Frage, welche Funktionen $k$ überhaupt als Kern taugen: genau die, deren Gram-Matrix auf jeder endlichen Punktmenge positiv semidefinit ist.

Dieses Kapitel baut direkt auf der Soft-Margin-SVM und ihrem dualen Problem aus Kapitel 6 auf. Die kernalisierte lineare Regression aus Kapitel 4 ist ein weiteres Beispiel für dieselbe Idee.

Aufbau des Kapitels

Abschnitt	Inhalt
7.1 Merkmalsräume	Skalarprodukt, lineare Maschinen und ihre Grenzen, Einbettung $\Phi$, Beispiel Monome 2. Grades (Folien 4–8)
7.2 Duale Darstellung	Einbettungsstärken, Repräsentertheorem, primal vs. dual, Skalarprodukt als Ähnlichkeit, duale SVM, Pegasos dual (Folien 9–13)
7.3 Der Kernel-Trick	Kernfunktion statt Skalarprodukt, Polynomkern Schritt für Schritt hergeleitet, Rechenaufwand (Folien 15–16)
7.4 Unendlichdimensionale Merkmalsräume	Folgenräume, $l_p$-Normen, Skalarprodukt auf $l_2$, lineare Maschinen mit unendlich vielen Merkmalen (Folien 17–20)
7.5 Mercer-Kerne	Symmetrie, Mercer-Theorem, positiv definite Kerne, Gram-Matrix mit Zahlenbeispielen (Folien 22–24)
7.6 Kernbeispiele und nichtlineare SVM	Polynom-, Sigmoid-, Gaußkern und Parameter, Kombinationsregeln, Kerne für Strings, kernalisierte SVM (Folien 25–28)

Die wichtigsten Formeln auf einen Blick

	Formel
Kernfunktion	$k(\mathbf{x},\mathbf{y}) = \langle\Phi(\mathbf{x})\cdot\Phi(\mathbf{y})\rangle$
duale Entscheidungsfunktion	$f(\mathbf{x}) = \sum_{i=1}^{\ell}\alpha_iy_i\,k(\mathbf{x}_i,\mathbf{x}) + b$
Polynomkern	$(\mathbf{x}^\top\mathbf{y})^p$ bzw. $(\mathbf{x}^\top\mathbf{y}+c)^p$
Gaußkern (RBF)	$\exp\big(-\lVert\mathbf{x}-\mathbf{y}\rVert^2/(2\sigma^2)\big)$
Kernbedingung	$K_{ij} = k(\mathbf{x}_i,\mathbf{x}_j)$ symmetrisch und $\mathbf{v}^\top K\mathbf{v}\ge 0$ für alle $\mathbf{v}$ und alle Punktmengen

Prüfungsrelevant / Selbsttest

1. Was ist die zentrale Beobachtung, auf der der Kernel-Trick beruht?

Antwort

In der dualen Form vieler linearer Lernverfahren (Perzeptron, SVM, Kleinste-Quadrate-Regression, allgemein: Repräsentertheorem) kommen die Datenpunkte nur in Skalarprodukten $\langle\mathbf{x}_i\cdot\mathbf{x}_j\rangle$ bzw. $\langle\mathbf{x}_i\cdot\mathbf{x}\rangle$ vor. Ersetzt man diese durch $k(\mathbf{x}_i,\mathbf{x}_j) = \langle\Phi(\mathbf{x}_i)\cdot\Phi(\mathbf{x}_j)\rangle$, arbeitet das Verfahren linear im Merkmalsraum, ohne dass $\Phi$ je berechnet wird. Siehe 7.3.

2. Zeige, dass $k(\mathbf{x},\mathbf{z}) = (\mathbf{x}^\top\mathbf{z})^2$ für $\mathbf{x},\mathbf{z}\in\mathbb{R}^2$ ein Skalarprodukt in einem Merkmalsraum ist. Wie sieht $\Phi$ aus?

Antwort

$(x_1z_1+x_2z_2)^2 = x_1^2z_1^2 + 2x_1x_2z_1z_2 + x_2^2z_2^2 = \langle\Phi(\mathbf{x})\cdot\Phi(\mathbf{z})\rangle$ mit $\Phi(\mathbf{x}) = (x_1^2,\ \sqrt2x_1x_2,\ x_2^2)^\top$. Der Faktor $\sqrt2$ ist nötig, damit der gemischte Term mit Vorfaktor 2 herauskommt. Siehe 7.3.

3. Was ist der Unterschied zwischen primaler und dualer Darstellung, und wann lohnt sich die duale?

Antwort

Primal lernt man $\mathbf{w}$ mit so vielen Komponenten wie der Merkmalsraum Dimensionen hat. Dual lernt man $\boldsymbol\alpha\in\mathbb{R}^\ell$, einen Koeffizienten pro Trainingspunkt, mit $\mathbf{w} = \sum_i\alpha_iy_i\Phi(\mathbf{x}_i)$. Die duale Form lohnt sich, wenn der Merkmalsraum sehr hoch- oder unendlichdimensional ist und die Anzahl der Trainingspunkte moderat. Siehe 7.2.

4. Welche Bedeutung haben die Einbettungsstärken $\alpha_i$ beim Perzeptron?

Antwort

$\alpha_i$ zählt, wie oft Beispiel $\mathbf{x}_i$ beim Training falsch klassifiziert wurde. Es ist ein Maß für Schwierigkeit bzw. Informationsgehalt des Punktes: Leichte Punkte haben $\alpha_i = 0$, Punkte nahe der Grenze große $\alpha_i$.

5. Wie lautet die notwendige und hinreichende Bedingung dafür, dass eine Funktion $k(\mathbf{x},\mathbf{y})$ ein gültiger Kern ist? Warum ist sie notwendig?

Antwort

Für jede endliche Punktmenge $\mathbf{x}_1,\dots,\mathbf{x}_l$ muss die Gram-Matrix $K_{ij} = k(\mathbf{x}_i,\mathbf{x}_j)$ symmetrisch und positiv semidefinit sein: $\mathbf{v}^\top K\mathbf{v}\ge 0$ für alle $\mathbf{v}\in\mathbb{R}^l$. Notwendig, weil für einen echten Kern $\mathbf{v}^\top K\mathbf{v} = \lVert\sum_iv_i\Phi(\mathbf{x}_i)\rVert^2 \ge 0$ gilt. Siehe 7.5.

6. Ist $k(\mathbf{x},\mathbf{y}) = \lVert\mathbf{x}-\mathbf{y}\rVert^2$ ein Kern? Begründe.

Antwort

Nein. Für $x_1 = 0$, $x_2 = 1$ ist $K = \begin{pmatrix}0&1\\1&0\end{pmatrix}$, und mit $\mathbf{v} = (1,-1)^\top$ folgt $\mathbf{v}^\top K\mathbf{v} = -2 \lt 0$. Ein Gegenbeispiel genügt. Siehe 7.5.

7. Welchen Einfluss hat der Parameter $\sigma$ beim Gaußkern?

Antwort

$\sigma$ ist die Breite der Gauß-Glocke, also die Reichweite der Ähnlichkeit. Kleines $\sigma$: Nur sehr nahe Punkte sind ähnlich, die Gram-Matrix nähert sich der Einheitsmatrix, die Entscheidungsgrenze wird zerklüftet, Gefahr der Überanpassung. Großes $\sigma$: Alle Punkte sind ähnlich, die Grenze wird glatt bis fast linear, Gefahr der Unteranpassung. In scikit-learn ist $\gamma = 1/(2\sigma^2)$. Siehe 7.6.

8. Sind $k_1 + k_2$, $k_1\cdot k_2$ und $k_1 - k_2$ Kerne, wenn $k_1, k_2$ Kerne sind?

Antwort

$k_1+k_2$ ja (Summe zweier psd-Matrizen ist psd), $k_1\cdot k_2$ ja (Folie 26, Einbettung über alle Produkte der Merkmale), $k_1 - k_2$ im Allgemeinen nein, z. B. ist $k_1 - 2k_1 = -k_1$ auf der Diagonale negativ. Siehe 7.6.

9. Wie kann eine lineare Maschine in einem unendlichdimensionalen Merkmalsraum überhaupt berechnet werden?

Antwort

Primal bräuchte man unendlich viele Gewichte. Dual ist $f(\mathbf{x}) = \sum_{i=1}^{\ell}\alpha_iy_ik(\mathbf{x},\mathbf{x}_i) + b$ eine endliche Summe über die Trainingspunkte. Die unendliche Summe $\sum_i\lambda_i\phi_i(\mathbf{x})\phi_i(\mathbf{y})$ steckt in der geschlossen berechenbaren Kernfunktion. Voraussetzung: $\sum_i\lambda_i\phi_i(\mathbf{x})^2 \lt \infty$ für alle $\mathbf{x}$. Siehe 7.4.

10. Warum überpasst die nichtlineare SVM trotz unendlichdimensionalem Merkmalsraum (z. B. Gaußkern) nicht zwangsläufig?

Antwort

Wegen der Maximierung der Trennbreite: Die Komplexität einer Trennebene mit großem Margin hängt nicht von der Raumdimension ab. Die SVM wählt unter allen trennenden Hyperebenen die mit größtem Margin, also die einfachste. Über $C$ und die Kernparameter (z. B. $\sigma$) steuert man den Kompromiss, sie werden per Kreuzvalidierung gewählt. Siehe 7.6.