Complete Diagrammatic Axiomatisations of Relative Entropy

Questo lavoro presenta un'assiomatizzazione completa delle divergenze di Kullback-Leibler e di Rényi, viste come arricchimenti quantitativi di categorie di matrici stocastiche, utilizzando un linguaggio grafico di diagrammi a stringa all'interno di due strutture monoidali naturali.

L'essenziale

Immagina di essere un chef che deve preparare due piatti diversi. Se i due piatti sono identici, non c'è nulla da dire. Ma se sono simili ma non uguali (uno è un po' più salato, l'altro un po' più dolce), come misuri esattamente quanto sono diversi?

Nel mondo dell'informatica e della statistica, questo è un problema enorme. Quando i computer prendono decisioni basate sul caso (come quando un'auto a guida autonoma decide se frenare o un algoritmo di raccomandazione sceglie un film), non ci interessa solo se due programmi fanno la stessa cosa, ma quanto si discostano l'uno dall'altro.

Ecco di cosa parla questo articolo, tradotto in una storia semplice:

1. Il Problema: Misurare la "Differenza"

Gli scienziati usano una formula chiamata Divergenza di Kullback-Leibler (o KL) per misurare questa differenza. È come un "metro" speciale per le probabilità.
Il problema è che finora non avevamo un modo semplice e universale per spiegare come funziona questo metro usando le regole della logica. Era come avere un'auto velocissima (il calcolo della divergenza) ma senza il manuale di istruzioni per costruirne una nuova.

2. La Soluzione: I "Disegni che Parlano" (String Diagrams)

Gli autori, Ralph e Fabio, hanno deciso di usare un linguaggio visivo chiamato String Diagrams (Diagrammi a Stringa).
Immagina di disegnare dei circuiti elettrici o dei tubi dell'acqua:

• Le linee sono i dati che fluiscono.
• I blocchi sono le operazioni che fanno qualcosa ai dati.
• Invece di scrivere equazioni matematiche complicate, puoi "disegnare" il processo.

L'obiettivo del paper è creare un manuale di istruzioni completo (una "assiomatizzazione") per questi disegni, in modo che se due disegni sono diversi, possiamo calcolare esattamente di quanto lo sono, usando solo le regole del disegno.

3. I Due Modi di Costruire il Mondo

Gli scienziati hanno scoperto che ci sono due modi principali per combinare questi "tubi" di dati, e ognuno richiede regole diverse:

• Il Metodo "Crociera" (Kronecker Product): Immagina di prendere due carte da gioco e incollarle insieme per formare un mazzo gigante. È come se ogni scelta che fai si moltiplicasse per tutte le altre scelte possibili. Questo è utile per le reti neurali e le catene causali.
• Il Metodo "Scelta" (Direct Sum): Immagina di avere due scatole separate. O scegli la scatola A o scegli la scatola B. È come un bivio nella strada. Questo è utile per capire la probabilità come una "scelta" o un'incertezza.

Il paper dice: "Abbiamo trovato le regole perfette per entrambi i metodi!".

4. La Magia della "Regola della Catena"

Il segreto del loro successo è una regola chiamata Chain Rule (Regola della Catena).
Immagina di voler misurare quanto due viaggi lunghi sono diversi. Invece di misurare tutto il viaggio in un colpo solo, puoi spezzarlo in tappe:

1. Quanto è diversa la prima tappa?
2. Quanto è diversa la seconda tappa?
3. Quanto è diversa la terza tappa?

La regola della catena dice: "Se sai quanto sono diverse le singole tappe, puoi calcolare esattamente quanto è diverso l'intero viaggio".
Gli autori hanno tradotto questa regola in un "disegno": se i disegni delle singole tappe sono simili, allora il disegno del viaggio intero è simile, e il loro sistema matematico ti dice esattamente di quanto.

5. Perché è Importante?

Prima di questo lavoro, se volevi usare questo "metro" (la divergenza KL) in un contesto complesso, dovevi fare calcoli lunghi e complicati.
Ora, grazie a questo paper:

