Was ist eine intuitive Erklärung dafür, wie sich PCA von einem geometrischen Problem (mit Abständen) zu einem linearen Algebraproblem (mit Eigenvektoren) entwickelt?

Ich habe viel über PCA gelesen, einschließlich verschiedener Tutorials und Fragen (wie diese , diese , diese und diese ).

Das geometrische Problem, das PCA zu optimieren versucht, ist mir klar: PCA versucht, die erste Hauptkomponente durch Minimierung des Rekonstruktionsfehlers (Projektionsfehlers) zu finden, wodurch gleichzeitig die Varianz der projizierten Daten maximiert wird.

Als ich das zum ersten Mal las, dachte ich sofort an eine lineare Regression. Vielleicht können Sie es bei Bedarf mit einem Gefälle lösen.

Als ich las, dass das Optimierungsproblem durch die Verwendung der linearen Algebra und das Auffinden von Eigenvektoren und Eigenwerten gelöst wird, war ich jedoch völlig außer mir. Ich verstehe einfach nicht, wie diese Verwendung der linearen Algebra ins Spiel kommt.

Meine Frage lautet also: Wie kann PCA von einem geometrischen Optimierungsproblem zu einem linearen Algebraproblem werden? Kann jemand eine intuitive Erklärung liefern?

Ich suche nicht nach einer Antwort wie dieser , die besagt: "Wenn Sie das mathematische Problem der PCA lösen, ist es am Ende gleichbedeutend mit dem Finden der Eigenwerte und Eigenvektoren der Kovarianzmatrix." Erklären Sie, warum Eigenvektoren die Hauptkomponenten darstellen und warum die Eigenwerte die Varianz der darauf projizierten Daten darstellen

Ich bin übrigens ein Software-Ingenieur und kein Mathematiker.

Hinweis: Die obige Abbildung wurde aus diesem PCA-Tutorial übernommen und modifiziert .

Problemstellung

Das geometrische Problem, das PCA zu optimieren versucht, ist mir klar: PCA versucht, die erste Hauptkomponente durch Minimierung des Rekonstruktionsfehlers (Projektionsfehlers) zu finden, wodurch gleichzeitig die Varianz der projizierten Daten maximiert wird.

Stimmt. Ich erkläre den Zusammenhang zwischen diesen beiden Formulierungen in meiner Antwort hier (ohne Mathe) oder hier (mit Mathe).

Nehmen wir die zweite Formulierung: PCA versucht, die Richtung so zu finden, dass die Projektion der Daten darauf die höchstmögliche Varianz aufweist. Diese Richtung wird per Definition die erste Hauptrichtung genannt. Wir können es wie folgt formalisieren: Wenn die Kovarianzmatrix $\mathbf C$ , suchen wir nach einem Vektor $\mathbf w$ mit der Längeneinheit $\|\mathbf w\|=1$ , so dass $\mathbf w^\top \mathbf{Cw}$ maximal ist.

(Nur für den Fall, dass dies nicht klar ist: Wenn $\mathbf X$ die zentrierte Datenmatrix ist, dann ist die Projektion durch $\mathbf{Xw}$ und ihre Varianz ist $\frac{1}{n-1}(\mathbf{Xw})^\top \cdot \mathbf{Xw} = \mathbf w^\top\cdot (\frac{1}{n-1}\mathbf X^\top\mathbf X)\cdot \mathbf w = \mathbf w^\top \mathbf{Cw}$.)

Andererseits ist ein Eigenvektor von $\mathbf C$ per Definition ein beliebiger Vektor $\mathbf v$ so dass $\mathbf{Cv}=\lambda \mathbf v$ .

Es zeigt sich, dass die erste Hauptrichtung durch den Eigenvektor mit dem größten Eigenwert gegeben ist. Dies ist eine nicht triviale und überraschende Aussage.

Beweise

Wenn man ein Buch oder Tutorial auf PCA aufschlägt, kann man dort den folgenden fast einzeiligen Beweis der obigen Aussage finden. Wir wollen $\mathbf w^\top \mathbf{Cw}$ unter der Bedingung maximieren , dass $\|\mathbf w\|=\mathbf w^\top \mathbf w=1$ ; dies kann durch Einführen eines Lagrange-Multiplikators und Maximieren von $\mathbf w^\top \mathbf{Cw}-\lambda(\mathbf w^\top \mathbf w-1)$ ; differenzierend erhalten wir $\mathbf{Cw}-\lambda\mathbf w=0$ , was die Eigenvektorgleichung ist. Wir sehen, dass $\lambda$muss tatsächlich der größte Eigenwert sein, indem diese Lösung in die Zielfunktion eingesetzt wird, was ergibt, dass $\mathbf w^\top \mathbf{Cw}-\lambda(\mathbf w^\top \mathbf w-1) = \mathbf w^\top \mathbf{Cw} = \lambda\mathbf w^\top \mathbf{w} = \lambda$ . Aufgrund der Tatsache, dass diese Zielfunktion maximiert werden soll, muss $\lambda$ der größte Eigenwert QED sein.

