2.2 Herleitung der PCA

Idee der Hauptkomponentenanalyse

📄 03_dimred.pdf, Folie 15

Die Hauptkomponentenanalyse (Principal Component Analysis, PCA) sucht Richtungen in den Daten, entlang derer die Daten extremale Varianz haben, also maximale oder minimale. Im Bild der Folie ist $v_1$ die lange Achse der Punktwolke (größte Varianz), $v_2$ die dazu senkrechte kurze Achse.

Anwendung: Dimensionsreduktion durch Weglassen der Richtungen mit der kleinsten Varianz. Dort passiert wenig, man verliert beim Weglassen kaum Information.

Annahme: Die Daten sind zentriert, d.h. ihr Schwerpunkt

$$\boldsymbol\mu_{\mathbf x} = \frac1n\sum_i\mathbf x_i$$

liegt im Ursprung. Das ist keine Einschränkung: Man zieht vorher einfach den Mittelwert von allen Datenpunkten ab. Ab hier gilt also $\boldsymbol\mu=\mathbf 0$ und $\Sigma=\mathcal E[\mathbf x\mathbf x^\top]$.

Fallstrick

Das Zentrieren vergisst man leicht. Ohne Zentrierung zeigt die „erste Hauptkomponente“ meist einfach vom Ursprung zum Schwerpunkt der Daten, statt entlang der Streurichtung. Bei neuen Daten (z.B. Testbildern) muss man den Mittelwert der Trainingsdaten abziehen, nicht einen neu berechneten.

PCA als Rotation

📄 03_dimred.pdf, Folie 16

Man kann die PCA auch als Drehung des Koordinatensystems sehen: Es wird so rotiert, dass die Daten

• entlang der ersten Koordinatenachse die größte Varianz haben,
• entlang der zweiten Achse die zweithöchste Varianz,
• usw.

Im Beispiel der Folie (vier Punkte in 2D) ist die Varianz maximal bei einer Rotation um ca. $-18°$. In 2D legt diese eine Achse die ganze Drehung fest, denn die zweite Achse muss senkrecht dazu stehen. In höheren Dimensionen wählt man nacheinander: erst die Richtung maximaler Varianz, dann unter allen dazu senkrechten Richtungen wieder die mit maximaler Varianz, und so weiter.

PCA als Optimierungsproblem

📄 03_dimred.pdf, Folie 17

Aus 2.1 wissen wir: Die Varianz entlang der Richtung $\mathbf q$ ist $\sigma^2(\mathbf q)=\mathbf q^\top\Sigma\mathbf q$. Die PCA ist damit ein Optimierungsproblem:

$$\text{maximiere}\quad \sigma^2(\mathbf q),\qquad \mathbf q\in\Omega.$$

Jedes Maximierungsproblem lässt sich durch Umkehren des Vorzeichens in ein Minimierungsproblem verwandeln, $f(\mathbf q)=-\sigma^2(\mathbf q)$:

$$\text{minimiere}\quad f(\mathbf q),\qquad \mathbf q\in\Omega.$$

Begriffe:

• $f(\mathbf q)$ ist die Zielfunktion (objective function).
• $\Omega$ ist der zulässige Bereich (feasible set): die Menge, die man bei der Optimierung durchsuchen muss. Hier: die Menge aller Raumrichtungen.

Man schreibt in der Optimierung üblicherweise alles als Minimierung. Deshalb das Minuszeichen.

Optimierung unter Nebenbedingungen

📄 03_dimred.pdf, Folie 18

Oft ist der zulässige Bereich nicht direkt gegeben, sondern implizit durch Gleichungen oder Ungleichungen beschrieben. Dann spricht man von einem Optimierungsproblem unter Nebenbedingungen (constrained optimization):

$$\begin{aligned} &\text{minimiere}\quad f(\mathbf q),\quad \mathbf q\in\Omega\\ &\text{unter den Nebenbedingungen}\\ &\qquad g_i(\mathbf q)\le 0,\quad i=1\dots k\qquad\text{(Ungleichheitsbedingungen)}\\ &\qquad h_i(\mathbf q)=0,\quad i=1\dots m\qquad\text{(Gleichheitsbedingungen)} \end{aligned}$$

Die Funktionen $g_i$ und $h_i$ schränken die Wahl von $\mathbf q$ auf den Teil von $\Omega$ ein, in dem alle Bedingungen erfüllt sind.

Ergänzung: Ungleichheitsbedingungen brauchen wir für die PCA nicht. Sie tauchen später bei den Support-Vektor-Maschinen wieder auf (Karush-Kuhn-Tucker-Bedingungen), siehe Kapitel 6.

Der zulässige Bereich der PCA

📄 03_dimred.pdf, Folie 19

Lässt man für

