Repr. Learn. mit Manifolds: MDS und ISOMAP, LLE und kPCA Flashcards
Multidimensional Scaling (MDS)?
= kPCA
Ähnlichkeitsstrukturanalyse
Konzeptionell nimmt MDS die Unterschiede oder Entfernungen zwischen den in den Daten beschriebenen Elementen auf und generiert eine Karte zwischen den Elementen
Es werden also Informationen über Paare von Objekten erhoben, um daraus metrische Informationen über die Objekte zu ermitteln
MDS: Koordinatenpunkte finden, Distanzen euklidisch berechnen und beibehalten, wenn in kleinere Dim. projiziert.
Die Objekte räumlich so anordnen, dass die Distanzen im Raum exakt den Un/ähnlichkeiten entsprechen. Je weiter die Objekte voneinander entfernt sind, desto unähnlicher sind sie.
Paarweise Ähnlichkeiten beurteilen - Distanzen in Euklidmetrik berechnen
PCA und MDS Unterschied?
Die Methoden finden die gleichen Feature am Ende, Mathemathik ist ähnlich/gleich.
PCA: Ermittelt Korrelation zwischen Datenpunkten
MDS: Ermittelt Distanzen zwischen Datenpunkten. Reproduziert Unterschiedlichkeiten auf der Karte direkter und genauer als PCA
nicht metrische MDS
Nichtlineare Methode zur Reduzierung der Dim., erweitert die metrische MDS durch Einbeziehung der geodätischen Entfernungen , die durch einen gewichteten Graphen vorgegeben werden .
lineare Subspace oft zu einfach –> also zum Manifold übergehen
ISOMAP
kPCA mit spezifischem Kernel
nutzt MDS (nicht-metrisch) Euclidean -> geodätische Distanzen
Wie die euklidischen Distanzen zu geodätischen machen? (ISOPMAP)
Die euklidischen Distanzen lokal nutzen –> mehrere euklidische Distanzen addieren (oder Integral)
Geodätische und euklidische Distanz?
Geodätisch: Die Distanz auf einer Mannigfaltigkeit (Oberfläche einer Kurve) gemessen (euklidische würde kürzer sein). die kürzeste mögliche Verbindung zwischen zwei Punkten unter bestimmten Bedingungen. Kreisbogen auf der Erde (nicht durch die Erde buddeln)
euklidisch: Länge oder auch der Betrag des Verbindungsvektors zweier Punkte oder Vektoren
ISOMAP Vorgang
1a: Nachbarschaft definieren.
Diese Nachbarschaft kann entweder durch Auswahl der
- K (nächstgelegenen Punkte) oder
- Epsilon (Menge der Punkte innerhalb eines Radius)
berechnet werden –> diese werden vorbestimmt.
1b: Nachbarn verbinden
1c: jede Kante gewichtet mit dem euklidischen Abstand zwischen zwei Punkten
2: –> geodätischer Abstand berechnen: kürzester Weg von A nach B mit den euklidischen Distanzen
2a: Abstand zwischen allen Paaren über allen verbundenen Wegen
2b: die kürzeste Distanz finden ( Stressmatrix minimieren)
wir haben dann Stressmatrix –> Gram Matrix –> Eigenvektoranalyse –> Lösung (Eigenwerte: wichtige Feature?)
Was muss beachtet werden bei der Nachbarschaft? ISOMAP
darf nicht zu klein/groß sein –> sonst trifft keine Datenpunkte/könnte die Struktur (der Spirale) zerstören
LLE?
= kPCA
LLE ist lokal, nicht global wie PCA
- Nachbarschaft definieren (wie ISOMAP)
- vermuten, dass wir lokale lineare Struktur haben: wir schätzen jeden Datenpunkt mit einer Gewichteten Summe dessen Nachbarn
- -> Fehler, wenn wir das mit dem originalen Datenpunkt vergleichen –> minimization/optimization problem wo wir die weights definieren. - eine Dim. wählen und behalten die weights, die von den Nachbarn und nicht vom Space abhängen
- die neuen Datenpunkte finden (feature) durch linearen Strukturen ,die vermutet werden erhalten zu bleiben,
- Bedingung festlegen: das die Summe der weights =1 für jeden Datenpunkt
- -> gelöst sparse Sigenwertprobem
kPCA?
Kernel?
kernel Trick?
Kernel:
- Klasse von Algorithmen, die sich eines Kernels (Kern) bedienen, um Berechnungen in höherdim. Raum auszuführen Support Vector Mashines und Kerne-PCA
- Eine Ähnlichkeitsfunktion, die zwei Eingaben entgegennimmt und die Ähnlichkeit zwischen den beiden zurückgibt. Gram Matrix)
- Für nicht-lineare Probleme
Kernel trick:
- Anwendung linearer Klassifikator auf nicht linear klassifizierbare Daten
- Daten werden in höherdim. Raum transformiert Hoffnung aufbessere lineare Seperierbarkeit
- Mit Phi als Featuremapping/Merkmalsabbildung in einem Featurespace/Merkmalsraum
- Phi: R^2 R^3 trotzdem vergrößern wir nicht wirklich die Dim., sondern eine andere Dim. Dazu projizieren.
LLE Algorithmus?
- k/Epsilon Nachbarschaft def.
- Weightmatrix finden durch Fehler minimieren über X (in Dim N)
- die neuen Datenpunkte/Feature in M finden durch minierung der embetteten Kostenfunktioen (Fehler Minimieren über Y, die Koeffizienten beibehalten, mit Bedingung)
Was würde passieren wenn die Größe der Nachbarchaft zu groß ist? (alle Datenpunkte abdecken)
Wie wählt man die Dimension des Featurespace M?
wie
man würde etwas wie die PCA bekommen.
- Wenn Dimension der Manifold nicht bekannt: Mit einer niedrigen Dim. Starten und dann sequentiell vergrößern bis zu Einbettungen,die das Problem lösen
typischer kernel?
Gaußscher Kernel
Kernelfunktion?
eine Funktion, die ein Skalarprodukt zurück bringt in den projizierten Raum: jede positive semi-definite pxp Matrix (kann Kpxp sein?)
Trick vom kPCA?
Wir machen etwas lineares in einem höher dim. Raum, im originalen Raum nichtlinear ist
