Order in Partial Markov Categories

1. Problématique et Contexte

Les catégories de Markov constituent un cadre synthétique pour la théorie des probabilités, permettant de raisonner sur les processus probabilistes via des axiomes de base (structure monoïdale symétrique, comonoides commutatifs pour le copiage et le rejet d'information). Cependant, ces catégories modélisent des calculs totaux : l'axiome de naturalité du rejet (discarding) implique que l'on peut ignorer n'importe quelle sortie sans affecter le sens du processus.

Ce cadre est insuffisant pour capturer la partialité inhérente à de nombreuses opérations probabilistes, notamment la mise à jour bayésienne (Bayesian updating). En effet, si une nouvelle donnée (évidence) est incompatible avec une croyance a priori, la mise à jour est impossible (le processus est partiel). Pour modéliser cela, les auteurs travaillent avec des catégories de Markov partielles, qui sont des catégories « copier-rejeter » (copy-discard) dotées de conditionnels, mais où la naturalité du rejet n'est plus requise.

Le problème central abordé par l'article est l'absence d'une structure d'ordre canonique dans les catégories de Markov partielles. Contrairement aux catégories de restriction cartésiennes ou aux bicatégories de relations, qui possèdent naturellement des ordres sur leurs morphismes, les catégories de Markov partielles générales manquaient d'une telle structure unifiée. Cela empêche le développement d'un raisonnement inéquationnel (inequational reasoning) fondamental pour la théorie probabiliste synthétique (par exemple, prouver que la mise à jour augmente la validité d'une preuve).

2. Méthodologie

Les auteurs adoptent une approche catégorique synthétique, utilisant la notation par diagrammes de cordes (string diagrams) et les axiomes algébriques des catégories monoïdales. Leur méthodologie se décompose en plusieurs étapes :

1. Définition d'une relation d'ordre : Ils introduisent une nouvelle relation d'ordre, appelée inégalité conditionnelle (conditional inequality), notée $\sqsubseteq$. Pour deux morphismes parallèles $f, g : X \to Y$, on dit que $f \sqsubseteq g$ s'il existe un morphisme témoin $r : Y \otimes X \to I$ tel que $f = g \triangleleft r$, où $\triangleleft$ est la composition conditionnelle.
2. Enrichissement en préordres : Ils démontrent que cette relation définit un préordre sur les ensembles de morphismes (hom-sets) et qu'elle est compatible avec la structure monoïdale symétrique (composition et produit tensoriel), rendant ainsi toute catégorie de Markov partielle enrichie en préordres.
3. Étude des conditionnels minimaux : Ils explorent l'existence de conditionnels « les plus petits » (least conditionals) par rapport à cet ordre et à l'ordre de restriction ($\preceq$). Ils établissent un lien crucial entre l'existence de ces conditionnels minimaux et l'existence de comparateurs (maps de multiplication $\mu$) ou de « caps » ($\cap$).
4. Dérivation synthétique d'inégalités classiques : En utilisant cet ordre, ils formulent une version synthétique de l'inégalité de Cauchy-Schwarz et de l'inégalité des moyennes (QM-AM).
5. Application à la validité bayésienne : Ils utilisent ces inégalités pour prouver de manière abstraite que la mise à jour bayésienne augmente la validité de l'évidence.

3. Contributions Clés

• Enrichissement canonique : La contribution principale est la preuve que toute catégorie de Markov partielle est canoniquement enrichie en préordres. Cet enrichissement généralise les ordres connus dans des sous-catégories spécifiques (comme les catégories de restriction ou les bicatégories de relations).
• Lien entre comparateurs et conditionnels minimaux : Les auteurs montrent que l'existence de comparateurs (structures de Frobenius partielles) est équivalente à l'existence de conditionnels minimaux pour les morphismes de copiage ($\delta$) et d'identité. Plus précisément, dans une catégorie équilibrée satisfaisant la propriété de témoin précis, l'existence de conditionnels minimaux implique que la catégorie est une catégorie de Markov partielle discrète (dotée de comparateurs).
• Synthèse de l'inégalité de Cauchy-Schwarz : Ils définissent une version catégorique de l'inégalité de Cauchy-Schwarz utilisant l'ordre conditionnel. Ils montrent que cette inégalité est satisfaite dans des modèles concrets comme les noyaux de probabilité sub-stochastiques ($FinStoch_{\le 1}$, $BorelStoch_{\le 1}$) et les bicatégories de relations.
• Théorème d'augmentation de la validité : En combinant l'inégalité des moyennes (dérivée de Cauchy-Schwarz) et des propriétés de cancellation des scalaires non nuls, ils prouvent que la mise à jour d'un état a priori par un prédicat augmente la validité de ce prédicat dans l'état a posteriori.

4. Résultats Principaux

• Théorème 3.3 : Toute catégorie de Markov partielle est une catégorie monoïdale symétrique enrichie en préordres via l'inégalité conditionnelle.
• Théorèmes 4.4 et 4.6 : Établissement d'une équivalence entre l'existence de comparateurs (multiplications $\mu$ et caps $\cap$) et l'existence de conditionnels minimaux pour les morphismes de copiage et d'identité. Cela permet de caractériser les catégories de Markov partielles discrètes.
• Proposition 3.10 & 3.12 : Dans les catégories de noyaux de probabilité sub-stochastiques ($BorelStoch_{\le 1}$) et les bicatégories de relations, l'ordre conditionnel coïncide avec les ordres ponctuels ou d'inclusion de relations habituels.
• Théorème 5.13 (Validité) : Dans une catégorie de Markov partielle satisfaisant l'inégalité des moyennes et dont les scalaires non nuls sont cancellatifs, pour tout état $\sigma$ et prédicat $p$, on a :
  $$\sigma \circ p \sqsubseteq p^\dagger_\sigma \circ p$$
  Cela signifie formellement que la validité de l'évidence après mise à jour est supérieure ou égale à sa validité avant mise à jour.

5. Signification et Impact

Cet article est significatif pour plusieurs raisons :

1. Unification théorique : Il fournit un cadre unifié pour comprendre les structures d'ordre dans divers modèles probabilistes (discrétisés, continus, relationnels) en les voyant tous comme des instances d'une même construction d'enrichissement conditionnel.
2. Fondements du raisonnement probabiliste : En introduisant un ordre naturel, l'article ouvre la voie à un raisonnement inéquationnel rigoureux en théorie des probabilités synthétique, essentiel pour l'analyse de programmes probabilistes et l'inférence.
3. Preuve synthétique de résultats classiques : La dérivation du théorème « l'update augmente la validité » (un résultat connu en probabilités discrètes) à partir d'axiomes catégoriques abstraits et d'une inégalité de Cauchy-Schwarz synthétique démontre la puissance de l'approche catégorique pour généraliser des résultats probabilistes au-delà des cas discrets.
4. Perspectives futures : L'article suggère que cette structure d'ordre pourrait être utilisée pour développer une théorie synthétique de la variance et de la covariance, et pour mieux comprendre les relations entre les catégories de Markov partielles et les effectus (effectuses) en logique quantique et probabiliste.

En résumé, ce travail transforme les catégories de Markov partielles d'un cadre purement équationnel en un cadre capable de supporter des raisonnements d'ordre, comblant ainsi un vide théorique important pour la modélisation de l'inférence bayésienne et des calculs probabilistes partiels.