date-created: 2024-06-04 02:08:21 date-modified: 2024-06-10 01:24:06

Dimensionsreduktion

anchored to 116.00_anchor_machine_learning Tags: #computerscience #machinelearning #Study

Benennen wir auch als Fluch der Dimensionalität:

Motivation

Wir wollen vorab ergründen, warum es notwendig ist eine gewisse Dimensionsreduktion einzuführen, um so etwa Datenpunkte aus einer Dimension $D$ in eine Dimension $n$ $,D<n$ überzuführen.

[!Motivation]

Betrachten wir jetzt etwa 40 zufallig verteilte Punkte in einer Gau’ßchen Normalverteilung $\mathcal{N}(\mu =\pm 1,\Sigma =0.25\mathbb{I})$ Wir wollen diese Datenpunkte nun in verschiedenen Dimensionen betrachten und hierbei erkennen / nachvollziehen, warum eine Dimensionsreduktion u.U. hilfreich sein kann.

gegebener Punkte, was können wir bei den Daten erkennen? Welche Abhängigkeit findet sich in der Dimension und der Verteilung? #card

Es ist erkennbar, dass die Daten im größeren Raum dazu tendieren, sich weiter zu entfernen / auszubreiten und somit weniger beisammen aufzutreten. (Vergleichbar mit dem Universum und dessen Expandierung!)

–> In höheren Dimensionen sind paarweise Distanzen also größer ( das heißt also, dass der Raum leerer wird).

Dass die Distanzen immer größer werden, ist etwa durch die euklidische Distanz zwischen Punkten erkennbar und wie sie sich immer weiter polarisieren, desto größer die Dimension ist.

[!Important] Interpretation und Erfassen in verschiedenen Dimensionen

Betrachten wir obiges Bild sehen wir, dass die Verteilung und Erfassung einer möglichen Struktur in verschiedenen Dimensionen abweicht.

Inwiefern variiert es in hoch / niedrig-dimensionalen Räumen? #card

Niedrigdimensional: -> Eine kleine Datenmenge erfasst ihre gesamte Struktur (wir haben eine Idee, wie die Daten gemustert / aufgeteilt sind.)

hochdimensional: -> Die gleiche Datenmenge geht im Raum verloren - weil sie sich zu sehr random verteilen.

Anhand der Verteilung in Abhängigkeit mit der euklidischen Distanz können wir ganz gut einsehen, dass sie sich immer weiter verteilen, desto größer die Dimension ist / wird.

[!Example] Fluch der Dimensionalität bei Daten

betrachten wir etwa folgendes Beispiel

was können wir über die Daten in der Dimension, sowie ihrer Verteilung aussagen? #card

• Die Ähnlichkeit von Punkten wird schwierier zu finde, wenn alle PUnkte weit auseinander liegen.
• Da die Daten sehr stark auseinander-fallen und sich in kleinere Gruppierungen / Cluster aufteilen, wird es schwieriger mit diesen zu arbeiten.
• Es wird dadurch zu viel leeren Raum kommen –> Denn die Daten “ leben in einem UNterraum“ bzw einer Mannigfaltigkeit innerhalb des vollen Raumes

Gründe für Dimensionsreduktion

[!Important] Gründe für die Dimensionsreduktion

Unter Betrachtung der Eigenschaft, dass sich Datenmengen mit höherer Dimension immer weiter aufteilen, und somit weniger in Gruppen auftreten:

weswegen möchten wir Dimensionreduktion anwenden? #card

• Wir wollen den Fluch der Dimensionalität bekämpfen bzw die Dimensionen verringern, um so die Komplexität reduzieren zu können.
• wenn wir jetzt einfacherer Modelle aufbauen - solche mit niedriger Dimension - dann sind sie bei kleinen Datensätzen auch robuster!
• Man kann die Daten besser verstehen / visualisieren.

Intuition

(was haben swiss rolls mit Dimensionsreduktion zu tun?) (Schmeckt!)

Man möchte bei der Reduktion meist eine niederdimensionale Struktur / Darstellung erhalten, die aber gewisse Strukturen (aus der Ausgangsdimension) beibehalten kann.

Reduktion | am Beispiel Ziffern erkennen

Wir möchten die Reduktion nun nach und nach definieren und uns hierbei auf das Ursprungsproblem in 116.02_supervised_learning - der Erkennung von hangeschriebenen Zahlen - widmen und es neu betrachten / neu bearbeiten.

Zu Beginn: Haben wir einfach jeden Pixel betrachtet und dann damit versucht die Vorhersage zu treffen. Das geht ohne weiteres ganz gut (bis Noise hinzugefügt wird PCA zum Denoising von Vorhersagen) Hierbei haben wir am Anfang jeden Pixel einzeln betrachtet und verarbeitet. Das waren entsprechend 764 Pixel, die betrachtet und bei der Evaluation bearbeitet werden mussten / müssten. –> wird sehr aufwendig!

Idee zur Verbesserung: Wir wollen eine neue Basis erstellen, in der Bilder dargestellt werden können. (Wir könnten etwa die Menge von Komponenten reduzieren und so überflüssige Details nach und nach entfernen):

