Erklären Sie die Schritte des LLE-Algorithmus (Local Linear Embedding).

12

Ich verstehe, dass das Grundprinzip des Algorithmus für LLE aus drei Schritten besteht.

  1. Ermitteln der Nachbarschaft jedes Datenpunkts anhand einer Metrik wie k-nn.
  2. Suchen Sie für jeden Nachbarn Gewichte, die die Auswirkung des Nachbarn auf den Datenpunkt angeben.
  3. Konstruieren Sie die niedrig dimensionale Einbettung der Daten basierend auf den berechneten Gewichten.

Die mathematische Erklärung der Schritte 2 und 3 ist jedoch in allen von mir gelesenen Lehrbüchern und Online-Ressourcen verwirrend. Ich kann nicht nachvollziehen, warum die Formeln verwendet werden.

Wie werden diese Schritte in der Praxis durchgeführt? Gibt es eine intuitive Möglichkeit, die verwendeten mathematischen Formeln zu erklären?

Referenzen: http://www.cs.nyu.edu/~roweis/lle/publications.html

User1234321232
quelle

Antworten:

9

Durch lokales lineares Einbetten (Local Linear Embedding, LLE) muss der Abstand zwischen entfernten Objekten nicht mehr geschätzt werden, und die globale nichtlineare Struktur wird durch lokale lineare Anpassungen wiederhergestellt. LLE ist vorteilhaft, weil es keine Parameter wie Lernraten oder Konvergenzkriterien enthält. LLE skaliert auch gut mit der intrinsischen Dimensionalität von Y . Die Zielfunktion für LLE ist

ζ(Y)=(YWY)2=Y(IW)(IW)Y
Die GewichtungsmatrixW Elementewij für Objektei undj werden auf Null gesetzt, wennj kein nächster Nachbar voni , andernfalls die Gewichte für die K- nächste Nachbarn des Objektsi überkleinsten Quadrate bestimmt werden Anfälle von
U=Gβ
wobei der abhängigen VariableU aK×1 - Vektor von Einsen,G aK×K Gramm-Matrix für alle nächsten Nachbarn des Objekts i , und β ist ein K×1 Vektor von Gewichten, die Summen-zu-Einheits-Beschränkungen folgen. Sei D eine symmetrisch positive semidefinite K×K Distanzmatrix für alle Paare der K-nächsten Nachbarn des p dimensionalen Objekts xi . Es kann gezeigt werden, dass G gleich der doppelt zentrierten Distanzmatrix τ mit Elementen
τlm=12(dlm21Kldlm21Kmdlm2+lmdlm2).
DieKRegressionskoeffizienten werden unter Verwendungnumerisch bestimmt
βK×1=(ττ)K×K1τUK×1,
und überprüftum sie auf Eins summieren zu bestätigen. Die Werte vonβsind in die ReiheivonWeingebettetW an den verschiedenen Spaltenpositionen, die den K-nächsten Nachbarn des Objekts entsprecheni , sowie den Transponierungselementen. Dies wird für jedesi te Objekt im Datensatzwiederholt. Es ist zu beachten, dass W spärlich sein kann, wenn die Anzahl der nächsten NachbarnK zu gering ist,was dazu führt, dass die Eigenanalyse schwierig wird. Es wurde beobachtet, dass K = 9 nächste Nachbarn zu W- Matrizen führten, die während der Eigenanalyse keine Pathologien enthielten. Die Zielfunktion wird minimiert, indem die kleinsten Nicht-Null-Eigenwerte von ( I - W ) ( I - W ermittelt werdenWK=9W
(IW)(IW)E=ΛDE.
Die reduzierte Form vonX wird durchY=E wobeiE Dimensionenn×2 die auf den zwei niedrigsten Eigenwerten vonΛ basieren.

JoleT
quelle
"K = 9 nächste Nachbarn" Kommt es nicht auf die Dimensionalität von ? Wenn Y beispielsweise weniger als 9 Dimensionen hat, wird die Gewichtsmatrix W nicht eindeutig bestimmt. Verursacht dies Probleme mit LLE? YYW
Scott
Ja, aber wenn es zum Beispiel 8 Dimensionen gibt, kann für zufällige Daten buchstäblich jeder Punkt perfekt als eine lineare Kombination von 9 anderen auf unendlich viele Arten geschrieben werden.
Scott
Bei der Implementierung einer Technik gibt es immer "Was-wäre-wenn" -Szenarien. Deshalb werden Parameterbeschränkungen verwendet.
JoleT