Complete Diagrammatic Axiomatisations of Relative Entropy

Imagine you are a chef trying to perfect a recipe. You have two versions of a soup: Soup A (your original recipe) and Soup B (your new experiment).

In the old days of computer science, we only asked a simple question: "Are these two soups identical?" If they tasted even slightly different, the answer was just "No." But in the world of machine learning and statistics, "No" isn't very helpful. We need to know how different they are. Is Soup B just a little too salty? Or is it completely inedible?

This paper is about creating a universal ruler to measure exactly how "different" two probability recipes are. This ruler is called Relative Entropy (or KL Divergence).

Here is the breakdown of what the authors did, using simple analogies.

1. The Problem: Measuring the "Distance" Between Recipes

In math, we often deal with probability distributions. Think of these as recipes for randomness.

Recipe A: A coin that lands Heads 50% of the time.
Recipe B: A coin that lands Heads 90% of the time.

How "far apart" are these two coins?

Total Variation Distance (an old ruler) says: "They are 0.4 units apart." It's like measuring the difference in the amount of salt.
Relative Entropy (the new ruler) says: "They are very far apart because if you bet on Heads, Recipe B will make you lose money much faster than Recipe A." It measures the surprise or the information loss when you use the wrong recipe.

The problem is, while we knew how to measure this distance for simple lists of numbers, we didn't have a complete set of rules (axioms) to calculate it for complex systems made of many interacting parts.

2. The Solution: String Diagrams (The LEGO Approach)

The authors use a visual language called String Diagrams. Imagine these as LEGO instructions or flowcharts.

Instead of writing long algebraic equations, you draw boxes and lines.
A line represents a piece of data flowing through a system.
A box represents a process (like a coin flip or a filter).

The authors built a new set of LEGO rules (axioms) that tell you how to combine these diagrams while keeping track of the "distance" (Relative Entropy) between them.

3. The Two Ways to Build: The "Kronecker" vs. The "Direct Sum"

The paper identifies two natural ways to combine these probability recipes, and they needed a specific ruler for each.

A. The "Kronecker" Way (The Multi-Player Game)

Imagine you have two independent games: a coin flip and a dice roll.

The Setup: You play both games at the same time.
The Analogy: This is like building a massive, multi-dimensional LEGO castle where every brick depends on every other brick in a grid.
The Rule: The authors created a rule called Chain⊗. It says: "To measure the difference between two giant castles, you measure the difference between the individual bricks and the rules that hold them together, then add them up."
Why it matters: This is crucial for Bayesian Networks and Causal Reasoning (figuring out cause-and-effect in complex systems like weather patterns or medical diagnoses).

B. The "Direct Sum" Way (The Buffet)

Imagine you have a buffet with two separate sections: a Salad Bar and a Dessert Bar.

The Setup: You pick either a salad or a dessert, but not both at once.
The Analogy: This is like having two separate LEGO sets sitting side-by-side on a table. They don't touch.
The Rule: They created a rule called Chain⊕. It says: "To measure the difference between two buffets, you look at the difference in the salad section and the dessert section, weighted by how likely people are to pick one over the other."
Why it matters: This is crucial for Convex Sets and understanding how randomness works as a "monadic effect" (a fancy way of saying how computers handle random choices).

4. The Secret Sauce: The "Chain Rule"

The most important part of this paper is how they handle the Chain Rule.

In the real world, complex systems are built from smaller parts.