Wir sehen im Bild etwa, dass mit nachträglicher Anpassung die Bilder ab einer gewissen Menge wieder relativ ähnlich der Grundlage sind –> wir haben also viele Informationen beibehalten, obwohl wir verringert haben

Dimensionsreduktion durchführen

[!Definition]

Es brauch eine Struktur / einen Ansatz, um Komponenten bzw. Dimensionen zu verringern oder manche entfernen zu können.

Willkürlich entfernen wird nicht helfen und ist somit keine Option zur Lösung.

Wir betrachten zwei Ansätze, um die Dimensionen reduzieren zu können, welche? #card

1. Feature Selection ( also solche entfernen, die womöglich relevanter sind)
2. Forward Selection
3. Backward Selection
4. Feature transformation ( also das Anpassen der vorhandenen Daten, wodurch man versucht gewisse Inhalte / Beziehungen nicht zu verlieren)
5. PCA
6. Isomap
7. t-SNE t-Distributed Stochastic Neighbor Ebedding
8. Autoencoder

Wir haben jetzt also eine Menge von Daten in einem Raum $D$ und möchten sie in einen Raum $N$ “komprimieren / übersetzen”. ( Es ist auch möglich die Dimension gleich zu behalten - dann werden nur die Daten etwas verschoben, was manchmal helfen kann).

Um jetzt diese Daten entsprechend übersetzen zu können betrachten wir zwei Möglichkeiten:

Transduktive | Dimensreduktion

[!Definition] Transduktive Dimensionreduktion

Wir haben bei dieser Reduktions-Maßnahme folgende Aufgabe: Finde eine Darstellung mit niedrigerer Dimenions

Womit werden wir hier also resultieren, was passiert mit Relationen zwischen verschiedenen Punkten aus der Original-Dimension? Welche Implikation entsteht durch neu eingefügte Daten? #card

Wir suchen eine Abbildung/Translation die auf eine niedrigere Dimension abbilden kann, sodass wir dann folgende Datenpunkte erhalten: $$\mathcal{Y}=\{y^1,\dots ,y^N\}\subseteq {\mathbb{R}}^n;n\le d$$

Wir wollen hierbei gewisse Metriken beibehalten, die zwischen den Daten vorgeherrscht haben, Also sollte etwa der Abstand zwischen zwei Punkten in Dimension $d$, weiterhin auch in der niedrigeren Dimension $n$ übertragbar/erkennbar sein.

Visuell etwa folgend:

Wir referenzieren die Übersetzung hierbei an einem vorhandenen Datensatz! -> Das heißt also, dass bei neuen Daten erst wieder die vorherige Menge und möglicherweise Übersetzungsmöglichkeiten gefunden werden müssen.

Das Ganze etwas funktionaler zu machen, beschreiben wir mit dem anderen Verfahren: Es wird jetzt also nicht mehr explizit nach Abhängigkeiten zwischen Punkten gesucht, sondern eine Methode gesucht, die zwischen den Dimensionen übersetzen soll (ohne Reevaluierung, wie bei der Transduktiven Struktur).

Induktiv | Dimensionreduktion

[!Definition] Induktive Dimensionreduktion

Auch hier haben wir wieder Daten einer Dimension gegeben und wollen reduzieren: $$\mathcal{X}=\{x^1,\dots ,x^N\}\subset {\mathbb{R}}^d$$

Unsere Aufgabe besteht auch wieder darin eine Darstellung auf niedrigerer Dimension, jedoch über eine Funktion $phi:{\mathbb{R}}^d\to {\mathbb{R}}^n$ die in den niedrigeren dimensionalen Raum abbildet. Wir wollen also weiterhin die Datenpunkte etablieren: $$\mathcal{Y}=\{y^1,\dots ,y^N\}\subseteq {\mathbb{R}}^n$$

Im Vergleich zur Transduktiven Reduktion, wie ist hier das Vorgehen? Was gilt für einen Datenpunkt Wie werden die Daten übersetzt, was passiert mit neuen Daten, die bei der Entwicklung der Methode nicht einbezogen wurden? #card

Unter Findung der Funktion möchten wir also jeden Datenpunkt folgend übersetzen können: $\varphi (x_i)=y_i$ -> Wir haben eine klare Übersetzungsstrategie, die einen Datenpunkt mit gewissen Parameter etc in einen anderen Raum übernehmen kann. Also $f(x):D\to R$

Vorteil: Bei einem neuen Datenpunkt können wir einfach diese Translation anwenden uund dann entsprechend übersetzen ( ohne Defizite zu erhalten).

Visuell also folgend:

Optimierung | Dimensionreduktionen

Natürlich möchten wir generell immer die beste Möglichkeit finden, um zu übersetzen (transduktiv oder induktiv, beide zielen darauf ab)

Das können wir auch wieder über Feedback evaluieren und verbessern –> etwa durch den Fehler, den wir betrachten können

Transduktive Optimierung

