Complete Diagrammatic Axiomatisations of Relative Entropy

Dieser Artikel liefert vollständige diagrammatische Axiomatisierungen der Kullback-Leibler-Divergenz und allgemeiner Rényi-Divergenzen beliebiger Ordnung im Rahmen der quantitativen monoidalen Algebra, indem er relative Entropie aus kategorientheoretischer Sicht als quantitative Erweiterung von Kategorien stochastischer Matrizen unter den monoidalen Strukturen des Kronecker-Produkts und der direkten Summe untersucht.

Das Wesentliche

Der große Vergleich: Wie man „Fehler" in Zufallsprozessen misst

Stellen Sie sich vor, Sie haben zwei verschiedene Rezepte für einen Kuchen. Beide versprechen, einen leckeren Schokoladenkuchen zu backen. Aber Rezept A ist etwas ungenau, und Rezept B ist noch ungenauer. Die Frage ist: Wie unterschiedlich sind die beiden Rezepte wirklich?

In der Welt der Wahrscheinlichkeit und des maschinellen Lernens nennen wir diese Unterschiede oft „Entfernungen". Eine besonders wichtige Art, diese Entfernung zu messen, ist die relative Entropie (oder Kullback-Leibler-Divergenz). Sie sagt uns: „Wenn ich dachte, ich würde Rezept A verwenden, aber stattdessen Rezept B nutze, wie sehr werde ich enttäuscht sein?"

Bisher gab es für diese Messung keine einfache, universelle „Rechenanleitung" (Axiome), mit der man alle möglichen Fälle durchgehen konnte. Genau das haben die Autoren Ralph Sarkis und Fabio Zanasi in diesem Papier geschafft.

Die Hauptakteure: Zwei verschiedene Welten

Die Autoren betrachten zwei verschiedene Arten, wie man diese Zufalls-Rezepte (stochastische Matrizen) kombinieren kann. Man kann sich das wie zwei verschiedene Spielregeln vorstellen:

1. Die Welt der „Kombinationen" (Kronecker-Produkt):

   • Analogie: Stellen Sie sich vor, Sie haben zwei separate Würfel. Wenn Sie sie kombinieren, werfen Sie beide gleichzeitig. Das Ergebnis ist ein riesiges Paar von Zahlen (z. B. „3 und 5").
   • Bedeutung: Dies ist die Standard-Welt für komplexe Systeme, wie sie in neuronalen Netzen oder bei der Analyse von Ursache und Wirkung vorkommen. Hier werden Systeme nebeneinander gestellt und multipliziert.

2. Die Welt der „Wahlmöglichkeiten" (Direkte Summe):

   • Analogie: Stellen Sie sich vor, Sie stehen an einer Kreuzung. Sie können entweder nach links (Rezept A) oder nach rechts (Rezept B) gehen. Sie tun beides nicht gleichzeitig, sondern wählen einen Pfad.
   • Bedeutung: Dies ist die Welt der Wahrscheinlichkeiten, bei der man zwischen verschiedenen Szenarien wählt (wie ein Münzwurf: Kopf oder Zahl).

Das Problem: Die alte Sprache reichte nicht

Bisher konnten Wissenschaftler mit einer Art „Bildersprache" (String-Diagramme) beschreiben, wie diese Rezepte funktionieren. Aber diese Bilder konnten nur sagen: „Rezept A ist genau wie Rezept B" oder „Rezept A ist nicht wie Rezept B".

Sie konnten aber nicht sagen: „Rezept A ist etwas anders als Rezept B, und zwar genau so viel wie eine Distanz von 0,5."
Es fehlte eine Sprache, die Abstände (Distanzen) in die Bilder einbauen konnte.

Die Lösung: Eine neue Sprache mit „Wenn-dann"-Regeln

Die Autoren haben eine neue Art von Sprache entwickelt, die sie quantitative Axiome nennen.

• Die Bilder (String-Diagramme): Stellen Sie sich diese wie Schaltungsschemata oder Flussdiagramme vor. Sie zeigen, wie Informationen durch ein System fließen.
• Die neuen Regeln (Implikationen): Das ist der geniale Teil. Früher sagten die Regeln nur: „Wenn du diesen Schritt machst, passiert das."
  Die neuen Regeln sagen: „Wenn der Fehler in Schritt A kleiner als 0,1 ist UND der Fehler in Schritt B kleiner als 0,2 ist, DANN ist der Gesamtfehler in Schritt C höchstens 0,3."

Das ist wie eine Kette von Domino-Steinen, bei der man nicht nur weiß, dass sie umfallen, sondern auch genau messen kann, wie stark jeder Stein beim Umfallen wackelt.

Die große Entdeckung: Die „Kettenregel"

Das Herzstück ihrer Arbeit ist die Kettenregel (Chain Rule).
Stellen Sie sich vor, Sie wollen wissen, wie unterschiedlich zwei lange Geschichten sind.

• Die alte Methode: Man vergleicht die ganze Geschichte auf einmal. Das ist schwer.
• Die Methode der Autoren: Man zerlegt die Geschichte in Sätze. Man vergleicht den ersten Satz, dann den zweiten, dann den dritten.
  • Wenn Satz 1 fast gleich ist (kleiner Fehler)
  • UND Satz 2 fast gleich ist (kleiner Fehler)
  • ...dann ist die ganze Geschichte fast gleich (kleiner Gesamtfehler).

Die Autoren haben bewiesen, dass man mit ihren neuen Bildern und Regeln jeden möglichen Unterschied zwischen zwei Zufallsprozessen exakt berechnen und beweisen kann. Es gibt keine Lücken mehr.

Warum ist das wichtig?

1. Für KI und Maschinelles Lernen: Wenn KI-Modelle lernen, müssen sie wissen, wie „falsch" ihre Vorhersagen im Vergleich zur Realität sind. Diese neue Sprache hilft, diese Fehler präzise zu verstehen und zu optimieren.
2. Für Datenschutz: Wenn man Daten anonymisiert, muss man sicherstellen, dass die „Entfernung" zwischen den echten Daten und den anonymisierten Daten groß genug ist, um niemanden zu verraten. Die Autoren liefern die Werkzeuge, um das mathematisch exakt zu prüfen.
3. Für die Mathematik: Sie haben gezeigt, dass man komplexe Zufallsprozesse nicht nur mit Formeln, sondern mit schönen, logischen Bildern beschreiben kann, die sogar die „Größe" des Unterschieds enthalten.

Zusammenfassung in einem Satz

Die Autoren haben eine neue Art von „Rechenbuch" für Zufallsprozesse erfunden, das nicht nur sagt, ob zwei Dinge gleich sind, sondern mit Hilfe von Bildern und logischen Regeln exakt misst, wie weit sie voneinander entfernt sind – und zwar für zwei verschiedene Arten, wie diese Prozesse kombiniert werden können.

Sie haben damit die Lücke geschlossen, die bisher fehlte, um die „Entfernung" zwischen Wahrscheinlichkeiten so präzise zu beschreiben wie die Geometrie eines Dreiecks.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papers auf Deutsch:

Titel: Complete Diagrammatic Axiomatisations of Relative Entropy (Vollständige diagrammatische Axiomatisierungen der relativen Entropie)

Autoren: Ralph Sarkis und Fabio Zanasi (University College London)
Veröffentlicht in: MFPS XLII (Proceedings)

---

1. Problemstellung

Relative Entropie (auch Kullback-Leibler-Divergenz, KL-Divergenz) und ihre Verallgemeinerungen, die Rényi-Divergenzen, sind fundamentale Maße für den Abstand zwischen Wahrscheinlichkeitsverteilungen. Sie spielen eine zentrale Rolle in der Statistik, im maschinellen Lernen, in der Informationstheorie und in der Differential-Privacy.

Bisherige Arbeiten im Bereich der quantitativen algebraischen Theorien (initiiert durch Mardare et al.) haben sich erfolgreich mit der axiomatischen Darstellung von Metriken wie der Kantorovich-Metrik und dem Total-Variations-Abstand befasst. Diese Theorien nutzen Gleichungen der Form $s =_\varepsilon t$, um auszudrücken, dass der Abstand zwischen Termen $s$ und $t$ höchstens $\varepsilon$ beträgt.

Das fehlende Glied: Bislang fehlte eine vollständige quantitative algebraische Theorie für die KL-Divergenz und allgemein für relative Entropien. Die Herausforderung besteht darin, diese Divergenzen nicht nur für Wahrscheinlichkeitsverteilungen, sondern für stochastische Matrizen (die als Morphismen in einer symmetrischen monoidalen Kategorie, SMC, betrachtet werden) axiomatisch zu erfassen. Insbesondere ist die KL-Divergenz nicht durch einfache Gleichungen, sondern durch Implikationen (Kettenregeln) charakterisierbar, was über den Rahmen klassischer quantitativer Gleichungen hinausgeht.

2. Methodik

Die Autoren entwickeln einen Rahmen, der String-Diagramme mit quantitativen Gleichungen und quantitativen Implikationen kombiniert.

• Kategorischer Rahmen: Die Arbeit betrachtet die Kategorie der stochastischen Matrizen ($FStoch$) und zwei ihrer monoidalen Strukturen:
  1. Kronecker-Produkt ($\otimes$): Entspricht dem tensoriellen Produkt (Standard für Bayes-Netze und kausale Modelle).
  2. Direkte Summe ($\oplus$): Entspricht der direkten Summe (verwandt mit konvexen Mengen und baryzentrischen Algebren).
• Erweiterung der Quantitativen Algebra: Das Paper erweitert das Framework der quantitativen monoidalen Algebra (aus [41]), indem es quantitative Implikationen einführt. Anstatt nur Gleichungen $s =_\varepsilon t$ zu betrachten, werden Regeln der Form $\Gamma \Rightarrow \phi$ erlaubt, wobei $\Gamma$ eine Menge von Prämissen (Abstandsbeschränkungen) und $\phi$ die Konklusion ist.
• Die Kettenregel (Chain Rule): Der Kern der Axiomatisierung ist die Darstellung der Kettenregel der relativen Entropie als eine quantitative Implikation. Diese Regel besagt, dass der Abstand zwischen gemeinsamen Verteilungen durch die Abstände der bedingten Verteilungen und der Randverteilungen beschränkt werden kann.
  • Formell: Wenn die Distanzen der Komponenten durch $\varepsilon$ und $\delta$ beschränkt sind, dann ist die Distanz des Gesamtsystems durch eine Funktion $C(\varepsilon, \delta)$ beschränkt.
• V-Relationen: Die theoretische Basis bildet die Kategorie der über einem Quantale $V$ (hier $[0, \infty]$) angereicherten Relationen, was eine formale Behandlung von Abständen als logische Prädikate ermöglicht.

3. Hauptbeiträge

1. Vollständige Axiomatisierung der KL-Divergenz:

   • Die Autoren stellen zwei quantitative Theorien vor: $\mathcal{T}_{KL}^\otimes$ (für die Kronecker-Struktur auf dem Subkategorie $BStoch^\otimes$, d.h. Matrizen mit Dimensionen $2^n$) und$\mathcal{T}_{KL}^\oplus$(für die direkte Summe auf$FStoch^\oplus$).
   • Diese Theorien erweitern bestehende diagrammatische Kalküle (für stochastische Matrizen) um die neuen Implikationen $Chain^\otimes$ und $Chain^\oplus$ sowie $If_{max}$ bzw. $Parmax$.
   • Ergebnis: Die frei erzeugten angereicherten symmetrisch-monoidalen Kategorien (SMCs) dieser Theorien sind isomorph zu den Kategorien der stochastischen Matrizen, angereichert mit der KL-Divergenz. Dies bedeutet, dass die Axiome vollständig sind: Jeder wahre Abstand kann durch die Axiome hergeleitet werden.

2. Verallgemeinerung auf Rényi-Divergenzen:

   • Die Methode wird auf die gesamte Familie der Rényi-Divergenzen beliebiger Ordnung $\alpha \in [0, \infty]$ erweitert.
   • Die Kettenregeln für $\alpha \neq 1$ werden durch eine verallgemeinerte Funktion $C_\alpha$ ausgedrückt, die die Abhängigkeit der Divergenz von den bedingten Divergenzen beschreibt.
   • Die Axiomatisierungen \mathcal{T}_{R}^\otimes_\alpha und \mathcal{T}_{R}^\oplus_\alpha liefern analoge Vollständigkeitsergebnisse für alle $\alpha$.

3. Einführung implizierender quantitativer Diagrammlogik:

   • Das Paper etabliert ein neues logisches System, das quantitative Implikationen in einem monoidalen Kontext erlaubt. Dies ist notwendig, da die Kettenregel eine logische Konsequenz (wenn die Teile nah beieinander liegen, ist das Ganze nah beieinander) und keine bloße Gleichheit ist.
   • Dies schließt eine Lücke zwischen diagrammatischen Ansätzen und der Theorie der quantitativen Algebra.

4. Wichtige Ergebnisse und Beweise

• Isometrie-Eigenschaft: Die Autoren beweisen, dass die kanonische Abbildung von der syntaktischen Kategorie (erzeugt durch die Axiome) zur semantischen Kategorie (stochastische Matrizen mit KL-Divergenz) eine lokale Isometrie ist. Das heißt, der syntaktisch hergeleitete Abstand entspricht exakt dem tatsächlichen KL-Abstand.
• Induktive Beweise: Die Vollständigkeitsbeweise nutzen strukturelle Induktion über die Dimension der Matrizen und die Zerlegung von Verteilungen in bedingte Anteile, gestützt auf die neuen Implikationsregeln.
• Unterscheidung der Strukturen: Es wird gezeigt, dass die Kronecker-Struktur ($\otimes$) und die direkte Summe ($\oplus$) unterschiedliche axiomatische Anforderungen haben, aber beide erfolgreich durch das Framework der quantitativen Implikationen erfasst werden können.

5. Bedeutung und Ausblick

• Theoretische Lücke geschlossen: Dies ist die erste vollständige axiomatische Charakterisierung der KL-Divergenz und Rényi-Divergenzen im Rahmen der quantitativen algebraischen Theorien.
• Anwendung in der Programmsemantik: Da relative Entropie entscheidend für die Analyse probabilistischer Programme, Bayes'scher Inferenz und Differential-Privacy ist, ermöglicht dieser Ansatz formale Beweise über die "Nähe" von Programmen oder Modellen unter Verwendung von String-Diagrammen.
• Synthetische Wahrscheinlichkeitstheorie: Die Arbeit stärkt den Ansatz der "synthetischen Wahrscheinlichkeitstheorie", bei der probabilistische Konzepte rein kategorial und diagrammatisch behandelt werden.
• Zukünftige Richtungen:
  • Erweiterung auf nicht-diskrete Räume.
  • Anwendung auf Quanten-Relative-Entropie (im Kontext von Quanten-Informationsverarbeitung).
  • Weiterentwicklung der funktionalen Semantik für implizierende Theorien.

Zusammenfassend liefert das Paper einen fundamentalen Baustein für das formale Verständnis probabilistischer Systeme, indem es die mächtigen Werkzeuge der diagrammatischen Logik mit der präzisen Quantifizierung von Unsicherheit durch relative Entropie verbindet.