Prototype Selection Using Topological Data Analysis

Sintesi Tecnica: Selezione di Prototipi Utilizzando l'Analisi Topologica dei Dati

Definizione del Problema
Le moderne pipeline di classificazione affrontano spesso colli di bottiglia in cui la dimensione del set di addestramento, piuttosto che il costo di una singola predizione, domina il tempo di inferenza. Mentre i modelli parametrici (ad esempio, SVM, Random Forests) spostano l'onere sul tempo di addestramento, essi continuano comunque a scalare con il numero di istanze di addestramento. La selezione dei prototipi affronta questo problema comprimendo il set di addestramento in un sottoinsieme piccolo e rappresentativo. Le tassonomie esistenti della selezione dei prototipi — incluse le famiglie di condensazione, edizione, ibrida, basata sulla competenza e basata sull'ottimizzazione — operano senza una rappresentazione esplicita della struttura topologica dei dati. Di conseguenza, la geometria dei confini decisionali tra le classi, che può esibire strutture complesse attraverso molteplici scale spaziali, viene catturata solo implicitamente. Questo articolo affronta il divario nell'utilizzo della struttura topologica multi-scala dei dati come criterio diretto per la selezione dei prototipi.

Metodologia
Gli autori introducono due varianti di un Selettore di Prototipi Topologico (TPS) che utilizzano l'omologia persistente, uno strumento fondamentale della Topological Data Analysis (TDA), per identificare e mantenere i prototipi. Entrambi i metodi si basano sulla filtrazione di Rips, ma differiscono nel modo in cui codificano l'informazione di confine:

1. Selettore di Prototipi Topologici Consapevole del Confine (BoundaryTPS):

   • Meccanismo: Si tratta di un metodo a stadio singolo che utilizza una filtrazione di Rips con pesatura dei vertici. Assegna pesi ai punti della classe target in base alla loro prossimità alle classi non target (specificamente, la somma delle distanze dai $k$ vicini più prossimi non target).
   • Processo: I punti vicini al confine decisionale ricevono pesi bassi ed entrano nella filtrazione precocemente, mentre i punti interni ricev oggettivi pesi elevati e vengono ritardati. Ciò assicura che la topologia della regione di confine venga risolta a scale più fini.
   • Selezione: I prototipi vengono selezionati identificando le caratteristiche di persistenza a un determinato quantile della distribuzione della durata della vita (lifetime). Un parametro di tolleranza $\tau$ permette di selezionare una finestra di caratteristiche attorno al quantile target per migliorare la robustezza.

2. Selettore di Prototipi Topologico (TPS):

   • Meccanismo: Questo è un metodo a due stadi che codifica implicitamente l'informazione di confine costruendo una nuvola di punti mista contenente sia osservazioni target che non target.
   • Stadio 1 (Vicinato di Confine): Una filtrazione di Rips standard viene costruita sulla nuvola mista per catturare la struttura topologica tra le classi. Le caratteristiche vengono selezionate in base a un quantile della distribuzione della durata della vita, e i punti della classe target sopravvissuti vengono mantenuti.
   • Stadio 2 (Interno): Una seconda filtrazione di Rips viene costruita sui sopravvissuti dello Stadio 1 per catturare la topologia intra-classe. Le caratteristiche vengono selezionate in base alla media della durata della vita per mantenere i campioni tipici dell'interno.
   • Risultato: Il set finale combina i punti rilevanti per il confine dello Stadio 1 con i punti di supporto dell'interno dello Stadio 2.

Contributi Chiave

• Nuovo Criterio: Il documento introduce l'omologia persistente come criterio di selezione dei prototipi, una capacità precedentemente non utilizzata in questo dominio.
• Doppia Realizzazione: Presenta TPS e BoundaryTPS, dimostrando che la codifica dell'informazione di confine tramite filtrazioni a classi miste (TPS) rispetto ai pesi dei vertici (BoundaryTPS) porta a specializzazioni empiricamente differenti.
• Benchmarking Completo: Entrambi i metodi sono valutati contro sette baseline classiche (CNN, CNN+ENN, DROP3, ICF, IB3, KMeans, SPOTGreedy) su quindici dataset del mondo reale e sei classificatori downstream sotto cross-validazione annidata.
• Preservazione Topologica: Lo studio dimostra che i metodi topologici preservano la struttura del diagramma di persistenza $H_1$ significativamente meglio dei baseline basati sulla densità o sulle decisioni a catena.
• Stabilità: Entrambi i metodi esibiscono una maggiore stabilità di selezione (misurata tramite la similitudine di Jaccard fold-to-fold) rispetto a qualsiasi selettore a decisioni a catena testato.
• Sbilanciamento delle Classi: I metodi ereditano le proporzioni di classe del set sorgente senza richiedere meccanismi sensibili alle etichette.

Risultati

• Fedeltà Topologica: BoundaryTPS raggiunge il rango medio di Friedman più basso (2.00) sulla distanza di Wasserstein-1 di $H_1$, superando significativamente cinque delle sette baseline. TPS si posiziona terzo (3.60). Entrambi i metodi si raggruppano nella parte alta dello spettro delle prestazioni per la preservazione delle strutture a loop ($H_1$), mentre i metodi classici spesso appiattiscono queste caratteristiche.
• Stabilità di Selezione: TPS raggiunge la massima similitudine di Jaccard media (0.225) tra i fold, seguito da BoundaryTPS (0.202). Entrambi sono significativamente più stabili dei metodi a decisioni a catena come CNN+ENN (0.057) e DROP3 (0.080).
• Prestazioni di Classificazione: Su media geometrica (G-Mean) aggregata, i metodi topologici sono competitivi ma non dominanti. SPOTGreedy e KMeans raggiungono la G-Mean aggregata più alta (0.84). TPS e BoundaryTPS raggiungono rispettivamente 0.79 e 0.76. Il documento nota che, sebbene non dominino l'accuratezza di classificazione pura, offrono un punto operativo distinto nello spazio di progettazione, particolarmente riguardo alla preservazione strutturale e alla stabilità.
• Scalabilità: Empiricamente, entrambi i metodi scalano in modo sub-quadratico rispetto alla dimensione del campione.

Significato e Rivendicazioni
Il documento sostiene che il significato primario di questo lavoro risieda nello spostamento del paradigma della selezione dei prototipi da pure euristiche geometriche o statistiche a un framework fondato su invarianti topologici multi-scala. Gli autori argomentano che, sebbene i metodi esistenti assumano implicitamente un principio di prossimità al confine, essi falliscono nel risolvere la complessa struttura multi-scala dei confini decisionali. Utilizzando esplicitamente l'omologia persistente, i metodi proposti offrono un modo rigoroso per mantenere i punti che definiscono la "forma" topologica dei dati, in particolare i loop e i confini che vengono spesso persi nella riduzione basata sulla densità.

Gli autori caratterizzano i risultati con modestia: i metodi topologici non superano universalmente i baseline esistenti in termini di accuratezza di classificazione downstream (G-Mean), ma occupano una regione unica e preziosa dello spazio di progettazione offrendo una superiore preservazione topologica e stabilità di selezione. Il lavoro suggerisce che per applicazioni in cui l'integrità strutturale del confine decisionale o la riproducibilità del processo di selezione sono fondamentali, i criteri topologici forniscono un'alternativa distinta ed efficace rispetto agli approcci classici.