Kiedy stosować lemat Johnson-Lindenstrauss zamiast SVD?

Lemat Johnsona-Lindenstraussa pozwala reprezentować punkty w przestrzeni o dużych wymiarach w punktach o niższych wymiarach. Podczas znajdowania najlepiej dopasowanych mniejszych wymiarów, standardową techniką jest znalezienie rozkładu wartości w liczbie pojedynczej, a następnie wzięcie podprzestrzeni wygenerowanej przez największe wartości w liczbie pojedynczej. Kiedy warto zastosować Johnson-Lindenstrauss zamiast SVD?

machine-learning użytkownik09128323
źródło

Odpowiedzi:

Te dwa podejścia dają bardzo różne gwarancje.

JL Lemma mówi w zasadzie: „dajesz mi pożądany błąd, a ja dam ci przestrzeń o małych wymiarach, która przechwytuje odległości do tego błędu”. Jest to również najgorszy przypadek pary: dla każdej pary punktów itp

SVD zasadniczo obiecuje „powiesz mi, w jakim wymiarze chcesz żyć, a dam ci najlepsze możliwe osadzenie”, gdzie „najlepsze” jest definiowane jako średnio : całkowity błąd prawdziwego podobieństwa w stosunku do przewidywanego podobieństwa jest minimalny.

Z teoretycznego punktu widzenia rozwiązują one bardzo różne problemy. W praktyce wybór zależy od modelu problemu, które parametry są ważniejsze (błąd lub wymiar) i jakiego rodzaju gwarancji potrzebujesz.

Suresh Venkat
źródło

Czy ktoś mógłby mi powiedzieć, jak dokładnie uzyskuje się

w (1-eps) | uv | ^ 2 <= | f (u) -f (v) | ^ 2 <= (1 + eps) | uv | ^ 2 (z en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma )?

f (\cdot)

$f(\cdot)$

T ....

To zupełnie inne pytanie. Ale w (bardzo) skrócie, jeśli weźmiesz macierz

i zapełnisz ją danymi narysowanymi ze standardowej normy, wtedy

jest zdefiniowane jako

A

$A$

f (x)

$f(x)$

A x

$Ax$

Suresh Venkat

Czy istnieje również schemat JL dla pól skończonych, w których zniekształcenie występuje w metodzie Hamminga? Jeśli tak, to co by

tu być?

f

$f$

T ....

Nie można tego skutecznie zmniejszać wymiarowości dla metryki Hamminga. Struktura

jest bardzo różna. W bardzo ręcznym znaczeniu przyznanie redukcji w stylu JL wiąże się z życiem w przestrzeni Hilberta.

ℓ_{1}

$\ell_1$

Suresh Venkat

SVD i JL również inaczej ekstrapolują do przyszłych punktów.

To znaczy, jeśli założymy, że dane pochodzą z jakiegoś podstawowego rozkładu, w zasadzie SVD powinien pozostać „dobry” dla wszelkich przyszłych punktów, o ile są one próbkowane z tego samego rozkładu. Z drugiej strony wymiar docelowy JL zależy od liczby punktów, co oznacza, że zastosowanie transformacji JL do dodatkowych punktów może zwiększyć prawdopodobieństwo błędu.

Staje się to istotne, na przykład, jeśli używasz redukcji wymiarowości jako kroku wstępnego przetwarzania dla jakiegoś innego algorytmu. Granice SVD dla danych treningowych mogą zawierać dane testowe, ale JL nie.

Marszczyć się
źródło

To bardzo dobry punkt.

Paul Siegel

Jest to kontynuacja odpowiedzi Suresha - po przeczytaniu jego odpowiedzi trochę googlowałem i doszedłem do następującego zrozumienia. Pierwotnie zamierzałem opublikować to jako komentarz do jego odpowiedzi, ale ciągle się zwiększało.

Proszę wskazać błędy w odpowiedzi, nie jestem ekspertem w tej dziedzinie.

W pewnym sensie JL i SVD są jak jabłka i pomarańcze.

1) Rozwiązane przez nich problemy są zupełnie inne. Jedna dotyczy odległości parami, druga ma najlepszą reprezentację. Jeden to najgorszy przypadek, drugi to przeciętny przypadek.

Zwraca JL podprzestrzeni ~~(JL nie jest konstruktywny, ale załóżmy, że zwróciła najlepszą podprzestrzeń)~~ jest rozwiązaniem następującej optymalizacji

\begin{matrix} (1) & \arg min_{P.} {\underset{u, v}{łyk} (| 1 - \frac{| | P. u - P. v | |_{2)}}{| | u - v | |_{2)}} |)} \end{matrix}

$\arg\min\limits_{P} \left\{\sup\limits_{u,v} \left(\Biggl\lvert 1- \frac{||Pu-Pv||_2}{||u-v||_2} \Biggl\rvert \right) \right\} \tag{1}$

(To nie jest dokładne, skomentuję to później)

Problem, który SVD rozwiązuje, to (biorąc pod uwagę wymiar ) $k$

\arg min_{P. z dim k} {Śr (| | u - P. u | |_{2)})}

$\arg\min\limits_{P\text{ of dim k}} \left\{\text{Avg}\left(||u-Pu||_2\right)\right\}$

$\epsilon$

3) JL nie jest konstruktywny, SVD jest konstruktywny - ten punkt jest nieco niejasny, ponieważ termin konstruktywny nie jest precyzyjnie zdefiniowany. Istnieją algorytmy deterministyczne do obliczania SVD, ale algorytm znajdowania przestrzeni JL jest randomizowany - wykonaj losowe projekcje, jeśli zawiedziesz, spróbuj ponownie.

$\epsilon$

(Zobacz komentarze, aby uzyskać wyjaśnienie dotyczące fragmentów odpowiedzi w odpowiedzi).

Edycja: @ john-myles-white napisał post o JL, aby zweryfikować swoje roszczenia i pokazać, jak można zbudować projekcję: http://www.johnmyleswhite.com/notebook/2014/03/24/a-note- on-the-johnson-lindenstrauss-lemma /

elexhobby
źródło

Twoja odpowiedź zawiera wiele błędów. (1) JL jest niezwykle konstruktywny: istnieją wszelkiego rodzaju algorytmy do konstruowania odwzorowania (2) nie zachowuje różnicy, ale różnicę względną (stosunek) (3) lemat JL został zdesandomizowany (4) JL działa dla dowolnego zestawu wektorów: konstrukcja jest niezależna od rzeczywistych danych wejściowych. jedyne potrzebne informacje to liczba wektorów.

Suresh Venkat

Dzięki Suresh. Uwzględniłem wszystkie oprócz twojej ostatecznej sugestii. Możesz dalej edytować odpowiedź. W ostatnim punkcie jestem zdezorientowany. Mówisz, że ta sama mapa będzie działać bez względu na to, jaki zestaw wektorów ci dam?

elexhobby

To nieco subtelny punkt. Po naprawieniu błędu i liczby wektorów na mapach jest ustalony rozkład prawdopodobieństwa, który będzie działał z dużym prawdopodobieństwem dla dowolnego zestawu wektorów. Oczywiście nie ma deterministycznie ustalonej mapy liniowej, która spełnia tę właściwość.

Sasho Nikolov

Warto sprawdzić implementację scikit-learn

KLDavenport

0

$0$

1

$1$

1

$1$