7.4 Unendlichdimensionale Merkmalsräume

Der Kernel-Trick erlaubt sogar Merkmalsräume mit unendlich vielen Dimensionen. Damit das mathematisch sauber ist, braucht man einen kurzen Einschub über unendlichdimensionale Vektorräume.

Folgen als unendlichdimensionale Vektoren

📄 10_kern.pdf, Folie 17

Unendlichdimensionale Vektoren kann man als unendliche Zahlenfolgen auffassen:

$$\mathbf{x} = (x_1, x_2, x_3, \dots, x_i, \dots) \qquad\text{oder}\qquad \mathbf{y} = (y_1, y_2, y_3, \dots, y_i, \dots).$$

Unendliche Folgen verhalten sich in vieler Hinsicht genau wie Vektoren im $\mathbb{R}^d$, sie bilden einen Vektorraum $V$, den Folgenraum $l$:

1. Zwei Folgen kann man addieren und erhält wieder eine gültige Folge:

$$\mathbf{x}+\mathbf{y} = (x_1+y_1,\ x_2+y_2,\ \dots,\ x_i+y_i,\ \dots)\in V .$$

2. Eine Folge kann man mit einer Zahl multiplizieren und erhält wieder eine gültige Folge:

$$a\cdot\mathbf{x} = (ax_1,\ ax_2,\ \dots,\ ax_i,\ \dots)\in V .$$

Normen und der Raum $l_p$

📄 10_kern.pdf, Folie 18

Leider lassen sich viele bekannte Eigenschaften des $\mathbb{R}^d$ nicht ohne Weiteres auf den Folgenraum übertragen. Ohne Einschränkungen an die erlaubten Folgen kann man z. B. weder eine Länge (Norm) noch ein Skalarprodukt definieren. Beispiel (Ergänzung): Für $\mathbf{x} = (1, 1, 1, \dots)$ wäre $\sum_i x_i^2 = \infty$. Ebenso wenig kann man eine (konstruktiv angebbare) Basis für den allgemeinen Folgenraum finden.

Vorgehensweise: Man definiert eine Norm für Folgen,

$$\lVert\mathbf{x}\rVert_p = \Big(\sum_{i=1}^{\infty}\lvert x_i\rvert^p\Big)^{1/p},$$

und betrachtet nur Folgen, bei denen diese Summe endlich ist. Diese Folgen bilden wieder einen Vektorraum $l_p$: Addition und Multiplikation mit einer Zahl führen wieder auf eine Folge mit endlicher Norm. Man sagt, diese Teilmenge von Folgen bildet einen normierten linearen Raum (normed linear space).

Beispiele (Ergänzung):

Folge	$\lVert\cdot\rVert_2^2 = \sum x_i^2$	in $l_2$?
$(1, 1, 1, \dots)$	$\infty$	nein
$(1, \tfrac12, \tfrac13, \tfrac14, \dots)$	$\sum 1/i^2 = \pi^2/6$	ja
$(1, \tfrac12, \tfrac14, \tfrac18, \dots)$	$\sum 1/4^i = 4/3$	ja
$(1, \tfrac{1}{\sqrt2}, \tfrac{1}{\sqrt3}, \dots)$	$\sum 1/i = \infty$ (harmonische Reihe)	nein

Skalarprodukt auf $l_2$

📄 10_kern.pdf, Folie 19

Für den Folgenraum $l_2$ (Folgen mit endlicher Quadratsumme) kann man ein kanonisches Skalarprodukt definieren:

$$\langle\mathbf{x}\cdot\mathbf{y}\rangle = \sum_{i=1}^{\infty} x_iy_i .$$

Man kann zeigen, dass dieses Skalarprodukt für jede Kombination von Folgen aus $l_2$ endlich ist. Ergänzung – warum: Wegen $\lvert x_iy_i\rvert \le \tfrac12(x_i^2 + y_i^2)$ gilt $\sum\lvert x_iy_i\rvert \le \tfrac12\big(\lVert\mathbf{x}\rVert_2^2 + \lVert\mathbf{y}\rVert_2^2\big) \lt \infty$.

Analog zum Endlichdimensionalen mit den beiden Fällen $\langle x\cdot y\rangle = x^\top y$ und $\langle x\cdot y\rangle_S = x^\top S y$ (mit positiv definiter Matrix $S$) kann man auch hier ein verallgemeinertes Skalarprodukt mit einer Folge nichtnegativer Gewichte $\boldsymbol\lambda = (\lambda_1, \lambda_2, \dots, \lambda_i, \dots)$ definieren:

