Compositional Imprecise Probability A Solution from Graded Monads and Markov Categories

作     者：Liell-cock, Jack Staton, Sam 

作者机构：Univ Oxford Oxford England 

出 版 物：《PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL》 (Proc. ACM Program. Lang.)

年 卷 期：2025年第9卷第POPL期

页      面：1596-1626页

核心收录：

基　　金：Clarendon Scholarship ERC Consolidator Grant BLAST AFOSR Project [FA9550-21-1-0038] ARIA programme on Safeguarded AI 

主　　题：imprecise probability probabilistic programming graded monads 

摘      要：Imprecise probability is concerned with uncertainty about which probability distributions to use. It has applications in robust statistics and machine learning. We look at programming language models for imprecise probability. Our desiderata are that we would like our model to support all kinds of composition, categorical and monoidal;in other words, guided by dataflow diagrams. Another equivalent perspective is that we would like a model of synthetic probability in the sense of Markov categories. Imprecise probability can be modelled in various ways, with the leading monad-based approach using convex sets of probability distributions. This model is not fully compositional because the monad involved is not commutative, meaning it does not have a proper monoidal structure. In this work, we provide a new fully compositional account. The key idea is to name the non-deterministic choices. To manage the renamings and disjointness of names, we use graded monads. We show that the resulting compositional model is maximal and relate it with the earlier monadic approach, proving that we obtain tighter bounds on the uncertainty.