The Old Way: You had to calculate the distance of the whole giant system from scratch.
The New Way (The Paper's Magic): The authors proved that you can break the system down.
- Analogy: If you want to know how different two complex recipes are, you don't need to taste the whole soup. You just need to taste the base broth and then taste the spices added later.
- The Math: They showed that the total difference = (Difference in the base) + (Weighted difference in the spices).

They turned this intuition into a formal inference rule. In their language, it looks like a logical "If/Then" statement:

IF the distance between the base ingredients is small, AND the distance between the spices is small,
THEN the distance between the final soup is guaranteed to be small (and we can calculate exactly how small).

5. Why Should You Care?

This might sound like abstract math, but it has huge real-world applications:

AI and Machine Learning: When AI models learn, they are constantly trying to minimize the "distance" between their predictions and reality. This paper gives AI a better, more rigorous way to measure how well they are learning.
Privacy: In "Differential Privacy" (protecting user data), we need to know exactly how much information is leaked. This ruler helps calculate that leakage precisely.
Verification: It allows computer scientists to prove that two complex probabilistic programs are "close enough" to be considered equivalent, without having to run them a billion times.

Summary

The authors took a fundamental concept in statistics (Relative Entropy) and built a complete, visual rulebook for it.

They used String Diagrams (visual LEGO blocks) to represent complex systems.
They created two specific rulebooks for two different ways systems interact (simultaneous vs. alternative).
They introduced Chain Rules that let us break down complex problems into simple, manageable pieces.

In short, they gave us a universal translator that turns the messy, hard-to-calculate differences between complex probabilistic systems into a clean, logical set of steps anyone (or any computer) can follow.

Here is a detailed technical summary of the paper "Complete Diagrammatic Axiomatisations of Relative Entropy" by Ralph Sarkis and Fabio Zanasi.

1. Problem Statement

The paper addresses a significant gap in the field of quantitative algebraic theories and categorical semantics. While previous work (notably by Mardare et al.) has successfully provided complete axiomatisations for certain probabilistic distances like the Kantorovich metric and total variation distance using string diagrams, Relative Entropy (specifically Kullback–Leibler (KL) divergence and Rényi divergences) had not yet been axiomatised within this framework.

The core challenges are:

Coarse Equivalence: Traditional program equivalence is insufficient for probabilistic systems; one needs to measure how far apart behaviors are.
Structural Complexity: Relative entropy does not behave linearly like total variation distance. It satisfies a chain rule that decomposes joint divergences into conditional divergences, involving non-linear combinations (e.g., weighted sums and logarithms).
Monoidal vs. Cartesian: Standard quantitative algebra often relies on Cartesian categories (where copying and discarding are natural). However, the category of stochastic matrices ( $FStoch$ ) is symmetric monoidal but not Cartesian, requiring a more general algebraic framework.

2. Methodology

The authors employ a categorical approach using string diagrams within the framework of Quantitative Monoidal Algebra.

A. Mathematical Framework

Enriched Categories: They treat the category of stochastic matrices as enriched over the quantale $[0, \infty]^+$ (extended non-negative reals). The hom-sets are equipped with a distance function (KL divergence) rather than just equality.
String Diagrams: They use the graphical language of symmetric monoidal categories (SMCs) to represent stochastic processes.
Quantitative Implications: A key methodological innovation is extending quantitative equational theories to allow implicational axioms. Instead of just stating $s =_\epsilon t$ , they introduce rules of the form:
$\Gamma \Rightarrow \phi$
where $\Gamma$ is a set of premises (bounds on distances) and $\phi$ is a conclusion (a bound on the resulting distance). This is necessary to encode the chain rule, which relates the distance of a joint distribution to the distances of its conditionals.

B. Two Monoidal Structures

The paper studies two distinct monoidal structures on stochastic matrices, each requiring a specific axiomatisation:

Kronecker Product ( $\otimes$ ): Denoted as $FStoch^\otimes$ . This corresponds to the standard setting for synthetic probability theory and Bayesian networks. The authors focus on a subcategory $BStoch^\otimes$ (matrices of dimensions $2^n \times 2^m$) which has a known complete axiomatisation for equivalence.
Direct Sum ( $\oplus$ ): Denoted as $FStoch^\oplus$ . This corresponds to convex sets and barycentric algebras, often used to interpret randomness as a monadic effect.

3. Key Contributions

I. Axiomatisations of KL Divergence

The authors provide complete axiomatisations for KL divergence in both monoidal settings:

For $BStoch^\otimes$ (Kronecker): They extend the existing theory $\mathcal{T}_{CC}$ $T_{C C}$ (Causal Circuits) with new quantitative implications.
- Chain Rule Axiom ( $Chain^\otimes$ ): A rule that decomposes the divergence of a joint distribution (represented by a "if" gate with a control bit) into the divergence of the control bit plus the weighted sum of the divergences of the conditional branches.
- Max Rule ( $Ifmax$ ): A rule stating that the divergence of a conditional choice is the maximum of the divergences of the branches.
For $FStoch^\oplus$ (Direct Sum): They extend the theory $\mathcal{T}_{CA}$ $T_{C A}$ (Convex Algebras) similarly.
- Chain Rule Axiom ( $Chain^\oplus$ ): Decomposes divergence for direct sums (convex combinations).
- Max Rule ( $Parmax$ ): Handles the divergence of parallel compositions (direct sums).

II. Extension to Rényi Divergences

The authors generalize their results to the entire family of Rényi divergences ( $D_\alpha$ ) for arbitrary order $\alpha \in [0, \infty]$ .

They define a generalized chain rule function $C_\alpha(p, q, \epsilon, \delta)$ that captures how Rényi divergence combines conditionals.
They show that the same diagrammatic structure used for KL divergence (where $\alpha=1$ ) applies to all $\alpha$ , simply by replacing the specific chain rule formula with the generalized $C_\alpha$ .

III. Theoretical Framework: Implicational Quantitative Theories

They formalize V-theories (theories over a quantale $V$ ) that allow implicational axioms. This allows the logical system to reason about upper bounds on distances derived from premises, mirroring the structure of the chain rule. This framework is shown to be sound and complete with respect to models in enriched monoidal categories.

4. Key Results

Completeness Theorems: The authors prove that the syntactic categories generated by their new theories ( $S_{KL}^\otimes$ $S_{K L}^{\otimes}$ and $S_{KL}^\oplus$ $S_{K L}^{\oplus}$ ) are isometrically isomorphic to the semantic categories of stochastic matrices equipped with KL divergence ( $BStoch^\otimes_{kl}$ $B S t oc h_{k l}^{\otimes}$ and $FStoch^\oplus_{kl}$ $F S t oc h_{k l}^{\oplus}$ ).
- This means the axioms are complete: any true inequality between stochastic matrices regarding KL divergence can be derived from the axioms.
Isometry: The mapping from the syntactic string diagrams to the actual stochastic matrices preserves the distance exactly (it is a local isometry).
Generalization: The proofs for Rényi divergences follow the same structure, confirming that the diagrammatic approach is robust across the family of relative entropies.

5. Significance and Impact

Bridging a Gap: This is the first complete axiomatisation of KL and Rényi divergences using string diagrams, filling a major void in quantitative algebraic theories.
Synthetic Probability: By working at the level of symmetric monoidal categories, the results apply to multi-dimensional systems (stochastic matrices) rather than just simple probability distributions. This is crucial for applications in Bayesian inference, causal reasoning, and probabilistic graphical models.
New Logical Tools: The introduction of implicational quantitative axioms provides a powerful new tool for reasoning about probabilistic systems where exact distances are hard to compute, but upper bounds derived from components are sufficient.
Future Directions:
- Bayesian Learning: The framework suggests a path to proving properties of probabilistic learning models (e.g., convergence, generalization bounds) using purely diagrammatic reasoning.
- Quantum Information: The authors note that relative entropy has quantum counterparts; the diagrammatic nature of this work makes it a strong candidate for extension to quantum processes.
- Non-Discrete Spaces: The current work is discrete; extending these results to continuous spaces (e.g., Gaussian mixtures) is a proposed future direction.

In summary, the paper successfully translates the complex, non-linear properties of relative entropy into a rigorous, complete, and graphical algebraic system, enabling new forms of formal verification and reasoning for probabilistic programs.