Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Vorlesungsaufzeichnung Kernel-Trick (VL 21, erste 32 Minuten)

Motivation: radiale Basisfunktion

Streudiagramm der Übungsdaten: eine dichte runde Punktwolke in der Mitte, umgeben von einem breiten Ring aus Punkten in etwa 8 bis 10 Einheiten Abstand. Alle Punkte haben dieselbe Farbe — die beiden Gruppen sind durch keine Gerade zu trennen.

Eine geometrische Transformation

Loading...
Loading...

Diese so transformierten Daten lassen sich nun mit 2-Means clustern!

k-Means im transformierten Raum

Drei dreidimensionale Ansichten derselben Punktwolke aus unterschiedlichen Blickwinkeln, nachdem die Daten über die Feature-Abbildung in die Höhe gehoben wurden — die Höhe ist der quadrierte Abstand vom Ursprung. Der innere Klumpen liegt blau und flach am Boden bei Höhe nahe null, der Ring bildet grün eine weit darüber schwebende Schale zwischen 70 und 110. In der dritten Ansicht, fast senkrecht von oben, erscheinen beide wieder als konzentrische Kreise. In dieser Höhe lassen sich die beiden Gruppen durch eine waagerechte Ebene trennen, in der Ebene darunter nicht.

Wir können auch nur die k-Means-Berechnung in diesem größeren Raum (mit dem radialen Feature x2+y2x^2+y^2) stattfinden lassen, die Labels dann mitnehmen und in unseren ‘alten’ zweidimensionalen Plot darstellen:

Dieselben Daten wie zuvor, jetzt nach den Labels von k-Means eingefärbt: der innere Klumpen grün, der äußere Ring blau. Nach dem Anheben in die dritte Dimension trennt k-Means die beiden Gruppen also sauber, obwohl sie in der Ebene ineinander verschachtelt liegen.

Was wir wirklich brauchten

Im k-Means-Verfahren werden die ganze Zeit Abstände gemessen. Es ist daher translations- und rotationsinvariant. Wenn wir außerdem nicht unsere Daten transformieren, sondern lediglich beim Messen der Abstände den Abstandsbegriff aus dem transformierten Raum verwenden, könnte das, je nach Transformation, weniger rechenintensiv sein.

Auch andere Verfahren, wie z.B. k-Nearest Neighbours und Support Vector Machines (was wir beides nicht besprochen haben) beruhen nur auf Abstandsmessungen.

Daten durch Abstände beschreiben

Der Kernel-Trick besteht nun darin, die Daten xix_i nicht durch die symmetrische Matrix d(xi,xj)d(x_i, x_j) zu beschreiben, sondern durch eine andere Funktion κ(xi,xj)\kappa(x_i, x_j), die die gleiche Rolle spielt wie eine Abstandsmessung in einem transformierten Koordinatensystem.

Der euklidische Abstand ist

d(a,b)=∥b−a∥=⟨b−a,b−a⟩=(b−a)T(b−a)d(a,b) = \lVert b - a \rVert = \sqrt{\langle b-a , b-a \rangle} = \sqrt{(b-a)^T (b-a)}

Wenn man eine lineare Transformation MM anwendet auf die Daten, so berechnet man danach

d(Ma,Mb)2=∥Mb−Ma∥2=∥M(b−a)∥2=⟨M(b−a),M(b−a)⟩=(b−a)TMTM(b−a)d(Ma, Mb)^2 = \lVert Mb - Ma \rVert^2 = \lVert M(b - a) \rVert^2 = \langle M(b-a), M(b-a) \rangle = (b-a)^T M^T M (b-a)

sodass wir für eine Abstandsmessung im transformierten Raum eigentlich gar nicht MaMa und MbMb ausrechnen müssen, sondern ‘nur’ MTMM^TM ziemlich oft anwenden. Wenn wir Glück haben, ist das einfacher.

Oftmals ist ein guter Abstandsbegriff auch das Skalarprodukt ⟨a,b⟩\langle a, b\rangle selbst bzw. ⟨Ma,Mb⟩=bTMTMa\langle Ma, Mb\rangle = b^T M^TM a.

Nebenbemerkung, um das zu erläutern: Wir können auch ausrechnen, dass

∥b−a∥2=⟨b−a,b−a⟩=⟨b,b⟩−2⟨a,b⟩+⟨a,a⟩=∥a∥2+∥b∥2−2⟨a,b⟩{\lVert b-a \rVert}^2 = \langle b-a, b-a\rangle = \langle b,b\rangle - 2\langle a, b\rangle + \langle a, a\rangle = {\lVert a \rVert}^2 + {\lVert b \rVert}^2 -2\langle a, b\rangle

