Sintesi Tecnica: Istogrammi di Voronoi per la Vettorizzazione Adattiva di Diagrammi di Persistenza Attesi

1. Definizione del Problema

L'Analisi Topologica dei Dati (TDA) utilizza la Persistenza Omologica (PH) per catturare le caratteristiche topologiche di nuvole di punti, codificate come Diagrammi di Persistenza (PD). Un PD rappresenta le caratteristiche topologiche (cicli) come punti $(b, d)$ in un semipiano aperto $\Omega$, dove $b$ e $d$ indicano i tempi di nascita (birth) e morte (death). Tuttavia, i PD non possono essere utilizzati direttamente come input per gli algoritmi standard di machine learning, rendendo necessaria la vettorizzazione.

Un collo di bottiglia significativo nell'uso dei PD è la loro elevata complessità computazionale; ottenere un PD può raggiungere $O(m^3)$ o persino $O(|X|^9)$ per le caratteristiche monodimensionali. Per mitigare questo problema, è stato sviluppato il Diagramma di Persistenza Atteso (EPD). Un EPD è una distribuzione di caratteristiche topologiche derivata dalla media dei PD di molteplici sottoinsiemi sottocampionati di una nuvola di punti. Sebbene gli EPD riducano i costi temporali, i metodi di vettorizzazione esistenti per gli EPD (come le Immagini di Persistenza, le Silhouette di Persistenza e i Paesaggi di Persistenza) si basano su funzioni di trasformazione di punti continue predefinite (ad esempio, kernel gaussiani o funzioni di paesaggio) e griglie di discretizzazione fisse. Questi metodi introducono scelte progettuali riguardanti la fluidità (smoothness), la larghezza di banda (bandwidth) e la risoluzione della griglia, che possono sfocare le differenze di massa locale o enfatizzare regioni non ottimali del piano $(nascita, morte)$.

Il documento affronta la necessità di un metodo di vettorizzazione alternativo che eviti espliciti modelli di trasformazione di punti fluidi e utilizzi invece una partizione adattiva e dipendente dai dati per rappresentare la distribuzione dell'EPD.

2. Metodologia: Rappresentazione basata su Voronoi (Vrep)

Gli autori propongono Vrep, un metodo di vettorizzazione che tratta l'EPD empirico come una distribuzione di caratteristiche topologiche e lo rappresenta utilizzando istogrammi basati su Diagrammi di Voronoi.

Meccanismo Centrale

1. Campionamento del Codebook: Inve แทน di una griglia fissa, Vrep costruisce un insieme di codebook casuali $S$. Ogni codebook $C = \{c_1, ..., c_k\}$ consiste di punti campionati dal supporto dell'EPD (l'insieme delle caratteristiche topologiche).
2. Partizione di Voronoi: Per un dato codebook $C$, il semipiano aperto $\Omega$ è partizionato in celle di Voronoi $V(c_i)$, dove ogni cella contiene punti più vicini a $c_i$ rispetto a qualsiasi altro $c_j$.
3. Costruzione dell'Istogramma: La rappresentazione $\Phi(\bar{\mu}, C)$ è definita come il vettore delle masse normalizzate dell'EPD $\bar{\mu}$ che ricadono in ciascuna cella di Voronoi:
   $$\Phi(\bar{\mu}, C) = [\bar{\mu}(V(c_1)), \bar{\mu}(V(c_2)), ..., \bar{\mu}(V(c_k))]$$
4. Aggregazione: Per formare la rappresentazione finale $\hat{\Phi}(\bar{\mu})$, il metodo concatena gli istogrammi generati da molteplici codebook campionati dal dataset.
5. Variante Consapevole della Diagonale (Vrepd): Una variante specifica, Vrepd, include una cella di Voronoi centrata sulla diagonale $\partial\Omega$ (dove $b=d$). Questo è fondamentale per separare il rumore (caratteristiche vicino alla diagonale) dalle caratteristiche topologiche significative.

Strategie di Campionamento del Codebook

Il documento valuta tre strategie per il campionamento dei punti all'interno di un codebook:

