A scalable version of MADD for big-data classification

Sintesi Tecnica: Una Versione Scalabile di MADD per la Classificazione di Big-Data

Problematica
I classificatori basati sulla distanza, in particolare quelli che si affidano alla distanza euclidea, sono fondamentali per l'apprendimento automatico moderno. Tuttavia, in scenari ad alta dimensionalità e basso numero di campioni (HDLSS), la distanza euclidea soffre della "concentrazione della distanza", dove le distanze tra punti della stessa classe diventano maggiori delle distanze tra punti di classi diverse. Ciò viola le strutture di vicinato e porta all'emergere di "hub", degradando severamente le prestazioni del classificatore.

Per affrontare questo problema, Pal et al. (2016) hanno introdotto il Mean Absolute Difference of Distances (MADD), una semi-metrica guidata dai dati che riesce a eludere con successo questi problemi ad alta dimensionalità mantenendo le corrette strutture di vicinato basate sulle differenze di posizione e scala. Nonostante i suoi vantaggi teorici, il MADD affronta un collo di bottiglia critico: la sua complessità computazionale. Calcolare il MADD tra due punti richiede $O(nd)$ operazioni (dove $n$ è la dimensione del campione di addestramento e $d$ è la dimensionalità), e classificare un singolo punto di test tramite un approccio Nearest Neighbor (NN) richiede $O(n^2d)$ operazioni. Come dimostrato nel paper, questa scalabilità quadratica rende il MADD computazionalmente proibitivo per grandi dataset con $n$ elevato, anche su hardware moderni.

Metodologia
Gli autori propongono una versione scalabile del MADD, denominata MADDsc, che riduce significativamente la complessità computazionale pur mantenendo i vantaggi statistici della metrica originale. La metodologia si compone di tre componenti principali:

1. Selezione di un Insieme Rappresentativo tramite Processi di Punto Determinanti (DPP):
   Invece di calcolare le distanze rispetto all'intero set di addestramento, MADDsc ridefinisce la metrica utilizzando un piccolo sottoinsieme rappresentativo di osservazioni, $X^* \subset X$. Gli autori sostengono che le proprietà di separazione teoriche del MADD siano preservate se l'insieme rappresentativo cattura la diversità dei dati originali.

   • Per selezionare questo insieme, gli autori impiegano i Processi di Punto Determinanti (DPP). A differenza del campionamento casuale semplice, che può mancare le strutture intrinseche dei dati (specialmente in distribuzioni multimodali), i DPP introducono un effetto di "repulsione". Costruendo una matrice di similarità $L$ utilizzando un kernel radiale gaussiano, i DPP selezionano un sottoinsieme di punti che sono diversificati e distribuiti attraverso la nuvola di dati, garantendo che l'insieme rappresentativo catturi il panorama dell'intero campione di addestramento.
   • Il costo computazionale è ridotto da $O(n^2d)$ a $O(knd)$, dove $k$ è la dimensione dell'insieme rappresentativo ($k \ll n$).

2. Cross-Validazione Incrementale per la Selezione degli Iperparametri:
   La dimensione dell'insieme rappresentativo ($k$) è un iperparametro cruciale. La cross-validazione standard richiederebbe la ripetuta selezione di campioni DPP e il ricalcolo delle distanze per ogni fold e candidato $k$, annullando i guadagni di velocità.

   • Gli autori propongono una tecnica di cross-validazione incrementale. Modificando l'algoritmo di campionamento DPP per garantire che i sottoinsiemi selezionati siano annidati (ovvero, $X^*(k_t) \subseteq X^*(k_{t+1})$), i valori di MADDsc possono essere calcolati incrementalmente. Ciò consente all'algoritmo di aggiornare la metrica all'aumentare di $k$ senza ricalcolare l'intera matrice di distanza, riducendo drasticamente l'overhead computazionale della selezione del modello.

