Compositional Imprecise Probability: A Solution from Graded Monads and Markov Categories

This video presents a research talk from POPL 2025 by Jack Liell-Cock and Sam Staton from the University of Oxford exploring compositional models for imprecise probability. Discover how the researchers tackle the challenge of creating fully compositional programming language models for imprecise probability, which deals with uncertainty about which probability distributions to use in robust statistics and machine learning. Learn about their innovative approach using graded monads to name non-deterministic choices, resulting in a maximal compositional model that overcomes limitations of previous monadic approaches using convex sets of probability distributions. The presentation explains how their solution supports all kinds of composition (categorical and monoidal) guided by dataflow diagrams, providing a model of synthetic probability in the sense of Markov categories, and demonstrates how it achieves tighter bounds on uncertainty compared to earlier methods. The 18-minute talk was presented at the POPL 2025 conference sponsored by ACM SIGPLAN.