7.1 Merkmalsräume

Lineare Lernmaschinen sind einfach, schnell und mathematisch gut verstanden. Ihr großes Manko: Sie können nur lineare Zusammenhänge darstellen. Die Idee dieses Kapitels ist, die Daten zuerst in einen geeigneten Merkmalsraum (feature space) abzubilden und dort linear zu arbeiten. Was dort linear ist, ist im ursprünglichen Eingaberaum nichtlinear.

Mathematische Vorbereitung: das Skalarprodukt

📄 10_kern.pdf, Folie 4

Der gesamte Kernel-Trick dreht sich um das Skalarprodukt. Deshalb zuerst die Definition.

Ein Skalarprodukt oder inneres Produkt (inner product) auf einem Vektorraum $V$ ist eine symmetrische, positiv definite Bilinearform $\langle\cdot\,,\cdot\rangle : V\times V\to\mathbb{R}$. Das heißt:

1. bilinear, also linear in jedem Argument:

$$\langle x+y,\, z\rangle = \langle x, z\rangle + \langle y, z\rangle,\qquad \langle x,\, y+z\rangle = \langle x, y\rangle + \langle x, z\rangle,\qquad \langle x, \lambda y\rangle = \lambda\langle x, y\rangle = \langle \lambda x, y\rangle$$

2. symmetrisch: $\langle x, y\rangle = \langle y, x\rangle$
3. positiv definit: $\langle x, x\rangle \ge 0$, und $\langle x, x\rangle = 0$ genau dann, wenn $x = 0$.

Das kanonische Skalarprodukt (Standardskalarprodukt) ist das bekannte

$$(a_1, a_2, \dots)^\top (b_1, b_2, \dots) = a_1 b_1 + a_2 b_2 + \dots$$

Die Folien schreiben das Skalarprodukt als $\langle \mathbf{x}\cdot\mathbf{y}\rangle$, gemeint ist dasselbe wie $\langle \mathbf{x},\mathbf{y}\rangle$ oder $\mathbf{x}^\top\mathbf{y}$.

Ergänzung, nicht auf den Folien: Ein Skalarprodukt liefert automatisch eine Länge $\lVert x\rVert = \sqrt{\langle x, x\rangle}$, einen Abstand $\lVert x-y\rVert$ und einen Winkel über $\cos\angle(x,y) = \langle x,y\rangle / (\lVert x\rVert\,\lVert y\rVert)$. Das ist der Grund, warum man im Merkmalsraum „Geometrie betreiben“ kann (Trennebenen, Margin, Abstände), sobald man nur das Skalarprodukt kennt. Insbesondere gilt

$$\lVert x-y\rVert^2 = \langle x,x\rangle - 2\langle x,y\rangle + \langle y,y\rangle,$$

Abstände lassen sich also allein aus Skalarprodukten berechnen.

Lineare Maschinen

📄 10_kern.pdf, Folie 5

Eine lineare Lernmaschine hat die Form

$$f(\mathbf{x}) = \langle \mathbf{w}\cdot\mathbf{x}\rangle + b \qquad\text{mit}\quad \mathbf{x},\mathbf{w}\in\mathbb{R}^d,\ b\in\mathbb{R}.$$

• Klassifikation: $f(\mathbf{x}) = 0$ ist eine Trennebene (Hyperebene) im $\mathbb{R}^d$, die Klasse ergibt sich aus $\operatorname{sign} f(\mathbf{x})$. Beispiele: Perzeptron, lineare SVM (siehe Kapitel 6).
• Regression: $f$ beschreibt einen linearen Zusammenhang zwischen Inputvektoren $\mathbf{x}\in\mathbb{R}^d$ und skalaren Outputwerten $y_i$, z. B. bei der Kleinste-Quadrate-Regression (siehe Kapitel 4). Im Bild der Folie ist das die Ebene $y = b + w_1 x_1 + w_2 x_2$.

Grenzen des linearen Ansatzes

📄 10_kern.pdf, Folie 6

In vielen Anwendungen reichen lineare Maschinen, die direkt im Eingaberaum arbeiten, nicht aus:

• Nicht linear trennbare Daten: Liegt z. B. eine Klasse in einem Kreis und die andere drumherum, gibt es keine Gerade, die beide trennt.
• Nichtlineare Input-Output-Beziehungen bei der Regression, z. B. $y = x^2$.
• Oft ist es sinnvoller, nicht mit den Rohdaten zu arbeiten, sondern daraus Merkmale (features) abzuleiten, die leichter zu verarbeiten sind.
• Für manche Probleme ist es gar nicht sinnvoll, die Datenpunkte als Vektoren darzustellen, z. B. Genomsequenzen in der Bioinformatik (Strings unterschiedlicher Länge). Dazu mehr in 7.6.
• Je höher die Dimensionalität des Merkmalsraumes, d. h. je mehr Merkmale man aus den Daten ableitet, desto wahrscheinlicher lassen sich die Daten (linear) trennen.

Ergänzung, nicht auf den Folien: Der letzte Punkt lässt sich präzisieren (Satz von Cover): $n$ Punkte in allgemeiner Lage im $\mathbb{R}^m$ lassen sich für $n \le m+1$ in jeder beliebigen Zweiklassen-Aufteilung durch eine Hyperebene trennen. Mehr Dimensionen heißen also mehr Ausdrucksstärke, aber auch mehr Gefahr der Überanpassung (overfitting).