Dies ist für die meisten Menschen nicht sehr intuitiv.

Ein besserer Beweis (siehe z. B. diese übersichtliche Antwort von @ cardinal ) besagt, dass $\mathbf C$ in seiner Eigenvektorbasis diagonal ist , weil es eine symmetrische Matrix ist. (Dies wird eigentlich Spektralsatz genannt .) Wir können also eine orthogonale Basis wählen, nämlich diejenige, die durch die Eigenvektoren gegeben ist, wobei $\mathbf C$ diagonal ist und Eigenwerte $\lambda_i$ auf der Diagonale hat. Auf dieser Basis vereinfacht sich $\mathbf w^\top \mathbf{C w}$ zu $\sum \lambda_i w_i^2$ , oder mit anderen Worten, die Varianz ist durch die gewichtete Summe der Eigenwerte gegeben. Es ist fast unmittelbar, dass man zur Maximierung dieses Ausdrucks einfach w nehmen sollte$\mathbf w = (1,0,0,\ldots, 0)$ , dh der erste Eigenvektor, der die Varianz$\lambda_1$ ergibt(in der Tat, wenn man von dieser Lösung abweicht und Teile des größten Eigenwerts gegen Teile der kleineren Teile "tauscht", führt dies nur zu insgesamt kleineren Werten Varianz). Beachten Sie, dass der Wert von$\mathbf w^\top \mathbf{C w}$ nicht von der Basis abhängt! Der Wechsel auf die Eigenvektorbasis ist eine Drehung. In 2D kann man sich also vorstellen, einfach ein Stück Papier mit dem Streudiagramm zu drehen. Dies kann natürlich keine Abweichungen ändern.

Ich halte dies für ein sehr intuitives und nützliches Argument, das sich jedoch auf den Spektralsatz stützt. Das eigentliche Problem hier ist meiner Meinung nach: Was ist die Intuition hinter dem Spektralsatz?

Spektralsatz

Nehmen eine symmetrische Matrix $\mathbf C$ . Nimm seinen Eigenvektor $\mathbf w_1$ mit dem größten Eigenwert $\lambda_1$ . Machen Sie diesen Eigenvektor zum ersten Basisvektor und wählen Sie andere Basisvektoren nach dem Zufallsprinzip (so dass alle orthonormal sind). Wie wird auf dieser Basis aussehen?$\mathbf C$

Es wird $\lambda_1$ in der oberen linken Ecke haben, weil $\mathbf w_1=(1,0,0\ldots 0)$ auf dieser Basis und $\mathbf {Cw}_1=(C_{11}, C_{21}, \ldots C_{p1})$ gleich sein muss $\lambda_1\mathbf w_1 = (\lambda_1,0,0 \ldots 0)$ .

Aus demselben Grund wird es in der ersten Spalte unter $\lambda_1$ Nullen geben .

Aber weil es symmetrisch ist, hat es auch nach $\lambda_1$ Nullen in der ersten Reihe . So wird es aussehen:

Wobei leerer Raum bedeutet, dass sich dort ein Block einiger Elemente befindet. Da die Matrix symmetrisch ist, ist auch dieser Block symmetrisch. Wir können also genau dasselbe Argument anwenden, indem wir effektiv den zweiten Eigenvektor als zweiten Basisvektor verwenden und $\lambda_1$ und $\lambda_2$ auf die Diagonale setzen. Dies kann fortgesetzt werden, bis $\mathbf C$ diagonal ist. Das ist im Wesentlichen der Spektralsatz. (Beachten Sie, wie es nur funktioniert, weil $\mathbf C$ symmetrisch ist.)

Hier ist eine abstraktere Neuformulierung genau des gleichen Arguments.

Wir wissen, dass $\mathbf{Cw}_1 = \lambda_1 \mathbf w_1$ , daher definiert der erste Eigenvektor einen eindimensionalen Unterraum, in dem $\mathbf C$ als skalare Multiplikation fungiert. Nehmen wir nun einen beliebigen Vektor $\mathbf v$ senkrecht zu $\mathbf w_1$ . Dann ist es fast unmittelbar, dass $\mathbf {Cv}$ auch orthogonal zu $\mathbf w_1$ . Tatsächlich:

