PCA-Zielfunktion: Welcher Zusammenhang besteht zwischen Maximierung der Varianz und Minimierung des Fehlers?

Der PCA-Algorithmus kann anhand der Korrelationsmatrix formuliert werden (vorausgesetzt, die Daten bereits normalisiert und es wird nur die Projektion auf den ersten PC in Betracht gezogen). Die Zielfunktion kann wie folgt geschrieben werden: $X$

max_{w} (X w)^{T} (X w) s.t. w^{T} w = 1.

$\max_w (Xw)^T(Xw)\; \: \text{s.t.} \: \:w^Tw = 1.$

Dies ist in Ordnung, und wir verwenden Lagrange-Multiplikatoren, um es zu lösen, dh umzuschreiben als:

max_{w} [(X w)^{T} (X w) - λ w^{T} w],

$\max_w [(Xw)^T(Xw) - \lambda w^Tw],$

das ist äquivalent zu

max_{w} \frac{(X w)^{T} (X w)}{w^{T} w},

$\max_w \frac{ (Xw)^T(Xw) }{w^Tw},$

und daher ( siehe hier auf Mathworld ) scheint

max_{w} \sum_{i = 1}^{n} {(distance from point x_{i} to line w)}^{2} .

$\max_w \sum_{i=1}^n \text{(distance from point $x_i$ to line $w$)}^2.$

Dies bedeutet jedoch, dass der Abstand zwischen Punkt und Linie maximiert werden soll, und nach dem, was ich hier gelesen habe , ist dies falsch - es sollte $\min$ , nicht $\max$ . Wo ist mein Fehler?

Oder kann mir jemand den Zusammenhang zwischen der Maximierung der Varianz im projizierten Raum und der Minimierung des Abstands zwischen Punkt und Linie zeigen?

pca optimization Cam.Davidson.Pilon
quelle

Ich denke, der Mindestabstand wird verwendet, um das Kriterium der Orthogonalität für die Komponenten zu erfüllen. Die Punkte werden orthogonal zueinander in die PCs projiziert, wobei jedoch in jeder nachfolgenden Komponente die verbleibende Varianz maximiert wird.

Michael R. Chernick

Hinweis: Was passiert, wenn Sie zuerst den kleinsten Eigenwert und nicht den größten betrachten?

Whuber

@whuber Der kleinste Eigenwert hat wahrscheinlich den PC, der die Lösung für die endgültige Zielfunktion darstellt. Dieser PC maximiert jedoch nicht die ursprüngliche Objektivfunktion.

Cam.Davidson.Pilon

Ich bin mir nicht sicher, was du mit "endgültiger" und "ursprünglicher" Objektivfunktion meinst, Cam. PCA ist kein (konzeptionelles) Optimierungsprogramm. Seine Ausgabe ist eine Reihe von Hauptrichtungen, nicht nur eine. Es ist ein (interessanter) mathematischer Satz, dass diese Richtungen durch Lösen einer Folge von beschränkten quadratischen Programmen gefunden werden können, aber das ist nicht grundlegend für die Konzepte oder die Praxis von PCA. Ich schlage nur vor, dass Sie, indem Sie sich auf den kleinsten Eigenwert anstatt auf den größten konzentrieren, die beiden Ideen der (1) Minimierung von Entfernungen und (2) Einnahme einer Optimierungsansicht von PCA in Einklang bringen können.

Whuber

Das ist in Ordnung - Ihre Antwort war die fehlerfreie Version dessen, was ich versuchte zu tun.

Cam.Davidson.Pilon

Antworten:

Let eine zentrierte Datenmatrix mit seiner Beobachtungen in Reihen. Sei seine Kovarianzmatrix. Sei ein Einheitsvektor, der eine Achse im Variablenraum angibt. Wir wollen, dass die erste Hauptachse ist. $\newcommand{\X}{\mathbf X}\X$ $n$ $\newcommand{\S}{\boldsymbol \Sigma}\S=\X^\top\X/(n-1)$ $\newcommand{\w}{\mathbf w}\w$ $\w$

Gemäß dem ersten Ansatz maximiert die erste Hauptachse die Varianz der Projektion (Varianz der ersten Hauptkomponente). Diese Varianz ist gegeben durch $\X \w$

