Wyjaśnić kroki algorytmu LLE (lokalne osadzanie liniowe)?

13

Rozumiem, że podstawowa zasada algorytmu dla LLE składa się z trzech kroków.

  1. Znajdowanie sąsiedztwa każdego punktu danych za pomocą niektórych miar, takich jak k-nn.
  2. Znajdź wagi dla każdego sąsiada, które oznaczają wpływ sąsiada na punkt danych.
  3. Skonstruuj osadzanie danych w małych wymiarach na podstawie obliczonych wag.

Ale matematyczne wyjaśnienie kroków 2 i 3 jest mylące we wszystkich podręcznikach i zasobach online, które przeczytałem. Nie jestem w stanie zrozumieć, dlaczego formuły są używane.

Jak te kroki są wykonywane w praktyce? Czy istnieje jakiś intuicyjny sposób objaśnienia zastosowanych wzorów matematycznych?

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

Użytkownik1234321232
źródło

Odpowiedzi:

10

Lokalne osadzanie liniowe (LLE) eliminuje potrzebę szacowania odległości między odległymi obiektami i odzyskuje globalną nieliniową strukturę przez lokalne dopasowania liniowe. LLE jest korzystny, ponieważ nie wymaga żadnych parametrów, takich jak wskaźniki uczenia się lub kryteria konwergencji. LLE skaluje się również dobrze z wewnętrzną wymiarowością . Funkcja celu dla LLE to Macierz wagowa elementów dla obiektów i jest ustawiona na zero, jeśliY

ζ(Y)=(YWY)2=Y(IW)(IW)Y
Wwijijjnie jest najbliższym sąsiadem , w przeciwnym razie wagi dla najbliższych K sąsiadów obiektu są określane przez dopasowanie najmniejszych kwadratów z gdzie zmienna zależna jest wektorem z nich, jest macierzą Gram dla wszystkich najbliższych sąsiadów obiektu , a jest wektorem wag, które są zgodne z ograniczeniami sumy do jedności. Niech będzie symetrycznym dodatnim półfinałemii
U=Gβ
UK×1GK×KiβK×1DK×Kmacierz odległości dla wszystkich par najbliższych sąsiadów K obiektu -wymiarowego . Można wykazać, że jest równa podwójnie wyśrodkowanej macierzy odległości z elementami W współczynniki regresji określono ilościowo stosując pxiGτ
τlm=12(dlm21Kldlm21Kmdlm2+lmdlm2).
K
βK×1=(ττ)K×K1τUK×1,
i są sprawdzane, aby potwierdzić, że sumują się do jedności. Wartości są osadzone w rzędzie z w różnych miejscach słupów odpowiadających K-najbliższych sąsiadów obiektu , jak również elementów transponowanie. Jest to powtarzane dla każdego tego obiektu w zbiorze danych. Warto zauważyć, że jeśli liczba najbliższych sąsiadów jest zbyt niska, może być rzadki, co może utrudniać analizę własną. Zaobserwowano, że najbliższych sąsiadów skutkowałoβiWiiKWK=9Wmatryce, które nie zawierały patologii podczas analizy własnej. Funkcja celu jest zminimalizowana przez znalezienie najmniejszych niezerowych wartości własnych Skrócona postać jest reprezentowana przez gdzie ma wymiary oparciu o dwie najniższe wartości własne .
(IW)(IW)E=ΛDE.
XY=EEn×2Λ

wrktsj
źródło
„K = 9 najbliższych sąsiadów” Czy to nie zależy od wymiarów ? Na przykład, jeśli ma mniej niż 9 wymiarów, to macierz wag nie jest jednoznacznie określona. Czy to powoduje problemy z LLE? YYW
Scott
Tak, ale jeśli istnieje, powiedzmy, 8 wymiarów, to dla losowych danych dosłownie każdy punkt można zapisać idealnie jako liniową kombinację 9 innych, na nieskończoną liczbę sposobów.
Scott
Podczas wdrażania techniki zawsze istnieją scenariusze „co jeśli” i dlatego stosowane są ograniczenia parametrów.
wrktsj