$$\text{minimiere}\quad -\mathbf q^\top\Sigma\mathbf q,\qquad\mathbf q\in\Omega$$

den ganzen Raum $\Omega=\mathbb R^n$ zu, gibt es keine endliche Lösung. Grund: Für $\mathbf q\to c\,\mathbf q$ wird $\mathbf q^\top\Sigma\mathbf q\to c^2\,\mathbf q^\top\Sigma\mathbf q$. Man kann die „Varianz“ also durch einfaches Verlängern von $\mathbf q$ beliebig groß machen, ohne die Richtung zu ändern.

Schon vorher wurde festgelegt, dass eine Raumrichtung durch einen Einheitsvektor dargestellt wird: $\lVert\mathbf q\rVert=1$, oder einfacher $\mathbf q^\top\mathbf q=1$. Das ist genau die Gleichheitsbedingung, die eine endliche Lösung erst ermöglicht.

PCA-Optimierungsproblem

$$\text{minimiere}\quad -\mathbf q^\top\Sigma\mathbf q,\qquad\mathbf q\in\mathbb R^n$$

unter der Nebenbedingung

$$h(\mathbf q)=\mathbf q^\top\mathbf q-1=0.$$

Geometrisch: Man sucht auf der Einheitskugel den Punkt, an dem $\mathbf q^\top\Sigma\mathbf q$ am größten ist.

Minima finden: Fermat und Lagrange

Ohne Nebenbedingungen: Satz von Fermat

📄 03_dimred.pdf, Folie 20

Satz (Fermat)

Sei $f$ differenzierbar. Eine notwendige Bedingung für ein Minimum an der Stelle $\mathbf q^*$ ist

$$\nabla_{\mathbf q}f(\mathbf q^*)=\mathbf 0.$$

Man findet Minimumkandidaten also durch Lösen von $\nabla_{\mathbf q}f(\mathbf q)=\mathbf 0$. „Notwendig“ heißt: Jedes Minimum erfüllt die Bedingung, aber auch Maxima und Sattelpunkte tun es.

Diese Methode funktioniert nicht unter Nebenbedingungen. Die Grafik auf der Folie zeigt warum: Das Minimum auf einer Gleichheitsbedingung (einer Kurve im zulässigen Bereich) liegt im Allgemeinen nicht dort, wo der Gradient verschwindet. Der Gradient zeigt dort zwar nicht entlang der Kurve, aber er ist nicht null. Bei der PCA hat $f(\mathbf q)=-\mathbf q^\top\Sigma\mathbf q$ ohne Nebenbedingung nur den stationären Punkt $\mathbf q=\mathbf 0$, und der liegt nicht auf der Einheitskugel.

Mit Gleichheitsbedingungen: Satz von Lagrange

📄 03_dimred.pdf, Folie 21

Man definiert die Lagrangefunktion (Lagrangian) $L$ mit den Lagrange-Multiplikatoren (Lagrange multipliers) $\beta_i$:

$$L(\mathbf q,\boldsymbol\beta)=f(\mathbf q)+\sum_{i=1}^m\beta_i\,h_i(\mathbf q).$$

Satz (Lagrange)

Notwendige Bedingung für ein Minimum unter den Nebenbedingungen $h_i(\mathbf q)=0$:

1. $\nabla_{\boldsymbol\beta}L(\mathbf q,\boldsymbol\beta)=\mathbf 0$ (das ist gleichbedeutend mit $h_i(\mathbf q)=0$),
2. $\nabla_{\mathbf q}L(\mathbf q,\boldsymbol\beta)=\mathbf 0$.

Die Optimierung von $f$ unter Nebenbedingungen wird also durch eine Optimierung von $L$ ohne Nebenbedingungen ersetzt. Der Preis: zusätzliche Unbekannte $\beta_i$.

Warum ist Bedingung 1 dasselbe wie $h_i=0$? $\partial L/\partial\beta_i=h_i(\mathbf q)$. Die Ableitung nach dem Multiplikator null zu setzen, erzwingt also genau die Nebenbedingung.

Ergänzung zur Intuition von Bedingung 2: $\nabla f+\sum\beta_i\nabla h_i=\mathbf 0$ heißt: Der Gradient der Zielfunktion ist eine Linearkombination der Gradienten der Nebenbedingungen. Bei einer Nebenbedingung: $\nabla f$ steht senkrecht auf der Fläche $h=0$. Hätte $\nabla f$ eine Komponente entlang der Fläche, könnte man sich in diese Richtung bewegen, die Nebenbedingung einhalten und $f$ trotzdem verkleinern. Dann wäre man nicht im Minimum.

Anwendung auf die PCA: die Eigenwertgleichung

📄 03_dimred.pdf, Folie 22

