2.1 Dimensionsreduktion & Kovarianz

Warum Dimensionsreduktion?

📄 03_dimred.pdf, Folie 4

Reale Daten sind oft sehr hochdimensional: Genomsequenzen, Bilder, Textdokumente. Das bringt zwei Probleme mit sich:

1. Lernalgorithmen werden deutlich erschwert. Mehr Variablen bedeuten mehr Parameter, mehr Rechenzeit und, bei wenigen Beispielen, Überanpassung.
2. Man kann die Daten nicht mehr visualisieren. Mehr als drei Achsen kann niemand anschauen.

Man versucht deshalb, die Anzahl der Variablen im Lernproblem zu reduzieren: Dimensionsreduktion (dimensionality reduction). Es gibt zwei grundsätzliche Wege:

	Merkmalsselektion (feature selection)	Merkmalsextraktion (feature extraction)
Idee	eine Teilmenge der vorhandenen Variablen auswählen	wenige neue Variablen (Merkmale) aus allen alten berechnen
Kriterien	z.B. Rekonstruktionsfehler, Informationszuwachs	die neuen Merkmale sollen die für das Lernproblem relevante Information möglichst gut repräsentieren
Ergebnis	Originalvariablen bleiben interpretierbar	neue Variablen sind Mischungen, oft schwerer zu deuten
Beispiel	nur die 50 aussagekräftigsten Gene behalten	PCA: Linearkombinationen aller Gene

Merke

Die PCA ist Merkmalsextraktion, nicht Selektion. Jede Hauptkomponente hängt von allen Originalvariablen ab.

Beispiele für hochdimensionale Daten

• MNIST (📄 03_dimred.pdf, Folie 5): handgeschriebene Ziffern als $28\times28$-Graustufenbilder. Jedes Pixel ist eine Variable, also $28\cdot28=784$ Merkmale pro Bild, bei 60 000 Trainingsbildern. Die Datenmatrix hat eine Zeile pro Bild (Fall, engl. case/sample) und eine Spalte pro Pixel.
• Genexpression in Microarrays (📄 03_dimred.pdf, Folie 6): rund 30 000 Gene (Merkmale), aber nur rund 100 Patienten (Chips). Hier gibt es viel mehr Variablen als Beispiele, ein typischer Fall von $n \gg N$.

Wie findet man in einer Tabelle mit 30 000 Spalten einen Fehler (📄 03_dimred.pdf, Folie 8)? Durch Hinschauen jedenfalls nicht.

Visualisierung durch Dimensionsreduktion

📄 03_dimred.pdf, Folie 9

Idee: Man stellt nur die zwei oder drei „wichtigsten“ Dimensionen dar. „Wichtig“ heißt hier: Richtungen, in denen die Daten möglichst breit streuen, also hohe Varianz haben. Dort werden interne Strukturen sichtbar.

Das Microarray-Beispiel auf der Folie zeigt, was man dabei entdecken kann:

• Die Proben zerfallen in zwei Gruppen, die zwei Gewebetypen entsprechen.
• Ein blauer Punkt liegt mitten in der roten Gruppe: ein falsch beschriftetes Experiment (mislabeled experiment).
• In einem anderen Datensatz trennen sich die Proben nach Labor (site effect), nicht nach Biologie. Das ist ein Messartefakt, das man ohne Visualisierung leicht übersieht.

Um „Richtung hoher Varianz“ präzise zu machen, braucht man die Kovarianzmatrix.

Wiederholung: Korrelation und Kovarianz

📄 03_dimred.pdf, Folie 10

Die Folie nennt die Korrelation zweier Variablen $x$ und $y$

$$C_{xy} = \mathcal E[xy] = \sum_{x_i\in\mathcal X}\sum_{y_j\in\mathcal Y} x_i\, y_j\, p(x_i,y_j).$$

Ergänzung zur Begriffswahl: In der Statistik versteht man unter „Korrelation“ meist den normierten Korrelationskoeffizienten $\rho_{xy}=\sigma_{xy}/(\sigma_x\sigma_y)$. Die Folie meint mit $C_{xy}$ dagegen das (unnormierte) gemischte zweite Moment $\mathcal E[xy]$, wie es in der Signalverarbeitung üblich ist.