Wir möchten also wieder eine Kostenfunktion definieren können, die wir zum minimieren anwenden können.

[!Information] nicht-parametrische Transformation Optimieren

Wie gehen wir vor um eine Kostenfunktion entsprechend definieren zu können, welche Metriken eignen sich etwa dafür? #card

Man kann die Kostenfunktion generell verschieden beschreiben - weil es darauf ankommt, wie die Übersetzung genau gesetzt wird bzw. woran man die Relationen zwischen Punkten in beiden Dimensionen abhängig macht (etwa gleicher Abstand zwischen zwei Punkten als Metrik) Dann könnte man folgend die Optimierung durchführen: $$\sum _{i=1,j=1}^N(\parallel (\parallel x^i-x^j{\parallel }^2-\parallel y^i-y^j{\parallel }^2){\parallel }^2),y\in {\mathbb{R}}^n$$ -> Also etwa die euklidische Distanz zwischen verschiedenen Punkten vergleichen und schauen, dass die Distanz zwischen Original/Ziel-Dim relativ gleich ist.

Methoden dafür sind etwa:

• Multdimensional Scaling, Local linear Embedding, Isomap, t-SNE

Induktive Optimierung

Auch hier möchten wir eine gewisse Kostenfunktion finden und folglich minimieren, um die beste Übersetzung zu finden.

[!Information] parametrische Transformation Optimieren

Wie definieren wir eine Kostenfunktion, wie wird sie optimiert? Welche Metriken können wir hierbei anwenden? Wie unterschieden wir zwischen linearen Funktionen, neuronalen? #card

Wir möchten auch hier also eine Kostenfunktion definieren, die aussagt “$\mathcal{Y}$ stellt $\mathcal{X}$ gut dar” und sie anschließend optimieren.

Es lässt sich etwa folgende Kostenfunktion definieren, die anschließend minimiert werden kann: $\sum _{i=1}^N(\parallel x^i-\psi (y^i){\parallel }^2),y^i=\varphi (x),\varphi ={\mathbb{R}}^d\to {\mathbb{R}}^n;\psi :{\mathbb{R}}^n\to {\mathbb{R}}^d$ Man möchte hier also einfach “Rücktranslatieren” und herausfinden, wie der Verlust der Informationen / der Position ist. –> Schließlich gehen wir ein, Daten zu verlieren, doch hoffen, dass die Grundstruktur erhalten bleibt.

Es lassen sich für verschiedene Strukturen jetzt Kostenfunktionen definieren.

• lineare Funktionen $\psi ,\varphi$ führen zu einer Hauptkomponentenanalyse / Principal Component Analysis (PCA)
• sofern $\varphi$ als neuronales Netz umgesetzt wird: Nutzung von Selforganizing Maps (SOM)
• sofern beide $\varphi ,\psi$ neuronale Netze sind werden Autoencoder genutzt.

Hauptkomponentenanalyse | Principal Component Analysis | PCA

104.10_matrizen_hauptachsentransformation als Referenz zu dieser Aufgabe, ferner noch 104.09_Singulärwertzerlegung_SZW_SVD

An einem Beispiel betrachten wir einen Raum von Punkten und die Konstruktion einer PCA

[!Example] PCA on data

Wir möchten in diesem Beispiel jetzt also die PCA definieren. Ferner wollen wir die Punkte $\in {\mathbb{R}}^2$ in den Raum ${\mathbb{R}}^1$ übersetzen -> Also 1-Dimensional abbilden

Wie wird die PCA definiert? Was muss beachtet werden? Was definiert / beschreibt die 1D-Darstellung, die wir anstreben? Wenn wir die Funktion gebildet haben ( es gibt viele) welche nehmen wir? #card

Die PCA ist hier eine lineare Funktion: $\varphi (x)=W\cdot x,\psi (y)=U\cdot y;W_{1,2}{x}_{2,1};U_{2,1},y_{1,1}$ Im Beispiel geben wir die Punkte also ${\mathbb{R}}^2\to {\mathbb{R}}^1$ via $\varphi$ an. Dabei ist die Kostenfunktion folgend beschrieben ( berechnet den Abstand) $$\sum _{i=1}^N(\parallel x^i-\psi (y^i){\parallel }^2)$$

Wir erhalten jetzt eine Linie! bzw. sehr viele -> wo wir jetzt noch die beste finden müssen!

Die beste Linie wir diese sein, bei welcher die Varianz der Daten maximiert wird –> wir wollen sie am besten streuen, damit die Informationen nicht verloren gehen: ( daher kommt dann der “Principle Componente”-Part)

Diese Idee müssen wir dann für alle Dimensionen betrachten und da immer die maximal Zerteilung finden und einsehen. –> Es darf keine Dimension vergessen werden.

[!Tip] Vorgehen bei den restlichen $n$ Dimensionen zur Dimensionreduzierung

Wir haben nun für eine gewisse Dimension die Parameter bestimmt, sodass die Translation die beste Variante gibt.

Was ist die zweite - 3,4,… - Richtung der verbleibenden höchsten Varianz? Was wird dadurch gebildet? Wie viele Dimensionen passt man an? #card