Lagrangefunktion der PCA (eine Nebenbedingung, ein Multiplikator $\beta$):

$$L(\mathbf q,\beta)=-\mathbf q^\top\Sigma\mathbf q+\beta\,(\mathbf q^\top\mathbf q-1).$$

Ableitung nach $\mathbf q$:

$$\nabla_{\mathbf q}L(\mathbf q,\beta)=-2\Sigma\mathbf q+2\beta\mathbf q.$$

Ergänzung, die beiden benutzten Ableitungsregeln: Für symmetrisches $A$ gilt $\nabla_{\mathbf q}(\mathbf q^\top A\mathbf q)=2A\mathbf q$ (allgemein $(A+A^\top)\mathbf q$), und $\nabla_{\mathbf q}(\mathbf q^\top\mathbf q)=2\mathbf q$. Analog zur skalaren Regel $(a q^2)'=2aq$.

Nach dem Satz von Lagrange muss am Minimum gelten (durch 2 geteilt)

$$-\Sigma\mathbf q+\beta\mathbf q=\mathbf 0,$$

also die Eigenwertgleichung (eigenvalue equation)

$$\boxed{\ \Sigma\mathbf q=\beta\mathbf q\ }$$

Zentrales Ergebnis

Die Eigenvektoren der Kovarianzmatrix sind die Richtungen extremaler Varianz. Der Lagrange-Multiplikator $\beta$ ist der zugehörige Eigenwert.

Welcher Eigenvektor ist das Maximum? Setzt man $\Sigma\mathbf q=\beta\mathbf q$ in die Zielfunktion ein: $\mathbf q^\top\Sigma\mathbf q=\beta\,\mathbf q^\top\mathbf q=\beta$. Die Varianz in Eigenrichtung ist also der Eigenwert. Das Maximum liegt beim größten, das Minimum beim kleinsten Eigenwert. Alle anderen Eigenvektoren sind Sattelpunkte (Ergänzung).

Hauptkomponenten

📄 03_dimred.pdf, Folie 23

Aus der linearen Algebra (Spektralsatz) weiß man über die symmetrische Matrix $\Sigma$:

• Die Eigenwertgleichung hat immer eine Lösung: $n$ reelle Eigenwerte.
• Die Eigenvektoren lassen sich zueinander orthogonal wählen.
• $\Sigma$ ist orthogonal diagonalisierbar: Es gibt eine orthogonale Matrix $Q$ (also $Q^\top Q=I$), so dass

$$\Sigma = Q\,\Sigma'\,Q^\top,\qquad \Sigma'=\begin{pmatrix}\beta_1&0&\cdots\\0&\beta_2&\cdots\\\vdots&\vdots&\ddots\end{pmatrix}.$$

Die Spalten von $Q$ sind die auf Länge 1 normierten Eigenvektoren $\mathbf q_i$. Sie bilden eine neue Orthonormalbasis des $\mathbb R^n$, in der die Kovarianzmatrix $\Sigma'$ diagonal ist. Diese neuen normierten Basisvektoren heißen Hauptkomponenten (principal components). $Q$ ist (bis auf eventuelle Spiegelung) eine Rotationsmatrix, also genau die vorhin gesuchte PCA-Rotation.

Hinweis zur Folie

Auf der Folie steht $\Sigma=Q^\top\Sigma' Q$. Das passt zur Konvention, dass die Eigenvektoren in den Zeilen von $Q$ stehen. Mit Eigenvektoren in den Spalten (wie im Text der Folie) lautet die Zerlegung $\Sigma=Q\Sigma'Q^\top$, gleichwertig $\Sigma'=Q^\top\Sigma Q$. Das kann man direkt nachrechnen: $\Sigma Q=(\Sigma\mathbf q_1,\dots,\Sigma\mathbf q_n)=(\beta_1\mathbf q_1,\dots,\beta_n\mathbf q_n)=Q\Sigma'$.

Konvention: Man sortiert die Hauptkomponenten nach absteigendem Eigenwert, $\beta_1\ge\beta_2\ge\dots\ge\beta_n$. Die erste Hauptkomponente ist dann die Richtung größter Varianz.

Neue Variablen: Principal Component Scores

📄 03_dimred.pdf, Folie 24

Nach der Rotation sind die Koordinatenachsen entlang der Richtungen extremaler Varianz ausgerichtet. Die Projektionen eines Datenpunkts auf die $\mathbf q_i$,

$$a_i=\mathbf q_i^\top\mathbf x=\mathbf x^\top\mathbf q_i,$$

sind die neuen Variablenwerte in der Hauptkomponentenbasis. Man nennt sie Scores (principal component scores). Für alle Komponenten auf einmal: $\mathbf a=Q^\top\mathbf x$.

