Complete Diagrammatic Axiomatisations of Relative Entropy

Cet article propose des axiomatisations complètes de la divergence de Kullback-Leibler et des divergences de Rényi d'ordre arbitraire en les étudiant sous un angle catégorique via une algèbre monoidale quantitative et un langage de diagrammes en cordes enrichi d'équations quantitatives, pour deux structures monoidales naturelles sur les matrices stochastiques.

L'essentiel

Imaginez que vous êtes un chef cuisinier qui prépare deux plats différents pour vos clients. L'un est un plat classique, l'autre est une version légèrement modifiée. La question n'est pas seulement : « Est-ce que les deux plats sont identiques ? » (oui ou non). La vraie question est : « À quel point sont-ils différents ? »

C'est exactement ce que font les mathématiciens et les informaticiens quand ils étudient les probabilités et l'apprentissage automatique. Ils ne veulent pas juste savoir si deux programmes donnent le même résultat, ils veulent mesurer la « distance » entre leurs comportements.

Ce papier, écrit par Ralph Sarkis et Fabio Zanasi, propose une nouvelle façon de mesurer cette distance, en utilisant une méthode visuelle et très élégante appelée diagrammes en ficelle (ou string diagrams).

Voici une explication simple de leur travail, avec quelques analogies pour rendre les choses claires.

1. Le Problème : Mesurer la différence entre deux mondes aléatoires

Dans le monde de l'informatique moderne (comme les IA qui génèrent du texte ou les systèmes de recommandation), tout est imprévisible. On ne dit pas « il va pleuvoir », mais « il y a 70 % de chances de pluie ».

Quand on compare deux systèmes probabilistes, on utilise souvent une mesure appelée Entropie Relative (ou divergence de Kullback-Leibler). C'est comme un « mètre-ruban » spécial qui vous dit à quel point une distribution de probabilité s'éloigne d'une autre.

• L'analogie du GPS : Imaginez que vous avez deux itinéraires GPS pour aller au travail. L'un est le trajet idéal (votre référence), l'autre est celui que vous avez pris hier. L'entropie relative ne vous dit pas juste « vous êtes arrivé », elle vous dit : « Vous avez pris 15 minutes de plus et vous avez fait 3 détours inutiles ».

Le problème, c'est que jusqu'à présent, il n'existait pas de « règle » simple et complète pour calculer cette distance dans tous les cas, surtout quand les systèmes deviennent complexes (comme des réseaux de neurones).

2. La Solution : Dessiner les mathématiques

Les auteurs utilisent une approche appelée catégorique. Au lieu d'écrire des équations compliquées avec des lettres et des chiffres, ils dessinent des diagrammes.

• L'analogie des Lego : Imaginez que chaque système probabiliste est un bloc Lego.
  • Les fils (les lignes du diagramme) représentent l'information qui circule.
  • Les boîtes (les formes sur les fils) représentent des opérations (comme « mélanger », « choisir », « diviser »).
  • Relier deux blocs ensemble, c'est comme connecter deux étapes d'un processus.

Ces diagrammes permettent de voir la structure du problème. C'est comme passer d'une recette écrite en texte à un dessin de montage de meuble : on comprend mieux comment les pièces s'assemblent.

3. La Grande Innovation : Les « Implications Quantitatives »

C'est ici que le papier devient vraiment brillant.

Habituellement, en mathématiques, on dit : « Si A est égal à B, alors C est égal à D ». C'est une règle stricte.
Mais ici, les auteurs disent : « Si la différence entre A et B est petite (disons moins de 5 %), alors la différence entre C et D sera au plus de telle taille ».

Ils ont créé un nouveau langage pour écrire ces règles.

