Nell'ambito dell'apprendimento automatico e nell'analisi dei dati, l'immersione localmente lineare (in inglese Locally-linear Embedding, LLE) è un metodo non lineare di riduzione della dimensionalità. Essenzialmente esso parte dal ritrovamento dell'insieme dei vicini più prossimi (ossia dalla costruzione del relativo grafo) per ogni punto del dataset. Quindi calcola, per ciascun punto, un insieme di pesi che meglio lo descrivano come combinazione lineare dei suoi vicini. Infine, usa una tecnica di ottimizzazione basata su autovettori per trovare l'immersione a bassa dimensionalità dei punti, tale che ciascun punto risulti ancora descritto attraverso la stessa combinazione dei suoi vicini. Si noti che il metodo non costruisce un modello interno.

Il metodo è stato introdotto quasi contemporaneamente a Isomap, rispetto al quale presenta alcuni vantaggi, quali un'ottimizzazione più rapida, se implementato sfruttando algoritmi per matrici sparse e, in generale, migliori risultati su diversi problemi di riduzione. Tuttavia LLE tende a non gestire bene casi di densità non uniformi degli esempi in quanto non c'è una unità che possa essere fissata per prevenire scostamenti errati dei pesi, dato che regioni diverse possono avere differenti densità.

Descrizione Siano i punti originari. Lo scopo del metodo è quello di proiettare ogni punto su un certo punto di dimensioni inferiori, ossia con .

LLE prevede due passi.

si calcola, per ogni punto , la sua migliore approssimazione basata sulle coordinate baricentriche dei suoi vicini . Il punto originario viene ricostruito in maniera approssimata da una combinazione lineare, data dalla matrice dei pesi , dei suoi vicini. Lerrore di ricostruzione è il seguente: I pesi si riferiscono al contributo del vicino nella ricostruzione del punto . La funzione di costo viene minimizzata sotto due vincoli: ogni punto viene ricostruito solo in base ai suoi vicini quindi dev'essere se il punto non è un vicino del punto . la somma di ogni riga della matrice dei pesi è unitaria: .Tali vincoli assicurano che non vari per rotazione o traslazione. 2. Si crea una mappa basata sui pesi che preservi il vicinato. Ogni punto viene mappato su un punto minimizzando un altro costo: A differenza della funzione precedente, i pesi sono tenuti fissi e si minimizza sui punti per ottimizzarne le coordinate. Questo problema di minimizzazione può essere risolto come problema sparso di ricerca degli autovalori (detto N il numero delle istanze nel dataset) i cui ultimi autovettori non nulli forniscono un insieme ortogonale di coordinate. Il solo iperparametro nell'algoritmo è il numero dei vicini considerati per ogni punto. Generalmente si ricostruiscono i punti a partire dai vicini più prossimi, in termini di distanza euclidea. In tal caso, l’algoritmo ha un solo iperparametro intero , che può essere determinato mediante cross validation.

Varianti

Immersione LL Hessiana (Hessian LLE) Come LLE, anche la versione denominata in inglese Hessian LLE si basa su tecniche per matrici sparse. Essa tende a fornire risultati di qualità molto superiore rispetto al metodo LLE originale. Sfortunatamente, però, ha una complessità computazionale molto ingente, per cui non costituisce una buona scelta per grandi dataset. Anche in tal caso non si produce un modello interno.

Immersione LL Modificata (MLLE)

La LLE modificata (MLLE) è un'altra variante di LLE che usa più pesi in ciascun vicinato per affrontare il problema di condizionamento della matrice dei pesi locale, il che porta a distorsioni delle mappe LLE. In altre parole, i diversi pesi sono le proiezioni ortogonali locali dei pesi originari prodotti da LLE. Gli ideatori di questa variante regolarizzata sono anche autori del metodo detto Local Tangent Space Alignment (LTSA), implicito nella formulazione di MLLE allorché si consideri che l'ottimizzazione globale delle proiezioni ortogonali di ogni vettore di pesi, essenzialmente, allinei gli spazi tangenti locali relativi a ogni punto. Le implicazioni teoriche ed empiriche della corretta applicazione di questo algoritmo sono di vasta portata.

Note

Categoria:Apprendimento automatico