• Default: Campionamento uniforme dal supporto dell'EPD.
• Persistence-Weighted (Pesato sulla Persistenza): Campionamento pesato sulla persistenza ($d-b$), dando priorità alle caratteristiche significative.
• Uniforme: Campionamento da un rettangolo fisso sopra la diagonale (irrilevante per l'EPD).

Normalizzazione

Il metodo normalizza l'EPD per una norma $l_1$ unitaria ($\bar{\mu} \leftarrow \bar{\mu}/\bar{\mu}(\Omega)$). Ciò tratta l'EPD come una distribuzione di probabilità, garantendo che tutti gli EPD abbiano la stessa massa, il che consente l'uso diretto della distanza di Wasserstein per l'analisi della stabilità e della dissimilarità, evitando la necessità di metriche di Optimal Partial Transport.

3. Contributi Teorici

Il documento stabilisce garanzie teoriche riguardo alla stabilità e alla capacità rappresentativa di Vrep sotto specifiche condizioni:

• Limiti di Stabilità: Gli autori dimostrano che Vrep è stabile sotto perturbazioni dell'EPD. Nello specifico, se l'EPD subisce una $\Delta$-perturbazione (piccolo movimento di masse Dirac), il cambiamento nella rappresentazione Vrep è Lipschitz continuo rispetto a $\Delta$. Il limite di errore dipende dalla dimensione del codebook $k$ e dalle proprietà del dataset.
• Limiti Relativi a Wasserstein: Il documento fornisce un limite inferiore condizionale che mette in relazione la distanza $l_1$ tra due vettori Vrep con la distanza di Wasserstein ($W_1$) tra gli EPD sottostanti.
  $$\|\Phi(\bar{\mu}, C) - \Phi(\bar{\nu}, C)\|_1 \geq \frac{W_1(\bar{\mu}, \bar{\nu}) - \text{errori di approssimazione}}{d_{max}(C)}$$
  Questo risultato chiarisce che Vrep preserva efficacementamente le variazioni su scala Wasserstein quando il codebook è "ben risolto" (ovvero, l'errore di approssimazione è piccolo rispetto alla separazione delle distribuzioni). Non è una garanzia di conservazione monotona generale, ma una dichiarazione di coerenza condizionale.

4. Risultati Sperimentali

Gli autori hanno valutato Vrep e Vrepd nella classificazione supervisionata di nuvole di punti e in compiti di riduzione della dimensionalità non supervisionata, confrontandoli con i metodi standard: Immagine di Persistenza (PI), Silhouette di Persistenza (PS), Paesaggio di Persistenza (PL) e la rete end-to-end PointNet.

Prestazioni di Classificazione

• Dataset: Gli esperimenti sono stati condotti su dataset diversificati, inclusi strutture proteiche, componenti meccaniche CAD e dati di serie temporali (trasformati in nuvole di punti tramite embedding a ritardo temporale).
• Risultati: Vrep e Vrepd hanno costantemente ottenuto un'accuratezza di classificazione superiore o comparabile (usando un classificatore Random Forest) rispetto a PI, PS e PL nella maggior parte dei dataset sensibili alla topologia.
  • Sul dataset Proteine, Vrep ha raggiunto un'accuratezza del 98,5% (rispetto al 95,5% di PI).
  • Sui dataset CAD, Vrep e Vrepd hanno superato gli altri metodi non supervisionati, sebbene PI abbia mostrato risultati competitivi in alcuni setting di rumore.
• Sensibilità del Codebook: La strategia di campionamento del codebook persistence-weighted ha spesso prodotto i risultati migliori, in particolare in ambienti rumorosi, poiché focalizza la rappresentazione sulle caratteristiche topologiche significative.

Stabilità e Scalabilità

• Stabilità alla Perturbazione: Esperimenti su un dataset di sistemi dinamici 3D hanno dimostrato che Vrep è stabile sotto perturbazioni di rumore Gaussiano. Interessante notare che Vrepd (con la cella della diagonale) ha dimostrato una stabilità leggermente superiore rispetto a Vrep, probabilmente grazie a una migliore separazione del rumore vicino alla diagonale.
• Complessità Temporale:
  • Vrep ha una complessità temporale di $O(m^2tk)$ per un dataset di dimensione $m$, dove $t$ è il numero di codebook e $k$ è la dimensione del codebook. È quadratica rispetto alla dimensione del dataset.
  • Tuttavia, Vrep è più veloce di PL e PS nel tempo di esecuzione effettivo e scala meglio con il numero di PD campionati ($n$) perché sottocampiona il supporto dell'EPD a una dimensione fissa, mentre PI/PS/PL devono elaborare individualmente ogni PD campionato.
  • Sebbene PointNet (supervisionato) abbia raggiunto un'alta accuratezza, Vrep offre un'alternativa competitiva per compiti non supervisionati (come la riduzione della dimensionalità) dove PointNet non può essere applicato.

Riduzione della Dimensionalità Non Supervisionata

In un compito di visualizzazione t-SNE su un dataset di sistemi dinamici, Vrep ha prodotto cluster con indici Calinski-Harabasz (CH) più elevati (1751) rispetto a PI (569) e PL (1655), indicando una separazione dei cluster superiore.

5. Significato e Rivendicazioni

Il documento posiziona Vrep come una rappresentazione complementare piuttosto che un sostituto universale dei metodi esistenti.

• Adattivo vs. Fluido: Il contributo primario è il passaggio da approssimazioni funzionali fluide basate su kernel a un conteggio adattivo e dipendente dai dati. Vrep aggrega la massa su celle definite dai dati stessi, il che la rende potenzialmente più fedele all'allocazione della massa empirica dell'EPD.
• Compromesso (Trade-off): Gli autori riconoscono esplicitamente il compromesso: Vrep riassume efficacementamente l'allocazione della massa grossolana, ma è intrinsecamente lossy (con perdita di informazione) riguardo alla geometria fine all'interno di una cella di Voronoi. Di conseguenza, i metodi fluidi (come PI o i metodi a kernel) possono superare Vrep quando la variazione topologica rilevante riguarda piccoli spostamenti locali o cambiamenti di forma all'interno di una cella.
• Utilità Non Supervisionata: Un significato chiave è l'applicabilità di Vrep all'apprendimento non supervisionato. A differenza degli approcci di deep learning supervisionati (es. PointNet, PersLay), Vrep non richiede etichette per l'estrazione delle caratteristiche, rendendolo adatto per compiti di riduzione della dimensionalità e clustering.
• Rivendicazioni Moderate: Gli autori non affermano che Vrep domini tutte le vettorizzazioni. Notano che i metodi a kernel (PWGK, SWK) possono superare Vrep su specifici dataset (es. CAD), ma a un costo computazionale significativamente più elevato. Il documento conclude che Vrep è un'alternativa adattiva e competitiva che offre una scalabilità favorevole con il numero di PD campionati e un bias di approssimazione distinto, adatto alla classificazione sensibile alla topologia.