Expliquer les étapes de l'algorithme LLE (local linear embedding)?

13

Je comprends le principe de base derrière l'algorithme pour LLE se compose de trois étapes.

  1. Trouver le voisinage de chaque point de données par une métrique telle que k-nn.
  2. Trouvez des poids pour chaque voisin qui dénotent l'effet du voisin sur le point de données.
  3. Construire l'incorporation de faible dimension des données sur la base des poids calculés.

Mais l'explication mathématique des étapes 2 et 3 prête à confusion dans tous les manuels et ressources en ligne que j'ai lus. Je ne peux pas expliquer pourquoi les formules sont utilisées.

Comment ces étapes sont-elles exécutées dans la pratique? Existe-t-il un moyen intuitif d'expliquer les formules mathématiques utilisées?

Références: http://www.cs.nyu.edu/~roweis/lle/publications.html

User1234321232
la source

Réponses:

10

L'incorporation linéaire locale (LLE) élimine le besoin d'estimer la distance entre des objets distants et récupère la structure non linéaire globale par ajustements linéaires locaux. Le LLE est avantageux car il n'implique aucun paramètre tel que les taux d'apprentissage ou les critères de convergence. LLE évolue également bien avec la dimensionnalité intrinsèque de . La fonction objective pour LLE est La matrice de poids éléments pour les objets et sont mis à zéro siY

ζ(Y)=(YWY)2=Y(IW)(IW)Y
Wwijijjn'est pas le plus proche voisin de , sinon, les poids pour les K-voisins les plus proches de l'objet sont déterminés via un ajustement aux moindres carrés de où la variable dépendante est un vecteur de uns, est une matrice Gram pour tous les voisins les plus proches de l'objet , et est un vecteur de poids qui suit des contraintes de somme à unité. Soit un semi-fini positif symétriqueii
U=Gβ
UK×1GK×KiβK×1DK×Kmatrice de distance pour toutes les paires des K plus proches voisins de l'objet à dimensions . On peut montrer que est égal à la matrice de distance doublement centrée avec les éléments Les coefficients de régression sont déterminés numériquement en utilisant pxiGτ
τlm=12(dlm21Kldlm21Kmdlm2+lmdlm2).
K
βK×1=(ττ)K×K1τUK×1,
et sont vérifiés pour confirmer leur somme à l'unité. Les valeurs de sont intégrées dans la ligne de aux différentes positions de colonne correspondant aux K voisins les plus proches de l'objet , ainsi que les éléments de transposition. Ceci est répété pour chaque ème objet du jeu de données. Il convient de noter que si le nombre de voisins les plus proches est trop faible, alors peut être clairsemé, ce qui rend l'analyse propre difficile. Il a été observé que voisins les plus proches entraînaientβiWiiKWK=9Wmatrices qui ne contenaient pas de pathologies lors de l'analyse propre. La fonction objectif est minimisée en trouvant les plus petites valeurs propres non nulles de La forme réduite de est représentée par où a des dimensions basées sur les deux valeurs propres les plus basses de .
(IW)(IW)E=ΛDE.
XY=EEn×2Λ

NXG Logic
la source
"K = 9 voisins les plus proches" Cela ne dépend-il pas de la dimensionnalité de ? Par exemple, si a moins de 9 dimensions, alors la matrice de poids n'est pas déterminée de manière unique. Est-ce que cela cause des problèmes avec LLE? Y WYYW
Scott
Oui, mais s'il y a, disons, 8 dimensions, pour les données aléatoires, chaque point peut littéralement être écrit parfaitement comme une combinaison linéaire de 9 autres, dans un nombre infini de façons.
Scott
Il existe toujours des scénarios de simulation lors de la mise en œuvre d'une technique, et c'est pourquoi des contraintes de paramètres sont utilisées.
NXG Logic du