Quand utiliser le lemme de Johnson-Lindenstrauss sur SVD?

Le lemme de Johnson-Lindenstrauss permet de représenter des points dans un espace de grande dimension en points de dimension inférieure. Lors de la recherche d'espaces de dimension inférieure de meilleur ajustement, une technique standard consiste à trouver la décomposition des valeurs singulières, puis à prendre le sous-espace généré par les plus grandes valeurs singulières. Quand est-il intéressant d'utiliser Johnson-Lindenstrauss sur le SVD?

machine-learning user09128323
la source

Réponses:

Les deux approches offrent des garanties très différentes.

Le lemme JL dit essentiellement "vous me donnez l'erreur que vous voulez, et je vais vous donner un espace de faible dimension qui capture les distances jusqu'à cette erreur". C'est également une garantie par paire dans le pire des cas : pour chaque paire de points , etc., etc.

Le SVD promet essentiellement "vous me dites dans quelle dimension vous voulez vivre, et je vous donnerai la meilleure intégration possible", où "le meilleur" est défini comme en moyenne : l'erreur totale de la vraie similitude par rapport à la similitude projetée est minimale.

Donc, d'un point de vue théorique, ils résolvent des problèmes très différents. En pratique, celui que vous souhaitez dépend de votre modèle pour le problème, des paramètres les plus importants (erreur ou dimension) et du type de garanties dont vous avez besoin.

Suresh Venkat
la source

Quelqu'un pourrait-il me dire exactement comment

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

f (\cdot)

$f(\cdot)$

T ....

Voilà une toute autre question. Mais en (très) bref, si vous prenez une matrice

et la remplissez avec des entrées tirées d'une normale standard, alors

est défini comme

A

$A$

f (x)

$f(x)$

A x

$Ax$

Suresh Venkat

Existe-t-il également un schéma JL pour les champs finis où la distorsion est dans la métrique de Hamming? Si oui, alors ce serait

ici?

f

$f$

T ....

Vous ne pouvez pas réduire efficacement la dimensionnalité pour la métrique Hamming. La structure

est très différente. Dans un sens très ondulé, admettre des réductions de style JL est lié à la vie dans un espace Hilbert.

ℓ_{1}

$\ell_1$

Suresh Venkat

SVD et JL extrapolent également aux points futurs différemment.

Autrement dit, si vous supposez que vos données proviennent d'une distribution sous-jacente, en principe, le SVD doit rester "bon" pour tous les points futurs tant qu'ils sont échantillonnés à partir de la même distribution. D'un autre côté, la dimension cible de JL dépend du nombre de points, ce qui signifie que l'application d'une transformation JL à des points supplémentaires peut augmenter la probabilité d'erreur.

Cela devient pertinent si, par exemple, si vous utilisez la réduction de dimensionnalité comme étape de prétraitement pour un autre algorithme. Les limites SVD pour les données d'entraînement peuvent contenir des données de test, mais pas JL.

Frumple
la source

C'est un très bon point.

Paul Siegel

Ceci est un suivi de la réponse de Suresh - j'ai googlé un peu après avoir lu sa réponse et j'ai trouvé la compréhension suivante. Au départ, j'allais poster ceci en tant que commentaire à sa réponse, mais cela a continué d'augmenter.

Veuillez signaler des erreurs dans la réponse, je ne suis pas un expert dans ce domaine.

Dans un certain sens, JL et SVD sont comme des pommes et des oranges.

1) Les problèmes qu'ils résolvent sont complètement différents. L'un concerne les distances par paires, l'autre la meilleure représentation. L'un est le pire des cas, l'autre est le cas moyen.

\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}$

(Ce n'est pas précis, je commenterai cela plus tard)

$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 est non constructif, SVD est constructif - ce point est un peu vague, car le terme constructif n'est pas défini avec précision. Il existe des algorithmes déterministes pour calculer la SVD, mais l'algorithme pour trouver un espace JL est aléatoire - faites des projections aléatoires, si vous échouez, essayez à nouveau.

$\epsilon$ différentes de leurs valeurs réelles . Il pourrait y avoir beaucoup de tels sous-espaces, certains meilleurs que les autres.

(Voir les commentaires pour des explications concernant les parties rayées de la réponse).

Edit: @ john-myles-white a écrit un article sur JL pour vérifier ses affirmations et montrer comment une projection peut être construite: http://www.johnmyleswhite.com/notebook/2014/03/24/a-note- on-the-johnson-lindenstrauss-lemma /

elexhobby
la source

Il y a un certain nombre d'erreurs dans votre réponse. (1) JL est extrêmement constructif: il existe toutes sortes d'algorithmes pour construire le mapping (2) il ne préserve pas la différence mais la différence relative (le ratio) (3) le lemme JL a été dérandomisé (4) JL fonctionne pour tout ensemble de vecteurs: la construction est indépendante de l'entrée réelle. la seule information nécessaire est le nombre de vecteurs.

Suresh Venkat

Merci Suresh. J'ai tout incorporé sauf votre suggestion finale. N'hésitez pas à modifier davantage la réponse. Sur le dernier point, je suis confus. Vous dites que la même carte fonctionnera quel que soit l'ensemble de vecteurs que je vous donne?

elexhobby

C'est un point légèrement subtil. Une fois que vous avez corrigé l'erreur et le nombre de vecteurs, il existe une distribution de probabilité fixe sur les cartes qui fonctionnera avec une probabilité élevée pour n'importe quel ensemble de vecteurs. Bien sûr, il n'y a pas de carte linéaire fixée de manière déterministe qui satisfait cette propriété.

Sasho Nikolov

Cela vaut la peine de vérifier la mise en œuvre

KLDavenport

0

$0$

1

$1$

1

$1$