Intuition: Hängen $x$ und $y$ zusammen, sind sie oft gleichzeitig positiv oder gleichzeitig negativ, sie kovariieren. Ihr Produkt ist dann oft groß, also auch $\mathcal E[xy]$.

Problem: $C_{xy}$ ist umso größer, je größer die Mittelwerte von $x$ und $y$ sind, ganz unabhängig davon, ob die Variablen zusammenhängen. Beispiel: $x$ und $y$ seien unabhängig mit Mittelwert 10. Dann ist $\mathcal E[xy]=\mathcal E[x]\,\mathcal E[y]=100$, obwohl keinerlei Zusammenhang besteht.

Lösung: Erst die Mittelwerte abziehen. Das ergibt die Kovarianz (covariance):

$$\sigma_{xy} = \mathcal E\big[(x-\mu_x)(y-\mu_y)\big] = \sum_{x_i}\sum_{y_j}(x_i-\mu_x)(y_j-\mu_y)\,p(x_i,y_j).$$

Vorzeichen von $\sigma_{xy}$	Bedeutung
positiv	liegt $x$ über seinem Mittel, dann meist auch $y$
negativ	liegt $x$ über seinem Mittel, dann $y$ meist darunter
null	kein linearer Zusammenhang (unkorreliert)

Fallstrick

Unkorreliert heißt nicht unabhängig. Für $x$ symmetrisch um 0 und $y=x^2$ ist $\sigma_{xy}=\mathcal E[x^3]=0$, obwohl $y$ vollständig von $x$ abhängt. Die Kovarianz misst nur lineare Zusammenhänge. (Ergänzung)

Die Kovarianzmatrix

📄 03_dimred.pdf, Folie 11

Hat man $n$ Variablen $x_1,\dots,x_n$, fasst man alle paarweisen Kovarianzen in der Kovarianzmatrix (covariance matrix) $\Sigma$ zusammen:

$$\Sigma = (\sigma_{ij}) = \begin{pmatrix} \sigma_{11} & \sigma_{12} & \cdots\\ \sigma_{21} & \sigma_{22} & \cdots\\ \vdots & \vdots & \ddots \end{pmatrix} = \begin{pmatrix} \sigma_1^2 & \sigma_{12} & \cdots\\ \sigma_{21} & \sigma_2^2 & \cdots\\ \vdots & \vdots & \ddots \end{pmatrix}.$$

Eigenschaften:

• Symmetrisch: $\Sigma_{ij}=\Sigma_{ji}$, denn $(x_i-\mu_i)(x_j-\mu_j)=(x_j-\mu_j)(x_i-\mu_i)$.
• Diagonale = Varianzen: $\sigma_{ii}=\mathcal E[(x_i-\mu_i)^2]=\sigma_i^2$.

Kompakt als äußeres Produkt

Fasst man die Variablen zu einem Merkmalsvektor $\mathbf x=(x_1,\dots,x_n)^\top$ mit Mittelwert $\boldsymbol\mu_{\mathbf x}$ zusammen, gilt:

$$\Sigma_{ij} = \mathcal E\big[(x_i-\mu_i)(x_j-\mu_j)\big] \quad\Rightarrow\quad \Sigma = \mathcal E\big[(\mathbf x-\boldsymbol\mu_{\mathbf x})(\mathbf x-\boldsymbol\mu_{\mathbf x})^\top\big].$$

Warum? Für einen Spaltenvektor $\mathbf v$ ist das äußere Produkt (outer product) $\mathbf v\mathbf v^\top$ eine $n\times n$-Matrix mit Eintrag $v_iv_j$ an Position $(i,j)$. Mit $\mathbf v=\mathbf x-\boldsymbol\mu$ steht dort genau $(x_i-\mu_i)(x_j-\mu_j)$. Den Erwartungswert nimmt man eintragsweise.