Weil $Q$ orthogonal ist, lässt sich das umkehren: $\mathbf x=Q\mathbf a=\sum_i a_i\mathbf q_i$. Es geht keine Information verloren, solange man alle Komponenten behält. Die Scores sind nur die Koordinaten desselben Punkts in einem gedrehten System.

Kovarianzstruktur der neuen Variablen

📄 03_dimred.pdf, Folie 25

Varianz der Scores. Für den $i$-ten Score gilt

$$\sigma_{i'}^2=\mathcal E[a_i^2]=\sigma^2(\mathbf q_i)=\mathbf q_i^\top\Sigma\,\mathbf q_i=\mathbf q_i^\top\beta_i\mathbf q_i=\beta_i.$$

(Die Folie schreibt im vorletzten Schritt $\Sigma'$, gemeint ist die ursprüngliche Kovarianzmatrix $\Sigma$, denn $\mathbf q_i$ ist in der Originalbasis ausgedrückt.)

Die Eigenwerte $\beta_i$ von $\Sigma$ sind also die Varianzen der Scores $a_i$. Da Varianzen nie negativ sind, gilt $\beta_i\ge0$: $\Sigma$ ist positiv semidefinit.

Kovarianz zwischen den Scores. Die transformierte Kovarianzmatrix $\Sigma'$ ist diagonal. Damit gilt

$$\sigma_{i'j'}=\Sigma'_{ij}=0\quad\text{für}\quad i\ne j.$$

Explizit (Ergänzung): $\mathcal E[a_ia_j]=\mathbf q_i^\top\Sigma\mathbf q_j=\beta_j\,\mathbf q_i^\top\mathbf q_j=0$ wegen der Orthogonalität.

Merke

Die PCA dekorreliert die Daten: Die neuen Variablen (Scores) sind untereinander unkorreliert, und ihre Varianzen sind die Eigenwerte. Das ist der Übergang von Fall 3 zu Fall 2 auf 📄 03_dimred.pdf, Folie 12.

Durchgerechnetes Beispiel

Ergänzung, nicht auf den Folien. Wir setzen das Beispiel aus 2.1 fort: vier zentrierte Punkte $(2,1)$, $(1,2)$, $(-1,-2)$, $(-2,-1)$ mit

$$\Sigma=\begin{pmatrix}2.5&2\\2&2.5\end{pmatrix}.$$

Schritt 1: Eigenwerte. Charakteristisches Polynom:

$$\det(\Sigma-\beta I)=(2.5-\beta)^2-2^2=0 \;\Rightarrow\; 2.5-\beta=\pm2 \;\Rightarrow\;\beta_1=4.5,\ \beta_2=0.5.$$

Schritt 2: Eigenvektoren.

• $\beta_1=4.5$: $(\Sigma-4.5I)\mathbf q=\begin{pmatrix}-2&2\\2&-2\end{pmatrix}\mathbf q=\mathbf 0\Rightarrow q_1=q_2$, normiert $\mathbf q_1=\tfrac1{\sqrt2}(1,1)^\top$.
• $\beta_2=0.5$: $\begin{pmatrix}2&2\\2&2\end{pmatrix}\mathbf q=\mathbf 0\Rightarrow q_1=-q_2$, normiert $\mathbf q_2=\tfrac1{\sqrt2}(1,-1)^\top$.

Probe: $\mathbf q_1^\top\mathbf q_2=\tfrac12(1-1)=0$ ✔ orthogonal.

Schritt 3: Scores $a_1=\tfrac{x_1+x_2}{\sqrt2}$, $a_2=\tfrac{x_1-x_2}{\sqrt2}$:

Punkt	$a_1$	$a_2$
$(2,1)$	$3/\sqrt2\approx2.12$	$1/\sqrt2\approx0.71$
$(1,2)$	$3/\sqrt2$	$-1/\sqrt2$
$(-1,-2)$	$-3/\sqrt2$	$1/\sqrt2$
$(-2,-1)$	$-3/\sqrt2$	$-1/\sqrt2$

Schritt 4: Kontrolle.

• $\operatorname{Var}(a_1)=\tfrac14\cdot4\cdot\tfrac92=4.5=\beta_1$ ✔
• $\operatorname{Var}(a_2)=\tfrac14\cdot4\cdot\tfrac12=0.5=\beta_2$ ✔
• $\operatorname{Cov}(a_1,a_2)=\tfrac14\cdot\tfrac{1}{2}(3-3-3+3)=0$ ✔ unkorreliert

Die Drehung geht hier um $45°$: Die erste Hauptkomponente liegt auf der Diagonalen. Die Gesamtvarianz $2.5+2.5=5$ ist vor und nach der Drehung gleich, wird aber umverteilt auf $4.5+0.5$. Wie man das für die Dimensionsreduktion nutzt, zeigt 2.3.