• L'analogie de la chaîne de montage : Imaginez une usine où chaque étape ajoute un peu de « bruit » ou d'erreur.
  • Si vous savez que l'étape 1 a une erreur de 2 % et l'étape 2 une erreur de 3 %, pouvez-vous prédire l'erreur totale ?
  • Les auteurs ont trouvé la règle exacte (qu'ils appellent la « règle de la chaîne ») pour dire : « Si l'erreur à l'étape 1 est X et à l'étape 2 est Y, alors l'erreur totale ne dépassera jamais Z ».

Ils ont prouvé que ces règles sont complètes. Cela signifie qu'avec ces diagrammes et ces règles, vous pouvez calculer la distance entre n'importe quelle paire de systèmes probabilistes, sans rien manquer.

4. Deux Façons de Construire le Monde

Le papier explore deux façons différentes d'assembler ces blocs Lego, ce qui correspond à deux façons de voir le monde :

1. Le Monde du « Produit » (Kronecker) : C'est comme si vous preniez deux cartes et que vous les superposiez pour créer une carte plus grande et plus complexe. C'est utile pour modéliser des réseaux de cause à effet (comme : « Si je mange du chocolat, puis-je avoir mal au ventre ? »).
2. Le Monde de la « Somme » (Direct Sum) : C'est comme si vous aviez deux boîtes séparées et que vous les mettiez côte à côte. C'est utile pour modéliser des choix ou des mélanges (comme : « Je choisis soit le bus, soit le train »).

Les auteurs ont créé des règles spécifiques pour les deux mondes. C'est comme avoir deux manuels de construction différents, mais tous deux parfaits.

5. Pourquoi c'est important pour nous ?

Pourquoi un chef cuisinier ou un développeur devrait-il s'en soucier ?

• Pour l'Intelligence Artificielle : Les IA apprennent en ajustant leurs probabilités pour se rapprocher de la réalité. Ces règles permettent de prouver mathématiquement à quel point l'IA s'améliore ou, au contraire, s'éloigne de ce qu'elle devrait être.
• Pour la Vie Privée : Dans le domaine de la confidentialité des données (comme le « differential privacy »), il faut s'assurer qu'un système ne révèle pas trop d'informations. Ces diagrammes aident à calculer exactement combien d'informations fuitent.
• Pour la Science : Cela donne un langage commun. Au lieu de réinventer la roue à chaque fois qu'on veut comparer deux systèmes, on peut utiliser ces diagrammes universels.

En résumé

Ce papier est comme la découverte d'un nouvel alphabet pour parler de l'incertitude.
Au lieu de se perdre dans des formules algébriques complexes, les auteurs nous disent : « Regardez, si vous dessinez vos systèmes comme des circuits électriques ou des Lego, et si vous appliquez ces quelques règles simples de "distance", vous pouvez comprendre et prédire le comportement de n'importe quelle machine probabiliste. »

C'est une victoire de la clarté visuelle sur la complexité mathématique, offrant un outil puissant pour construire des systèmes plus fiables, plus sûrs et plus intelligents.

Résumé technique

Voici un résumé technique détaillé de l'article « Complete Diagrammatic Axiomatisations of Relative Entropy » de Ralph Sarkis et Fabio Zanasi.

1. Problématique et Contexte

La sémantique des langages de programmation vise traditionnellement à déterminer l'équivalence de deux programmes ou à vérifier leurs propriétés (correction, terminaison). Cependant, dans les domaines du programmation probabiliste, de l'inférence statistique et de l'apprentissage automatique, l'équivalence stricte est souvent trop coarse. Il est plus pertinent de mesurer la distance entre les comportements probabilistes.

Bien que des axiomatisations quantitatives existent pour des métriques comme la distance de Kantorovich ou la variation totale (travaux de Mardare et al.), il manquait jusqu'à présent une théorie algébrique quantitative complète pour la divergence de Kullback-Leibler (KL) et, plus généralement, pour les divergences de Rényi. Ces mesures sont fondamentales en théorie de l'information, en apprentissage automatique et en confidentialité différentielle, mais leur nature non-symétrique et leur comportement complexe (notamment via la règle de chaîne) rendaient leur axiomatisation dans un cadre diagrammatique difficile.

L'objectif de cet article est de combler ce vide en fournissant des axiomatisations complètes de la divergence relative (KL et Rényi) pour les matrices stochastiques, en utilisant le formalisme des diagrammes de chaînes (string diagrams) enrichis.

2. Méthodologie

Les auteurs adoptent une perspective catégorique en considérant la divergence relative comme un enrichissement quantitatif de catégories de matrices stochastiques.

• Cadre Théorique : Ils travaillent dans le cadre de l'algèbre monoidale quantitative. Ils étendent le cadre existant (introduit par Lobbia et al.) pour permettre des implications quantitatives. Au lieu de simples équations $s =_\varepsilon t$ (distance $\le \varepsilon$), ils introduisent des règles d'inférence de la forme $\Gamma \Rightarrow \varphi$, où $\Gamma$ est un ensemble d'équations quantitatives (prémisses) et $\varphi$ une conclusion. Cela est crucial pour modéliser la règle de chaîne de la divergence, qui relie la distance entre des distributions conjointes aux distances entre leurs distributions conditionnelles.
• Structures Monoidales : L'étude porte sur deux structures monoidales naturelles sur les matrices stochastiques :
  1. Le produit de Kronecker ($\otimes$), noté $\mathbf{FStoch}_\otimes$, pertinent pour la théorie synthétique des probabilités et les réseaux bayésiens.
  2. La somme directe ($\oplus$), notée $\mathbf{FStoch}_\oplus$, liée aux ensembles convexes et aux algèbres barycentriques.
• Langage Graphique : Les théories sont formulées en utilisant des diagrammes de chaînes. Les objets sont des listes de types, et les morphismes sont des diagrammes représentant des matrices stochastiques. Les axiomes sont des implications entre ces diagrammes enrichis par des valeurs dans le quantale $[0, \infty]$.

3. Contributions Clés

Les auteurs apportent trois contributions majeures :

1. Axiomatisation de la Divergence KL :

   • Ils définissent des théories quantitatives ($\mathcal{T}_{KL}^\otimes$ et $\mathcal{T}_{KL}^\oplus$) pour les catégories $\mathbf{BStoch}_\otimes$ (matrices stochastiques de dimensions $2^n$) et$\mathbf{FStoch}_\oplus$.
   • Le cœur de l'axiomatisation réside dans l'introduction de règles d'implication spécifiques, notées Chain (pour la règle de chaîne) et Ifmax (ou Parmax pour la somme directe). Ces règles capturent la décomposition de la divergence d'une distribution conjointe en fonction des divergences conditionnelles et des poids marginaux.
   • Ils prouvent que les catégories syntaxiques générées par ces théories sont isomorphes aux catégories de matrices stochastiques enrichies par la divergence KL.

2. Extension aux Divergences de Rényi :

   • Ils montrent que leur méthode s'étend naturellement à la famille entière des divergences de Rényi d'ordre $\alpha \in [0, \infty]$.
   • La divergence KL apparaît comme le cas particulier $\alpha = 1$.
   • Ils définissent des fonctions de combinaison $C_\alpha$ qui généralisent la formule de la règle de chaîne pour tout $\alpha$, permettant de construire des axiomatisations complètes ($\mathcal{T}_{R}^\otimes$ et $\mathcal{T}_{R}^\oplus$) pour chaque ordre.

3. Cadre Logique des Implications Quantitatives :

   • Ils formalisent l'extension des théories monoidales quantitatives pour inclure des axiomes sous forme d'implications. Ce cadre est d'intérêt indépendant et permet de traiter des raisonnements diagrammatiques où la distance n'est pas exacte mais bornée par des prémisses, reflétant mieux la structure des règles de chaîne probabilistes.

4. Résultats Principaux

• Complétude et Isométrie : Les théorèmes principaux (Théorèmes 4.4, 4.8, 5.5, 5.7) établissent que le foncteur d'interprétation des diagrammes vers les matrices stochastiques est un isomorphisme isométrique. Cela signifie que :
  • L'équivalence syntaxique correspond exactement à l'égalité des matrices.
  • La distance quantitative calculée dans le diagramme (via les axiomes) correspond exactement à la divergence KL (ou Rényi) calculée sur les matrices.
• Règle de Chaîne comme Axiome : La preuve de complétude repose essentiellement sur la capacité à décomposer toute matrice stochastique en termes élémentaires (portes "if", combinaisons convexes) et à appliquer la règle de chaîne itérativement pour reconstruire la distance globale à partir des distances locales.
• Généralité : Les résultats couvrent à la fois le cas des matrices stochastiques générales (pour la somme directe) et le cas restreint aux puissances de 2 (pour le produit de Kronecker), ce dernier étant nécessaire car le produit de Kronecker sur toutes les dimensions naturelles ne forme pas une catégorie cartésienne, contrairement à la somme directe.

5. Signification et Perspectives

• Avancée Théorique : Ce travail fournit la première axiomatisation complète et diagrammatique de la divergence KL et de Rényi. Il comble un manque important dans la littérature sur les algèbres quantitatives, qui se concentraient jusqu'ici sur des métriques symétriques.
• Outils pour la Vérification : En offrant un langage diagrammatique pour raisonner sur les distances entre processus probabilistes, ce cadre ouvre la voie à des preuves synthétiques de propriétés de modèles d'apprentissage, d'algorithmes d'inférence bayésienne ou de protocoles de confidentialité différentielle.
• Fondations Catégoriques : L'introduction d'axiomes implicatifs dans l'algèbre monoidale quantitative enrichit le cadre théorique, permettant de traiter des structures qui ne sont ni purement cartésiennes ni cocartésiennes.
• Travaux Futurs : Les auteurs suggèrent d'étendre ces résultats aux espaces non discrets, d'explorer la sémantique fonctorielle complète pour les théories implicatives, et d'adapter ces techniques aux processus quantiques, où la divergence relative quantique joue un rôle central en informatique quantique.

En résumé, cet article établit un pont rigoureux entre la théorie de l'information (divergences) et la théorie des catégories (diagrammes de chaînes), offrant un outil puissant pour l'analyse formelle des systèmes probabilistes.