Merke: $\mathbf v^\top\mathbf v$ ist ein Skalar (inneres Produkt), $\mathbf v\mathbf v^\top$ eine Matrix (äußeres Produkt).

Ergänzung: Schätzung aus Daten. In der Praxis kennt man $p(\mathbf x)$ nicht, sondern hat $N$ Datenpunkte $\mathbf x_1,\dots,\mathbf x_N$. Man ersetzt den Erwartungswert durch den Mittelwert:

$$\hat{\boldsymbol\mu} = \frac1N\sum_{k=1}^N\mathbf x_k,\qquad \hat\Sigma = \frac1N\sum_{k=1}^N(\mathbf x_k-\hat{\boldsymbol\mu})(\mathbf x_k-\hat{\boldsymbol\mu})^\top = \frac1N X_c^\top X_c,$$

wobei $X_c$ die zentrierte Datenmatrix ist (eine Zeile pro Datenpunkt). Oft wird durch $N-1$ statt $N$ geteilt (erwartungstreue Schätzung). Für die PCA ist das egal: Ein konstanter Faktor ändert die Eigenvektoren nicht, nur die Eigenwerte skalieren mit.

Zahlenbeispiel. Vier zentrierte Punkte (Mittelwert schon $(0,0)$):

$$\mathbf x_1=\begin{pmatrix}2\\1\end{pmatrix},\ \mathbf x_2=\begin{pmatrix}1\\2\end{pmatrix},\ \mathbf x_3=\begin{pmatrix}-1\\-2\end{pmatrix},\ \mathbf x_4=\begin{pmatrix}-2\\-1\end{pmatrix}.$$

• $\sigma_1^2=\tfrac14(4+1+1+4)=2.5$
• $\sigma_2^2=\tfrac14(1+4+4+1)=2.5$
• $\sigma_{12}=\tfrac14(2+2+2+2)=2$

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

Die positive Kovarianz sagt: Die Punkte liegen entlang der Diagonale „rechts oben – links unten“. Dieses Beispiel wird in 2.2 weitergerechnet.

$\Sigma$ beschreibt Form und Orientierung der Daten

📄 03_dimred.pdf, Folie 12

Die Kovarianzmatrix beschreibt die Form und Orientierung der Punktwolke im Merkmalsraum. Die Folie zeigt drei 2D-Fälle (die Ellipsen sind Höhenlinien einer Normalverteilung mit dieser Kovarianz):

Fall	$\Sigma$	Form der Punktwolke	Korrelation
1	$\begin{pmatrix}\sigma^2&0\\0&\sigma^2\end{pmatrix}$	Kreis: Varianz in allen Richtungen gleich, die Daten sind isotrop verteilt	unkorreliert
2	$\begin{pmatrix}\sigma_1^2&0\\0&\sigma_2^2\end{pmatrix}$	achsenparallele Ellipse	noch unkorreliert
3	$\begin{pmatrix}\sigma_1^2&\sigma_{12}\\\sigma_{21}&\sigma_2^2\end{pmatrix}$, $\sigma_{12}=\sigma_{21}\neq0$	beliebig gedrehte Ellipse	korreliert

Die Intuition für die PCA kommt aus diesem Bild: Fall 3 ist nur ein gedrehter Fall 2. Dreht man das Koordinatensystem passend mit, wird die Ellipse achsenparallel, die Nebendiagonale verschwindet, und die Variablen sind unkorreliert. Genau diese Drehung sucht die PCA.

Varianz entlang einer Raumrichtung

📄 03_dimred.pdf, Folie 13

Gesucht ist die Varianz der Daten entlang einer beliebigen Richtung. Eine Richtung im $\mathbb R^d$ wird durch einen Einheitsvektor $\mathbf q$ dargestellt, $\lVert\mathbf q\rVert=\sqrt{\mathbf q^\top\mathbf q}=1$. Die Datenpunkte werden nach Abzug des Mittelwerts auf $\mathbf q$ projiziert:

$$a = (\mathbf x-\boldsymbol\mu_{\mathbf x})^\top\mathbf q = \mathbf q^\top(\mathbf x-\boldsymbol\mu_{\mathbf x}).$$

