Complete Diagrammatic Axiomatisations of Relative Entropy

Dit artikel biedt volledige axiomatische beschrijvingen van Kullback-Leibler- en Rényi-divergenties binnen een categorisch raamwerk, waarbij deze divergenties worden geanalyseerd als kwantitatieve verrijkingen van categorieën van stochastische matrices onder zowel de Kronecker-product- als de direct-sum-monoidale structuren.

De kern

Stel je voor dat je twee verschillende recepten voor een taart hebt. De ene is gemaakt door je oma, de andere door een beroemde chef-kok. Als je ze proeft, zijn ze misschien heel erg op elkaar, maar niet exact hetzelfde. De ene is misschien net iets zoeter, de andere net iets luchtiger.

In de wereld van computers en wiskunde proberen we vaak te zeggen of twee programma's of twee manieren van denken "hetzelfde" zijn. Maar bij dingen die met kans en toeval te maken hebben (zoals kunstmatige intelligentie of voorspellingen), is "hetzelfde zijn" vaak te streng. Het is nuttiger om te weten: hoe ver liggen ze van elkaar?

Dit is waar dit paper over gaat. De auteurs, Ralph Sarkis en Fabio Zanasi, hebben een nieuwe manier bedacht om die "afstand" tussen waarschijnlijkheden te meten en te begrijpen, met behulp van een heel visueel taalgebruik.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Het Probleem: De "Afstand" meten

Stel je voor dat je twee kaarten hebt die de weersvoorspelling voor een stad tonen. Kaart A zegt: "70% kans op regen". Kaart B zegt: "65% kans op regen".
Zijn ze hetzelfde? Nee. Maar hoe groot is het verschil?
In de wiskunde noemen ze dit Relative Entropy (of Kullback-Leibler divergentie). Het is een maatstaf voor hoe "ver" twee waarschijnlijkheden van elkaar staan.

Het probleem is dat dit heel lastig te berekenen is als je complexe systemen hebt (zoals een heel netwerk van kaarten). De auteurs zeggen: "Laten we dit niet alleen met formules doen, maar met tekeningen."

2. De Oplossing: Tekeningen als Wiskunde (String Diagrams)

Stel je voor dat je wiskundige formules niet schrijft als $A + B = C$, maar als een tekening met kabeltjes en blokken.

• Een blok is een handeling (bijvoorbeeld: "gooi een munt").
• Een kabeltje is de informatie die erdoorheen gaat.
• Als je twee blokken naast elkaar zet, doe je twee dingen tegelijk.
• Als je ze onder elkaar zet, doe je het eerst het ene, dan het andere.

De auteurs hebben een systeem bedacht waarbij je met deze tekeningen kunt "rekenen". Maar ze hebben iets extra's toegevoegd: afstand.
In hun tekeningen staat niet alleen geschreven wat er gebeurt, maar ook hoe ver het resultaat afwijkt van een ander resultaat. Het is alsof je op je tekening een meetlint hangt dat aangeeft hoe "verkeerd" een tekening is vergeleken met een andere.

3. De Twee Manieren om te Bouwen

Het paper beschrijft twee manieren om deze blokken en kabeltjes samen te voegen, net zoals je Lego kunt bouwen:

• Manier A: De "Kubus" (Kronecker-product)
  Stel je voor dat je twee Lego-kasten naast elkaar zet en ze samenvoegt tot één grote, complexe kast. Dit is handig voor systemen waar alles met elkaar verbonden is, zoals een netwerk van sensoren. De auteurs hebben bewezen dat je met hun tekenregels precies kunt voorspellen hoe de "afstand" (de fout) zich gedraagt in zo'n grote kast.

  • Vergelijking: Het is alsof je twee verschillende muzieknummers samenvoegt tot één symfonie. Je kunt nu precies berekenen hoe veel de nieuwe symfonie afwijkt van het origineel.

• Manier B: De "Lijst" (Directe Som)
  Stel je voor dat je twee Lego-kasten naast elkaar zet, maar ze raken elkaar niet. Ze zijn twee aparte opties. Dit is handig als je kiest tussen verschillende scenario's (bijvoorbeeld: "Of het regent, of het zonnig is").
  Ook hier hebben ze regels bedacht om de "afstand" tussen deze opties te berekenen.

4. De Magische Regel: De "Kettingreactie" (Chain Rule)

Het meest interessante deel van hun werk is een regel die ze de Chain Rule noemen.
Stel je voor dat je een lange ketting hebt. Als je wilt weten hoe ver de hele ketting uitgerekt is, hoef je niet de hele ketting in één keer te meten. Je kunt kijken naar elk klein schakeltje afzonderlijk.

