Riduzione della dimensionalità

Nell'apprendimento automatico e in statistica multivariata, la riduzione della dimensionalità, o riduzione delle dimensioni, è la trasformazione dei dati da uno spazio ad alta dimensionalità a uno di dimensionalità minore, in modo che questa rappresentazione mantenga alcune proprietà significative dei dati di origine, idealmente vicina alla sua dimensione intrinseca. Lavorare con spazi ad alta dimensionalità può essere indesiderabile per molte ragioni: i dati grezzi sono spesso sparsi come conseguenza della maledizione della dimensionalità e l'analisi dei dati è di solito più computazionalmente poco conveniente. La riduzione della dimensionalità è pratica comune in ambiti in cui si trattano dataset con un gran numero di variabili, come l'elaborazione del segnale, il riconoscimento vocale, la neuroinformatica e la bioinformatica.

I metodi sono comunemente suddivisi in approcci lineari e non lineari. Gli approcci possono anche essere suddivisi in selezione ed estrazione delle caratteristiche. La riduzione della dimensionalità può essere utilizzata per la riduzione del rumore, la visualizzazione dei dati, l'analisi dei cluster o come passaggio intermedio per facilitare altre analisi.

Selezione delle caratteristiche

Gli approcci basati sulla selezione delle caratteristiche cercano di trovare un sottoinsieme delle variabili di input (chiamate anche caratteristiche o attributi o feature). Le tre principali strategie sono: la strategia del filtro (basata su misure di guadagno di informazione), la strategia wrapper (ad es. una ricerca guidata dall'accuratezza del modello costruito sulla base delle diverse combinazioni di feature) e la strategia basata su immersione (selezione contestuale alla costruzione dei modelli basata su loss regolarizzate).

L'analisi dei dati per problemi di regressione o classificazione può essere condotta nello spazio ridotto in modo più accurato ed efficiente rispetto allo spazio originario.

Proiezione delle caratteristiche

La proiezione delle caratteristiche (chiamata anche estrazione delle caratteristiche) trasforma i dati dallo spazio ad alta dimensione a uno spazio con meno dimensioni. La trasformazione dei dati può essere lineare, come nell'analisi delle componenti principali (PCA), ma esistono anche molte tecniche non lineari per la riduzione della dimensionalità.Samet, H. (2006) Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. C. Ding, X. He, H. Zha, H.D. Simon, Adaptive Dimension Reduction for Clustering High Dimensional Data, Proceedings of International Conference on Data Mining, 2002 Per i dati multidimensionali, la rappresentazione tensoriale può essere utilizzata nella riduzione della dimensionalità attraverso lapprendimento subspaziale multilineare.

Decomposizione ai valori singolari (SVD)

La decomposizione ai valori singolari (SVD dall'inglese Singular Value Decomposition) è alla base di tutte le tecniche di riduzione lineare della dimensionalità. Data una matrice questa può essere espressa come il prodotto di tre matrici tali che:

ha le colonne tra loro ortonormali, ovvero è una matrice diagonale che ha come valori sulla diagonale i valori singolari: è una matrice ortogonale, ovvero

Per la riduzione della dimensionalità, risulta utile considerare la formula alternativa, essendo diagonale si può scrivere

dove

è l'i-esimo valore singolare è l'i-esima colonna di è l'iesima colonna di è una matrice a rango 1 ottenuta dal prodotto

Dal teorema di Eckart-Young la miglior approssimazione nella norma di Frobenius di ad una matrice di rango inferiore è data da , dove è il rango a cui si vuole approssimare e i valori singolari sono ordinati in maniera decrescente. Avendo approssimato ad una matrice di rango inferiore possiamo facilmente convertirla nella relativa matrice dove

è la matrice costituita dalle prime colonne di è la matrice diagonale che contiene i primi valori singolari ordinati in maniera decrescente.

L'analisi delle componenti principali è un caso specifico dell'SVD. Infatti la PCA è l'SVD applicata alla matrice dei dati centrati.

Analisi delle componenti principali (PCA)

L'analisi delle componenti principali (la principale tecnica lineare per la riduzione della dimensionalità) esegue una mappa lineare dei dati in uno spazio a dimensione inferiore in modo tale che la varianza dei dati nella rappresentazione a bassa dimensione sia massima. In pratica, si costruisce la matrice della covarianza (o talvolta correlazione) dei dati e si calcolano gli autovettori. Quelli che corrispondono agli autovalori maggiori (le componenti principali) possono ora essere utilizzati per ricostruire una grande frazione della varianza dei dati originali. Inoltre, i primi autovettori possono spesso essere interpretati in termini del comportamento fisico del sistema su larga scala, perché spesso contribuiscono alla maggior parte dell'energia del sistema, specialmente nei sistemi a bassa dimensionalità. Tuttavia, questo deve essere dimostrato caso per caso poiché non tutti i sistemi mostrano questo comportamento. Lo spazio originale (con dimensione del numero di punti) è stato ridotto (con perdita di dati, ma idealmente conservando la varianza più importante) allo spazio coperto da pochi autovettori.

Fattorizzazione a matrice non negativa (NMF) NMF decompone una matrice non negativa nel prodotto di due non negative, che è stato uno strumento promettente in campi in cui esistono solo segnali non negativi, come l'astronomia. NMF è ben noto sin dalla regola di aggiornamento moltiplicativo di Lee & Seung, che è stata continuamente sviluppata: l'inclusione delle incertezze, la considerazione dei dati mancanti e il calcolo parallelo, costruzione sequenziale che porta alla stabilità e linearità di NMF, così come altri aggiornamenti inclusa la gestione dei dati mancanti nell'elaborazione digitale delle immagini.

Con una base di componenti stabili durante la costruzione e un processo di modellazione lineare, l'NMF sequenziale è in grado di preservare il flusso nellimaging diretto delle strutture circumstellari in astronomia, come uno dei metodi per rilevare gli esopianeti, in particolare per l'imaging dei dischi circumstellari. Rispetto a PCA, NMF non rimuove la media delle matrici, il che porta a flussi non negativi non fisici; pertanto NMF è in grado di conservare più informazioni rispetto alla PCA come dimostrato da Ren et al.

Kernel PCA L'analisi delle componenti principali può essere impiegata in modo non lineare mediante il metodo kernel. La tecnica risultante è in grado di costruire mappature non lineari che massimizzano la varianza nei dati. Questa tecnica è chiamata kernel PCA.

Kernel PCA basata su grafo Tra le altre, alcune importanti tecniche non lineari sono tecniche di manifold learning, come Isomap, l'embedding localmente lineare (LLE), l'LLE Hessiana, le automappe (eigenmap) laplaciane e i metodi basati sullanalisi dello spazio tangente. Queste tecniche costruiscono una rappresentazione dei dati a bassa dimensionalità utilizzando una funzione di costo che conserva le proprietà locali dei dati e può essere vista come la definizione di un kernel basato su grafo per il metodo kernel PCA.

Più recentemente, sono state proposte tecniche che, invece di definire un kernel fisso, cercano di imparare il kernel usando la programmazione semidefinita. L'esempio più eminente di tale tecnica è il maximum variance unfolding (MVU, letteralmente "dispiegamento della massima varianza"). L'idea centrale di MVU è di preservare esattamente tutte le distanze a coppie tra i primi vicini, massimizzando le distanze tra i punti che non sono primi vicini.

Un approccio alternativo alla conservazione dei punti vicini è attraverso la minimizzazione di una funzione di costo che misura le differenze tra le distanze negli spazi di input e output. Esempi importanti di tali tecniche includono: scaling multidimensionale classico, che è identico a PCA; Isomap, che utilizza le distanze geodetiche nello spazio dati; mappe di diffusione, che utilizzano distanze di diffusione nello spazio dei dati; t-distributed stochastic neighbor embedding (t-SNE), che minimizza la divergenza tra le distribuzioni su coppie di punti; e analisi delle componenti curvilinee.

Un approccio diverso alla riduzione della dimensionalità non lineare è attraverso l'uso di autoencoder, un tipo speciale di reti neurali feed-forward con uno strato nascosto a collo di bottiglia.Hongbing Hu, Stephen A. Zahorian, (2010) "Dimensionality Reduction Methods for HMM Phonetic Recognition", ICASSP 2010, Dallas, TX L'addestramento degli encoder profondi viene in genere eseguito utilizzando una forma greedy di pre-addestramento a strati (ad esempio, utilizzando una pila di macchine Boltzmann limitate) seguita da una fase di fine-tuning basata sulla retropropagazione.

Analisi discriminante lineare (LDA)

L'analisi discriminante lineare (LDA) è una generalizzazione del discriminante lineare di Fisher, un metodo utilizzato in statistica, riconoscimento di modelli e apprendimento automatico per trovare una combinazione lineare di caratteristiche che caratterizza o separa due o più classi di oggetti o eventi.

Analisi discriminante generalizzata (GDA) GDA si occupa dell'analisi discriminante non lineare utilizzando l'operatore di funzione del kernel. La teoria sottostante è vicina alle macchine a vettori di supporto (SVM) nella misura in cui il metodo GDA fornisce una mappatura dei vettori di input nello spazio delle caratteristiche ad alta dimensione. Simile a LDA, l'obiettivo di GDA è trovare una proiezione per le caratteristiche in uno spazio dimensionale inferiore massimizzando il rapporto tra dispersione tra classi e dispersione all'interno della classe.

Autocodificatore

Gli autocodificatori, o autoencoder, possono essere utilizzati per apprendere le funzioni e le codifiche di riduzione delle dimensioni non lineari insieme a una funzione inversa dalla codifica alla rappresentazione originale.

t-SNE

L'algoritmo t-distributed stochastic neighbor embedding (t-SNE) è una tecnica di riduzione della dimensionalità non lineare utile per la visualizzazione di set di dati ad alta dimensionalità. Non è raccomandato per l'uso in analisi come il clustering o il rilevamento di valori anomali poiché non conserva necessariamente bene densità o distanze.

UMAP Lapprossimazione e proiezione di varietà uniformi (UMAP) è una tecnica di riduzione della dimensionalità non lineare. I risultati, a livello visivo, sono simili a quelli di t-SNE, ma UMAP assume che i dati siano distribuiti uniformemente su una varietà riemanniana localmente connessa e che la metrica riemanniana sia localmente costante, almeno approssimativamente.

Riduzione delle dimensioni Per insiemi di dati ad alta dimensionalità (cioè con un numero di dimensioni superiore a 10), la riduzione delle dimensioni viene solitamente eseguita prima di applicare un algoritmo, come ad esempio K-nearest neighbors (k-NN) per evitare la cosiddetta maledizione della dimensionalità (nota anche come effetto Hughes).Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft (1999) "When is "nearest neighbor" meaningful?". Database Theory—ICDT99, 217–235

L'estrazione delle caratteristiche e la riduzione delle dimensioni possono essere combinate in un unico passaggio utilizzando l'analisi delle componenti principali (PCA), l'analisi discriminante lineare (LDA), l'analisi di correlazione canonica (CCA) o le tecniche di fattorizzazione a matrice non negativa (NMF) come fase di pre-elaborazione seguita mediante clustering di K-NN su vettori di caratteristiche in spazi di dimensioni ridotte. Nell'apprendimento automatico questo processo è anche chiamato embedding a bassa dimensione.