Manifold Learning è un approccio molto recente per la riduzione di dimension- alità non lineare.
Gli algoritmi per questo tipo, sono basati sull'idea, che la dimensionalità di molte serie di dati è solo arti cialmente elevata, anche se ogni punto di dati è costituito da migliaia di feature, può essere descritto come una funzione di solo alcuni parametri sottostanti. Cioè, i punti di dati campione sono in realtà manifold di bassa dimensionalità, che sono incorporati in uno spazio di elevata dimensionalità.
Gli algoritmi di manifold learning, tentano di scoprire questi parametri al ne di trovare una rappresentazione a bassa dimensionalità dei dati.
Ci sono molti approcci alla riduzione della dimensionalità sulla base di una serie di ipotesi e utilizzate in una varietà di contesti.
Un approccio avviato recentemente, basato sull'osservazione che i dati di dimensione alta sono, molto spesso, più semplici di quello che la dimensionalità indicherebbe.
In particolare, un dato insieme di dati di dimensione alta può contenere molte feature che sono tutte le misurazioni del medesimo dato sottostante, e così sono dati strettamente correlati. Questo tipo di fenomeno è comune: per esempio, quando si prendono riprese video di un singolo oggetto da più ango- lazioni contemporaneamente.
Le feature di tale insieme di dati contiene molta sovrapposizione infor- mazioni, ma sarebbe utile in qualche modo creare una versione sempli cata, con una rappresentazione dei dati non sovrapposti e le cui feature, siano iden- ti cabili con i parametri di riferimento che governano i dati. Questa intuizione è formalizzata con la nozione di manifold.
Il set di dati si trova lungo un manifold di bassa dimensionalità incorporato in uno spazio di alta dimensione, dove lo spazio di bassa dimensione, ri ette i parametri di riferimento e quello di alta dimensione è lo spazio delle feature.
Il tentativo per scoprire questa struttura in un data set è indicato come manifold learning .
Figure 50: Un piano arricciato:swiss roll
16.2.1 Notazione e convenzioni
In questo agoritmo vi sarà interesse al problema della riduzione della dimen- sionalità di un determinato set di dati composto da punti di alta dimensione nello spazio euclideo.
All'alta dimensionalità dei punti di ingresso si farà riferimento come x1, x2, ...xn.
A volte sarà conveniente per lavorare con questi punti come un'unica ma- trice X, dove la i-esima riga di X è xi.
La rappresentazione di bassa dimensionalità che LLE trova sarà denomi- nata y1, y2, ..., yn. Y è la matrice di questi punti.
n è il numero di punti in ingresso.
D è la dimensionalità dell'ingresso (cioè xiRD).
d è la dimensionalità del manifold in cui si presume che giacciano i punti d'ingresso e, di conseguenza, la dimensionalità dell'output (cioè yiRd.).
k è il numero di vicini più vicini utilizzati da LLE. N(i) denota l'insieme dei k-vicini più vicini di xi.
16.2.2 L'intuizione su cui è basato:
l'idea viene dalla visualizzazione di un manifold come la sovrapposizione coor- dinata di patch.
Se le distanze dai vicini sono piccole e il manifold su cientemente smooth, allora queste patch saranno approssimativamente lineari.
In più, il gra co dal manifold aRd sarà più o meno lineare su queste piccole
patch.
L'idea allora è di identi care queste patch lineari che caratterizzano la ge- ometria e trovare una mappatura a Rd che conservi questa geometria locale che
è quasi lineare.
Assunto che queste patch locali si sovrapporranno una con l'altra in modo che le ricostruzioni locali si combineranno in una più globale. Come in tutti questi metodi, il numero dei vicini scelto è un parametro dell'algoritmo.
Sia N(i) l'insieme dei k-vicini più vicini al punto xi, il primo passo dell'algoritmo
è modellare il manifold come una collezione di pach lineari e tentare di carat- terizzare la geometria di queste pach.
Per fare questo tenta di rappresentare xi come una combinazione pesata
convessa dei suoi vicini.
I pesi sono scelti per minimizzare il seguente errore quadratico per ogni i: xi− X jN (i) Wijxj 2 . (40)
La matrice dei pesi viene utilizzata come un surrogato delle pach della ge- ometria locale.
Intuitivamente, Wi rivela la disposizione dei punti intorno a xi.
Esistono un paio di vincoli sui pesi: ogni riga è a somma 1 (equivalentemente, ogni punto è rappresentato come combinazione convessa dei suoi vicini) e Wij =
0se j non appartiene ad N(i). Il secondo vincolo ri ette che LLE è un metodo locale; il primo rende i pesi invarianti a traslazioni globali: se ogni xiè shiftato
di α allora xi+ α − X jN (i) Wij(xj+ α) 2 = xi− X jN (i) Wijxj 2 . (41)
quindi W non è in uenzato.
Inoltre, W è invariante a rotazioni globali e scaling. Fortunatamente c'è una soluzione in forma chiusa per W, che discende dai moltiplicatori di Lagrange.
In particolare, i pesi di ricustruzione di ciascun punto xi sono dati da:
¯ Wi= P kC −1 jk P lmC −1 lm (42) dove C è la matrice di covarianza con entry Cjk= (xi− ηj)T(xi− ηk)e nj,
ηk sono i vicini di xi.
¯
W Rnxk è trasformata in una matrice sparsa W nxn; W
ij = ¯Wil se xj è
l'ellesimo vicino di xi, ed è 0 se j non apartiene a N(i).
Wi è una caratterizzazione della geometria locale intorno xi del manifold.
Poiché è invariante alle rotazioni, cambi di scala, e traslazioni, Wi caratter-
izza la geometria locale intorno xianche per ogni mappatura lineare della patch
vicine che circondano xi. Ci si aspetta che il gra co di questa patch vicine a allo
spazio parametrico debba essere approssimativamente lineare poiché il manifold è smooth.
Così, Widovrebbe catturare anche la geometria locale dello spazio paramet-
rico. Il secondo passo dell'algoritmo trova una con gurazione in d-dimensioni (la dimensionalità dello spazio dei parametri) la cui geometria locale è carat- terizzata bene da W.
La dimensione d deve essere nota a priori o stimata. la con gurazione è trovata minimizzando
X i yi− X j Wijyj 2 (43)
rispetto a y1, ..., yn Rd.. Si noti che questa espressione ha la stessa forma
l'errore minimizzata il primo passo dell'algoritmo, ma che ora siamo minimiz- zando rispetto a y1,. . . , Yn, anziché W. La funzione di costo (43) può essere riscritta come
YTM Y, dove Mij = δij− Wij− Wji+ X k WkiWkj e δij = 1se i = j 0 altrimenti.
M può essere scritto in modo conciso come (I − W )T(I − W )
ci sono un paio di vincoli su Y.
Primo, YTY = I, che forza la soluzione ad essere di rango d.
secondo, PiYi= 0; questo vincolo centra l'embedding sull'origine.
Questa funzione di costo è una forma quoziente di Rayleigh , quindi è min- imizzato impostando le colonne di Y per i d autovettori corrispondenti agli autovalori più bassi di M.
Tuttavia, la coppia (autovettore, autovalore) inferiore è (1, 0), in modo che il quota nale di ogni punto è identico. per evitare che questo degeneri la dimensione, l'embedding d-dimensionale è dato dagli d autovettori inferiori non costanti.
16.2.3 L'algoritmo Locally Linear Embedding
Input: x1, ..., xn RD,d ,k
1. Calcola la ricostruzione dei pesi per ogni punto: per ogni punto
Wi:= P kC −1 jk P lmC −1 lm
2. Calcola il low-dimensional embedding
Sia U una matrice le cui colonne siano gli autovettori di (I − W )T(I − W )
con i rispettiviautovalori non nulli Return Y := [U]nxd