Structure-aware divergences for comparing probability distributions

1. Il Problema

Molti sistemi nelle scienze naturali e sociali sono descritti da distribuzioni di probabilità su elementi che possiedono relazioni intrinseche (es. occupazioni con competenze condivise, specie con tratti funzionali simili).
Le misure standard della teoria dell'informazione, come l'entropia di Shannon e le divergenze $f$ (inclusa la divergenza di Kullback-Leibler, KL), trattano gli elementi come intercambiabili e sono "cieche" alla struttura di similarità sottostante. Questo approccio ignora informazioni cruciali: due distribuzioni possono essere considerate identiche dalle metriche standard, anche se gli elementi ad alta probabilità in una sono molto diversi tra loro rispetto all'altra.
Esistono già misure di diversità "consapevoli della struttura" (come l'indice di Rao o le entropie di Leinster e Cobbold), ma manca un quadro coerente di divergenze (misure di dissimilarità tra distribuzioni) che incorporino tale struttura, mantenendo le proprietà geometriche vantaggiose della KL.

2. Metodologia

Gli autori introducono una nuova famiglia di divergenze consapevoli della struttura (Structure-aware divergences), costruite come divergenze di Bregman di entropie consapevoli della struttura.

• Entropia Consapevole della Struttura ($H^Z_\alpha$):
  Partendo dalle entropie di Havrda-Charvát (HC), generalizzate da Ricotta e Szeidl, definiscono l'entropia di ordine $\alpha$ per una distribuzione $p$ su un insieme $X$ con una matrice di similarità $Z$:
  $$H^Z_\alpha(p) = \frac{1}{\alpha - 1} \left( 1 - p^\top (Zp)^{\alpha-1} \right) \quad (\text{per } \alpha \neq 1)$$
  dove $Z$ è una matrice di similarità (simmetrica, valori in $[0,1]$, diagonale unitaria). Per $\alpha=1$ si recupera la forma logaritmica. Questa entropia misura la "sorpresa" media, tenendo conto che elementi simili contribuiscono meno alla diversità.

• Divergenza Consapevole della Struttura ($d^Z_\alpha$):
  Sfruttando la connessione geometrica tra entropia e divergenza KL (la KL è la divergenza di Bregman dell'entropia negativa), definiscono la nuova divergenza come la divergenza di Bregman generata da $-H^Z_\alpha$.
  Affinché ciò sia possibile, $-H^Z_\alpha$ deve essere strettamente convessa. Gli autori dimostrano che $H^Z_\alpha$ è strettamente concava (e quindi $-H^Z_\alpha$ strettamente convessa) nell'interno del simplesso di probabilità se $\alpha \ge 2$ e $Z$ è una matrice definita positiva ($Z \succ 0$).
  La formula esplicita per $\alpha \ge 2$ è:
  $$d^Z_\alpha(p || q) = \frac{1}{\alpha - 1} p^\top \left( (Zp)^{\alpha-1} - (Zq)^{\alpha-1} \right) - q^\top \text{diag}\left((Zq)^{\alpha-2}\right) Z (p - q)$$

• Costruzione di $Z$:
  Per garantire che $Z$ sia definita positiva, gli autori suggeriscono di derivarla da spazi metrici di "tipo negativo" (es. distanze euclidee, alberi pesati, grafi con resistenza efficace) tramite trasformazioni esponenziali $Z_{ij} = \exp(-\tau D_{ij})$. Se una matrice di similarità non è definita positiva, può essere approssimata tramite ottimizzazione convessa.

• Informazione di Bregman:
  Viene definita l'informazione di Bregman come generalizzazione della varianza e dell'informazione mutua, utile per il clustering. Per una collezione di distribuzioni, è la divergenza attesa dalla loro media.

3. Contributi Chiave

1. Nuova Famiglia di Divergenze: Introduzione di una classe parametrica di divergenze che generalizzano la KL e la distanza di Mahalanobis (caso $\alpha=2$), incorporando esplicitamente la similarità tra elementi.
2. Proprietà Geometriche: Dimostrazione che queste divergenze ereditano le proprietà vantaggiose delle divergenze di Bregman, rendendole ideali per compiti di clustering, proiezioni e ottimizzazione.
3. Efficienza Computazionale: A differenza delle distanze di trasporto ottimo (OT) come la metrica di Wasserstein, che richiedono la risoluzione di problemi di ottimizzazione costosi, le nuove divergenze hanno una forma chiusa, permettendo calcoli estremamente rapidi.
4. Ricostruzione di Pattern: Dimostrazione che queste metriche riescono a recuperare pattern nascosti (planted patterns) in dati sottocampionati, dove i metodi tradizionali falliscono perché non distinguono elementi strutturalmente diversi.

4. Risultati Sperimentali e Applicazioni

• Esperimenti Sintetici:

  • Clustering: In un task di clustering su dati sintetici con gruppi strutturati, la divergenza consapevole della struttura ha recuperato la partizione corretta anche con pochi campioni ($m=2$), mentre i metodi ciechi alla struttura (usando $Z=I$) non sono riusciti a distinguere i gruppi.
  • Velocità: Il calcolo della divergenza (Jensen-Bregman) è ordini di grandezza più veloce rispetto al calcolo della distanza di Wasserstein-1, pur mantenendo una forte correlazione con essa (Pearson $r \approx 0.92$).

• Geografia Economica (Occupazioni in Inghilterra e Galles):

  • Applicando il metodo ai dati del censimento 2021, gli autori hanno analizzato la diversità e la rappresentatività delle basi di capacità occupazionali dei Local Authorities (LA).
  • Definizioni di Relazione: Hanno confrontato diverse matrici di similarità: nessuna, similarità basata sulle competenze (skills), similarità basata sulla co-localizzazione (co-location) e gerarchia.
  • Risultati: Le diverse definizioni di similarità portano a regionalizzazioni qualitativamente diverse. Ad esempio, la similarità basata sulle competenze tende a raggruppare aree con forza lavoro blu-collar simile, mentre la co-localizzazione evidenzia regioni specializzate in settori specifici (es. agricoltura vs servizi). Questo dimostra che la struttura influenza profondamente l'interpretazione della diversità economica.

• Ecologia (Beta-diversità nel Ghiacciaio Rutor):

  • Analisi della diversità funzionale delle comunità vegetali in diverse fasi di successione primaria.
  • Utilizzando le caratteristiche funzionali (traits) delle piante per costruire $Z$, il metodo riproduce i risultati ottenuti precedentemente con costosi metodi di trasporto ottimo (OT): le fasi tardive mostrano una beta-diversità funzionale molto più bassa rispetto alla fase iniziale, suggerendo che, sebbene le specie cambino, la composizione funzionale rimane stabile.
  • Il metodo offre la stessa interpretazione biologica dell'OT ma con costi computazionali trascurabili.

5. Significato e Implicazioni

Questo lavoro colma un divario fondamentale tra la teoria della diversità strutturata e la teoria dell'informazione classica.

• Versatilità: Offre un quadro unificato per analizzare distribuzioni in contesti dove la similarità tra elementi è cruciale (economia, ecologia, scienze sociali).
• Scalabilità: Risolve il collo di bottiglia computazionale associato al trasporto ottimo, rendendo l'analisi di grandi dataset strutturati (es. abbondanza di specie, dati censuari) fattibile in tempo reale.
• Interpretabilità: Permette di modellare diverse nozioni di "relazione" (es. competenze vs co-localizzazione) ottenendo risultati qualitativamente diversi, fornendo agli analisti uno strumento flessibile per esplorare la struttura dei dati senza perdere informazioni critiche.

In sintesi, gli autori propongono uno strumento matematico potente che combina la rigore geometrico della divergenza di KL con la ricchezza descrittiva delle metriche di similarità, superando i limiti computazionali e concettuali degli approcci precedenti.