Wir wollen ja alle möglichen Richtungen betrachten und die Punkt und deren Varianzen in diesen Daten beibehalten bzw annähern.

Wichtig ist, dass diese “neue Linie” dann Orthogonal zur vorherigen sein wird (weil wir ja eine neue Richtung betrachten)

Wir bilden somit ein neues Koordinatensystem mit einer abnehmenden Varianz entlang der Achsen - die wir aufspannen.

Wir wählen dafür dann immer die ersten $n$ Dimensionen für die Dimensionsreduzierung!

In folgender Darstellung macht man etwa verschiedene PCAs über die Datenmenge, um die Dimensionen abzudecken / ihre Metriken zu übernehmen.

Also von etwa 716 Dimensionen, nehmen wir nur die ersten 100 um sie auf eine Funktion umzusetzen / abzubilden. ( So werden wir es bei der Erkennung von Ziffern umsetzen!)

Herleitung der PCA

[!Important] Herleitung der PCA

Soeben haben wir herausgefunden, dass folgende zwei Ziele bei der Bestimmung der PCA gleich sind: #card

Wir wollen den Unterraum (der Datenmenge, die wir reduzieren wollen) finden, sodass die orthogonale Projektion darauf dann:

• den kleinsten Rekonstruktionsfehler verursacht –> wir verlieren möglichst wenige Informationen aus der Reduktion!
• die meiste Datenvarianz bewahrt –> Also Abstände und Verhältnisse zwischen ihnen erhalten bleiben sollten (im best case) (auch weider geringer Datenverlust als Ziel)

Das möchten wir jetzt folgen konstruieren und formalisieren.

PCA \ Varianz- Maximierungsprojektion

Wir wollen, wie obig gesagt, also die maximale Datenvarianz beibehalten. Das kann durch das finden einer optimalen Richtung beschrieben und definiert werden.

[!Definition] Varianz-Maximierungsprojektion

Wir haben jetzt also das Zie $w\in {\mathbb{R}}^d$ mit der größten Varianz in den Daten zu finden ( $d$ ist die Ausgangsdimension der Daten)

Wir erzeugen jetzt ferner die Projektion $w^T\cdot x$ und dadurch projizieren wir auf einen anderen Raum.

auf diesen Projizierten Raum wollen wir jetzt die Varianz bestimmen: $$Var(w^T\mathcal{X})=\frac{1}{N-1}\cdot \sum _{i=1}^N(w^T\cdot x^i-w^T\overline{x}{)}^2=w^T\cdot S\cdot w$$ (also wir nehmen einfach die normale Definition der Varianz, wenden sie aber auf die Punkte unter Betrachtung der Projektion - die wir konstruiert haben - an)

Hierbei ist ferner $S=\frac{1}{N-1}\sum _{i=1}^N(x^i-\overline{x}{)}^T$ die Kovarianzmatrix

wie fahren wir mit diesen Informationen fort? Was muss gefunden werden, womit resulieren wir? #card

Wir müssen jetzt ferner die Varianz maximieren (indem wir also die Eingabewerte $x\in \mathcal{X}$ manipulieren) $Var(w^T\mathcal{X})$ sollte maximal sein –> das brauch aber constraints.

Diesen Constraint können wir folgend beschreiben $w^T\cdot w{=}^{!}1$ (ist die neue Koordinatenachse)

Dadurch können wir es jetzt folgend umschreiben: $$w=\arg \max (w^T\cdot S\cdot w+\lambda (1-\underbrace{w^T\cdot w}=1))$$ Hierbei beschreibt $\lambda$ den Lagrange Multiplikator (und gleich auch die Eigenwerte):

Wir müssen das Maximum finden, wollen also entsprechend ableiten: $w:S\cdot w=\lambda \cdot w$ und somit sehen wir, dass es sich um ein Eigenwertproblem handelt!

visuell:

Wir lösen jetzt also das Problem der Eigenvektoren und Eigenwerte für die Kovarianzmatrix $S$ ! math2_Eigenvektoren

[!Lemma] Kovarianzmatrix bestimmen:

Wir wollen die Kovarianz-Matrix bestimmen,um anschließend die Eigenwerte für diese bestimmen zu können. Grundlegend baut sich diese Matrix nur aus den Covarianzen zwischen allen $k$ Features ( also Dimensionen) auf.

In welcher Form liegt diese Matrix vor? Wie berechnen wir die Kovarianz $Cov(X_1,X_2)$, was benötigen wir noch? #card

