Was ist die objektive Funktion von PCA?

Die Hauptkomponentenanalyse kann eine Matrixzerlegung verwenden, dies ist jedoch nur ein Werkzeug, um dorthin zu gelangen.

Wie würden Sie die Hauptkomponenten ohne die Verwendung von Matrixalgebra finden?

Was ist die objektive Funktion (Ziel) und welche Einschränkungen gibt es?

pca Neil McGuigan
quelle

Vielleicht fehlt mir etwas, bitte korrigieren Sie mich, wenn ich falsch liege, aber es sollte (zumindest im Prinzip) möglich sein, das, was in PCA gemacht wird, mit Matrizen als (kompliziertem) linearem Programmierproblem zu konstruieren, aber ich nicht wissen, wie Sie alle erforderlichen Einschränkungen angeben würden. Ich bin mir auch nicht sicher, ob das sehr einfach ist, verglichen mit der Verwendung von PCA. Warum versuchen Sie, Matrizen zu vermeiden?

Chris Simokat

@ Chris Ich verstehe nicht, wie man zu einem linearen Programmierproblem kommen kann. Es war auch nicht mein Verständnis, dass Matrizen bei der Berechnung vermieden werden sollten . Die Frage war, welche Art von Problem von PCA gelöst wird und nicht wie es gemacht wird (zum Beispiel durch Berechnung der SVD). Die Lösung von Kardinal besagt, dass Sie aufeinanderfolgende orthogonale Richtungen maximaler Varianz finden . Die Lösung, die ich vorgestellt habe, besagt, dass Sie Hyperebenen mit minimalen Rekonstruktionsfehlern finden.

NRH

@chris Ich hoffe, einen anderen Weg zu finden, um PCA ohne die Matrixalgebra anzuzeigen, um mein Verständnis davon zu verbessern.

Neil McGuigan

@ Chris, Sie haben eine quadratische Zielfunktion und eine ell_2-Normgleichheitsbedingung . Alternativ haben Sie unter der Formulierung in der Antwort von @ NRH eine Matrixrangbeschränkung. Das wird sich nicht auf ein lineares Programmierproblem beschränken. @NRH vermittelt eine gute Vorstellung, und tatsächlich besteht ein sehr enger Zusammenhang zwischen den beiden Perspektiven auf PCA, die gegeben wurden. Vielleicht können wir dies in Zusammenarbeit mit @NRH zu seinem Beitrag hinzufügen, um die Gesamtheit der Antworten zu vervollständigen.

ℓ_{2}

$\ell_2$

Kardinal

@NRH, Eigentlich mag ich ESL sehr, aber ich denke, dass die Behandlung dieses Themas dort ziemlich oberflächlich ist, wie es für viele der Themen in dem Buch der Fall ist. Insbesondere beweisen sie den wichtigen Teil der Lösung für das Optimierungsproblem, das Sie geben, nicht (oder weisen ihn nicht einmal als Übung zu).

Kardinal

Antworten:

Ohne zu versuchen, auf PCA einen vollständigen Primer zu geben, ist vom Standpunkt der Optimierung die primäre Zielfunktion der Rayleigh-Quotient . Die im Quotienten angegebene Matrix ist (ein Vielfaches davon) die Beispiel-Kovarianzmatrix wobei jedes ein Vektor von Merkmalen ist und die Matrix ist, so dass die te Zeile .

S = \frac{1}{n} \sum_{i = 1}^{n} x_{i} x_{i}^{T} = X^{T} X / n