• Als schakel 1 een beetje uitrekt...
• En schakel 2 een beetje uitrekt...
• Dan weet je precies hoeveel de hele ketting uitrekt.

De auteurs hebben bewezen dat je dit ook kunt doen met hun tekenregels voor waarschijnlijkheden. Als je weet hoe ver de losse onderdelen van een systeem van elkaar staan, kun je precies berekenen hoe ver het hele systeem van elkaar staat. Dit maakt het mogelijk om enorme, complexe systemen op te breken in kleine, beheersbare stukjes.

5. Waarom is dit belangrijk?

Vroeger was het heel moeilijk om wiskundig te bewijzen dat twee complexe computerprogramma's (die toeval gebruiken) "bijna hetzelfde" werken.
Met dit nieuwe systeem kunnen programmeurs en wiskundigen nu:

1. Fouten meten: Ze kunnen precies zeggen hoe slecht een AI-model presteert vergeleken met de realiteit.
2. Veiligheid: Ze kunnen bewijzen dat een systeem niet te ver afwijkt van een veilig model (belangrijk voor bijvoorbeeld zelfrijdende auto's).
3. Privacy: Ze kunnen meten hoeveel informatie er "lekkt" in een systeem (een concept dat belangrijk is voor privacywetgeving).

Samenvatting in één zin

De auteurs hebben een nieuwe "taal van tekeningen" bedacht waarmee we niet alleen kunnen zien wat een computer doet, maar ook precies kunnen meten hoe ver die computer van het juiste antwoord afwijkt, zelfs in de meest ingewikkelde systemen.

Het is alsof ze een meetlat hebben uitgevonden die je kunt vastmaken aan elke tekening van een computerprogramma, zodat je direct ziet hoe "verkeerd" of "ver" die tekening is van de waarheid.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Complete Diagrammatic Axiomatisations of Relative Entropy" van Ralph Sarkis en Fabio Zanasi, geschreven in het Nederlands.

Titel: Complete Diagrammatische Axiomatisaties van Relatieve Entropie

Auteurs: Ralph Sarkis en Fabio Zanasi (University College London)
Context: MFPS XLII (Mathematical Foundations of Programming Semantics)

---

1. Probleemstelling

In de traditionele semantiek van programmeertalen wordt vaak gekeken naar equivalentie: produceren twee programma's identieke output? Bij probabilistische programma's (zoals in machine learning en statistische inferentie) is deze binaire benadering echter vaak te grof. Het is nuttiger om de afstand tussen het gedrag van twee programma's te meten.

Hoewel er reeds kwantitatieve algebraïsche theorieën bestaan voor afstanden zoals de Kantorovich-metriek en de totale variatieafstand, ontbreekt er een volledige axiomatische theorie voor relatieve entropie (Kullback-Leibler divergentie en Rényi-divergenties). Deze maten zijn fundamenteel in statistiek, informatietheorie en differentieel privacy, maar hun categorische karakterisering via stringdiagrammen was tot nu toe niet volledig uitgewerkt.

Het specifieke probleem is het vinden van een complete axiomatisatie voor relatieve entropie binnen de context van stochastische matrices, gezien als objecten in een symmetrisch monoidale categorie (SMC). Er zijn twee natuurlijke monoidale structuren op stochastische matrices die beide relevant zijn, maar die verschillende algebraïsche eigenschappen hebben:

1. Het Kronecker-product ($\otimes$), relevant voor synthetische probabiliteitstheorie en Bayesiaanse netwerken.
2. De directe som ($\oplus$), relevant voor convexe verzamelingen en barycentrische algebra.

2. Methodologie

De auteurs hanteren een categorische benadering waarbij relatieve entropie wordt gezien als een kwantitatieve verrijking (quantitative enrichment) van categorieën van stochastische matrices.

• Kader: Ze gebruiken de theorie van kwantitatieve monoidale algebra, waarbij redenering plaatsvindt via stringdiagrammen.
• Verrijking: De hom-sets van de categorieën worden verrijkt met waarden in de quantale $[0, \infty]$, wat de afstand (divergentie) tussen morfismen (stochastische matrices) voorstelt.
• Innovatie in Logica: Een cruciale stap is de uitbreiding van het bestaande kader van kwantitatieve equaties (waarbij $s =_\varepsilon t$ betekent dat de afstand $\le \varepsilon$ is) naar kwantitatieve implicaties.
  • De auteurs introduceren axioma's van de vorm $\Gamma \Rightarrow \phi$, waarbij $\Gamma$ een set van kwantitatieve vergelijkingen (premises) is en $\phi$ de conclusie.
  • Dit is noodzakelijk om de kettingregel (chain rule) van relatieve entropie te modelleren. De kettingregel stelt dat de divergentie van gezamenlijke verdelingen kan worden afgeleid uit de divergentie van voorwaardelijke verdelingen. Dit is een implicatie: als de afstanden tussen de voorwaardelijke verdelingen begrensd zijn, dan is de afstand tussen de gezamenlijke verdelingen ook begrensd.
• Structuren: Ze definiëren twee specifieke verrijkte categorieën:
  • $\mathbf{BStoch}^\otimes_{kl}$: Stochastische matrices met dimensies $2^n$ (voor het Kronecker-product).
  • $\mathbf{FStoch}^\oplus_{kl}$: Alle stochastische matrices (voor de directe som).

3. Belangrijkste Bijdragen

1. Complete Axiomatisaties voor KL-divergentie:
   De auteurs presenteren twee kwantitatieve theorieën, $\mathcal{T}_{KL}^\otimes$ en $\mathcal{T}_{KL}^\oplus$, die respectievelijk de categorieën $\mathbf{BStoch}^\otimes_{kl}$ en $\mathbf{FStoch}^\oplus_{kl}$ volledig axiomatiseren.

   • De theorieën bevatten de bestaande axioma's voor stochastische matrices (uit eerdere werken [52, 23]) aangevuld met nieuwe kwantitatieve implicaties.
   • De kern van de axiomatisatie vormen de regels Chain en Ifmax (voor $\otimes$) en Chain en Parmax (voor $\oplus$). Deze regels formaliseren de kettingregel en de manier waarop divergentie zich gedraagt onder het nemen van maximums of parallelle composities.

2. Generalisatie naar Rényi-divergenties:
   De methode wordt uitgebreid naar de volledige familie van Rényi-divergenties ($\alpha \in [0, \infty]$), waarbij KL-divergentie het speciale geval is voor $\alpha = 1$.

   • Ze definiëren een functie $C_\alpha$ die de kettingregel voor Rényi-divergenties kwantificeert.
   • De axioma's worden aangepast om deze functie $C_\alpha$ te gebruiken in plaats van de lineaire combinatie die specifiek is voor KL-divergentie.

3. Volledigheidsbewijzen:
   De auteurs bewijzen dat de syntactische categorieën (gegenereerd door hun stringdiagramtheorieën) isomorf zijn met de semantische categorieën van stochastische matrices verrijkt met de respectievelijke divergenties.

   • Dit betekent dat elke kwantitatieve eigenschap die waar is voor de stochastische matrices, ook afleidbaar is binnen hun diagrammatische calculus.
   • De bewijzen maken gebruik van inductie op de structuur van de matrices en de eigenschappen van de kettingregel.

4. Resultaten

• Isometrie: De functor die de stringdiagrammen afbeeldt op de stochastische matrices is een lokale isometrie. Dit betekent dat de afstand tussen twee diagrammen in de syntactische categorie exact overeenkomt met de KL- (of Rényi-) divergentie tussen de corresponderende stochastische matrices.
• Uniciteit: De axioma's karakteriseren de divergenties uniek. Er is geen andere verrijking die voldoet aan deze axioma's en de kettingregel.
• Formele Kader: De introductie van implicaties in kwantitatieve monoidale theorieën biedt een krachtiger kader dan eerdere modellen die zich beperkten tot equaties. Dit maakt het mogelijk om theorieën te modelleren die afhankelijk zijn van voorwaarden (zoals de kettingregel), wat eerder niet mogelijk was binnen het standaard kader van [45].

5. Betekenis en Toekomstperspectief

• Synthetische Bewijzen: De resultaten maken het mogelijk om wiskundige eigenschappen van probabilistische modellen (zoals convergentie of foutgrenzen in Bayesiaanse inferentie) synthetisch te bewijzen met behulp van diagrammatische redenering, zonder terug te vallen op complexe berekeningen met matrices.
• Verbinding met Bestaand Werk: Het werk verenigt eerdere diagrammatische axiomatisaties van probabilistische computation (zoals [20]) met het formele kader van kwantitatieve algebra.
• Toepassingen: De theorie is direct toepasbaar op gebieden als differentieel privacy, machine learning (variational inference) en het analyseren van probabilistische programmeertalen.
• Toekomst: De auteurs wijzen op de mogelijkheid om deze resultaten uit te breiden naar kwantumprocessen (quantum relative entropy), gezien de sterke adoptie van stringdiagrammen in de kwantuminformatie. Ook wordt verwezen naar het uitbreiden van de theorie naar niet-discrete ruimtes.

Kortom, dit artikel vult een cruciale lacune in de categorische probabiliteitstheorie door de eerste complete, diagrammatische en kwantitatieve axiomatisatie van relatieve entropie te leveren, zowel voor het Kronecker-product als voor de directe som, en breidt het theoretische kader uit met implicaties.