$a$ ist die (vorzeichenbehaftete) Länge des Schattens von $\mathbf x-\boldsymbol\mu$ auf der Geraden durch den Schwerpunkt in Richtung $\mathbf q$. Wegen $\lVert\mathbf q\rVert=1$ ist das wirklich eine Länge. Für längere $\mathbf q$ würde $a$ künstlich mitwachsen.

Der Mittelwert von $a$ ist 0: $\mathcal E[a]=\mathbf q^\top(\mathcal E[\mathbf x]-\boldsymbol\mu)=0$. Also ist die Varianz einfach $\mathcal E[a^2]$:

$$\begin{aligned} \sigma^2(\mathbf q) &= \mathcal E[a^2]\\ &= \mathcal E\big[\big(\mathbf q^\top(\mathbf x-\boldsymbol\mu)\big)\big((\mathbf x-\boldsymbol\mu)^\top\mathbf q\big)\big]\\ &= \mathbf q^\top\,\mathcal E\big[(\mathbf x-\boldsymbol\mu)(\mathbf x-\boldsymbol\mu)^\top\big]\,\mathbf q\\ &= \mathbf q^\top\Sigma\,\mathbf q. \end{aligned}$$

Die einzelnen Schritte:

1. $a$ ist ein Skalar, also $a^2=a\cdot a$. Für den ersten Faktor nimmt man die Form $\mathbf q^\top(\mathbf x-\boldsymbol\mu)$, für den zweiten die transponierte Form $(\mathbf x-\boldsymbol\mu)^\top\mathbf q$.
2. $\mathbf q$ ist fest (nicht zufällig) und kann wegen der Linearität aus dem Erwartungswert herausgezogen werden.
3. Was übrig bleibt, ist die Definition von $\Sigma$.

Kernaussage

Die Varianz der Daten in Richtung $\mathbf q$ ist die quadratische Form $\mathbf q^\top\Sigma\mathbf q$. Die Kovarianzmatrix enthält also die Varianz in jeder Richtung, nicht nur entlang der Koordinatenachsen.

Zahlenbeispiel mit $\Sigma=\begin{pmatrix}2.5&2\\2&2.5\end{pmatrix}$:

Richtung $\mathbf q$	$\mathbf q^\top\Sigma\mathbf q$
$(1,0)^\top$ ($x_1$-Achse)	$2.5$ (das ist einfach $\sigma_1^2$)
$(0,1)^\top$ ($x_2$-Achse)	$2.5$
$\tfrac1{\sqrt2}(1,1)^\top$ (Diagonale)	$\tfrac12(2.5+2+2+2.5)=4.5$
$\tfrac1{\sqrt2}(1,-1)^\top$ (Gegendiagonale)	$\tfrac12(2.5-2-2+2.5)=0.5$

Entlang der Diagonale ist die Varianz mit 4.5 viel größer als entlang jeder Koordinatenachse. Zur Kontrolle: Die Projektionen der vier Punkte auf $\tfrac1{\sqrt2}(1,1)^\top$ sind $\pm\tfrac3{\sqrt2}$, ihr Quadrat ist jeweils $4.5$. ✔

Die Folie hält außerdem fest: Die Varianzen entlang aller Raumrichtungen haben im Allgemeinen Paare von Maxima und Minima, die senkrecht aufeinander stehen. Im Beispiel: Maximum 4.5 bei der Diagonale, Minimum 0.5 bei der dazu senkrechten Gegendiagonale. Diese Richtungen extremaler Varianz sind die Hauptkomponenten, um die es im nächsten Abschnitt geht.

Ergänzung zur Anschauung: Für $\mathbf q=(\cos\varphi,\sin\varphi)^\top$ ergibt sich im Beispiel $\sigma^2(\varphi)=2.5+2\sin2\varphi$. Diese Funktion hat ihr Maximum bei $\varphi=45°$ und ihr Minimum bei $\varphi=135°$, also genau $90°$ versetzt.