Wann sollte das Lemma von Johnson-Lindenstrauss über SVD verwendet werden?

Das Johnson-Lindenstrauss-Lemma ermöglicht die Darstellung von Punkten in einem hochdimensionalen Raum in Punkte in einer niedrigeren Dimension. Wenn Sie am besten passende Räume mit niedrigeren Dimensionen finden, besteht eine Standardtechnik darin, die Singularwertzerlegung zu finden und dann den durch die größten Singularwerte erzeugten Unterraum zu nehmen. Wann ist es von Interesse, Johnson-Lindenstrauss über die SVD zu nutzen?

machine-learning user09128323
quelle

Antworten:

Die beiden Ansätze bieten sehr unterschiedliche Garantien.

Das JL Lemma sagt im Wesentlichen: "Sie geben mir den Fehler, den Sie wollen, und ich gebe Ihnen einen Raum mit geringen Abmessungen, der die Entfernungen bis zu diesem Fehler erfasst." Dies ist auch eine paarweise Garantie im ungünstigsten Fall : für jedes Punktepaar usw

Die SVD verspricht im Wesentlichen, "Sie sagen mir, in welcher Dimension Sie leben möchten, und ich gebe Ihnen die bestmögliche Einbettung", wobei "am besten" als Durchschnitt definiert wird : Der Gesamtfehler der wahren Ähnlichkeit gegenüber der projizierten Ähnlichkeit ist minimal.

Theoretisch lösen sie also sehr unterschiedliche Probleme. In der Praxis hängt es von Ihrem Modell ab, welche Parameter für das Problem wichtiger sind (Fehler oder Dimension) und welche Art von Garantien Sie benötigen.

Suresh Venkat
quelle

Könnte mir jemand sagen, wie genau

, erhalten in (1-eps) | uv | ^ 2 <= | f (u) -f (v) | ^ 2 <= (1 + eps) | uv | ^ 2 (vonen.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma)?

f (\cdot)

$f(\cdot)$

T ....

Das ist eine ganz andere Frage. Aber in (sehr) kurzen Worten, wenn Sie eine Matrix

und sie mit Einträgen aus einer Standardnormalen füllen, dann ist

als

definiert .

A

$A$

f (x)

$f(x)$

A x

$Ax$

Suresh Venkat

Gibt es ein JL-Schema auch für endliche Felder, bei denen die Verzerrung in der Hamming-Metrik liegt? Wenn ja, was wäre dann

hier sein?

f

$f$

T ....

Dies ist für die Hamming-Metrik nicht effektiv möglich. Die

Struktur ist sehr unterschiedlich. Das Eingestehen von Reduktionen im JL-Stil ist in einem sehr handgewagten Sinne mit dem Leben in einem Hilbert-Raum verbunden.

ℓ_{1}

$\ell_1$

Suresh Venkat

SVD und JL extrapolieren auch anders auf zukünftige Punkte.

Wenn Sie also davon ausgehen, dass Ihre Daten aus einer zugrunde liegenden Verteilung stammen, sollte die SVD im Prinzip für alle zukünftigen Punkte "gut" bleiben, solange sie aus derselben Verteilung abgetastet werden. Andererseits hängt die Zieldimension von JL von der Anzahl der Punkte ab, was bedeutet, dass das Anwenden einer JL-Transformation auf zusätzliche Punkte die Fehlerwahrscheinlichkeit erhöhen kann.

Dies ist beispielsweise dann relevant, wenn Sie die Dimensionsreduzierung als Vorverarbeitungsschritt für einen anderen Algorithmus verwenden. SVD-Grenzen für Trainingsdaten können für Testdaten gelten, JLs jedoch nicht.

Frumple
quelle

Das ist ein sehr guter Punkt.

Paul Siegel

Dies ist ein Follow-up zu Sureshs Antwort. Nachdem ich seine Antwort gelesen hatte, googelte ich ein wenig und kam zu folgendem Verständnis. Ich wollte dies ursprünglich als Kommentar zu seiner Antwort posten, aber es nahm weiter zu.

Bitte weise in der Antwort auf Fehler hin, ich bin kein Experte auf diesem Gebiet.

In gewissem Sinne sind JL und SVD wie Äpfel und Orangen.

1) Die Probleme, die sie lösen, sind völlig unterschiedlich. Einer befasst sich mit paarweisen Abständen, der andere mit der besten Darstellung. Einer ist der schlimmste Fall, der andere ist der durchschnittliche Fall.

\begin{matrix} (1) & \arg min_{P} {sup_{u, v} (| 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}$

(Dies ist nicht genau, dazu später mehr)

$k$

\arg min_{P of dim k} {Avg (| | u - P u | |_{2})}

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

$\epsilon$

3) JL ist nicht konstruktiv, SVD ist konstruktiv - dieser Punkt ist etwas vage, da der Begriff konstruktiv nicht genau definiert ist. Es gibt deterministische Algorithmen zum Berechnen der SVD, aber der Algorithmus zum Finden eines JL-Raums ist randomisiert. Versuchen Sie es mit zufälligen Projektionen, falls Sie versagen.

$\epsilon$

(Erläuterungen zu gestrichenen Teilen der Antwort finden Sie in den Kommentaren.)

Edit: @ john-myles-white hat einen Post über JL geschrieben, um seine Behauptungen zu verifizieren und um zu zeigen, wie eine Projektion erstellt werden kann: http://www.johnmyleswhite.com/notebook/2014/03/24/a-note- auf-der-johnson-lindenstrauss-lemma /

elexhobby
quelle

Ihre Antwort enthält eine Reihe von Fehlern. (1) JL ist äußerst konstruktiv: Es gibt alle Arten von Algorithmen zum Erstellen des Mappings. (2) Der Unterschied wird nicht beibehalten, aber der relative Unterschied (das Verhältnis). (3) Das JL-Lemma wurde derandomisiert. (4) JL funktioniert Für jede Menge von Vektoren: Die Konstruktion ist unabhängig von der tatsächlichen Eingabe. Die einzige Information, die benötigt wird, ist die Anzahl der Vektoren.

Suresh Venkat

Danke Suresh. Ich habe bis auf Ihren letzten Vorschlag alles aufgenommen. Fühlen Sie sich frei, die Antwort weiter zu bearbeiten. In letzterem Punkt bin ich verwirrt. Sie sagen, die gleiche Karte wird funktionieren, egal welche Vektoren ich Ihnen gebe?

Elexhobby

Das ist ein etwas subtiler Punkt. Sobald Sie den Fehler und die Anzahl der Vektoren behoben haben, gibt es auf Karten eine feste Wahrscheinlichkeitsverteilung, die mit hoher Wahrscheinlichkeit für jeden Vektorsatz funktioniert. Natürlich gibt es keine deterministisch festgelegte lineare Karte, die diese Eigenschaft erfüllt.

Sasho Nikolov

Es lohnt sich, Olivier Grisels Implementierung zum Lernen

KLDavenport,

0

$0$

1

$1$

1

$1$