Dies bedeutet, dass $\mathbf C$ auf den gesamten verbleibenden Teilraum senkrecht zu $\mathbf w_1$ einwirkt, so dass er von $\mathbf w_1$ getrennt bleibt . Dies ist die entscheidende Eigenschaft von symmetrischen Matrizen. Also können wir den größten Eigenvektor dort finden, $\mathbf w_2$ , und auf die gleiche Weise vorgehen, um schließlich eine orthonormale Basis von Eigenvektoren zu konstruieren.

Es gibt ein Ergebnis aus dem Jahr 1936 von Eckart und Young ( https://ccrma.stanford.edu/~dattorro/eckart%26young.1936.pdf ), in dem Folgendes angegeben ist

$\sum_1^r d_k u_k v_k^T = arg min_{\hat{X} \epsilon M(r)} ||X-\hat{X}||_F^2$

wobei M (r) die Menge der Rang-r-Matrizen ist, was im Grunde genommen bedeutet, dass die ersten r Komponenten der SVD von X die beste Näherung der niedrigrangigen Matrix von X ergeben und am besten durch die quadratische Frobenius-Norm definiert sind - die Summe der Quadrate Elemente einer Matrix.

Dies ist ein allgemeines Ergebnis für Matrizen und hat auf den ersten Blick nichts mit Datensätzen oder Dimensionsreduktion zu tun.

$X$$X$$\hat{X}$

$\textit{Spectral Theorem}$$S = ADA^{-1}$$D = \mbox{diag} (\lambda_1, \lambda_2, \ldots, \lambda_n)$ . A ist die Änderung der Basismatrix. Das heißt, wenn unsere ursprüngliche Basis x 1 war , bedeutet dies in Matrixausdrücken, dass X ( v $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n$$x_1,x_2, \ldots, x_n$$A(x_1), A(x_2), \ldots A(x_n)$$A(x_i)$$||A(x_i)|| = \lambda_i$$A(x_i)$
$n>p$$rk(X) = p$$X = U \Sigma V^{t}$$\Sigma = (s_{ij})$$s_{11} \geq s_{22} \geq \ldots s_{pp}> 0$$X(v_i) = s_{ii} u_i$$i \leq p$$s_{ii} = 0$$i> n$$v_i$$\Sigma V^{t}$

"Das maximiert gleichzeitig die Varianz der projizierten Daten." Haben Sie von Rayleigh Quotient gehört ? Vielleicht ist das eine Art, das zu sehen. Der Rayleigh-Quotient der Kovarianzmatrix gibt Ihnen die Varianz der projizierten Daten an. (und die Wiki-Seite erklärt, warum Eigenvektoren den Rayleigh-Quotienten maximieren)

@amoeba gibt ordentliche Formalisierung und Beweis von:

Wir können es wie folgt formalisieren: Wenn die Kovarianzmatrix C gegeben ist, suchen wir nach einem Vektor w mit der Längeneinheit lengthw‖ = 1, so dass w ^T Cw maximal ist.

Aber ich denke, es gibt einen intuitiven Beweis für:

Es zeigt sich, dass die erste Hauptrichtung durch den Eigenvektor mit dem größten Eigenwert gegeben ist. Dies ist eine nicht triviale und überraschende Aussage.

Wir können w ^T Cw als ein Punktprodukt zwischen dem Vektor w und Cw interpretieren , das durch Durchlaufen der Transformation C erhalten wird:

w ^T Cw = ‖w‖ * ‖Cw‖ * cos (w, Cw)

Da w eine feste Länge hat, benötigen wir zur Maximierung von w ^T Cw:

1. maximiere ‖Cw‖
2. cos maximieren (w, Cw)

Wenn wir w als Eigenvektor von C mit dem größten Eigenwert annehmen, können wir beide gleichzeitig archivieren:

1. ‖Cw‖ ist max. (Wenn w von diesem Eigenvektor abweicht und entlang orthogonaler Eigenvektoren zerlegt wird, sollte sich ‖Cw‖ verringern.)
2. w und Cw in gleicher Richtung, cos (w, Cw) = 1, max

Da Eigenvektoren orthogonal sind, bilden sie zusammen mit den anderen Eigenvektoren von C eine Menge von Hauptkomponenten zu X.

nachweis von 1

zerlegen w in orthogonale primäre und sekundäre Eigenvektoren v1 und v2 , vorausgesetzt, ihre Länge ist v1 bzw. v2. wir wollen beweisen

(λ ₁ w) ² > ((λ ₁ v1) ² + (λ ₂ v2) ² )

da λ ₁ > λ ₂ , haben wir

((λ ₁ v1) ² + (λ ₂ v2) ² )

<((λ ₁ v1) ² + (λ ₁ v2) ² )

= (λ ₁ ) ² * (v1 ² + v2 ² )

= (& lgr; ₁ ) ² · w ²