Entspricht Kernel-PCA mit linearem Kernel Standard-PCA?

Wenn ich in der Kernel-PCA einen linearen Kernel , wird sich das Ergebnis von der normalen linearen PCA unterscheiden ? Unterscheiden sich die Lösungen grundlegend oder gibt es einen genau definierten Zusammenhang? $K(\mathbf{x},\mathbf{y}) = \mathbf x^\top \mathbf y$

pca kernel-trick tgoossens
quelle

Antworten:

Zusammenfassung: Kernel-PCA mit linearem Kernel entspricht genau der Standard-PCA.

Sei die zentrierte Datenmatrix der Größe mit Variablen in Spalten und Datenpunkten in Zeilen. Dann ist die Kovarianzmatrix gegeben durch , ihre Eigenvektoren sind Hauptachsen und Eigenwerte sind PC-Varianzen. Gleichzeitig kann man die sogenannte Gram-Matrix der Größe . Es ist leicht zu sehen , dass es die gleichen Eigenwerte (dh PC - Varianzen) bis zum $\mathbf{X}$ $N \times D$ $D$ $N$ $D \times D$ $\mathbf{X}^\top\mathbf{X}/(n-1)$ $\mathbf{X}\mathbf{X}^\top$ $N \times N$ $n-1$ Der Faktor und seine Eigenvektoren sind Hauptkomponenten, die auf die Einheitennorm skaliert sind.

Dies war Standard PCA. Nun, im Kernel - PCA betrachten wir eine Funktion , die jeden Datenpunkt in einem anderen Vektorraum zuordnet , die in der Regel hat größere Dimensionalität , möglicherweise sogar unendlich. Die Idee von Kernel-PCA ist es, die Standard-PCA in diesem neuen Bereich durchzuführen. $\phi(x)$ $D_\mathrm{new}$

Da die Dimensionalität dieses neuen Raums sehr groß (oder unendlich) ist, ist es schwierig oder unmöglich, eine Kovarianzmatrix zu berechnen. Wir können jedoch den oben beschriebenen zweiten Ansatz auf PCA anwenden. In der Tat wird die Gram-Matrix immer noch dieselbe handhabbare Größe haben. Elemente dieser Matrix sind gegeben durch , die wir als Kernfunktion $N \times N$ $\phi(\mathbf{x}_i)\phi(\mathbf{x}_j)$ $K(\mathbf{x}_i,\mathbf{x}_j)=\phi(\mathbf{x}_i)\phi(\mathbf{x}_j)$ . Dies ist der sogenannte Kernel-Trick : Man muss eigentlich nie berechnen , sondern nur . Eigenvektoren dieser Gram-Matrix sind die Hauptkomponenten im Zielraum, an denen wir interessiert sind. $\phi()$ $K()$

Die Antwort auf Ihre Frage wird jetzt offensichtlich. Wenn , reduziert sich die Kernel-Gram-Matrix auf was der Standard-Gram-Matrix entspricht, und daher ändern sich die Hauptkomponenten nicht. $K(x,y)=\mathbf{x}^\top \mathbf{y}$ $\mathbf{X} \mathbf{X}^\top$

Eine gut lesbare Referenz sind Scholkopf B, Smola A und Müller KR, Kernel Principal Component Analysis, 1999 , und es ist zu beachten, dass sie sich in Abbildung 1 explizit auf Standard-PCA beziehen, bei dem das Skalarprodukt als Kernelfunktion verwendet wird:

kernel PCA

Amöbe sagt Reinstate Monica
quelle

Woher stammen diese Bilder in deiner Antwort? Aus irgendeinem Buch?

Pinocchio

@Pinocchio, die Figur stammt von Scholkopf et al. Artikel, auf den in meiner Antwort verwiesen und verwiesen wird.

Amöbe sagt Reinstate Monica

"Es ist leicht zu erkennen, dass es die gleichen Eigenwerte (dh PC-Varianzen) bis zum Faktor n − 1 hat " - würde das nicht bedeuten, dass sie dann nicht vollständig äquivalent sind? Nehmen wir an, ich habe eine Matrix mit n = 10 Samples, d = 200 Dimensionen. In Standard-PCA wäre ich in der Lage, die Daten auf 199 Dimensionen zu projizieren, wenn ich wollte, aber in Kernel-PCA mit linearem Kernel kann ich nur bis zu 10 Dimensionen.

Cesar

@Cesar, nein, wenn Sie n = 10 Samples haben, hat die Kovarianzmatrix den Rang 10-1 = 9 und Standard-PCA findet nur 9 Dimensionen (sowie Kernel-PCA). Siehe hier: stats.stackexchange.com/questions/123318 .

Amöbe sagt Reinstate Monica

Ich erhalte die Datei für den Referenzlink von Scholkopf B, Smola A und Müller KR nicht gefunden.

24.

$X$ $N \times D$ $D$ $N$ $X = U \Sigma V^\top$ $U$ the principal components of $X$ . The singular value decomposition of the linear kernel $XX^\top = U \Sigma^2 U^\top$ has the same left singular vectors and so the same principal components.

Martha White
quelle

For standard PCA, I thought we cared, about the SVD of the covariance matrix, so don't really understand how is the SVD of X relevant, can you please expand?

m0s

@m0s For PCA, we care about eigendecomposition of the covariance matrix which we usually perform by the SVD of the (centered) data matrix.

MrDrFenner

It seems to me that that a KPCA with linear kernel should be the same as the simple PCA.

The covariance matrix that you are going to get the eigenvalues from is the same:

l i n e a r K P C A_{m a t r i x} = \frac{1}{l} \sum_{j = 1}^{l} K (x_{j}, x_{j}) = \frac{1}{l} \sum_{j = 1}^{l} x_{j} x_{j}^{T} = P C A_{m a t r i x}

$linearKPCA_{matrix} = \frac{1}{l} \sum_{j=1}^{l}K(x_{j},x_{j}) = \frac{1}{l} \sum_{j=1}^{l}x_{j}x_{j}^T = PCA_{matrix}$

You can check with more details here.

Jundiaius
quelle

Your answer is correct in spirit, but the formula looks confusing. KPCA works with Gram matrix

K (x_{i}, x_{j})

$K(x_i, x_j)$ , not with covariance matrix (for many nonlinear kernels it's actually impossible to compute covariance matrix as the target space has infinite dimensionality). See page 2 of the paper you cite.

amoeba says Reinstate Monica