Riepilogo Tecnico: La Distanza di Wasserstein Osservabile

Enunciato del Problema

La sfida principale affrontata in questo articolo è l'intrattabilità computazionale del calcolo della distanza di Wasserstein esatta tra misure di probabilità su dataset su larga scala e non euclidei. Sebbene la teoria del trasporto ottimo (OT) fornisca un quadro rigoroso per il confronto delle distribuzioni, il calcolo esatto scala tipicamente in modo cubico o quadratico con il numero di punti dati, rendendolo impraticabile per dataset massivi.

Le approssimazioni esistenti, come la distanza di Wasserstein tagliata (Sliced Wasserstein), offrono efficienza computazionale proiettando le misure su sottospazi unidimensionali. Tuttavia, questi metodi si basano sulla struttura lineare degli spazi euclidei ($\mathbb{R}^d$), utilizzando prodotti scalari e norme per definire le direzioni di proiezione. Molti dataset di interesse — come forme 3D, grafi, strutture proteiche e superfici funzionali — risiedono in spazi metrici generali dove sono assenti linearità e prodotti scalari. Di conseguenza, gli approcci standard di Wasserstein tagliato non possono essere applicati direttamente, e vi è la necessità di un'alternativa computazionalmente trattabile che fornisca limiti inferiori sulla distanza di Wasserstein in spazi metrici polacchi generali.

Metodologia

Il Framework della Distanza di Wasserstein Osservabile

Gli autori introducono la distanza di Wasserstein osservabile, un framework che generalizza il concetto di taglio a spazi metrici arbitrari $(X, d)$. Invece di proiettare su sottospazi lineari, il metodo proietta le misure di probabilità sulla retta reale utilizzando osservabili metriche.

1. Osservabili Metriche: Un osservabile è definito come una funzione 1-Lipschitziana $f: X \to \mathbb{R}$, tale che $|f(x) - f(y)| \leq d(x, y)$. L'insieme di tutte tali funzioni è denotato $\Lambda(X)$.
2. Misure di Trasporto Spinto: Per una misura $\mu \in \mathcal{P}(X)$ e un osservabile $f$, la misura di trasporto spinto $f_\sharp \mu$ è definita su $\mathbb{R}$.
3. Definizione della Distanza: La distanza di Wasserstein osservabile $p$, $\theta_p(\mu, \nu)$, è definita come il supremo delle distanze di Wasserstein tra le misure di trasporto spinto su tutti i possibili osservabili:
   $$\theta_p(\mu, \nu) := \sup_{f \in \Lambda(X)} w_p(f_\sharp \mu, f_\sharp \nu)$$
   Poiché gli osservabili sono 1-Lipschitziani, ne consegue che $\theta_p(\mu, \nu) \leq w_p(\mu, \nu)$, stabilendolo come un limite inferiore.

Approssimazione Gerarchica e Identificabilità

Per gestire il costo computazionale dell'ottimizzazione sullo spazio infinito-dimensionale $\Lambda(X)$, gli autori costruiscono una gerarchia di sottospazi $\Lambda_n(X) \subseteq \Lambda(X)$.

• Osservabili di Base: La costruzione inizia con funzioni distanza-da-un-punto $f_a(x) = d(x, a)$.
• Prodotti a Cuneo: Gli osservabili di ordine superiore sono formati tramite prodotti a cuneo (minimi) ponderati di queste funzioni di base: $f_{\mathbf{a}}^\alpha = \alpha_0 f_{a_0} \wedge \dots \wedge \alpha_n f_{a_n}$.
• La Gerarchia: $\Lambda_n(X)$ consiste di osservabili formati da prodotti a cuneo di al massimo $n+1$ funzioni di base. Ciò induce una sequenza di pseudo-metriche $\theta_{p,n}(\mu, \nu)$.

Contributi Teorici: Iniettività Stratificata

Un risultato teorico centrale è un analogo nello spazio metrico del Dispositivo di Cramér-Wold. L'articolo stabilisce che la collezione di misure di trasporto spinto tramite osservabili in $\Lambda_n(X)$ caratterizza univocamente una misura di probabilità $\mu$ se la dimensione di copertura metrica del suo supporto è $\leq n$.

• Dimensione di Copertura Metrica ($\xi_X$): Una nozione di dimensione definita dal raffinamento di ricoprimenti aperti in sfere aperte.
• Teorema di Iniettività Stratificata: Se il supporto di $\mu$ ha dimensione di copertura metrica $\leq n$, allora $\mu$ è univocamente determinato dalle sue proiezioni $f_\sharp \mu$ per ogni $f \in \Lambda_n(X)$.
• Implicazione: Per misure supportate su spazi con bassa dimensione di copertura metrica (ad esempio, insiemi finiti, grafi o varietà a bassa dimensione), la restrizione dello spazio degli osservabili a $\Lambda_n(X)$ produce una vera metrica (non solo una pseudo-metrica) che è strettamente limitata inferiormente dalla vera distanza di Wasserstein.

