Manifold Learning

Problem: Methoden wie PCA / ICA finden nur lineare Teilräume zur Beschreibung der Daten -> in manchen Fällen für die Repräsentation nicht geeignet

Grund: euklidische Distanzen spiegeln nicht die wahre Verteilung der Daten wider -> stattdessen sollten geodesische Distanzen verwendet werden, die entlang eines gekrümmten Teilraums berechnet werden

Punktmenge M, in der jeder Punkt eine offene lokale Nachbarschaft hat, die 1:1 auf den R^N (für ein N) abgebildet werden kann

• M ist lokal ähnlich zu R^N

dim(M) = N

generell: Manifold ist ein Raum, der lokal wie der Euklidische Raum behandelt werden kann

Manifolds können durch eine Menge von überlappenden, lokal Euklidischen Approximationen beschrieben werden

= Multi-dimensional Scaling

Ziel: finde Koordinaten von Punkten anhand ihrer paarweisen Distanzen

für Representation Learning: bilde Datenpunkte von Dimension N auf niedrigerdimensionalen Raum M ab unter Beibehaltung der paarweisen Distanzen zwischen den Datenpunkten

starte mit Dissimilarity Matrix (enthält paarweise Distanzen zwischen Punkten im Originalraum)

• verschiedene Metriken möglich

dann: ordne jeden Punkt einer Position im neuen Feature Space zu

• Bedingung: Distanzen werden von der Abbildung beibehalten

Annahme: Input Space ist Euklidisch, Distanzmetrik ist euklidische Norm

Optimierungsproblem: minimiere Summe (dijX-dijY)^2 über alle Kombinationen i,j = 1,…,p bezüglich Y

• dijX = ||xi-xj||^2: quadrierte Abstände im Originalraum

• dijY = ||yi-yj||^2: quadrierte Abstände im Merkmalsraum

Differenz zwischen Distanzmatrizen DX und DY: “stress”

Erzeuge Gram’sche Matrix B = -1/2 HDH

• H: zentriert Datenpunkte (H= I-1/p 11^T)

• D =DX: Distanzmatrix

Lösung: Y = V S (Dimension pxM)

• V (dim pxM): enthält Eigenvektoren zu M größten Eigenwerten von B

• S^2: Diagonalmatrix mit M größten Eigenwerten von B

Classical MDS (Metrik global euklidisch) liefert dieselben Features wie PCA

ersetze Euklidische Abstäde durch geodesiche Abstände

geodesische Distanzen können lokal durch Euklidische Distanzen approximiert werden

• Annahme: lineares Modell kann nichtlineare Struktur ausreichend beschreiben

• für weiter entfernte Punkte: schätze geodesische Distanz durch Summe aller benachbarten Punkte auf dem entsprechenden Pfad

praktische Umsetzung: definiere Nachbarschaft durch K (nächste Punkte) oder ε (Radius)

• kritische Parameter, müssen vorab festgelegt werden

• wenn Nachbarschaft zu groß: Annahme eines lokal linearen Modells trifft nicht mehr zu, Topologie des Manifolds wird verfälscht (ähnlicher zu Euklidischen Distanzen) => v.a. problematisch bei verrauschten Daten

• Nachbarschaft zu klein: Manifold zerfällt in unverbundene Regionen -> Distanzen unendlich

Idee: jeder Datenpunkt + seine Nachbarn liegen auf einem (nahezu) lokal linearen Patch

Datenpunkt kann durch Linearkombination seiner Nachbarpunkte linear rekonstruiert werden -

Ansatz: dieselben Koeffizienten zur Rekonstruktion im Originalraum sollten auch für die Rekonstruktion im Merkmalsraum verwendet werden können

• -> Erhalt der lokalen Geometrie

Optimierungsproblem:

1. minimiere Kostenfunktion E(W), um Koeffizienten Wij zu finden

2. minimiere Embedding Cost function Φ(Y), um embedding Y = (yi) zu finden

Problem ist korrektgestellt, kann als sparses Eigenvektor-Problem gelöst werden

• zusätzliche Bedingungen: mittelwertfreie zentrierte Daten, Kovarianzmatrix = I

Ermittlung von Dimension M des Merkmalsraums: Energie-Threshold für Eigenwerte der Lösung

recheneffizient:

• vermeidet große dynamic programming problems

• Matrizen sind generell sparse -> Ausnutzung für Einsparungen (Speicher & Rechenzeit)

Unterschied zwischen LLE und Isomap:

• LLE nutzt ausschließlich lokale Eigenschaften des Manifolds

• Isomap nutzt globale (geodesische) Distanzen

wenn Datenpunkte nur in Form des Skalarprodukts auftreten, können Daten in anderen Raum Φ(x) abgebildet werden

• Skalarprodukte <Φ(xi),Φ(xj)> können ausgerechnet werden, ohne Φ direkt auszuwerten

Kernel (functions): K(xi,xj) = <Φ(xi),Φ(xj)>

• Φ(x) muss nicht bekannt sein; es reicht die Kernel-Matrix zu kennen

• wenn K positiv semidefinit: kann wie Matrix von Skalarprodukten verwendet werden

oft in Klassifikation angewandt -> Muster sind in höherdimensionalen Räumen linear separabel

• alternative Interpretation: linear Klassifikator im Raum von Φ(x) korrespondiert zu nichtlinearem Klassifikator im Raum der x

typisches Beispiel: Gauss-Kernel

Ziel: lerne nichtlineare Repräsentation mit dem Kernel-Trick

Kernel K (dim pxp) = B: Gram Matrix im Raum der Φ(x)

Kernel-PCA und MDS sind äquivalent wenn die Kernel-Funktion isotropisch ist (nur von Distanzen abhängt)

Lösung: Y = V*S (siehe MDS)

• äquivalent zu PCA im Raum der Φ(x)

no-trick-solution: Eigenwertanalyse auf C = K^T statt auf K

alle Methoden können als Spezialfall von Kernel-PCA mit verschiedenen Kernels betrachtet werden

MDS: K = B = -0.5(I - 1/p 11^T) D I - 1/p 11^T)

Isomap: wie MDS, aber andere Distanzmatrix (geodesische Distanzen)

LLE: K = λmax I - L

• λmax: größter Eigenwert von L

• L = (I-W)^T (I-W) (W: Matrix mit Gewichten zur Rekonstruktion)

• LLE ist Kernel-PCA, wobei der Kernel für den spezifischen Datensatz gelernt wurde