Die Kovarianz $Cov(X_1,X_2)=\frac{1}{N-1}\cdot \sum _i^N((x_i^1-\overline{x^2})\cdot (x_i^2-\overline{x^2}))$ wobei hier $\overline{x^2},\overline{x^1}$ jeweils die Mittelwerte der Dimension (Komponente $x^i$) darstellt. $\overline{x}=\frac{1}{N}\cdot x_1+x_2\dots$ (also einfach die Summe) Ferner ist $Cov(X_1,X_1)=Var(X_1)=\frac{1}{N-1}\cdot \sum _{i=1}^N()$ Die Matrix wird dann folgende Form haben: $$\begin{array}{r}>\left[\begin{array}{cccc}& & & \\ >Var(X_1)& Cov(X_1,X_2,\dots )& \dots & \\ >Cov(X_1,X_2,\dots )& Var(X_2)& \dots & \\ >⋮& ⋮& \ddots & \\ >\dots & \dots & Var(X_n)& \end{array}\right]>\end{array}$$

Dabei ist sie auch symmetrisch!

Wir haben jetzt also gezeigt, dass die Varianz im projizierten Raum beschrieben wird durch folgende Darstellung: $$Var(w^T\mathcal{X})=w^T\cdot S\cdot w$$

[!Tip] Eigenwertproblem lösen zur Maximierung von $w$

Ferner kam noch hinzu, dass wir diese Varianz (den Wert $w$ maximieren möchten) hierbei aber eine Beschränkung definieren mit: $w^T\cdot w=1$.

Wir haben damit dann dem Eigenwertproblem resultiert: $$S\cdot w=\lambda \cdot w$$

sofern wir das Eigenwertproblem lösen, was erhalten wir dann für $w_k,k=1,\dots ,d$_ Wie erhalten wir die Varianz für die neue Achse dann?_ #card

Lösen wir also das Eigenwertproblem, folgt: Wir erhalten: $w_k,{\lambda }_k,k=1,\dots ,d$ Wir können dann die neue Varianz über die neue Achse $k$ folgend beschreiben: $$w_k^T\cdot S\cdot w_k={\lambda }_k$$ -> Also der $k-te$ Eigenvektor zum $k$-ten Eigenwert. (beachte hierbei weiterhin $w^T\cdot w=1$)

Ergebnis:

In dieser Betrachtung ist der Eigenvektor des größten Eigenwertes die Richtung der größten projizierten Varianz!

–> Alle PCA Komponenten $k=1,\dots ,d$ sind dann durch die Eigenvektoren gegeben.

[!Attention] dabei sind sie mit den abnehmenden Eigenwerten gegeben!

Also haben wir diesen Wert, wissen wir das Maximum für den Parameter ( weil wir da ja ein Maximum gefunden haben, bezüglich der Ableitung der Grundformulierung).

Wenn wir jetzt die $w$ berechnet und anders dargestellt haben, wurden die Datenpunkte - wenn wir die Dimensionen nicht verringern - noch nicht wirklich verändert (es würde sich nur drehen).

Das kann manchmal helfen, aber prinzipiell ist dei Komplexität der Daten ähnlich / gleich geblieben!

math2_Matrizen_Grundlage

PCA - Algorithmus

Für die Übungsaufgabe ist die EigenSystem-Funtion noch nicht sortiert - also die erhaltenen Eigenwerte, weswegen wir das noch machen müssen!

Wir möchten jetzt den Algorithmus betrachten, welcher hilft die PCA zu bestimmen und zu definieren:

[!Satz]

Betrachten wir hierfür die mittelwertfreie Datenmatrix $X\in {\mathbb{R}}^{N\times d}=X^{origin}-\overline{X}$ betrachten. Dabei ist $\overline{X}$ spaltenweise der Mittelwert und ferner die Zeilen $x_i\in X$ die N-Datenpunkte darstellt ( also wir haben die Datenpunkte pro Zeile und weiterhin für jede Zeile noch den Mittelwert mit eingebracht!)

Wie läuft der Algorithmus zur Bestimmung der PCA ab?, welche zwei Dinge müssen wir berechnen? Wie wird dann $\varphi$ ausgeführt, was macht es? #card

1. Wir wollen also die Kovarianzmatrix $S$ berechnen: $$S=\frac{1}{N-1}\cdot \sum _{i=1}^N(x^i\cdot x^{i^T})=\frac{1}{N-1}\cdot X^T\cdot X$$ Die Berechnung resultiert in folgendem Raum $\Sigma \in {\mathbb{R}}^{d\times d}$
2. jetzt werden wir die Parameter $w$ und die Eigenwerte entsprechend der vorherigen Umformung bestimmen –> Wir wissen, dass das Eigenwertproblem genau die Werte zur Bestimmung der besten Varianz beschreibt. Bei $W,\lambda =EigenSystem(S)$ sind folgend: $W\in {\mathbb{R}}^{d\times d},\lambda \in {\mathbb{R}}^d,{\lambda }_1\ge {\lambda }_2,\dots$ also die Eigenwerte sind ihrer Größe nach sortiert!
3. anschließend geben wir die berechneten Parameter und den größten Eigenwert zurück (welcher aus der Berechnung folgte)

Hat man diese Werte dann gefunden, kann man noch $\varphi (X,W,n)$ beschreiben, also die Funktion, die die Reduktion mit den gefundenen Parametern umsetzt und darstellen kann!

Der Algorithmus wird folgend beschrieben:

\begin{algorithm}
\begin{algorithmic}
	\Procedure{PCA}{X}
		\State $S = \frac{1}{N-1} \sum\limits_{i=1}^{N}(x^{i}x^{i^{T}}) = \frac{1}{N-1} X^{T}\cdot X$ 
		\Comment{Erstelle Kovarianzmatrix}
		\State $W, \lambda = EigenSystem(S)$ \Comment{Löse das Eigenwertproblem und erhalte die Eigenvektoren $w$ und Eigenwerte $\lambda$}
		\state return $W,\lambda$
		
	\EndProcedure
	
	\Procedure{phi}{X,W,n} 
		\State $W' = W_{i,k=1,\dots n}$ 
		\Comment{ $W' \in \mathbb{R}^{d\times n}$  Where the first n columns are from W So we are reducing the amount we apply / take}
		\State $Y = X \cdot W'$ 
		\Comment{We are reducing the dimension and create new datapoints,$Y \in \mathbb{R}^{N\times n}$ } 
		\State $return~Y$
		\EndProcedure
\end{algorithmic}
\end{algorithm}

Visuell folgend:

Wir wollen noch die Rücktransfomration beschreiben, damit etwa eine Fehlerbetrachtung vorgenommen werden kann:

[!Beweis] Rücktransformieren von niedrigerer Dimension $d\to n$

Wir können ferner noch den Algorithmus beschreiben, der die Translation von der Ziel-Dimension in die Ursprungsdimension ermöglicht / beschreibt:

Wie läuft dieser ab? Welche 3 Werte werden gesetzt/ beschrieben? #card

  \begin{algorithm} 
  \begin{algorithmic}  
  \Procedure{psi}{Y,W}
  \State $n = Dimension(Y)_{2}$  \Comment{taking the amount of columns in $Y$}
  \State $W' = W_{k=1,\dots,n,i}$ \Comment{taking the first $n$ rows from $W$ to process $W'$ accordingly (reverse changes basically)}
  \State $\hat{X} = Y \cdot W'^{T}$ \Comment{retrieving the "original" $\hat{X} \in \mathbb{R}^{N\times d}$}
  \State $return ~ \overline{X}$

\EndProcedure \end{algorithmic} \end{algorithm}

Wir nehmen also die Zielwerte und versuchen dann ein angepasste <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.9468em;"></span><span class="mord accent"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.9468em;"><span style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord mathnormal" style="margin-right:0.07847em;">X</span></span><span style="top:-3.2523em;"><span class="pstrut" style="height:3em;"></span><span class="accent-body" style="left:-0.1667em;"><span class="mord">^</span></span></span></span></span></span></span></span></span></span> - was die original-annehmen soll - zu bestimmen, indem wir die Parameter von <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.13889em;">W</span></span></span></span> entnehmen und die Matixmultiplikation umsetzen.

Während jetzt die Grundidee und die Umsetzung klar / bzw definiert ist steht die Frage offen, welche Komponenten man nimmt, bzw. wie viele sinnig sind –> Bei Der Reduktion von einer hohen Dimension in eine niedrigere.

$$\text{Wann lohnt es sich eine gewisse Menge von Komponenten nicht zu betrachten?}$$

Bestimmen der Menge von Komponente (Zieldimension $d$)

Wir können dieses Vorgehen ganz gut am Beispiel der MNIST-Ziffern (die wir erkennen möchten) darstellen.

Anwendung bei Ziffern-Erkennung

Darstellung der Pixel entspricht primär der Summe der einzelnen Werte $\sum _{i=1}^{728}(x_i{e}_i)$ wobei $x_i$ der Pixelwert und $e_i$ der Einheitsvektor ist. Visuell haben wir also folgende Grundwerte vorliegen: (Also jeder Pixel in einem möglichen Bild - die in ihrer Größe genormt sind - hat einen Einfluss auf das Bild –> ist also ein Parameter den wir betrachten müssen).

Wir wollen eine neue Darstellung definieren, die die Menge von Pixeln, die relevant sind für eine Aussage, reduzieren. wie gehen wir hierbei vor? #card Wir können jetzt die neue Darstellung mit $\sum _{i=}^n(y_i{w}_i)$ beschreiben, wobei $y_i$ Koeffizient, $w_i$ Hauptkomponenten sind. (Wir haben also effektiv die Menge von Datenpunkten, die wir betrachten, reduziert und versucht möglich redundante Pixel (Dimensionen hier) zu entfernen). Visuell sieht die neue Darstellung etwa folgend aus:

Wir können jetzt mit der neuen Darstellung $\sum _{i=1}^n(y_i{w}_i)$ (wobei $y$ die angepassten Daten darstellt, und $w_i$ die Parameter zum translatieren waren/sind) folgend in den Urpsrungs-Raum abbilden. wie wird das umgesetzt, was brauchen wir? #card

