Mathematical Morphology in Machine Learning

Sintesi Tecnica: Morfologia Matematica nel Machine Learning

Definizione del Problema
Sebbene la Morfologia Matematica (MM) sia una teoria consolidata nella visione computazionale per l'analisi di oggetti grafici basata su forma, dimensione e convessità, la sua applicazione nel machine learning rimane sottoutilizzata. Le tecniche di machine learning esistenti spesso non riescono a sfruttare sufficientemente le informazioni su forma e densità. Inoltre, gli attuali metodi di clustering e classificazione o si affidano a euristiche che non aderiscono pienamente ai principi della MM, o mancano della capacità di modellare simultaneamente informazioni frattali, forma e densità. Inoltre, in ambienti discreti (come il processamento basato su GPU), le metriche di distanza standard presentano dei compromessi: la distanza Euclidea è computazionalmente costosa e richiede la quantizzazione, mentre le distanze di Chebyshev e Manhattan sono veloci ma di natura "quadrata", fallendo nell'approssimare efficacemente l'iterazione circolare della distanza Euclidea.

Metodologia
Il documento propone un framework che integra la morfologia matematica nel machine learning attraverso tre componenti primarie:

1. Algoritmo di Clustering k-Morphological Sets (k-MS):

   • Questo algoritmo utilizza la ricostruzione morfologica invece delle operazioni binarie (a differenza dei precedenti algoritmi di clustering morfologico binario).
   • Opera su una griglia dove le istanze dei dati vengono mappate. Un elemento strutturante $B$ (inizialmente contenente zeri) e una maschera $M$ vengono utilizzati per eseguire la ricostruzione.
   • L'algoritmo impiega una variabile interna $\delta$ per controllare la dimensione dell'elemento strutturante. Aumenta iterativamente $\delta$ per far crescere i cluster fino a quando non viene raggiunto uno stato idempotente o un numero predefinito di cluster ($k$).
   • Se il numero di indici di cluster unici supera $k$, $\delta$ viene incrementato; se la ricostruzione diventa non idempotente (i cluster si fondono), $\delta$ viene resettato a 1 e il processo si ripete.
   • Il metodo segmenta intrinsecamente il rumore in piccoli cluster indipendenti senza costi di elaborazione aggiuntivi.

2. Nuova Metrica di Distanza:

   • Per ottimizzare l'iterazione dei vicini in spazi discreti (specificamente per l'implementazione su GPU), viene proposta una nuova metrica di distanza.
   • Questa metrica è una combinazione pesata della distanza di Chebyshev e della distanza di Minkowski (Equazione 1: $d_{R^p}(x,y) = w_1 \sum |x_i - y_i|^p + w_2 \max |x_i - y_i|$).
   • Regolando i pesi $w_1$ e $w_2$ e il parametro $p$, la metrica può convergere verso comportamenti di tipo Chebyshev o Minkowski.
   • In 2D ($R^2$), questa distanza produce una forma ottagonale, che è geometricamente più vicina alla distanza circolare Euclidea rispetto alle forme quadrate prodotte dalle distanze Manhattan o Chebyshev.

3. Classificatori Morfologici:

   • Gli autori propongono classificatori che fanno crescere le istanze di addestramento tramite dilatazioni per coprire lo spazio non etichettato.
   • Questi classificatori sono implementati su unità di elaborazione grafica (GPU) per sfruttare l'elaborazione parallela, dove le celle della griglia crescono simultaneamente.
   • Quando si verificano intersezioni durante la crescita, un sistema di voto determina l'etichetta.

Contributi Chiave

• Algoritmo k-MS: Una tecnica di clustering che preserva forma e densità, offre un senso intrinseco del numero massimo di cluster creabili (indipendentemente da $k$) e rimuove il rumore senza sovraccarichi computazionali aggiuntivi.
• Metrica di Distanza Ibrida: Una nuova metrica che combina le distanze di Chebyshev e Minkowski, offrendo un equilibrio tra l'efficienza computazionale delle distanze "quadrate" e l'accuratezza geometrica della distanza Euclidea.
• Implementazione Ottimizzata per GPU: Lo sviluppo di classificatori morfologici e calcoli di distanza specificamente adattati per ambienti GPU a basso livello, evitando accessi ai kernel lenti e dimensioni dei kernel indefinite.
• Valutazione Comprensiva: Test estesi della metrica di distanza proposta utilizzando il classificatore k-Nearest Neighbors (k-NN) su 33 dataset UCI.

Risultati

• Efficienza del Clustering: L'algoritmo k-MS è risultato più veloce delle tecniche di clustering basate sulla densità allo stato dell'arte, fornendo al contempo caratteristiche uniche come la rimozione del rumore e la preservazione della forma. In termini di analisi temporale rispetto al k-Means parallelo (CPU), il k-MS ha dimostrato prestazioni competitive o superiori, particolarmente all'aumentare del numero di cluster grazie alle ottimizzazioni di interruzione anticipata (early-break).
• Prestazioni della Metrica di Distanza:
  • Velocità: Nelle attività di iterazione dei vicini discreti in $Z^2$, la distanza proposta è stata circa 1,3 volte più veloce della distanza di Manhattan e 329,5 volte più veloce della distanza Euclidea.
  • Accuratezza: Quando valutata con k-NN su 33 dataset UCI, la distanza proposta ha ottenuto accuratezze superiori alla media di altre 14 distanze in 26 casi su 33. Ha raggiunto la migliore accuratezza singola in 9 casi su 33.
• Clustering Visivo: In dataset rumorosi, il k-MS ha separato con successo i cluster genuini dagli outlier, mentre altri algoritmi (come Chameleon) hanno talvolta raggruppato gli outlier con i cluster genuini, e altri (come Mitosis) non sono riusciti a separare il rumore.

Significatività e Rivendicazioni
Gli autori affermano che questo lavoro rappresenta la prima proposta di tecniche di classificazione e clustering che si basano interamente su tecniche di morfologia matematica, andando oltre le connessioni euristiche. Il documento asserisce che nessun altro classificatore nella letteratura attuale può modellare correttamente simultaneamente forma, densità e informazioni frattali.

La significatività del lavoro risiede nel colmare il divario tra la teoria della visione computazionale e il machine learning, fornendo strumenti che non sono solo teoricamente solidi riguardo a forma e densità, ma anche computazionalmente efficienti per l'hardware moderno (GPU). La metrica di distanza proposta è evidenziata come una soluzione pratica per ambienti di calcolo ad alte prestazioni dove la distanza Euclidea è troppo lenta e le distanze Manhattan/Chebyshev mancano di sufficiente fedeltà geometrica. Gli autori sottolineano che questi contributi hanno già portato a molteplici pubblicazioni in riviste prestigiose come Pattern Recognition e Pattern Recognition Letters.