7.5 Mercer-Kerne

Die umgekehrte Frage

📄 10_kern.pdf, Folie 22

• Bisher: Wie kann man aus einer gegebenen Abbildung $\Phi$ in den Merkmalsraum einen Kern konstruieren? (Antwort: $k(\mathbf{x},\mathbf{y}) = \langle\Phi(\mathbf{x})\cdot\Phi(\mathbf{y})\rangle$ ausrechnen und vereinfachen, siehe 7.3.)
• Umgekehrte Frage: Wie kann man überprüfen, ob eine beliebige zweistellige Funktion $k(\mathbf{x},\mathbf{y})$ eine Kernfunktion ist, ob es also irgendein $\Phi$ gibt mit $k(\mathbf{x},\mathbf{y}) = \langle\Phi(\mathbf{x})\cdot\Phi(\mathbf{y})\rangle$? Antwort: das Mercer-Theorem.
• Durch das Mercer-Theorem kann man Kernfunktionen konstruieren, ohne die Einbettung zu kennen, z. B. durch Anwendung bestimmter Kombinationsregeln (siehe 7.6).

Warum ist das wichtig? Wenn man irgendeine „Ähnlichkeitsfunktion“ in die SVM steckt, die kein echtes Skalarprodukt ist, gibt es keinen Merkmalsraum, in dem die SVM eine Trennebene sucht. Die ganze Geometrie (Margin, Abstände) bricht zusammen, und das Optimierungsproblem ist eventuell nicht mehr konvex (Ergänzung: der quadratische Term $\sum\alpha_i\alpha_jy_iy_jk(\mathbf{x}_i,\mathbf{x}_j)$ kann dann negativ werden, das Problem ist nach unten unbeschränkt oder hat lokale Optima).

Notwendige Voraussetzung: Symmetrie. Weil das Skalarprodukt symmetrisch ist, muss auch jeder Kern symmetrisch sein:

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

Symmetrie ist notwendig, aber nicht hinreichend.

Das Mercer-Theorem

📄 10_kern.pdf, Folie 23

Mercer-Theorem

Sei $k(\mathbf{x},\mathbf{y})$ eine stetige und symmetrische Funktion auf $X\times X$, wobei $X$ eine kompakte Teilmenge des $\mathbb{R}^d$ ist.

Falls

$$\int_{X\times X} k(\mathbf{x},\mathbf{y})\, f(\mathbf{x})\, f(\mathbf{y})\; d\mathbf{x}\, d\mathbf{y} \ \ge\ 0$$

für alle quadratisch integrierbaren Funktionen $f(\mathbf{x})$ gilt, so kann man $k(\mathbf{x},\mathbf{y})$ durch folgende Reihenentwicklung darstellen:

$$k(\mathbf{x},\mathbf{y}) = \sum_{i=1}^{\infty}\lambda_i\,\phi_i(\mathbf{x})\,\phi_i(\mathbf{y})\qquad\text{mit}\quad\lambda_i\ge 0 .$$

D. h. $k(\mathbf{x},\mathbf{y})$ ist in diesem Fall eine gültige Kernfunktion mit Einbettung $\Phi = \lbrace\phi_i(\mathbf{x})\rbrace_{i=1}^{\infty}$ und Skalarprodukt $\sum_{i=1}^{\infty}\lambda_i x_i y_i$.

Das ist genau die Form aus 7.4: ein gewichtetes Skalarprodukt im Folgenraum mit nichtnegativen Gewichten $\lambda_i$.

Begriffe zur Bedingung:

• quadratisch integrierbar (square integrable): $\int_X f(\mathbf{x})^2\, d\mathbf{x} \lt \infty$.
• Die Integralbedingung heißt Mercer-Bedingung. Sie ist das kontinuierliche Gegenstück zu $\mathbf{v}^\top K\mathbf{v}\ge 0$: Statt über eine Summe $\sum_{i,j}v_iv_jK_{ij}$ wird über ein Doppelintegral mit einer Funktion $f$ als „unendlich langem Vektor“ summiert.