Dann können wir ferner die Grundstruktur wieder rekonstruieren: indem wir also die Rückkehr-Abbildung und die Abbildung vom Ursprungs-Raum $x$ in den Zielraum $d$, also die Funktion $\varphi (x)=y$ anwenden: $$\hat{x}=\psi (\varphi (x))$$ Visuell etwa –> Wir können erkennen, dass die “Bilder” sich nur schwach unterscheiden, aber die markanten Formen / Strukturen noch erkennbar sind! (Man brauch also nicht alle Werte, um bestimmen zu können)

Menge der Komponenten festlegen

Wir sehen in den obigen Beispielen, dass mit unterschiedlicher Reduktion die Rekonstruktionen meist ähnlich aussehen - jedoch teils auch verschiedene charakteristiken verloren gehen können.

Fraction Variance Explained ist die Metrik, die uns angibt, wie viel Varianz wir beim Rekonstruieren recovern/ erzielen konnten –> Im Vergleich zum Ausgangswert, den wir vor der Reduktion hatten bzw betrachtet haben

[!Definition] Bestimmen der Fraction Variance Explained (FVE)

Unter folgender Leitfrage möchten wir jetzt eine Metrik betrachten, um die richtige Menge von Komponenten zu erhalten / entfernen.

–> Wie viel Varianz können wir von den Daten wegnehmen, um dennoch eine gute Rekonstruktion zu erhalten?

Wie können wir das durch die FVE bestimmen. Was berechnet sie, was sagt sie aus? #card

Wir wollen dafür die FVE als Metrik zum Einschätzen der optimalen Komponenten (um weiterhin eine gute Rekonstruktion zu erhalten) berechnen: $$FVE=\frac{\sum _{k=1}^n({\lambda }_k)}{\sum _{j=1}^d({\lambda }_j)}$$ (Wir sehen hier, dass die Eigenwerte miteinander in relation gesetzt werden. Die Summe der $n$ Eigenwerte wird durch die Menge der $d$ (Entsprechend der Zieldimension) Eigenwerte berechnet)

Interpretieren: Wir betrachten die Ergebnisse der folgenden Werte immer im Kontext darin, dass wir die Fehlerrate der Rekonstruktion berechnen möchten: $\hat{x}=\psi (\varphi (x))$!

Ist der $FVE=1$, dann haben wir eine perfekte Rekonstruktion erhalten, wo es keine Fehler gibt. (Das wird angestrebt, weil es darüber aussagt, dass wir eine gute Menge von Komponenten haben)

Ist $FVE=0$ gibt es uns eine Aussage darüber, dass die Auswahl der Komponenten nicht gut ist –> wir eine schlechte Vorhersage haben und diese so schlecht, wie der Mittelwert ist!

Die obige Berechnung kann man jetzt als Funktion darstellen, um so einen bestimmten Wert zu finden –> gewisse Threshold zu setzen etwa:

Was wir hieraus also ziehen / erkennen können:

Desto mehr Dimensionen / Komponenten, wir einbeziehen, desto höher wird der $FVE$-Score. Aber er wächst nur noch sehr marginal, das heißt wir können hier die Reduktion erhöhen, wenn wir eine gewisse Sicherheit/ beibehalten möchten –> Wir suchen also das Optimum, sodass wir die Anzahl der Komponenten bestimmen können.

BSP: $N=D$, haben wir dann irgendeinen Fehler, der auftritt. –> Nein, weil wir den Raum nur einmal drehen und bei der Rekonstruktion wieder zurückdrehen –> wir haben also keinen Verlust von Informationen

Folgerung dieser Idee:

Wir können jetzt durch diese Betrachtung erfahren, wie viele Komponenten wir entfernen können, ohne zu viel Sicherheit zu verlieren - während aber der Aufwand sinkt.

Anwendungen der PCA | Principal Component Analysis

[!Tip] Datenkompression

Angenommen wir haben hochdimensionale Daten, inwiefern kann uns hier die PCA helfen? Wie wird $n$ meist gewählt? #card

Wenn die ursprünglichen Daten hochdimensional sind, dann kann man die PCA verwenden, um eine niederdimensionale Darstellung zu erhalten ( also die Dimensionsreduktion!), sodass wir weniger Speicher nutzen, und die Berechnungen sparender durchführen können.

Weiterhin wird für das $n$ (also die Menge von Dimensionen die wir erhalten) meist so gewählt, dass die varianz zu 95% / 99% erhalten bleibt! (Betrachten wir etwa durch den FVE score!)

[!Tip] Anwendung für Denoising | Daten-Entrauschung

Angenommen die Ursprungsdaten sind verrauscht, inwiefern kann die PCA dabei helfen? Wie verhält sich das $n$ hier? #card

Sind die Ursprungsdaten verrauscht, so kann man mit der PCA und anschließender Rekonstruktion die Daten etwas vom rauschen reduzieren. Wir nehmen also die Hauptpunkte und wichtigsten Parameter der Ursprungswerte, bilden diese ab und nehmen dann die Rekonstruktion als Ursprung an –> sodass die Ausreißer nicht mehr inbegriffen sind.

Hierbei hängt $n$ vom bekannten Rauschpegel ab! –> sonst komprimieren wir ähnlich, wie bei der Datenkompression!