$$\langle\mathbf{x}\cdot\mathbf{y}\rangle_{\boldsymbol\lambda} = \sum_{i=1}^{\infty}\lambda_i x_i y_i .$$

Das entspricht $x^\top S y$ mit einer (unendlichen) Diagonalmatrix $S = \operatorname{diag}(\lambda_1, \lambda_2, \dots)$. Ergänzung: Für echte positive Definitheit braucht man streng genommen $\lambda_i \gt 0$; Komponenten mit $\lambda_i = 0$ spielen einfach keine Rolle und können weggelassen werden.

Lineare Maschinen in unendlichdimensionalen Merkmalsräumen

📄 10_kern.pdf, Folie 20

Jetzt sei die Einbettung $\Phi(\mathbf{x}) = (\phi_1(\mathbf{x}), \phi_2(\mathbf{x}), \dots)$ eine unendliche Folge von Merkmalen.

Voraussetzung für eine funktionierende lineare Maschine: Für alle denkbaren Inputwerte $\mathbf{x}$ muss

$$\sum_{i=1}^{\infty}\lambda_i\,\phi_i(\mathbf{x})^2 \lt \infty$$

gelten. Nur dann ist das (gewichtete) Skalarprodukt für alle Kombinationen von $\mathbf{x}$ und $\mathbf{y}$ endlich, und es existiert eine Kernfunktion

$$k(\mathbf{x},\mathbf{y}) = \langle\Phi(\mathbf{x})\cdot\Phi(\mathbf{y})\rangle = \sum_{i=1}^{\infty}\lambda_i\,\phi_i(\mathbf{x})\,\phi_i(\mathbf{y}) .$$

Der entscheidende Punkt: Durch die Kernfunktion lässt sich die Lernmaschine im Dualen durch eine endliche Anzahl von Termen darstellen:

$$f(\mathbf{x}) = \underbrace{\sum_{i=1}^{\infty}\lambda_i w_i\phi_i(\mathbf{x}) + b}_{\text{primal: unendlich viele Gewichte}} = \underbrace{\sum_{i=1}^{\ell}\alpha_i y_i\, k(\mathbf{x},\mathbf{x}_i) + b}_{\text{dual: } \ell \text{ Gewichte}} .$$

Primal bräuchte man unendlich viele Gewichte $w_i$, das ist nicht berechenbar. Dual sind es nur $\ell$ Gewichte $\alpha_i$, eines pro Trainingspunkt, und die unendliche Summe steckt komplett in der geschlossen auswertbaren Funktion $k$.

Beispiel: ein Kern mit unendlich vielen Merkmalen

Ergänzung, nicht auf den Folien. Der Gaußkern (RBF-Kern) aus 7.6 ist so ein Fall. In 1D mit $\sigma = 1$:

$$k(x,y) = e^{-\frac{(x-y)^2}{2}} = e^{-\frac{x^2}{2}}\, e^{-\frac{y^2}{2}}\, e^{xy} = e^{-\frac{x^2}{2}}\, e^{-\frac{y^2}{2}} \sum_{n=0}^{\infty}\frac{(xy)^n}{n!} = \sum_{n=0}^{\infty}\phi_n(x)\,\phi_n(y)$$

mit

$$\phi_n(x) = e^{-\frac{x^2}{2}}\,\frac{x^n}{\sqrt{n!}}, \qquad n = 0, 1, 2, \dots$$

Benutzt wurden $(x-y)^2 = x^2 - 2xy + y^2$ und die Exponentialreihe $e^t = \sum_n t^n/n!$. Der zugehörige Merkmalsraum enthält also (gedämpfte) Monome aller Grade, er ist unendlichdimensional. Trotzdem kostet $k(x,y)$ nur eine Subtraktion, ein Quadrat und eine Exponentialfunktion. Die Bedingung von oben ist erfüllt: $\sum_n\phi_n(x)^2 = e^{-x^2}e^{x^2} = 1 \lt \infty$.

Intuition

Ein unendlichdimensionaler Merkmalsraum klingt nach unbegrenzter Kapazität und damit nach garantierter Überanpassung. Warum das bei der SVM trotzdem funktioniert, steht am Ende von 7.6: Die Margin-Maximierung kontrolliert die Komplexität, nicht die Dimension.