Ergänzung, nicht auf den Folien: Die $\phi_i$ und $\lambda_i$ sind die Eigenfunktionen und Eigenwerte des Integraloperators $(T_kf)(\mathbf{x}) = \int_X k(\mathbf{x},\mathbf{y})f(\mathbf{y})\,d\mathbf{y}$, also $T_k\phi_i = \lambda_i\phi_i$. Das ist die unendlichdimensionale Version der Eigenzerlegung $K = \sum_i\lambda_i\mathbf{u}_i\mathbf{u}_i^\top$ einer symmetrischen Matrix. Die Mercer-Bedingung sagt: Alle Eigenwerte sind nichtnegativ.

Positiv definite Kerne und die Gram-Matrix

📄 10_kern.pdf, Folie 24

Die Mercer-Bedingung ist mit Integralen unhandlich. Aus dem Mercer-Theorem folgt eine praktischere, äquivalente Charakterisierung über endliche Punktmengen:

Positiv definite Kerne

$k(\mathbf{x},\mathbf{y})$ ist genau dann eine gültige Kernfunktion, wenn

• für jede endliche Menge von Trainingsdatenpunkten $\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_l\in X$
• und für jeden Vektor $\mathbf{v}\in\mathbb{R}^l$

$$\mathbf{v}^\top K\mathbf{v} \ge 0\qquad\text{mit}\quad K_{ij} = k(\mathbf{x}_i,\mathbf{x}_j)$$

gilt.

D. h. die Gram-Matrix (Gram matrix, auch Kernmatrix) $K$ muss auf jeder denkbaren Trainingsmenge positiv semidefinit (positive semidefinite, psd) sein.

Ausgeschrieben für $l$ Punkte:

$$K = \begin{pmatrix} k(\mathbf{x}_1,\mathbf{x}_1) & k(\mathbf{x}_1,\mathbf{x}_2) & \cdots & k(\mathbf{x}_1,\mathbf{x}_l)\\ k(\mathbf{x}_2,\mathbf{x}_1) & k(\mathbf{x}_2,\mathbf{x}_2) & \cdots & k(\mathbf{x}_2,\mathbf{x}_l)\\ \vdots & \vdots & \ddots & \vdots\\ k(\mathbf{x}_l,\mathbf{x}_1) & k(\mathbf{x}_l,\mathbf{x}_2) & \cdots & k(\mathbf{x}_l,\mathbf{x}_l) \end{pmatrix}.$$

Begriffsfalle: „positiv definit“

Im Kern-Kontext heißt ein Kern traditionell positiv definit, wenn seine Gram-Matrizen positiv semidefinit sind ($\mathbf{v}^\top K\mathbf{v}\ge 0$, Gleichheit erlaubt). Die Folie verwendet genau diese Konvention. In der linearen Algebra hieße „positiv definit“ dagegen $\mathbf{v}^\top K\mathbf{v} \gt 0$ für $\mathbf{v}\ne 0$. In der Prüfung: Die Gram-Matrix muss positiv semidefinit sein.

Warum ist die Bedingung notwendig?

Ergänzung, nicht auf den Folien – kurze Herleitung, sehr prüfungsnah. Ist $k(\mathbf{x},\mathbf{y}) = \langle\Phi(\mathbf{x})\cdot\Phi(\mathbf{y})\rangle$, dann gilt für beliebige Punkte und beliebiges $\mathbf{v}$:

$$\mathbf{v}^\top K\mathbf{v} = \sum_{i,j} v_iv_j\,\langle\Phi(\mathbf{x}_i)\cdot\Phi(\mathbf{x}_j)\rangle = \Big\langle\sum_i v_i\Phi(\mathbf{x}_i)\cdot\sum_j v_j\Phi(\mathbf{x}_j)\Big\rangle = \Big\lVert\sum_i v_i\Phi(\mathbf{x}_i)\Big\rVert^2 \ \ge\ 0 .$$

Eine quadrierte Länge kann nicht negativ sein. Die Umkehrung (psd auf allen endlichen Mengen ⇒ es gibt ein $\Phi$) ist der eigentlich tiefe Teil und folgt aus dem Mercer-Theorem.

Zahlenbeispiel 1: Gram-Matrix des linearen Kerns

Drei Punkte $\mathbf{x}_1 = (1,0)$, $\mathbf{x}_2 = (0,1)$, $\mathbf{x}_3 = (1,1)$, linearer Kern $k(\mathbf{x},\mathbf{y}) = \mathbf{x}^\top\mathbf{y}$:

$$K = \begin{pmatrix} 1 & 0 & 1\\ 0 & 1 & 1\\ 1 & 1 & 2\end{pmatrix}.$$

