Kernel-Methode mit Python
Einführung
Neulich habe ich in einem Seminar Kapitel 3 der Einführung von Professor Kenji Fukumizu in die Kernel-Methode gelesen. Da es im Seminar handgeschrieben wurde, möchte ich die Präsentationsmaterialien neu organisieren und eine kurze Einführung in die Kernel-Methode geben. Schließlich (abgesehen von der detaillierten Theorie) werden wir die Kernel-Hauptkomponentenanalyse in Python implementieren. Da mein Präsentationsbereich der Kernel mit positivem Wert in der ersten Hälfte und der letzte Teil der Implementierung war, gibt es in der Mitte einige wichtige Auslassungen, aber ich glaube nicht, dass es ein großes Problem gibt.
Hinweis ・ Atmosphäre ist wichtiger als Theorie. ・ Die nummerierten Elemente entsprechen den Nummern in Fukumizu-senseis Buch.
Vorausgesetztes Wissen ・ Einfache Statistik ·Lineare Algebra ・ Funktionsanalyse (Hilbert-Raumtheorie)
Inhaltsverzeichnis
- [Übersicht über die Kernel-Methode](#Übersicht über die Kernel-Methode)
- [Kernel mit normalem Wert](Kernel mit regulärem Wert) ・ [Regenerierter nuklearer Hügelgürtelraum](# Regenerierter nuklearer Hügelgürtelraum)
- [Kernel-Hauptkomponentenanalyse (Kernel PCA)](# Kernel-Hauptkomponentenanalyse)
- [Kanonische Korrelationsanalyse des Kernels (Kernel CCA)](# Kanonische Korrelationsanalyse des Kernels) ← Hinzufügen, wenn Sie Lust dazu haben.
(Viele Leute fragen sich vielleicht, warum sie keine Vektormaschinen unterstützen, aber das Seminar ging einfach nicht so weit. Ich denke, ich werde es selbst lesen, wenn ich Zeit habe.)
Übersicht über die Kernelmethode
Nehmen Sie als Beispiel die Hauptkomponentenanalyse. N Elemente der Dimension $ m $ $ X_1, ..., X_N \ in \ chi = \ mathbb {R} ^ m $, projiziert mit dem Einheitsvektor $ u $ nach $ u ^ \ mathsf { Suchen Sie nach $ u $ mit der p-ten größten Verteilung von T} X $. Dies wird als p-te Hauptkomponente bezeichnet, und die Dimensionskomprimierung und Rauschentfernung können durchgeführt werden, indem eine Achse kleiner als $ m $ genommen wird. Wenn Sie dies in eine Formel schreiben
\frac{1}{N}\sum_{i=1}^{N}\left\{u^{\mathsf{T}}X_{i}-\frac{1}{N}\left(\sum_{j=1}^{N}u^{\mathsf{T}}X_{j}\right)\right\}^{2}
Ist der p-te größte
Der Kern der obigen Berechnung ist das innere Produkt von $ u $ und $ X $. Im obigen Beispiel haben wir an $ \ mathbb {R} ^ m $ gedacht, also das normale innere Produkt $ \ langle u, X \ rangle_ {\ mathbb {R} ^ m} = u ^ \ mathsf {T} X $ Es wurde entschieden. Dies kann berechnet werden, selbst wenn die Daten $ X_i $ durch die nichtlineare Abbildung $ \ phi: \ chi → H $ an einen anderen Raum $ H $ gesendet werden, wenn das innere Produkt in diesem Raum bestimmt wird. In diesem Fall wird das innere Produkt von $ u $ und $ X $ $ \ langle u, X \ rangle_ {\ mathbb {R} ^ m} $ anstelle von $ f \ in H $ und $ \ langle f verwendet Dies bedeutet, dass die Hauptkomponentenanalyse als \ phi (X) \ rangle_H $ durchgeführt werden sollte.
Mit anderen Worten, die Kernel-Methode besteht darin, das Mapping $ \ phi $ zu verwenden, um zu einem anderen Raum zu springen und über das ursprüngliche Problem in diesem Raum nachzudenken. Bei der herkömmlichen Methode war es der Mainstream, nichtlineare Operationen unter Verwendung der Erweiterung $ (X, Y, Z ...) \ rightarrow (X ^ 2, Y ^ 2, Z ^ 2, XY ...) $ durchzuführen. Es gab jedoch das Problem, dass die Dimension der zu verarbeitenden Daten mit der Änderung der Zeit zunahm und der Rechenaufwand enorm wurde. Die Kernel-Methode ermöglicht es, nichtlineare Operationen mit einem Berechnungsbetrag auszuführen, der sich nicht wesentlich von normalen Problemen unterscheidet, indem eine Kernelfunktion verwendet wird, die das innere Produkt des vom Feature-Mapping $ \ phi $ gesendeten Raums effizient berechnet.
Das obige Ziel besteht darin, die Feature-Zuordnung $ \ phi $ und den Raum $ H $ erfolgreich zu definieren.
Kernel mit positivem Wert
Der Datenraum sei $ \ chi $ und definiere die Feature-Zuordnung $ \ phi $ als $ \ phi: \ chi → H $. Wobei $ H $ ein innerer Produktraum mit einem inneren Produkt $ \ langle ·, · \ rangle_H $ ist.
Es wäre schön, wenn das innere Produkt leicht mit einer Funktion $ k (x, y) = \ langle \ phi (x), \ phi (y) \ rangle_H $ berechnet werden könnte. Auf diese Weise können Sie nur $ k $ anzeigen, ohne die direkte Darstellung von $ \ phi $ und $ H $ zu berücksichtigen (auf die in dem später beschriebenen konkreten Beispiel eingegangen wird), und die Berechnungskosten betragen $ \ phi $. Sie können sehen, dass es nicht darauf ankommt.
Hier definieren wir einen Kernel mit positivem Wert und betrachten die Eigenschaften, die er erfüllt.
Def Positive Value Kernel
Wenn die Funktion $ k: \ chi × \ chi → \ mathbb {R} $ die folgenden zwei Eigenschaften erfüllt, wird $ k $ als Kernel mit positivem Wert für $ \ chi $ bezeichnet.
-Symmetrie: $ k (x, y) = k (y, x) $ für jedes $ x, y \ in \ chi $ · Positiver Wert: $ \ sum_ {i, j für jedes $ n \ in \ mathbb {N}, x_1 ... x_N \ in \ chi, c_1 ... c_N \ in \ mathbb {R} $ = 1} ^ {n} c_ic_jk (x_i, x_j) \ geq0 $
Die Kanonizität unter der Annahme der Symmetrie entspricht der Definition des Halbrechtecks in einer $ N × N $ -Quadratmatrix, in der die $ ij $ -Komponente $ k (x_i, x_j) $ ist. Der Grund für das Schreiben eines positiven Wertes ist, dass die obige Definition gemäß Konvention als regulärer Wert bezeichnet wird.
Prop2.1
Die folgenden Eigenschaften gelten für den Kernel mit positivem Wert.
(1)
proof(2)
A = \left(\begin{matrix}
k(x,x) & k(x,y)\\k(x,y) & k(y,y) \end{matrix}
\right)
Ist eine halbpositive symmetrische Matrix mit festem Wert, und alle Eigenwerte sind reell und nicht negativ. Wenn Sie also die Matrixformel diagonal betrachten, ist $ det (A) \ geq0 $. Wie definiert, kann auch der Matrixausdruck berechnet und die nicht negative Ungleichung transformiert werden.
Prop2.2
Der Kernel mit positivem Wert wird für die folgenden Operationen geschlossen:
Sei $ k_i $ ein Kernel mit positivem Wert,
(1) $ ak_i + bk_j $ für $ a, b \ in \ mathbb {R_ {\ geq0}} $
(2)
proof:(2) Da es ausreichend ist, wenn die $ N × N $ -Matrix, deren Komponente $ k_ik_j $ ist, ein halbfester Wert ist, betrachten Sie das Adamal-Produkt zweier Matrizen, deren Komponenten $ k_i und k_j $ sind, und diagonalisieren Sie eine der Matrizen auf einen positiven Wert. Ersatz in der Definitionsformel des Geschlechts.
Prop2.6 Sei $ V ein innerer Produktraum mit einem inneren Produkt \ langle ・, ・ \ rangle_V $. Gegeben sei $ \ phi: \ chi \ rightarrow V, x \ mapsto \ phi (x) $, $ k (x, y) = \ langle \ phi (x), \ phi (y) \ rangle_V $ Ist ein Kernel mit positivem Wert.
proof Sie kann gemäß der Definition des Kernels mit positivem Wert berechnet werden.
Ich wollte, dass das Feature-Mapping $ \ phi $ diese Eigenschaften erfüllt. Wenn Sie $ V $ entsprechend einstellen und ein Mapping vorbereiten, sollten Sie es leicht mit dem Kernel $ k $ mit positivem Wert berechnen können. Wenn jedoch $ k $ definiert ist, wird $ V $ eindeutig bestimmt, und wie oben erwähnt, ist der direkte Ausdruck von $ \ phi $ in der tatsächlichen Berechnung nicht erforderlich. Daher sollte der Kernel mit positivem Wert $ k $ bestimmt werden. Ich verstehe das.
Regenerierter nuklearer Hügelgürtelraum
Hier bestätigen wir, dass es eine Eins-zu-Eins-Entsprechung zwischen dem positiven Wertkern $ k $ und dem inneren Produktraum $ H $ gibt, der bestimmte Eigenschaften hat.
Def Regeneration Nuclear Hilbert Space
Der gesamte innere Produktraum $ H $ heißt Hilbert-Raum. Ein Hügelgürtelraum $ H $, der aus Funktionen auf $ \ chi $ mit $ \ chi $ als Menge besteht und die folgenden Eigenschaften erfüllt, wird als regenerierter nuklearer Hügelgürtelraum bezeichnet. -Playability: $ \ forall x \ in \ chi, \ forall f \ in H, \ existiert k_x \ in H s.t. \ langle f, k_x \ rangle_H = f (x) $
Für $ k_x \ in H $, das oben definiert wurde, wird der durch $ k (y, x) = k_x (y) $ bestimmte Kernel $ k $ als Regenerationskern von $ H $ bezeichnet.
prop2.7 Regenerierter Kern auf $ \ chi $ Regenerierter Kern im Hilbert-Raum $ H $ $ k $ ist ein Kernel mit positivem Wert auf $ \ chi $, und der regenerierte Kern in $ H $ ist einzigartig.
proof Da es transformiert werden kann als $ k (x, y) = k_y (x) = \ langle k_y, k_x \ rangle_H = \ langle k (・, y), k (・, x) \ rangle_H $ Sie können $ \ sum_ {i, j = 1} ^ {n} c_ic_jk (x_i, x_j) \ geq0 $ sehen. Die Eindeutigkeit kann gezeigt werden, indem $ k und \ override {k} $ als regenerierte Kerne auf $ H $ verwendet werden und Symmetrie und $ k = \ override {k} $ verwendet werden.
prop2.8 $||k(・,x)||_H=\sqrt{k(x,x)} $
proof Das Quadrat der linken Seite kann unter Verwendung der Reproduzierbarkeit berechnet werden.
prop2.11 Für einen Kernel mit positivem Wert $ k $ auf der Menge $ \ chi $ existiert ein regenerierter nuklearer Hilbert-Raum auf $ \ chi $, der die folgenden drei Eigenschaften erfüllt, eindeutig. (1) $ \ für alle x \ in \ chi, k (・, x) \ in H $ (2) Der um $ k (・, x) (x \ in \ chi) $ gestreckte Unterraum (lineares Paket) ist innerhalb von $ H $ dicht (3) $ k $ ist der Regenerationskern von $ H $
Wenn prop2.7 und prop2.11 kombiniert werden, ist ersichtlich, dass es eine Eins-zu-Eins-Entsprechung zwischen dem Kernel mit positivem Wert und dem regenerierten nuklearen Hilbert-Raum gibt.
Wenn hier die Feature-Zuordnung $ \ phi: \ chi → H $ als $ x \ mapsto k (・, x) $ definiert ist, wenn die Reproduzierbarkeit verwendet wird,
\begin{align}
&\begin{split}
\langle\phi(x),\phi(y)\rangle_H &= \langle k(・,x), k(・,y)\rangle_H \\
&= \langle k_x, k_y \rangle_H \\
&= k_x(y) \\
&= k(y,x) \\
&= k(x,y)
\end{split}\\
\end{align}
Also fand ich heraus, dass das innere Produkt, das ich berechnen wollte, mit dem positiven Wert Kernel $ k $ berechnet werden kann.
Hier sind einige häufig verwendete Beispiele für Kernel mit positivem Wert.
-Linearer Kern (normales euklidisches inneres Produkt)
k_0(x,y) = x^\mathsf{T} y
・ Exponentieller Typ
k_E(x,y)=exp(\beta x^\mathsf{T} y) \ (\beta>0)
・ Gauß-Kernel
k_G(x,y) =exp \left(-\frac{\|x-y\|^2}{2 \sigma^2} \right)
Kernel-Hauptkomponentenanalyse
Ich habe die Theorie kurz vorgestellt, es handelt sich also um ein Anwendungsbeispiel.
Normale Hauptkomponentenanalyse
\frac{1}{N}\sum_{i=1}^{N}\left\{u^{\mathsf{T}}X_{i}-\frac{1}{N}\left(\sum_{j=1}^{N}u^{\mathsf{T}}X_{j}\right)\right\}^{2}
Feature-Mapping in der Kernel-Hauptkomponentenanalyse
\frac{1}{N}\sum_{i=1}^{N}\left\{\langle f,\phi\left(X_{i}\right)\rangle_{H}\ -\ \frac{1}{N}\left(\sum_{j=1}^{N}\left\langle f,\ \phi\left(X_{j}\right)\right\rangle_H \right)\right\}^{2}
Wenn Sie es mit $ \ tilde {\ phi} (X_i) = \ phi (X_i) - \ frac {1} {N} \ sum_ {i = j} ^ {N} \ phi (X_j) $ zentralisieren
\frac{1}{N}\sum_{i=1}^{N}\left(\langle f,\ \tilde{\phi}\left(X_{i}\right)\rangle_{H} \right)^{2}
Es stellt sich heraus, dass Sie an $ f $ denken sollten, das maximiert.
$ ||f||_{H}=1$Denn es ist
Span\left\{\tilde{\phi}\left(X_{1}\right),...,\tilde{\phi}\left(X_{N}\right)\right\} \subset H
Sie können es sich als ein Element von vorstellen. Deshalb,
f = \sum_{i=1}^{N}\alpha_{i}\tilde{\phi}\left(X_{i}\right)
Kann ausgedrückt werden als. Mit anderen Worten, das innere Produkt $ \ angle f, \ tilde {\ phi} (X_ {i}) \ rangle_H $ ist $ \ langle \ tilde {\ phi} (X_i), \ tilde {\ phi} (X_j) \ rangle Es kann durch eine lineare Kombination von $ dargestellt werden, und wenn die Zentralisierung von $ \ tilde {\ phi} $ vorgenommen wird, ist dies $ k (X_i, X_j) = \ langle \ phi (X_i), \ phi (X_j) \ rangle $. Es kann durch eine lineare Kombination von k $ dargestellt werden, und der Koeffizient kann auch unter Verwendung von $ \ alpha $ dargestellt werden. Daher wird durch Finden von $ \ alpha $ $ f $ als Funktion von $ H $ bestimmt, und es kann eine Maximierung erreicht werden.
Hier der Einfachheit halber
\tilde{k}(X_i,X_j)= \langle \tilde{\phi}(X_i), \tilde{\phi}(X_j) \rangle_H
Sei $ \ tilde {K} $ die Matrix mit $ \ tilde {k} (X_i, X_j) $ als $ ij $ -Komponente. Dies wird als zentralisierte Grammmatrix bezeichnet.
Das zu maximierende Problem kann wie folgt transformiert und auf das verallgemeinerte Eigenwertproblem reduziert werden.
\begin{align}
&\begin{split}
\frac{1}{N}\sum_{i=1}^{N}\left(\langle f,\ \tilde{\phi}\left(X_{i}\right)\rangle_{H} \right)^{2}
&= \frac{1}{N}\sum_{i=1}^{N}\left\{\sum_{j=1}^{N}\alpha_j\tilde{k}(X_j,X_i)\right\}^{2}\\
&=\frac{1}{N}\sum_{i=1}^{N}\left\{\sum_{j=1}^{N}\sum_{k=1}^{N}\alpha_{j}\alpha_{k}\tilde{k}(X_j,X_i)\tilde{k}(X_k,X_i)\right\} \\
&= \frac{1}{N}\sum_{j=1}^{N}\sum_{k=1}^{N}\left\{\alpha_{j}\alpha_{k}\sum_{i=1}^{N}\tilde{k}(X_j,X_i)\tilde{k}(X_i,X_k)\right\}\\
&= \frac{1}{N}\sum_{j=1}^{N}\sum_{k=1}^{N}\left(\alpha_{j}\alpha_{k}\tilde{K}_{jk}^2\right)\\
&=\frac{1}{N}\alpha^\mathsf{T} \tilde{K}^2 \alpha\\
\end{split}\\
&\begin{split}
||f||_H &= \langle f, f \rangle \\
&= \langle \sum_{i=1}^{N}\alpha_{i}\tilde{\phi}\left(X_{i}\right), \sum_{j=1}^{N}\alpha_{j}\tilde{\phi}\left(X_{j}\right) \rangle \\
&= \sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i \alpha_j \langle \tilde{\phi}(X_i), \tilde{\phi}(X_j) \rangle \\
&= \alpha^\mathsf{T} \tilde{K} \alpha
\end{split}\\
\end{align}
Aus dem Obigen ergibt sich das Maximierungsproblem
\newcommand{\argmax}{\mathop{\rm arg~max}\limits}
\argmax_{\alpha \in \mathbb{R}^N} \, \alpha^\mathsf{T} \tilde{K}^2 \alpha \ \ s.t. \ \alpha^\mathsf{T} \tilde{K} \alpha = 1
Da $ \ tilde {K} $ eine halbregelmäßige symmetrische Matrix mit konstantem Wert ist, sind bei der Durchführung der Eigenwertzerlegung (Diagonalisierung) $ N $ der vertikalen Vektoren $ u ^ i $ in einer einheitlichen Matrix $ U $ und einer diagonalen Matrix $ angeordnet Verwenden von \ Lambda = diag (\ lambda_1, ..., \ lambda_N) \ (\ lambda_1 \ geq \ lambda_2 \ geq ... \ geq \ lambda_N \ geq 0) $,
\tilde{K} = U \Lambda U^{*}
Kann zerlegt werden. $ \ Tilde {K} ^ 2 = U \ Lambda ^ 2 U ^ {*} $
\alpha^\mathsf{T} \tilde{K}^2 \alpha = \sum_{i=1}^{N} (\alpha^\mathsf{T} u^i)^2 \lambda_i^2
Unter Berücksichtigung von $ \ lambda_1 \ geq \ lambda_2 \ geq ... \ geq \ lambda_N \ geq 0 $ liegt das p-te größte $ \ alpha $ daher bei $ \ alpha \ parallel u ^ p $. Die Länge sollte angepasst werden, um $ \ alpha ^ \ mathsf {T} \ tilde {K} \ alpha = 1 $ zu erfüllen. Wenn Sie $ \ alpha = c_p u ^ p $ setzen, beachten Sie, dass $ u ^ i $ ein Spaltenvektor einer einheitlichen Matrix ist.
\begin{align}
&\begin{split}
\alpha^\mathsf{T} \tilde{K} \alpha &= \sum_{i=1}^{N} (c_p u^{p^{\mathsf{T}}} u^i)^2 \lambda_i \\
&= c_p^2 \lambda_p
\end{split}\\
\end{align}
Daher ist $ c_p = \ frac {1} {\ sqrt {\ lambda_p}} $. Daher $ f $ (p-te Spindel), die die Varianz zur p-ten größten macht
f^p = \sum_{i=1}^{N}\frac{1}{\sqrt{\lambda_p}} u_i^p \tilde{\phi}(X_i)
Und die p-te Hauptkomponente der Daten $ X_i $ ist
\begin{align}
&\begin{split}
\langle \tilde{\phi}(X_i), f^p \rangle_H &= \sum_{j=1}^N \frac{1}{\sqrt{\lambda_p}} u_j^p \langle \tilde{\phi}(X_i), \tilde{\phi}(X_j) \rangle_H \\
&= \sum_{j=1}^N \frac{1}{\sqrt{\lambda_p}} u_j^p \tilde{K}_{ij} \\
&= \sum_{j=1}^N \frac{1}{\sqrt{\lambda_p}} u_j^p \sum_{k=1}^N \lambda_k u_i^k u_j^k \\
&= \frac{1}{\sqrt{\lambda_p}} \sum_{k=1}^N \lambda_k u_i^k \sum_{j=1}^N u_j^p u_j^k \\
&= \frac{1}{\sqrt{\lambda_p}} \sum_{k=1}^N \lambda_k u_i^k \delta(p,k) \\
&= \sqrt{\lambda_p} u_i^p
\end{split}\\
\end{align}
Mit anderen Worten ist es ausreichend, den Eigenwert und die Einheitsmatrix zu kennen, wenn die Matrix $ \ tilde {K} $ mit $ \ tilde {k} (X_i, X_j) $ als $ ij $ -Komponente in Eigenwerte zerlegt wird.
Implementieren Sie das Obige mit Python. Weindaten (http://archive.ics.uci.edu/ml/datasets/Wine) Benutzen. Wir werden den Gaußschen Kernel für die Kernelfunktionen verwenden.
import numpy as np
import matplotlib.pyplot as plt
#Daten lesen
wine = np.loadtxt("wine.csv", delimiter=",")
N = wine.shape[0] #178
labels = np.copy(wine[:,0]).flatten()
wine = wine[:, 1:]
#Standardisierung
mean = wine.mean(axis=0)
wine -= mean
std = wine.std(axis=0)
wine /= std
def kernel(x,y, σ=4): return np.exp(-((x-y)**2).sum() / (2*σ**2))
#Berechnung der zentralisierten Grammmatrix K.
K = np.zeros(shape=(N,N))
for i,j in np.ndindex(N,N):
K[i,j] = kernel(wine[i,:], wine[j,:])
Q = np.identity(N) - np.full(shape=(N,N), fill_value=1/N)
K_tilde = Q @ K @ Q
#Einzigartige Wertzerlegung
λs, us = np.linalg.eig(K_tilde)
#In absteigender Reihenfolge nach eindeutigem Wert sortieren
λ_index = np.argsort(λs)
D = np.zeros(shape=(N))
U = np.zeros(shape=(N,N))
for i, index in enumerate(λ_index[::-1]):
D[i] = λs[index]
U[:,i] = us[:,index]
#N-te Hauptkomponente der Daten
X_1 = np.sqrt(D[0]) * U[:,0]
X_2 = np.sqrt(D[1]) * U[:,1]
#Diagramm erstellen
clasters = dict([(i,[[],[]]) for i in range(1,4)])
for i,label in enumerate(labels):
clasters[label][0].append(X_1[i])
clasters[label][1].append(X_2[i])
for label,marker in zip(range(1,4), ["+","s","o"]):
plt.scatter(clasters[label][0], clasters[label][1], marker=marker)
plt.show()
Sie können sehen, dass es gut klassifiziert ist. Übrigens ändert sich die Form des Diagramms stark, je nachdem, wie Sie die Kernelfunktion auswählen. Selbst mit demselben Gaußschen Kernel ändert sich dies abhängig von den Hyperparametereinstellungen, sodass Sie so etwas wie eine Rastersuche durchführen können.
Verweise
Kenji Fukumizu, Einführung in die Kernel-Methode [Datenanalyse mit positivem Festwertkern], Asakura Shoten, 2010
Recommended Posts