• È come avere un Lego matematico: Puoi costruire sistemi complessi di probabilità e sapere subito quanto sono diversi l'uno dall'altro, semplicemente seguendo le regole dei disegni.
• È più sicuro: Aiuta a costruire intelligenze artificiali più affidabili, perché possiamo misurare con precisione quanto un modello si allontana dalla realtà.
• È universale: Funziona non solo per la divergenza KL, ma per tutta una famiglia di "metriche" chiamate Divergenze di Rényi (che sono come versioni diverse dello stesso metro, utili per scopi diversi).

In Sintesi

Gli autori hanno scritto il manuale di istruzioni definitivo per misurare le differenze tra sistemi probabilistici usando un linguaggio di disegni. Hanno dimostrato che, se segui le loro regole (come la regola della catena), puoi calcolare la distanza tra due mondi di probabilità in modo perfetto e completo, senza perdere nulla. È un passo avanti enorme per rendere l'intelligenza artificiale e la statistica più trasparenti e comprensibili.

Sommario tecnico

Ecco un riassunto tecnico dettagliato del paper "Complete Diagrammatic Axiomatisations of Relative Entropy" di Ralph Sarkis e Fabio Zanasi, presentato alla conferenza MFPS XLII.

1. Il Problema

La divergenza di entropia relativa (in particolare la divergenza di Kullback-Leibler o KL, e più in generale le divergenze di Rényi) è una classe fondamentale di distanze tra distribuzioni di probabilità, con applicazioni cruciali nell'inferenza statistica, nell'apprendimento automatico e nella privacy differenziale.
Nonostante l'importanza di queste misure, mancava una teoria algebrica quantitativa completa per la divergenza KL e le entropie relative. Le teorie algebriche quantitative esistenti (come quelle per la distanza di variazione totale o la metrica di Kantorovich) si basano su equazioni quantitative del tipo $s =_\varepsilon t$, che esprimono che la distanza tra due termini è al massimo $\varepsilon$. Tuttavia, la divergenza KL possiede proprietà strutturali (come la regola della catena) che non possono essere catturate semplicemente da equazioni quantitative dirette, ma richiedono relazioni implicazionali più complesse.

2. Metodologia

Gli autori adottano una prospettiva categorica, trattando la divergenza relativa come un arricchimento quantitativo di categorie di matrici stocastiche. La metodologia si articola nei seguenti punti:

• Struttura Categorieale: Si studiano due strutture monoidali naturali sulle matrici stocastiche:
  1. Il prodotto di Kronecker ($\otimes$), che definisce la categoria $FStoch_\otimes$ (rilevante per la teoria sintetica della probabilità e le reti bayesiane).
  2. La somma diretta ($\oplus$), che definisce la categoria $FStoch_\oplus$ (rilevante per gli insiemi convessi e gli effetti monadici della casualità).
• Linguaggio dei Diagrammi a Stringa: L'analisi viene condotta nel linguaggio dei diagrammi a stringa (string diagrams) all'interno del quadro dell'algebra monoidale quantitativa. Questo permette di ragionare su sistemi multidimensionali (matrici stocastiche) piuttosto che solo su distribuzioni unidimensionali.
• Estensione delle Teorie Quantitative: Il contributo metodologico principale è l'estensione delle "teorie monoidali quantitative" (introdotte in lavori precedenti come [41]) per includere assiomi implicazionali. Invece di limitarsi a equazioni quantitative, gli autori introducono regole di inferenza della forma:
  $$\Gamma \Rightarrow \varphi$$
  dove $\Gamma$ è un insieme di equazioni quantitative (premesse) e $\varphi$ è una conclusione quantitativa. Questo è essenziale per formalizzare la regola della catena (chain rule), che lega la divergenza di una distribuzione congiunta alle divergenze delle sue distribuzioni condizionate.