Modello Computazionale Discreto

Per l'implementazione pratica, gli autori propongono un modello discreto in cui lo spazio metrico è approssimato da una $\delta$-copertura finita (una griglia). Gli osservabili sono limitati a quelli ancorati su punti all'interno di questo insieme finito. Vengono forniti limiti teorici che mostrano come la distanza osservabile discreta converga alla versione continua all'aumentare della risoluzione della griglia, con un errore proporzionale alla spaziatura della griglia $\delta$.

Risultati Chiave

Risultati Teorici

• Proprietà Metrica: $\theta_p$ è una metrica sullo spazio di tutte le misure di probabilità. La versione ristretta $\theta_{p,n}$ è una metrica sul sottospazio delle misure con dimensione del supporto $\leq n$.
• Equivalenza per $p=1$: Per $p=1$, la distanza di Wasserstein osservabile è esattamente uguale alla distanza di Wasserstein standard ($\theta_1 = w_1$), un risultato derivato dalla dualità di Kantorovich-Rubinstein.
• Monotonia: La gerarchia soddisfa $\theta_{p,n} \leq \theta_{p,m} \leq \theta_p \leq w_p$ per $n \leq m$, offrendo un compromesso sintonizzabile tra efficienza computazionale e precisione del limite.

Esperimenti Numerici

L'articolo presenta diversi esperimenti di prova di concetto che confrontano le distanze di Wasserstein Osservabile (OW) con la Distanza di Wasserstein Tagliata (SW), la distanza di Wasserstein standard e la distanza Chamfer:

1. Classificazione Gaussiana: In spazi euclidei ad alta dimensionalità, OW e SW performano in modo comparabile nel distinguere classi Gaussiane. Tuttavia, OW mostra un vantaggio di performance relativo all'aumentare della dimensionalità, potenzialmente dovuto al fenomeno della concentrazione della misura che influenza le proiezioni 1D in SW.
2. Distribuzioni su Grafi: Su spazi di grafi non euclidei, OW supera significativamente la distanza di Wasserstein standard nelle attività di classificazione mantenendo una scalabilità computazionale superiore. OW dimostra robustezza al rumore che la distanza di Wasserstein classica non possiede.
3. Distribuzioni su Sfera: Esperimenti su sfere illustrano il compromesso tra il numero di osservabili/funzioni e il costo computazionale. Aumentare la complessità degli osservabili (maggiore $n$) riduce l'errore relativo ma comporta costi combinatori.
4. Classificazione di Nuvole di Punti (ModelNet10): Su dati reali di oggetti 3D, le distanze OW ottengono i punteggi di classificazione migliori tra le metriche scalabili, in particolare in regimi rumorosi, superando sia SW che la distanza Chamfer.
5. Applicazione nel Deep Learning: Gli autori hanno integrato OW in una funzione di perdita per un autoencoder di nuvole di punti. L'uso di OW (in particolare una variante in stile $L_2$ per la differenziabilità) ha portato a una maggiore accuratezza di classificazione nello spazio latente e a una densità di punti più uniforme nelle ricostruzioni rispetto alla distanza Chamfer, che ha prodotto output più nitidi ma con densità non uniforme.

Significato e Affermazioni

L'articolo afferma di fornire un framework computazionalmente trattabile per derivare limiti inferiori sulla distanza di Wasserstein in spazi metrici generali, aggirando le limitazioni dei metodi specifici per spazi euclidei come il Wasserstein Tagliato.

• Novità Teorica: Il lavoro stabilisce un legame rigoroso tra la dimensione di copertura metrica del supporto di una misura e l'ordine degli osservabili richiesto per il recupero univoco. Ciò funge da strumento teorico fondamentale per comprendere l'identificabilità nell'OT non euclideo.
• Utilità Pratica: Il framework offre un approccio "sintonizzabile" in cui i praticanti possono regolare l'ordine degli osservabili ($n$) per bilanciare il costo computazionale con la precisione del limite di distanza.
• Scalabilità: Il modello discreto consente un'implementazione efficiente su grandi dataset, con evidenze empiriche che suggeriscono una scalabilità lineare nel numero di proiezioni/ancoraggi, rendendolo adatto a dataset massivi dove l'OT esatto è intrattabile.
• Robustezza: Gli esperimenti suggeriscono che le distanze OW possono offrire una robustezza superiore al rumore rispetto alle distanze di Wasserstein classiche, rendendole adatte ad applicazioni su dati reali.

Gli autori posizionano questo lavoro come un passo fondamentale, notando che, sebbene gli attuali esperimenti numerici siano prove di concetto, il framework apre la strada a future ricerche sulla convergenza del campionamento, sull'equivalenza bi-Lipschitziana per $p \neq 1$ e sull'integrazione di osservabili apprendibili nelle pipeline di deep learning.