Sintesi Tecnica: Diagrammi di Persistenza Non Ridotti per il Machine Learning Topologico

Definizione del Problema

L'analisi dei dati topologici (TDA) combinata con l'apprendimento automatico (ML) supervisionato è diventata un approccio standard per l'analisi di dati complessi in diversi domini, tra cui la biologia, le neuroscienze e la scienza dei materiali. La pipeline standard prevede il calcolo della Persistenza Omologica (PH) per generare Diagrammi di Persistenza (PD), la vettorizzazione di tali diagrammi e l'addestramento di modelli ML.

Tuttavia, sono state osservate due criticità fondamentali in questa pipeline:

1. Ridondanza dell'Informazione: Evidenze empiriche suggeriscono che i modelli di ML spesso ignorano porzioni significative di informazione contenute nei PD vettorizzati. Ad esempio, compiti di regressione hanno mostrato prestazioni "quasi ottimali" utilizzando solo la persistenza del 28° punto più persistente, e i benchmark indicano che le vettorizzazioni statistiche naive spesso performano quanto quelle complesse.
2. Costo Computazionale: Il calcolo dei PD completamente ridotti è spesso il passaggio più dispendioso dal punto di vista computazionale, richiedendo una quantità sostanziale di memoria e tempo, specialmente per dataset di grandi dimensioni.

La tesi centrale di questo lavoro è che, se i modelli di ML possono performare bene con vettorizzazioni che scartano informazioni, allora l'intero calcolo della PH (specificamente la riduzione delle matrici di bordo) potrebbe essere una spesa computazionale non necessaria. Gli autori propongono di evitare interamente la riduzione della matrice di bordo, utilizzando invece diagrammi di persistenza non ridotti derivati direttamente dalle matrici di bordo non ridotte.

Metodologia

Framework Teorico

Gli autori definiscono diversi tipi di diagrammi di persistenza (PD) non ridotti costruiti da una matrice di bordo $M$ senza eseguire l'algoritmo standard di riduzione per colonne. Questi sono definiti in base alle proprietà delle colonne della matrice:

• Diagramma AP (Apparent Pair): Coppie $(low(M_j), j)$ dove l'unica voce non nulla nella riga corrispondente a sinistra dell'elemento più basso non nullo nella colonna $j$ è la stessa (un pattern specifico che indica una coppia di persistenza senza riduzione).
• Diagramma qAP↓ (Lower Quasi-Apparent Pair): Coppie $(low(M_j), j)$ dove $\beta(M_j) \neq -1$.
• Diagramma qAP↑ (Upper Quasi-Apparent Pair): Coppie $(\beta(M_j), j)$ dove $\beta(M_j) \neq -1$. Qui, $\beta(M_j)$ è l'indice di riga più alto di un elemento 1 nella colonna $j$ che non può essere eliminato dalla riduzione.
• Diagramma L1 (Low-Ones): Il multinsieme di coppie $(low(M_j), j)$ per tutte le colonne dove $low(M_j) \neq -1$.

I costrutti L1 e qAP↑ sono particolarmente enfatizzati per i complessi di Vietoris-Rips (VR), poiché gli altri tipi di unreduced potrebbero generare solo coppie effimere (persistenza zero) nelle dimensioni dell'omologia superiore per queste filtrazioni.

Analisi della Stabilità

Il documento investiga la stabilità di Lipschitz delle trasformazioni rispetto alla distanza di bottleneck ($d_B$).

• Risultati Teorici: La trasformazione PD completamente ridotta (FR) è globalmente stabile con una costante di Lipschitz $C=1$. Al contrario, i PD non ridotti (AP, qAP) non sono generalmente stabili globalmente. Piccole perturbazioni nella funzione di filtratura possono riordinare le colonne della matrice di bordo, causando la comparsa o la scomparsa di coppie apparenti, portando a un'instabilità combinatoria.
• Stabilità Locale: Gli autori dimostrano che i PD non ridotti sono localmente Lipschitz stabili. Se la perturbazione nella funzione di filtratura è sufficientemente piccola da preservare l'ordinamento dei simplessi (specificamente, più piccola della metà del gap minimo tra i valori di filtratura adiacenti), le trasformazioni rimangono stabili.
• Stabilità Sperimentale: Esperimenti computazionali su nuvole di punti perturbate mostrano che, sebbene si verifichino picchi di instabilità significativi (dove il numero di punti nel diagramma cambia), questi sono rari. La maggior parte delle perturbazioni produce rapporti di stabilità comparabili o migliori rispetto al caso completamente ridotto.

Implementazione Computazionale

Per testare i vantaggi computazionali, gli autori hanno implementato una versione modificata dell'algoritmo Ripser per calcolare i diagrammi qAP↑ per i complessi VR.