[!Important] Anwendung in der Datenvisualisierung

Angenommen die Ursprungsdaten sind hochdimensional, wie kann uns PCA hier helfen, sie besser zu visualisieren? #card

Da wir durch die PCA in verschiedene Dimensionen abbilden können, kann sie etwa in den 2 / 3 dimensionalen Raum abbilden und so Cluster oder Ähnlichkeiten gut / einfach verständlich darstellen.

Man wähle hier dann also $n=3\vee 2$, um entsprechend zu visualisieren!

Wir sehen also, dass wir die PCA insofern anwenden können, um die wichtigsten Merkmale zu extrahieren, gewisse Abhängigkeiten oder Beziehungen zu visualisieren - Datenvisualisierung - oder um Daten “von Unreinheiten zu bereinigen” (Denoising).

Letzteres können wir nochmal am Beispiel der MNIST-Werte zeigen / darstellen:

Beispiel |PCA zum Denoising von Vorhersagen:

Wir wollen jetzt die Eigenschaft der PCA durch einen Datensatz von den MNIST-Ziffern mit Noise darstellen/zeigen.

Wir haben also Ziffern mit noise versehen, wodurch sie mehr random sind bzw. unser Modell eventuell beeinflusst wird. Das originale MNIST-Erkennungstool, mit allen Komponenten wurde somit weniger akkurat, weil wir ja jetzt plötzlich Noise haben, die bei manchen “Bereichen der Erkennung” einen neuen Bias geschaffen haben:

Wir möchten jetzt die PCA zur Denoising anwenden. Wir erhalten mit einer PCA und $n=150$ (was noch 95% der Varianz erhält) folgenden Datensatz:

Wir können folgend die Ergebnisse einsehen, einen Vergleich zwischen der Erkennung mit und weniger Noise betrachten ziehen:

(Hat sich also gelohnt :))

Beispiel | Datenvisualisierung via PCA:

Wir wollen auch noch den Aspekt der Datenvisualisierung betrachten und an einem Beispiel festmachen:

Dafür können wir auch wieder die MNIST-daten und die erste beiden PCA betrachten:

Was wir hierbei sehen:

[!Attention] Erkenntnis zur PCA als Datenvisualisierung

Wir sehen hier, dass die PCA uns einen stark überlappenden Haufen von Daten verschiedener Art darstellt. Es kam also keine gute Clusterung vor, die das Ganze eventuell besser visualisiert

Das ist ein wichtiger Trait der PCA: Sie kann Daten nicht immer so optimal trennen

Ferner kann die PCA-Analyse manche Charakteristiken, wie die Orientierung nicht gut erkennen ( sie schaut sich ja nur ähnliche Werte an, mehr nicht (im Beispiel unten sind es die Helligkeitswerte! )).

Dass sie die Orientierung nicht gut erkennen kann, sieht man im folgenden Beispiel gut:

[!Attention] Alternative, die besser zur Visualisierung genutzt werden kann:

116.11_t_SNE_visualisation

PCA | Anmerkungen | Fazit

[!Beweis] Anmerkung zur Daten-Normalisierung

Angenommen wir wissen, dass die Skalierung von Merkmalen eine gewisse Bedeutung einfügt, wie gehen wir dann vor? Wenn wir nicht wissen, wie die Merkmale strukturiert sind - davon ausgehen, dass sie gleich wichtig sind - was machen wir dann? #card

Wenn die Skalierung der Merkmale eine Bedeutung hat, dann transformieren wir nur die Daten, damit dann der Mittelwert $0$ ist!

Wissen wir nicht, wie die Merkmale aufgeteilt sind ( oder wir denken, dass sie alle gleich wichtig sind), dann müssen wir die Daten ferner standardisieren

Wir können folgend zum Mittelwert $=0$ umwandeln. Beschrieben wir das durch die Einheitsvarianz: $$X_i=(X_i^{origin}-\overline{X_i})/Var(X_i)$$

Zusammenfassung zur PCA:

[!Summary] PCA und ihre Eigenschaften

Folgend also eine Zusammenfassung, die Vorteile, Eigenschaften, Nachteile und die Core-Idee der PCA wiedergibt:

Was macht die PCA mit Daten? Welcher Abbildung entspricht sie? Welche Vorteile weist sie auf, welche Nachteile? #card

1. Die PCA dreht das Koordinatensystem so, dass die erste Achse die höchste Varianz aufweist, die zweite die zweithöchste etcetc (daher ordnen wir auch die Eigenwerte, weil sie darüber einen Aufschluss geben!)
2. Die PCA ist verlustfrei und eine lineare Transformation, wenn alle Komponenten beibehalten werden (sie verändert also nicht viel, außer die Orientierung!)
3. Wir können mit der PCA Unterräume entfernen, welche wenig Varianz (und somit weniger Relevanz in der Betrachtung) haben

Vorteile

1. PCA ist relativ einfach
2. PCA ist schnell und kann schnell / gut helfen!

Nachteile: Sie ist durch eine linearität, die sie charakterisiert beschränkt in den Fähigkeiten!