• Semantica Arricchita: Si utilizzano categorie arricchite su $VRel$ (relazioni a valori in un quantale, specificamente $[0, \infty]$ con l'ordine opposto), dove i morfismi sono mappati da funzioni non espansive rispetto alla distanza.

3. Contributi Chiave

A. Assiomatizzazione della Divergenza KL

Gli autori forniscono due teorie complete per la divergenza KL:

1. Per $BStoch_\otimes$ (Prodotto di Kronecker): Viene definita la teoria $\mathcal{T}_{KL}^\otimes$. Include assiomi per la struttura algebrica delle matrici stocastiche (già noti) più due nuove regole implicazionali:
   • Chain$_\otimes$: Formalizza la regola della catena per il prodotto di Kronecker. Se le distanze tra le distribuzioni condizionate sono limitate da $\varepsilon$ e $\delta$, allora la distanza tra le distribuzioni congiunte è limitata da una funzione specifica di $\varepsilon, \delta$ e dei parametri di probabilità.
   • Ifmax: Gestisce il comportamento della divergenza rispetto alla scelta condizionale (gate "if"), mostrando che la divergenza è il massimo delle divergenze dei rami.
2. Per $FStoch_\oplus$ (Somma Diretta): Viene definita la teoria $\mathcal{T}_{KL}^\oplus$ con regole analoghe (Chain$_\oplus$ e Parmax) adattate alla struttura della somma diretta.

B. Completezza

Il risultato principale è la dimostrazione che queste teorie sono complete.

• Le categorie sintetiche generate liberamente dalle teorie $\mathcal{T}_{KL}^\otimes$ e $\mathcal{T}_{KL}^\oplus$ sono isomorfe, come categorie arricchite, alle categorie concrete $BStoch_\otimes^{kl}$ e $FStoch_\oplus^{kl}$ (dove i morfismi sono matrici stocastiche e la distanza è la divergenza KL definita colonna per colonna).
• L'isomorfismo è una isometria locale, il che significa che la distanza calcolata sinteticamente nei diagrammi corrisponde esattamente alla divergenza KL calcolata sulle matrici.

C. Generalizzazione alle Divergenze di Rényi

Gli autori dimostrano che il metodo si estende alle divergenze di Rényi di ordine arbitrario $\alpha \in [0, \infty]$.

• La divergenza KL è il caso speciale per $\alpha = 1$.
• Vengono introdotte funzioni di combinazione $C_\alpha$ che generalizzano la formula della regola della catena per qualsiasi $\alpha$.
• Le teorie $\mathcal{T}_{R^\otimes_\alpha}$ e $\mathcal{T}_{R^\oplus_\alpha}$ sono presentate e dimostrate complete per le rispettive categorie arricchite con le divergenze di Rényi.

4. Risultati Tecnici

• Regole di Inferenza: Le regole implicazionali (Chain e Ifmax/Parmax) sono sufficienti a derivare qualsiasi relazione di distanza valida tra termini nel linguaggio dei diagrammi a stringa.
• Gestione dei Casi Limite: Le dimostrazioni di completezza gestiscono rigorosamente i casi in cui le probabilità sono zero o le divergenze sono infinite, sfruttando le convenzioni standard ($0 \cdot \infty = 0$).
• Induzione Strutturale: Le prove di completezza procedono per induzione sulla struttura dei termini (o sulla dimensione degli spazi), decomponendo le matrici stocastiche in componenti più semplici (distribuzioni condizionate) e applicando le regole implicazionali per ricostruire la distanza globale.

5. Significato e Implicazioni

• Colmare un Gap Teorico: Questo lavoro colma una lacuna significativa nella letteratura sull'algebra quantitativa, fornendo la prima caratterizzazione assiomatica completa della divergenza KL e di Rényi in un contesto diagrammatico.
• Nuovo Strumento per il Ragionamento: L'introduzione di assiomi implicazionali nelle teorie monoidali quantitative apre nuove possibilità per il ragionamento su sistemi probabilistici complessi, permettendo di derivare proprietà di performance di modelli (es. in apprendimento automatico) direttamente attraverso manipolazioni di diagrammi.
• Fondamenti per la Probabilità Sintetica: Le teorie ottenute offrono una base sintetica rigorosa per la probabilità, permettendo di trattare la divergenza come una proprietà intrinseca della struttura categoriale, piuttosto che come una funzione esterna.
• Estensibilità: Il framework è progettato per essere esteso ad altri contesti, inclusi spazi non discreti e, potenzialmente, a processi quantistici (dove l'entropia relativa quantistica gioca un ruolo chiave), sfruttando l'ampio uso dei diagrammi a stringa nella teoria quantistica.

In sintesi, il paper stabilisce un ponte solido tra la teoria dell'informazione classica (divergenze) e l'algebra categoriale moderna, fornendo un calcolo completo e manipolabile per le distanze tra processi stocastici.