• Symmetrisch ✔, Diagonale nichtnegativ ✔ (das sind $\lVert\mathbf{x}_i\rVert^2$).
• Mit $\mathbf{v} = (1, 1, -1)^\top$: $K\mathbf{v} = (0, 0, 0)^\top$, also $\mathbf{v}^\top K\mathbf{v} = 0$. Das passt: $\mathbf{x}_1 + \mathbf{x}_2 - \mathbf{x}_3 = \mathbf{0}$, die Punkte sind linear abhängig. $K$ ist also positiv semidefinit, aber nicht positiv definit (im Sinn der linearen Algebra). Das ist erlaubt.
• Eigenwerte (zur Kontrolle): $0,\ 1,\ 3$, alle nichtnegativ ✔.

Zahlenbeispiel 2: der Polynomkern

Gleiche Punkte, $k(\mathbf{x},\mathbf{y}) = (\mathbf{x}^\top\mathbf{y})^2$, man quadriert also einfach jeden Eintrag von oben:

$$K = \begin{pmatrix} 1 & 0 & 1\\ 0 & 1 & 1\\ 1 & 1 & 4\end{pmatrix},\qquad \mathbf{v} = (1, 1, -1)^\top:\ \ \mathbf{v}^\top K\mathbf{v} = 1 + 1 + 4 - 2 - 2 = 2 \gt 0 .$$

Im Merkmalsraum sind $\Phi(\mathbf{x}_1) = (1,0,0)$, $\Phi(\mathbf{x}_2) = (0,0,1)$, $\Phi(\mathbf{x}_3) = (1,\sqrt2,1)$ linear unabhängig. Das ist der Effekt der nichtlinearen Einbettung: Was im Eingaberaum abhängig war, wird im Merkmalsraum unabhängig, und die Daten werden „leichter trennbar“.

Zahlenbeispiel 3: ein Nicht-Kern

Ist das quadrierte Abstandsmaß $k(\mathbf{x},\mathbf{y}) = \lVert\mathbf{x}-\mathbf{y}\rVert^2$ ein Kern? Es ist symmetrisch. Aber nimm in 1D die Punkte $x_1 = 0$, $x_2 = 1$:

$$K = \begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix},\qquad \mathbf{v} = (1, -1)^\top:\ \ \mathbf{v}^\top K\mathbf{v} = 0 - 1 - 1 + 0 = -2 \lt 0 .$$

Kein gültiger Kern. Das ist auch anschaulich: Ein Abstand ist ein Unähnlichkeitsmaß (groß für verschiedene Punkte), ein Kern dagegen ein Ähnlichkeitsmaß. Ein schneller Test: Für jeden gültigen Kern ist $k(\mathbf{x},\mathbf{x}) = \lVert\Phi(\mathbf{x})\rVert^2 \ge 0$ und (Cauchy-Schwarz) $k(\mathbf{x},\mathbf{y})^2 \le k(\mathbf{x},\mathbf{x})\,k(\mathbf{y},\mathbf{y})$. Hier ist $k(0,0) = 0$, aber $k(0,1) = 1$, Widerspruch.

Checkliste: Ist $k$ ein Kern?

1. Symmetrisch? Wenn nein: kein Kern.
2. Diagonale $k(\mathbf{x},\mathbf{x})\ge 0$ und $k(\mathbf{x},\mathbf{y})^2\le k(\mathbf{x},\mathbf{x})k(\mathbf{y},\mathbf{y})$? Wenn verletzt: kein Kern. (Ergänzung)
3. Gegenbeispiel suchen: zwei oder drei Punkte, Gram-Matrix aufstellen, $\mathbf{v}$ mit $\mathbf{v}^\top K\mathbf{v}\lt 0$ finden (z. B. Eigenvektor zum negativen Eigenwert).
4. Positiv zeigen: explizites $\Phi$ angeben (7.3) oder $k$ aus bekannten Kernen mit den Kombinationsregeln zusammensetzen.

Fallstrick

Dass die Gram-Matrix auf deinem Datensatz psd ist, beweist nicht, dass $k$ ein Kern ist. Die Bedingung muss für jede endliche Punktmenge gelten. Umgekehrt genügt ein Gegenbeispiel, um zu zeigen, dass $k$ kein Kern ist.