V a r (X w) = w^{⊤} X^{⊤} X w / (n - 1) = w^{⊤} Σ w .

$\mathrm{Var}(\X\w)=\w^\top\X^\top \X \w/(n-1)=\w^\top\S\w.$

Gemäß dem zweiten Ansatz minimiert die erste Hauptachse den Rekonstruktionsfehler zwischen und seiner Rekonstruktion , dh die Summe der quadratischen Abstände zwischen den ursprünglichen Punkten und ihren Projektionen auf . Das Quadrat des Rekonstruktionsfehlers ergibt sich aus $\X$ $\X\w\w^\top$ $\w$

\begin{aligned} ‖ X - X w w^{⊤} ‖^{2} & = t r ((X - X w w^{⊤}) (X - X w w^{⊤})^{⊤}) \\ = t r ((X - X w w^{⊤}) (X^{⊤} - w w^{⊤} X^{⊤})) \\ = t r (X X^{⊤}) - 2 t r (X w w^{⊤} X^{⊤}) + t r (X w w^{⊤} w w^{⊤} X^{⊤}) \\ = c o n s t - t r (X w w^{⊤} X^{⊤}) \\ = c o n s t - t r (w^{⊤} X^{⊤} X w) \\ = c o n s t - c o n s t \cdot w^{⊤} Σ w . \end{aligned}

$\begin{align}\newcommand{\tr}{\mathrm{tr}} \|\X-\X\w\w^\top\|^2 &=\tr\left((\X-\X\w\w^\top)(\X-\X\w\w^\top)^\top\right) \\ &=\tr\left((\X-\X\w\w^\top)(\X^\top-\w\w^\top\X^\top)\right) \\ &=\tr(\X\X^\top)-2\tr(\X\w\w^\top\X^\top)+\tr(\X\w\w^\top\w\w^\top\X^\top) \\ &=\mathrm{const}-\tr(\X\w\w^\top\X^\top) \\ &=\mathrm{const}-\tr(\w^\top\X^\top\X\w) \\ &=\mathrm{const} - \mathrm{const} \cdot \w^\top \S \w. \end{align}$

Beachten Sie das Minuszeichen vor dem Hauptbegriff. Aus diesem Grund läuft das Minimieren des Rekonstruktionsfehlers darauf hinaus, , also die Varianz, zu maximieren . Die Minimierung des Rekonstruktionsfehlers entspricht also der Maximierung der Varianz. beide Formulierungen ergeben das gleiche . $\w^\top \S \w$ $\w$

Amöbe sagt Reinstate Monica
quelle

Etwas , das ich bemerkte, ist nicht eine konvexe Funktion (in Bezug auf als PSD ist , wie kommen wir versuchen , es zu maximieren?

w^{T} Σ w

${w}^{T} \Sigma w$

w

$w$

Σ

$\Sigma$

Royi

@amoeba kannst du erklären, wie du im letzten Schritt von tr () zu const kommst?

Alberto

@alberto Was sich in der Spur befindet, ist eine Zahl (1x1-Matrix); Eine Spur einer Zahl ist diese Zahl selbst, sodass die Spur entfernt werden kann. Die Konstante erscheint, weil gleich , also gibt es diesen Faktor.

Σ

$\Sigma$

X^{⊤} X / n

$X^\top X/n$

1 / n

$1/n$

Amöbe sagt Reinstate Monica

@Leullame Die Berechnung gilt wörtlich für wenn es sich um eine Matrix mit orthonormalen Spalten handelt. Sie benötigen , um von Zeile 3 zu Zeile 4 zu wechseln. Wenn die Matrix orthonormale Spalten hat, ist tatsächlich eine Projektion von auf den durch die Spalten von Unterraum (hier ist ein Zeilenvektor).

W

$W$

W^{⊤} W = I

$W^\top W = I$

W

$W$

x W W^{⊤}

$xWW^\top$

x

$x$

W

$W$

x

$x$

Amöbe sagt Reinstate Monica

@ DanielLópez Nun, wir suchen nach einem eindimensionalen Subraum, der den Rekonstruktionsfehler minimiert. Ein eindimensionaler Unterraum kann durch einen Einheitsnormvektor definiert werden, der in seine Richtung zeigt, als was wird. Es hat eine Einheitsnorm von der Konstruktion.

w

$w$

Amöbe sagt Reinstate Monica