was für normierte Vektoren a,ba,b (also ∥a∥=1{\lVert a \rVert} = 1 und ∥b∥=1{\lVert b \rVert} = 1) zeigt, dass es einen engen Zusammenhang zwischen ⟨a,b⟩=∥a∥∥b∥cos⁡(∡(a,b))=cos⁡(∡(a,b))\langle a, b\rangle = {\lVert a \rVert}{\lVert b \rVert}\cos(\measuredangle(a,b)) = \cos(\measuredangle(a,b)) und d(a,b)=21−⟨a,b⟩d(a,b) = \sqrt{2}\sqrt{1-\langle a, b\rangle} gibt.

Von der linearen Situation abstrahiert man nun, und lässt eine beliebige Abbildung in einen Vektorraum mit Skalarprodukt zu.

Kernel

Man muss bei einem Kernel den Raum FF und die Abbildung ϕ\phi gar nicht kennen, weil für symmetrische positiv definite Funktionen κ ⁣:X×X→R\kappa \colon \mathcal{X} \times \mathcal{X} \to \mathbb{R} stets eine Konstruktion ϕ ⁣:X→F\phi \colon \mathcal{X} \to F existiert, sodass κ\kappa damit als Kernel dargestellt werden kann (Satz von Mercer).

Man spricht auch von einem Mercer-Kernel und nennt allgemeiner Funktionen κ\kappa, die nicht notwendig positiv definit oder symmetrisch sind, ebenfalls Kernel-Funktionen.

Man spricht allgemein von der Kernel-Methode, wenn man einen Algorithmus so umformuliert, dass er nur mit den Skalarprodukten der Feature-Vektoren arbeitet, und ersetzt diese dann durch eine Kernelfunktion.

Gausssche Kernel

Man beachte, dass wir hier nicht (x−μ)(x-\mu) mit (y−μ)(y-\mu) vergleichen müssen, weil diese die gleiche Differenz x−yx-y haben. Die sonst übliche Normierung entfällt ebenfalls, weil wir es nicht mit Wahrscheinlichkeiten zu tun haben, sondern mit einem Abstandsbegriff.

array([[1.00000000e+00, 5.99739246e-33, 8.16001067e-14, ..., 6.54905753e-16, 6.68458610e-26, 4.77998504e-22], [5.99739246e-33, 1.00000000e+00, 6.21026247e-61, ..., 1.97600107e-19, 4.23471174e-21, 1.23356941e-10], [8.16001067e-14, 6.21026247e-61, 1.00000000e+00, ..., 1.22257133e-15, 7.75803174e-22, 5.76000560e-28], ..., [6.54905753e-16, 1.97600107e-19, 1.22257133e-15, ..., 1.00000000e+00, 5.54264452e-02, 1.27386311e-02], [6.68458610e-26, 4.23471174e-21, 7.75803174e-22, ..., 5.54264452e-02, 1.00000000e+00, 1.22581743e-02], [4.77998504e-22, 1.23356941e-10, 5.76000560e-28, ..., 1.27386311e-02, 1.22581743e-02, 1.00000000e+00]], shape=(4000, 4000))

Nur, was fängt man jetzt mit dem Kernel an?

Zum Beispiel lineare Regression mit Ridge Regularisierung:

Dieselbe Anordnung aus Ring und Klumpen, eingefärbt nach der Vorhersage einer Kernel-Ridge-Regression. Der Ring ist durchgehend dunkel, der innere Klumpen hell, dazwischen liegen am Rand des Klumpens einige Punkte in einer Zwischenfarbe — dort ist die Vorhersage unentschieden.

Kernel PCA

Bei der Hauptachsentransformation werden die Eigenvektoren der Kovarianzmatrix berechnet. Man kann die Daten auch zuerst nichtlinear transformieren, bevor man das tut - oder aber die entsprechend transformierte Kovarianzmatrix verwenden.

Zwei Streudiagramme nebeneinander. Links die gewöhnliche Hauptkomponentenanalyse der Daten: Ring und Klumpen liegen unverändert ineinander, die PCA hat nichts getrennt. Rechts dieselbe Stichprobe nach einer Kernel-PCA: die innere Klasse ist auf einen schmalen Strich ganz links zusammengefallen, die äußere breitet sich rechts als Sichel aus — in dieser Darstellung sind die beiden Klassen durch eine senkrechte Gerade trennbar.

Genau genommen vergrößert Kernel-PCA zunächst die Anzahl an Dimensionen (mit der nichtlinearen Feature-Abbildung), um sie daraufhin linear auf Hauptkomponenten zu transformieren, sodass man wiederum unwichtige Dimensionen wegschmeißen kann. Die erste Hauptkomponente im Feature-Raum entspricht im ursprünglichen Beobachtungsraum keiner Geraden mehr, sondern einer nichtlinearen Kurve.