3. Random Fourier Features (RFF) per Dataset Massivi:
   Per dataset estremamente grandi dove anche la costruzione della matrice $n \times n$ per il DPP è impraticabile (a causa di vincoli di memoria o costi di decomposizione degli autovettori), gli autori integrano le Random Fourier Features (RFF).

   • Basandosi sul teorema di Bochner, il kernel gaussiano viene approssimato tramite un'aspettativa Monte Carlo. La matrice di similarità $L$ è approssimata da $R R^T$, dove $R$ è una matrice di mappatura delle caratteristiche a bassa dimensionalità ($n \times 2D$).
   • Ciò consente di eseguire la decomposizione degli autovettori richiesta per il campionamento DPP su una matrice molto più piccola $2D \times 2D$ (o tramite SVD di $R$), riducendo sia la complessità temporale che quella di memoria. Questo approccio è formalizzato come NN-MADDsc con RFF.

Il framework è esteso anche a gMADDsc, una versione scalabile del MADD generalizzato (gMADD), che gestisce i casi in cui le popolazioni differiscono oltre i primi due momenti (posizione e scala).

Risultati Chiave
Studi di simulazione estesi e analisi su dati reali su dataset UCR Time Series dimostrano l'efficacia dei metodi proposti:

• Performance vs. MADD Originale: Nelle simulazioni attraverso varie distribuzioni (posizione, scala, miscela e code pesanti), NN-MADDsc raggiunge tassi di errore di classificazione quasi identici al NN-MADD originale (differenze tipicamente $\le 1\%$).
• Efficienza Computazionale:
  • NN-MADDsc è significativamente più veloce di NN-MADD. Per una dimensione di addestramento di $n=16.384$, NN-MADD ha richiesto oltre 6,5 ore, mentre NN-MADDsc ha completato l'operazione in una frazione di quel tempo.
  • La strategia di cross-validazione incrementale riduce ulteriormente il tempo di esecuzione rispetto alla cross-validazione standard, tagliando il tempo di calcolo di quasi la metà per $n=4096$.
  • L'approccio basato su RFF offre l'accelerazione più drastica. Per $n=25.000$, il metodo basato su RFF ha completato l'operazione in meno di 25 minuti, mentre il NN-MADDsc standard richiedeva oltre 15 ore, e l'originale NN-MADD falliva a causa dei limiti di memoria.
• Confronto con Altri Classificatori: NN-MADDsc supera costantemente o eguaglia i classificatori allo stato dell'arte (inclusi Random Forest, SVM e GLMNET) in contesti ad alta dimensionalità, particolarmente quando le distribuzioni dei dati differiscono per forma o scala. Nei benchmark di serie temporali reali, ha ottenuto i tassi di errore più bassi in diversi dataset (ad esempio, Synthetic Control Chart, Two Patterns).
• Garanzie Teoriche: Il paper stabilisce che, sotto regimi ad alta dimensionalità e alto numero di campioni (HDHSS), le decisioni di classificazione di NN-MADDsc convergono a quelle di NN-MADD con una probabilità che tende a 1, a condizione che la dimensione dell'insieme rappresentativo cresca in modo appropriato rispetto al logaritmo del campione.

Significatività e Rivendicazioni
Il paper sostiene di ampliare l'ambito di applicazione di MADD, rendendolo applicabile a scenari di big-data caratterizzati sia da alta dimensionalità che da un elevato numero di osservazioni. Il contributo primario è il disaccoppiamento della robustezza statistica del MADD dalla sua complessità computazionale quadratica. Sfruttando i DPP per il sottocampionamento che preserva la diversità e le RFF per l'approssimazione del kernel, gli autori forniscono una soluzione pratica e scalabile che mantiene i benefici teorici del MADD negli spazi ad alta dimensionalità. Il lavoro non pretende di sostituire tutti i classificatori, ma posiziona MADDsc come un'alternativa superiore per la classificazione basata sulla distanza in regimi in cui la distanza euclidea fallisce e il MADD tradizionale è computazionalmente intrattabile.