Merkmalsbildung und Einbettung

📄 10_kern.pdf, Folie 7

Ansatz: Statt auf den Eingabedaten wird die lineare Lernmaschine auf die extrahierten Merkmale angewandt. Bei geschickter Wahl der Merkmale wird das Problem dadurch linear trennbar bzw. linear modellierbar.

Die Merkmalsbildung beschreibt man durch eine Abbildung vom Eingaberaum in den Merkmalsraum, die sogenannte Einbettung (embedding, feature map):

$$\Phi : \mathbb{R}^d \to \mathbb{R}^m \qquad\text{mit}\quad \Phi(\mathbf{x}) = \begin{pmatrix}\phi_1(\mathbf{x})\\ \phi_2(\mathbf{x})\\ \vdots\end{pmatrix}.$$

• Jedes Merkmal entspricht einer Dimension im Merkmalsraum. Für jede Dimension muss eine eigene Abbildungsfunktion $\phi_i(\mathbf{x})$ definiert werden.
• Oft ist die Dimension $m$ des Merkmalsraumes viel höher als die des Eingaberaumes, manchmal sogar unendlich.

Genau der zweite Punkt ist das Problem, das der Kernel-Trick löst: Bei sehr vielen (oder unendlich vielen) Merkmalen kann man $\Phi(\mathbf{x})$ nicht mehr explizit ausrechnen oder speichern.

Beispiel: Monome zweiten Grades

📄 10_kern.pdf, Folie 8

Das Standardbeispiel aus der Vorlesung (nach Schölkopf): Die Daten liegen im $\mathbb{R}^2$, die roten Kreise innerhalb einer Ellipse, die blauen Kreuze außerhalb. Linear ist das nicht trennbar. Man bildet ab in den Raum der Monome zweiten Grades:

$$\Phi : \mathbb{R}^2 \to \mathbb{R}^3,\qquad \begin{pmatrix}x_1\\ x_2\end{pmatrix} \mapsto \begin{pmatrix}z_1\\ z_2\\ z_3\end{pmatrix} = \begin{pmatrix}\phi_1(\mathbf{x})\\ \phi_2(\mathbf{x})\\ \phi_3(\mathbf{x})\end{pmatrix} = \begin{pmatrix}x_1^2\\ \sqrt{2}\,x_1x_2\\ x_2^2\end{pmatrix}.$$

Warum wird das linear trennbar? Eine achsenparallele Ellipse im Eingaberaum hat die Gleichung

$$\frac{x_1^2}{a^2} + \frac{x_2^2}{c^2} = 1 .$$

Im Merkmalsraum mit $z_1 = x_1^2$, $z_3 = x_2^2$ lautet sie

$$\frac{1}{a^2}\, z_1 + 0\cdot z_2 + \frac{1}{c^2}\, z_3 = 1,$$

und das ist eine Ebene im $\mathbb{R}^3$. Punkte innerhalb der Ellipse liegen auf der einen Seite dieser Ebene, Punkte außerhalb auf der anderen. Eine lineare Maschine $f(\mathbf{z}) = \langle\mathbf{w}\cdot\mathbf{z}\rangle + b$ im Merkmalsraum mit $\mathbf{w} = (1/a^2,\, 0,\, 1/c^2)^\top$ und $b = -1$ trennt also perfekt. Eine schräg liegende Ellipse braucht zusätzlich den gemischten Term $x_1x_2$, also $z_2$.

Zahlenbeispiel (Kreis mit Radius 1, also $a = c = 1$):

Punkt $\mathbf{x}$	$\Phi(\mathbf{x}) = (x_1^2, \sqrt2 x_1x_2, x_2^2)$	$f = z_1 + z_3 - 1$	Klasse
$(0.5,\ 0.5)$	$(0.25,\ 0.354,\ 0.25)$	$-0.5$	innen (rot)
$(0,\ 0.8)$	$(0,\ 0,\ 0.64)$	$-0.36$	innen (rot)
$(1,\ 1)$	$(1,\ 1.414,\ 1)$	$+1$	außen (blau)
$(-1.5,\ 0)$	$(2.25,\ 0,\ 0)$	$+1.25$	außen (blau)

Die Entscheidungsfunktion ist im Merkmalsraum linear, im Eingaberaum aber eine Kreis- bzw. Ellipsengleichung, also nichtlinear.

Warum der Faktor $\sqrt{2}$?

Für die Trennbarkeit allein wäre der Faktor egal, eine lineare Maschine kann jede Koordinate beliebig skalieren. Der Faktor $\sqrt{2}$ sorgt aber dafür, dass das Skalarprodukt im Merkmalsraum eine besonders einfache Form bekommt: $\langle\Phi(\mathbf{x})\cdot\Phi(\mathbf{z})\rangle = \langle\mathbf{x}\cdot\mathbf{z}\rangle^2$. Das ist die Grundlage des Kernel-Tricks, siehe 7.3.

Fallstrick

„Höherdimensional“ heißt nicht automatisch „besser“. Die Merkmale müssen zum Problem passen: Mit Monomen 2. Grades trennt man Ellipsen, aber z. B. keine Spirale. Außerdem steigt mit der Dimension die Gefahr der Überanpassung, dagegen hilft bei der SVM die Margin-Maximierung (siehe 7.6).