• Parallelizzazione: A differenza dell'algoritmo di riduzione standard, che elabora le colonne serialmente (da sinistra a destra), il calcolo dei diagrammi qAP↑ può essere parallelizzato. L'algoritmo ricerca attraverso le colonne della matrice di cobordo della filtratura in modo indipendente.
• Efficienza della Memoria: L'implementazione evita di memorizzare l'intera matrice di bordo e i bordi di lavoro necessari per la riduzione. Utilizza una hash map per memorizzare le coppie e salta precocemente le "coppie apparenti zero" (coppie effimere).

Risultati Chiave

Prestazioni Computazionali

Il benchmarking su un sistema AMD Ryzen Threadripper PRO a 32 core contro lo standard Ripser ha rivelato guadagni significativi:

• Tempo di Esecuzione (Wall Time): Il calcolo parallelizzato di qAP↑ ha ottenuto un incremento medio di velocità di 20 volte nel tempo di esecuzione rispetto al calcolo della persistenza completa.
• Memoria: L'approccio non ridotto ha richiesto circa 1/13 della memoria di Ripser per gli esempi non soglia e 1/1.86 per quelli soglia.
• Scalabilità: Gli autori hanno calcolato con successo i diagrammi non ridotti per il dataset torus4 (50.000 punti), un compito in cui Ripser è fallito a causa dei limiti di memoria (richiedendo >300GB di RAM). Per il dataset cyclo-octane, il calcolo qAP↑ ha utilizzato 454 volte meno memoria e 59.5 volte meno tempo di esecuzione rispetto a Ripser.

Prestazioni di Machine Learning

Gli autori hanno valutato le prestazioni di classificatori e regressori Random Forest addestrati su vettorizzazioni di PD non ridotti (L1, qAP, AP) rispetto ai PD completamente ridotti (FR) attraverso tre compiti:

1. Classificazione di Forme Sintetiche: Classificare nuvole di punti (cerchio, sfera, toro, ecc.) con vari livelli di rumore.
2. Classificazione Fashion-MNIST: Classificare immagini di abbigliamento utilizzando complessi cubici.
3. Regressione dell'Arteria Cerebrale: Predire l'età del soggetto da dati di scansioni cerebrali 3D.

Risultati:

• Parità e Miglioramento: In tutti gli esperimenti, almeno un tipo di PD non ridotto ha performato almeno quanto o meglio del PD completamente ridotto (FR).
• Superiorità di L1: I diagrammi L1 hanno costantemente performato in linea con o meglio dei diagrammi FR. Nel compito Fashion-MNIST, i diagrammi L1 hanno superato i diagrammi FR di almeno 10 punti percentuali in precisione media.
• Robustezza: Questi risultati sono stati robusti attraverso diversi tipi di filtratura (Alpha, Rips), metodi di vettorizzazione (Persistence Images, coordinate di Adcock-Carlsson) e livelli di rumore.
• Importanza delle Caratteristiche: L'analisi del compito Fashion-MNIST ha rivelato che i modelli L1 e FR si basano su regioni distinte dello spazio dell'immagine di persistenza. Le caratteristiche più importanti per i modelli L1 erano concentrate in $H_0$ (componenti connesse), mentre i modelli FR utilizzavano le caratteristiche sia di $H_0$ che di $H_1$ in modo più equilibrato. Ciò suggerisce che i diagrammi non ridotti codificano informazioni diverse, potenzialmente utili, che vengono scartate durante la riduzione completa.

Significato e Rivendicazioni

Il documento conclude che i diagrammi di persistenza non ridotti sono sostituti efficaci dei diagrammi completamente ridotti nelle pipeline di machine learning topologico.

• Efficienza Computazionale: Evitando lo costoso passaggio di riduzione, i praticanti possono ottenere riduzioni significative nell'uso della memoria e nel tempo di calcolo, consentendo l'analisi di dataset attualmente intrattabili per i metodi PH standard.
• Prestazioni: Contrariamente all'assunto che la riduzione sia necessaria per la qualità, gli autori dimostrano che l'informazione scartata dalla riduzione è spesso non critica per le prestazioni a valle del ML e che i diagrammi non ridotti possono persino catturare caratteristiche distinte e benefiche.
• Direzioni Future: Gli autori notano che, sebbene i diagrammi non ridotti risparmino calcoli, la loro vettorizzazione può essere più lenta a causa del maggior numero di punti. Suggeriscono che il lavoro futuro dovrebbe concentrarsi sulla progettazione di algoritmi che calcolino le vettorizzazioni direttamente dalle matrici non ridotte senza memorizzare esplicitamente tutte le coppie, ottimizzando ulteriormente la pipeline.

Lo studio afferma con moderazione che questi risultati suggeriscono un possibile cambiamento nel modo in cui vengono costruite le pipeline PH-ML, privilegiando potenzialmente l'efficienza computazionale e la ritenzione di caratteristiche topologiche "grezze" rispetto alla rigorosa completezza matematica dei diagrammi completamente ridotti.