LLE — Locally Linear Embedding
Préserver les relations locales entre voisins : chaque point est une combinaison linéaire de ses voisins, et cette propriété doit être conservée en basse dimension.
1. L'idée fondamentale
LLE part d'une observation simple : localement, une variété ressemble à un espace euclidien. Autour de chaque point, le voisinage est approximativement plat. On peut donc exprimer chaque point comme une combinaison linéaire de ses voisins. Si on trouve la représentation basse dimension qui respecte ces mêmes poids de reconstruction, on "déplie" la variété.
2. Algorithme en 3 étapes
Trouver les k plus proches voisins
Pour chaque point \(x_i \in \mathbb{R}^p\), identifier ses \(k\) plus proches voisins \(\mathcal{N}(i)\) par distance euclidienne.
Calculer les poids de reconstruction
Trouver les poids \(W_{ij}\) qui minimisent l'erreur de reconstruction locale de chaque point par ses voisins. C'est un problème de moindres carrés avec contrainte :
Trouver l'embedding basse dimension
Trouver les coordonnées \(y_i \in \mathbb{R}^q\) qui respectent les mêmes poids \(W_{ij}\). On minimise une erreur similaire, mais cette fois les coordonnées sont les inconnues.
3. Les formules d'optimisation
Minimiser l'erreur de reconstruction sous contrainte de somme des poids = 1 :
Wᵢⱼ : poids de reconstruction du point \(x_j\) pour reconstruire \(x_i\) ·
N(i) : k plus proches voisins de \(x_i\)Les poids sont nuls hors du voisinage : \(W_{ij} = 0\) si \(j \notin \mathcal{N}(i)\)
Solution par moindres carrés locaux : \(W_{ij} = \frac{\sum_l (G^{-1})_{jl}}{\sum_{mn}(G^{-1})_{mn}}\) où \(G_{jl} = (x_i - x_j)^T(x_i - x_l)\)
Les poids \(W_{ij}\) sont fixés. On cherche les \(y_i \in \mathbb{R}^q\) minimisant :
M = (I - W)^T(I - W) : matrice de coût (sparse, \(n \times n\)) ·
Y : matrice des coordonnées basses dimension (\(n \times q\))Solution : les \(q\) vecteurs propres de \(M\) correspondant aux \(q\) plus petites valeurs propres non nulles.
Contrainte : \(Y^TY = I\) (coordonnées centrées et orthogonales)
Dans les deux cas, on diagonalise une matrice. En ACP : on cherche les plus grandes valeurs propres de \(X^TX\) (variance maximale). En LLE : on cherche les plus petites valeurs propres non nulles de \(M\) (erreur de reconstruction minimale).
4. Visualisation — reconstruction locale
Le point orange est reconstruit à partir de ses k voisins violets. Les flèches montrent les poids de reconstruction.
5. Limites de LLE
Sensibilité à k : comme ISOMAP, k trop petit = graphe disconnecté, k trop grand = voisinage non local.
Variétés non convexes : LLE peut "plier" incorrectement la variété si la géométrie globale est complexe.
Pas de fonction de projection : impossible de projeter de nouveaux points sans recalculer tout l'algorithme (contrairement à l'ACP).
Sensibilité au bruit : les poids de reconstruction peuvent être instables si les données sont bruitées.
LLE vs ACP vs ISOMAP
📌 À retenir / À l'examen
- LLE = préserver les poids de reconstruction locale en passant en basse dimension
- Étape 1 : k-NN · Étape 2 : minimiser \(\|x_i - \sum W_{ij}x_j\|^2\) sous \(\sum W_{ij}=1\) · Étape 3 : minimiser \(\|y_i - \sum W_{ij}y_j\|^2\)
- Solution étape 3 : petites valeurs propres non nulles de \(M = (I-W)^T(I-W)\)
- Différence ACP/LLE : ACP = grandes vp (variance max), LLE = petites vp (erreur locale min)
- Hypothèse clé : la variété est localement plate (approximation linéaire locale valide)
- Limite : pas de projection de nouveaux points, sensible au bruit et à k