$\newcommand{\m}[1]{\mathbf{#1}}\newcommand{\x}{\m{x}}\newcommand{\S}{\m{S}}\newcommand{\u}{\m{u}}\newcommand{\reals}{\mathbb{R}}\newcommand{\Q}{\m{Q}}\newcommand{\L}{\boldsymbol{\Lambda}} \S = \frac{1}{n} \sum_{i=1}^n \x_i \x_i^T = \m{X}^T \m{X} / n$

x_{i}

$\x_i$

p

$p$

X

$\m{X}$

i

$i$

x_{i}^{T}

$\x_i^T$

PCA versucht, eine Folge von Optimierungsproblemen zu lösen. Das erste in der Sequenz ist das uneingeschränkte Problem

\begin{array}{ll} maximize & \frac{u^{T} S u}{u^{T} u}, u \in R^{p} . \end{array}

$\begin{array}{ll} \text{maximize} & \frac{\u^T \S \u}{\u^T\u} \;, \u \in \reals^p \> . \end{array}$

Daist das obige uneingeschränkte Problem gleichbedeutend mit dem eingeschränkten Problem $\u^T \u = \|\u\|_2^2 = \|\u\| \|\u\|$

\begin{array}{ll} maximize & u^{T} S u \\ subject to & u^{T} u = 1 . \end{array}

$\begin{array}{ll} \text{maximize} & \u^T \S \u \\ \text{subject to} & \u^T \u = 1 \>. \end{array}$

Hier kommt die Matrixalgebra ins Spiel. Da eine symmetrisch positive semidefinite Matrix ist (konstruktionsbedingt!), Hat sie eine Eigenwertzerlegung der Form wobei eine ist orthogonale Matrix (also ) und ist eine diagonale Matrix mit nichtnegativen Einträgen so dass . $\S$

S = Q Λ Q^{T},

$\S = \Q \L \Q^T \>,$

Q

$\Q$

Q Q^{T} = I

$\Q \Q^T = \m{I}$

Λ

$\L$

λ_{i}

$\lambda_i$

λ_{1} \geq λ_{2} \geq \dots \geq λ_{p} \geq 0

$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_p \geq 0$

Daher ist . Da im Problem auf eine Norm von eins beschränkt ist, gilt dies auch für da , da orthogonal ist. $\u^T \S \u = \u^T \Q \L \Q^T \u = \m{w}^T \L \m{w} = \sum_{i=1}^p \lambda_i w_i^2$ $\u$ $\m{w}$ $\|\m{w}\|_2 = \|\Q^T \u\|_2 = \|\u\|_2 = 1$ $\Q$

Aber wenn wir die Menge unter den Bedingungen , dann ist das Beste, was wir tun können, zu setze , und für . $\sum_{i=1}^p \lambda_i w_i^2$ $\sum_{i=1}^p w_i^2 = 1$ $\m{w} = \m{e}_1$ $w_1 = 1$ $w_i = 0$ $i > 1$

Wenn wir nun das entsprechende , nach dem wir zuerst gesucht haben, erhalten wir Folgendes: wobei bezeichnet die erste Spalte von , dh den Eigenvektor, der dem größten Eigenwert von . Der Wert der Zielfunktion wird dann auch leicht als . $\u$

u^{⋆} = Q e_{1} = q_{1}

$\u^\star = \Q \m{e}_1 = \m{q}_1$

q_{1}

$\m{q}_1$

Q

$\Q$

S

$\S$

λ_{1}

$\lambda_1$

Die verbleibenden Hauptkomponentenvektoren werden dann durch Lösen der mit indizierten Folge von Optimierungsproblemen gefunden. Das Problem ist also dasselbe, außer dass wir die zusätzliche Einschränkung hinzufügen, dass die Lösung zu allen vorherigen Lösungen in der Sequenz orthogonal sein muss . Es ist nicht schwierig , das Argument oben induktiv zu zeigen , zu verlängern , dass die Lösung der - ten Problem ist in der Tat , der - te Eigenvektor . $i$

\begin{array}{ll} maximize & u_{i}^{T} S u_{i} \\ subject to & u_{i}^{T} u_{i} = 1 \\ u_{i}^{T} u_{j} = 0 \forall 1 \leq j < i . \end{array}

$\begin{array}{ll} \text{maximize} & \u_i^T \S \u_i \\ \text{subject to} & \u_i^T \u_i = 1 \\ & \u_i^T \u_j = 0 \quad \forall 1 \leq j < i\>. \end{array}$

i

$i$

q_{i}

$\m{q}_i$

i

$i$

S

$\S$

Die PCA-Lösung wird häufig auch als Singularwertzerlegung von ausgedrückt . Um zu sehen , warum, lassen . Dann ist und so (Streng genommen bis zum Signieren von Flips) und . $\m{X}$ $\m{X} = \m{U} \m{D} \m{V}^T$ $n \S = \m{X}^T \m{X} = \m{V} \m{D}^2 \m{V}^T$ $\m{V} = \m{Q}$ $\L = \m{D}^2 / n$

Die Hauptkomponenten werden durch Projizieren von auf die Hauptkomponentenvektoren gefunden. Aus der gerade gegebenen SVD-Formulierung ist leicht ersichtlich, dass $\m{X}$

X Q = X V = U D V^{T} V = U D .

$\m{X} \m{Q} = \m{X} \m{V} = \m{U} \m{D} \m{V}^T \m{V} = \m{U} \m{D} \> .$

Die Einfachheit der Darstellung sowohl der Hauptkomponentenvektoren als auch der Hauptkomponenten selbst in Bezug auf die SVD der Merkmalsmatrix ist ein Grund, warum die SVD bei einigen Behandlungen von PCA so prominent ist.

Kardinal
quelle

Wenn nur die ersten paar singulären Werte / Vektoren benötigt werden, geben Nash und Shlien einen Algorithmus an, der an die übliche Potenzmethode zur Berechnung dominanter Eigenwerte erinnert. Dies könnte für das OP von Interesse sein.

JM ist kein Statistiker

@NRH, Danke, dass du meine Tippfehler abgefangen (und korrigiert) hast, bevor ich sie sehen konnte!

Kardinal

Hallo Kardinal, danke für deine Antwort. Aber es scheint, dass Sie nicht den Schritt gegeben haben, zu beweisen, warum die sequentielle Optimierung zu einem globalen Optimum führt. Könnten Sie das bitte näher erläutern? Vielen Dank!

Lifu Huang

Die von cardinal vorgestellte Lösung konzentriert sich auf die Kovarianzmatrix der Stichprobe. Ein weiterer Ausgangspunkt ist der Rekonstruktionsfehler der Daten durch eine q- dimensionale Hyperebene. Wenn die p- dimensionalen Datenpunkte das Ziel zu lösen $x_1, \ldots, x_n$

min_{μ, λ_{1}, \dots, λ_{n}, V_{q}} \sum_{i = 1}^{n} | | x_{i} - μ - V_{q} λ_{i} | |^{2}

$\min_{\mu, \lambda_1,\ldots, \lambda_n, \mathbf{V}_q} \sum_{i=1}^n ||x_i - \mu - \mathbf{V}_q \lambda_i||^2$

für eine Matrix mit orthonormalen Spalten und . Dies ergibt die beste Rang- q- Rekonstruktion, gemessen durch die euklidische Norm, und die Spalten der Lösung sind die ersten q Hauptkomponentenvektoren. $p \times q$ $\mathbf{V}_q$ $\lambda_i \in \mathbb{R}^q$ $\mathbf{V}_q$

Für festes lautet die Lösung für und (dies ist eine Regression) $\mathbf{V}_q$ $\mu$ $\lambda_i$

μ = \bar{x} = \frac{1}{n} \sum_{i = 1}^{n} x_{i} λ_{i} = V_{q}^{T} (x_{i} - \bar{x})

$\mu = \overline{x} = \frac{1}{n}\sum_{i=1}^n x_i \qquad \lambda_i = \mathbf{V}_q^T(x_i - \overline{x})$

Nehmen wir zur Vereinfachung der Notation an, dass in den folgenden Berechnungen zentriert wurde. Wir müssen dann minimieren $x_i$

\sum_{i = 1}^{n} | | x_{i} - V_{q} V_{q}^{T} x_{i} | |^{2}

$\sum_{i=1}^n ||x_i - \mathbf{V}_q\mathbf{V}_q^T x_i||^2$

über mit orthonormalen Spalten. Beachten Sie, dass die Projektion auf den q- dimensionalen Spaltenraum ist. Daher ist das Problem äquivalent zum Minimieren von über Rang q Projektionen . Das heißt, wir müssen Maximierungs über Rang q- Projektionen , wobei die Beispiel-Kovarianzmatrix ist. Jetzt $\mathbf{V}_q$ $P = \mathbf{V}_q\mathbf{V}_q^T$

\sum_{i = 1}^{n} | | x_{i} - P x_{i} | |^{2} = \sum_{i = 1}^{n} | | x_{i} | |^{2} - \sum_{i = 1}^{n} | | P x_{i} | |^{2}

$\sum_{i=1}^n ||x_i - P x_i||^2 = \sum_{i=1}^n ||x_i||^2 - \sum_{i=1}^n||Px_i||^2$

P

$P$

\sum_{i = 1}^{n} | | P x_{i} | |^{2} = \sum_{i = 1}^{n} x_{i}^{T} P x_{i} = tr (P \sum_{i = 1}^{n} x_{i} x_{i}^{T}) = n tr (P S)

$\sum_{i=1}^n||Px_i||^2 = \sum_{i=1}^n x_i^TPx_i = \text{tr}(P \sum_{i=1}^n x_i x_i^T) = n \text{tr}(P \mathbf{S})$

P

$P$

S

$\mathbf{S}$

tr (P S) = tr (V_{q}^{T} S V_{q}) = \sum_{i = 1}^{q} u_{i}^{T} S u_{i}

$\text{tr}(P\mathbf{S}) = \text{tr}(\mathbf{V}_q^T\mathbf{S}\mathbf{V}_q) = \sum_{i=1}^q u_i^T \mathbf{S} u_i$ wobei die (orthonormalen) Spalten in sind und die in der Antwort von @ cardinal dargestellten Argumente zeigen, dass das Maximum erhalten wird, indem man das 'nimmt. s ist Eigenvektoren für mit den größten Eigenwerten.

u_{1}, \dots, u_{q}

$u_1, \ldots, u_q$

q

$q$

V_{q}

$\mathbf{V}_q$

u_{i}

$u_i$

q

$q$

S

$\mathbf{S}$

q

$q$

Der Rekonstruktionsfehler weist auf eine Reihe nützlicher Verallgemeinerungen hin, beispielsweise auf spärliche Hauptkomponenten oder Rekonstruktionen durch niedrigdimensionale Mannigfaltigkeiten anstelle von Hyperebenen. Einzelheiten finden Sie in Abschnitt 14.5 unter Die Elemente des statistischen Lernens .

NRH
quelle

(+1) Gute Punkte. Einige Vorschläge: Es wäre gut, zu definieren, und es wäre wirklich nett, einen kurzen Beweis für das Ergebnis zu liefern. Alternativ kann es mit dem Optimierungsproblem verbunden sein, das Rayleight-Quotienten umfasst. Ich denke, das würde die Antworten auf diese Frage sehr vollständig machen!

λ_{i}

$\lambda_i$

Kardinal

@ Cardinal, ich glaube, ich habe die fehlenden Schritte abgeschlossen, um von der Rekonstruktionsformulierung zu dem von Ihnen gelösten Problem zu gelangen.

NRH

Gute Arbeit. Ich glaube, die einzige verbleibende Lücke ist in Ihrer letzten Erklärung. Es ist nicht sofort ersichtlich, dass das Optimieren der Summe mit dem Ausführen der Optimierungssequenz in meiner Antwort identisch ist. Tatsächlich denke ich nicht, dass es im Allgemeinen direkt folgt. Aber es muss auch hier nicht angesprochen werden.

Kardinal

@ Kardinal, es folgt durch Induktion. Sie geben den Induktionsstart vor und wählen im Induktionsschritt orthonormale Vektoren , die die Summe maximieren, und ordnen sie so an, dass ein zu orthogonaler Einheitsvektor ist . Dann durch Ihre Ergebnisse und durch die Induktionsannahme . Natürlich ist die Basis keine eindeutige Basis für den dimensionalen Raum. Sie können auch das "konvexe Kombinationsargument" verallgemeinern, das Sie verwenden, um einen direkten Beweis zu liefern.

w_{1}, \dots, w_{q}

$w_1, \ldots, w_q$

w_{q}

$w_q$

u_{1}, \dots, u_{q - 1}

$u_1, \ldots, u_{q-1}$

w_{q}^{T} S w_{q} \leq u_{q}^{T} S u_{q}

$w_q^T \mathbf{S} w_q \leq u_q^T \mathbf{S} u_q$

\sum_{i = 1}^{q - 1} w_{i}^{T} S w_{i} \leq \sum_{i = 1}^{q - 1} u_{i}^{T} S u_{i}

$\sum_{i=1}^{q-1} w_i^T \mathbf{S} w_i \leq \sum_{i=1}^{q-1}u_i^T \mathbf{S} u_i$

q

$q$

NRH

@ Kardinal, ich erzwinge keine Verschachtelung, sondern verwende lediglich eine Dimensionsüberlegung. Wenn wir einen dimensionalen Unterraum haben, können Sie in diesem Raum immer so wählen , dass es orthogonal zu einem -dimensionalen Unterraum ist. Dann füllen Sie die Basis nach Belieben auf.

q

$q$

w_{q}

$w_q$

(q - 1)

$(q-1)$

w

$w$

NRH

In NIPALS ( Wiki ) finden Sie einen Algorithmus, der keine explizite Matrixzerlegung verwendet. Ich nehme an, das meinst du, wenn du sagst, dass du Matrixalgebra vermeiden willst, da du Matrixalgebra hier wirklich nicht vermeiden kannst :)

JMS
quelle