nLab category-theoretic approaches to probability theory

Contents

Context

Measure and probability theory

measure theory

probability theory

Contents

Idea

There are a number of approaches to apply category theory to probability and related fields, such as statistics, information theory and dynamical systems.

On one hand, one can study the existing structures in traditional probability theory (such as probability spaces, integration, and so on) using a categorical lens. For instance, the Giry monad models the formation of spaces of probability measures and its iterations, used for example in the context of de Finetti's theorem.

On the other hand, one can try to express certain aspects of probability and statistics synthetically. One looks for structures and axioms which can be thought of as “fundamental” in probability and statistics, and which one can use to prove theorems, without having to use measure theory directly. One then proves that the usual measure-theoretic treatment is a model (or semantics) of this theory. This approach is often called synthetic probability theory, in analogy for example with synthetic differential geometry. One of the most recent approaches to synthetic probability theory is given by Markov categories.

The main end goals of categorical probability are

• To generalize existing results in probability theory to more general settings, for example with less stringent conditions on countability, separability, etc.;
• To find new results, which with the traditional methods would have been too complex to prove;
• To make probability and related fields more accessible to practitioners, thanks to the fact that the formalism incorporates measure theory without requiring any deep knowledge of it.

Main structures of interest

Category theory was first developed to model particular structures in algebraic topology, and subsequently algebraic geometry, algebra, logic and computer science. Each one of these intended applications shaped a piece of the theory, adding to category theory the relevant structures of interest for each application.

The applications of category theory to probability are among the most recent, and are both bringing new categorical structures into the theory (such as Markov categories), as well as repurposing and reinterpreting existing ideas (such as monads).

Markov categories

Markov categories are a recent framework that models categories whose morphisms can be thought of as having randomness, such as stochastic maps and Markov kernels.

It has a graphical formalism which keeps track of the stochastic dependencies, and which can be used to prove theorems in probability purely graphically.

For more details, see Markov category.

Probability monads

Probability monads can be thought of as a way of adding a notion of “randomness” to an existing theory.

A monad often models the idea of “forming spaces of particular structures”, and in probability theory, one is interested in forming spaces of probability measures. Monads are particularly useful when this construction needs to be iterated, for example, when in de Finetti situations one needs to form probability measures over probability measures.

For more details, see probability monad.

Dagger categories

Dagger categories can be thought of as “undirected” categories, where morphisms can be seen as going either way as in an undirected graph.

In probability theory, joint distributions, or transport plans exhibit such a behavior, sometimes called Bayesian inversion. Several probabilistic ideas can be modelled in terms of dagger-categorical concepts, for example, conditional expectation.

For more details, see category of couplings.

Main results

Using category-theoretic methods, several results have been obtained in the past few years.

Firstly, some known concepts and results of probability theory have been given a category-theoretic description. (For example: expressing Kolmogorov's extension theorem as a cofiltered limit condition.) This allows to incorporate the existing theory of probability into the categorical framework, and is the basic starting point for further results. (For example, every time in traditional probability Kolmogorov’s extension theorem is invoked, one now knows that a certain universal property is being used.)

Secondly, some classical results of probability theory have been restated and reproven using category theory. Often this adds new insight into the problem, and allows, for example, to drop further unnecessary assumptions (see the next point). In addition, the category-theoretic formalism often trades higher complexity for higher abstraction. This way, while more abstract, the categorical proofs tend to be simpler than their measure-theoretic counterparts. (And so, they also allow to prove more difficult results more easily.)

Thirdly, and most importantly, new theorems have been proven, as well as generalizations and extensions of old theorems, especially from the discrete to the continuous case.

Here is a partial list, roughly in alphabetical order, roughly divided by subject.

(Work in progress, for more material see also the references below.)

(…)

(…)

(…)

(…)

(…)

(…)

References

(in alphabetical order by author)

• Mauricio Alvarez-Manilla, Achim Jung, Klaus Keimel, The probabilistic powerdomain for stably compact spaces, Theoretical Computer Science 328, 2004. Link here.

• Nathanael L. Ackerman, Cameron E. Freer, Younesse Kaddar, Jacek Karwowski, Sean K. Moss, Daniel M. Roy, Sam Staton, Hongseok Yang, Probabilistic programming interfaces for random graphs: Markov categories, graphons, and nominal sets, Proceedings of POPL, 2024. (arXiv)

• Tom Avery, Codensity and the Giry monad, Journal of Pure and Applied Algebra, 220(3), 2016.

• Pedro H. Azevedo de Amorim, Dexter Kozen, Radu Mardare, Prakash Panangaden, Michael Roberts, Universal semantics for the stochastic $\lambda$-calculus, Proceedings of LICS, 2021. (pdf)

• Giorgio Bacci, Radu Mardare, Prakash Panangaden, Gordon Plotkin, An algebraic theory of Markov processes, Proceedings of LICS, 2018. (pdf)

• John Baez and Tobias Fritz, A Bayesian characterization of relative entropy, Theory and Application of Categories, 29(16), 2014. (arXiv)

• John Baez, Tobias Fritz and Tom Leinster, A characterization of entropy in terms of information loss, Entropy 13(2), 2011. (arXiv)

• Tai-Danae Bradley, Entropy as a topological operad derivation, Entropy 23(9), 2021. (arXiv)

• Franck van Breugel, The metric monad for probabilistic nondeterminism, unpublished, 2005. (pdf)

• Philippe Chaput, Vincent Danos, Prakash Panangaden and Gordon Plotkin, Approximating Markov processes by averaging, Proceedings of ICALP 2009. (pdf)

• N. N. Chentsov, The categories of mathematical statistics, Dokl. Akad. SSSR 164, 1965.

• Kenta Cho, Bart Jacobs, Disintegration and Bayesian Inversion via String Diagrams, Mathematical Structures of Computer Science 29, 2019. (arXiv:1709.00322)

• Bob Coecke, Eric Oliver Paquette, Dusko Pavlovic, Classical and quantum structuralism, (arXiv:0904.1997)

• Bob Coecke and Robert W. Spekkens, Picturing classical and quantum Bayesian inference, Synthese, 186(3), 2012. (arXiv)

• Carmen Constantin and Andreas Döring, A topos-theoretic notion of entropy, 2020. (arXiv)

• Rob Cornish, Stochastic Neural Network Symmetrization in Markov Categories, 2024. (arXiv)

• Fredrik Dahlqvist, Vincent Danos, Ilias Garnier, and Alexandra Silva, Borel kernels and their approximation, categorically. In MFPS 34: Proceedings of the Thirty-Fourth Conference on the Mathematical Foundations of Programming Semantics, volume 341, 91–119, 2018. arXiv.

• Swaraj Dash, Younesse Kaddar, Hugo Paquet and Sam Staton, Affine monads and lazy structures for Bayesian programming, Proceedings of POPL, 2023. (pdf)

• Swaraj Dash and Sam Staton, A monad for probabilistic point processes, Proceedings of Applied Category Theory, 2020. (pdf)

• Elena Di Lavore and Mario Román, Evidential Decision Theory via Partial Markov Categories, Proceedings of LICS, 2023. (arXiv)

• Noé Ensarguet, Paolo Perrone, Categorical probability spaces, ergodic decompositions, and transitions to equilibrium, arXiv:2310.04267

• Brendan Fong, Causal theories: A categorical prespective on Bayesian networks, master thesis, University of Oxford, 2012. (arXiv)

• James Fullwood, On a 2-relative entropy, Entropy 24(1), 2022. (arXiv)

• Arthur J. Parzygnat, Reversing information flow: retrodiction in semicartesian categories, 2024. (arXiv)

• James Fullwood and Arthur J. Parzygnat, From time-reversal symmetry to quantum Bayes rules, PRX Quantum 4, 2023. (arXiv)

• James Fullwood and Arthur J. Parzygnat, On quantum states over time, Proceedings of the Royal Society A 478, 2022. (arXiv)

• James Fullwood and Arthur J. Parzygnat, The information loss of a stochastic map, Entropy 2021, 23(8), 2021. (arXiv)

• Robert W. J. Furber and Bart Jacobs: From Kleisli Categories to Commutative C-algebras: Probabilistic Gelfand Duality_, LMCS 11(2), 2015. (arXiv)

• Tobias Fritz, A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics, Advances of Mathematics 370, 2020. (arXiv:1908.07021)

• Tobias Fritz, Fabio Gadducci, Paolo Perrone and Davide Trotta, Weakly Markov categories and weakly affine monads, Proceedings of CALCO, LIPIcs 10, 2023. (arXiv)

• Tobias Fritz, Fabio Gadducci, Davide Trotta, Andrea Corradini, From gs-monoidal to oplax-cartesian categories: constructions and functorial completeness, Applied Categorical Structures 31, 42, 2023. (arXiv)

• Tobias Fritz, Tomáš Gonda, Nicholas Gauguin Houghton-Larsen, Paolo Perrone and Dario Stein, Dilations and information flow axioms in categorical probability. Mathematical Structures in Computer Science, 2023. (arXiv:2211.02507).

• Tobias Fritz, Tomáš Gonda, Antonio Lorenzin, Paolo Perrone, Dario Stein, Absolute continuity, supports and idempotent splitting in categorical probability, (arXiv:2308.00651)

• Tobias Fritz, Tomáš Gonda, Paolo Perrone, De Finetti’s theorem in categorical probability. Journal of Stochastic Analysis, 2021. (arXiv:2105.02639)

• Tobias Fritz, Tomáš Gonda, Paolo Perrone, Eigil Fjeldgren Rischel, Representable Markov categories and comparison of statistical experiments in categorical probability, Theoretical Computer Science 961, 2023. (arXiv:2010.07416)

• Tobias Fritz and Andreas Klingler, The d-separation criterion in Categorical Probability, Journal of Machine Learning Research 24(46), 2023. (arXiv)

• Tobias Fritz, Andreas Klingler, Drew McNeely, Areeb Shah-Mohammed and Yuwen Wang, Hidden Markov models and the Bayes filter in categorical probability, 2024. (arXiv)

• Tobias Fritz, Wendong Liang, Free gs-monoidal categories and free Markov categories, Applied Categorical Structures 31, 21, 2023. (arXiv:2204.02284)

• Tobias Fritz and Antonio Lorenzin, Involutive Markov categories and the quantum de Finetti theorem, 2023. (arXiv)

• Tobias Fritz and Paolo Perrone, Stochastic order on metric spaces and the ordered Kantorovich monad, Advances in Mathematics 366, 2020. (arXiv:1808.09898)

• Tobias Fritz and Paolo Perrone, Monads, partial evaluations, and rewriting, Proceedings of MFPS, 2020. (arXiv)

• Tobias Fritz and Paolo Perrone, A Probability Monad as the Colimit of Spaces of Finite Samples, Theory and Applications of Categories 34, 2019. (arXiv:1712.05363)

• Tobias Fritz, Paolo Perrone, Bimonoidal Structure of Probability Monads, Proceedings of MFPS, 2018, (arXiv:1804.03527)

• Tobias Fritz, Paolo Perrone, Sharwin Rezagholi, Probability, valuations, hyperspace: Three monads on Top and the support as a morphism, Mathematical Structures in Computer Science 31(8), 2021. (arXiv:1910.03752)

• Tobias Fritz and Eigil Fjeldgren Rischel, Infinite products and zero-one laws in categorical probability, Compositionality 2(3) 2020. (arXiv:1912.02769)

• Nicolas Gagne and Prakash Panangaden, A categorical characterization of relative entropy on standard Borel spaces, ENTCS 336, 2018. (arXiv)

• Nicholas Gauguin Houghton-Larsen, A Mathematical Framework for Causally Structured Dilations and its Relation to Quantum Self-Testing, PhD thesis, University of Copenhagen, 2021. (arXiv)

• Michèle Giry, A categorical approach to probability theory, Categorical aspects of topology and analysis, Lecture notes in Mathematics 915, Springer, 1982.

• Peter V. Golubtsov, Axiomatic description of categories of information converters, Problemy Peredachi Informatsii (Problems in Information Transmission) 35(3), 1999.

• Peter V. Golubtsov, Monoidal Kleisli category as a background for information transformers theory. Information Theory and Information Processing 2, 2002.

• Peter V. Golubtsov, Information transformers: category-theoretical structure, informativeness, decision-making problems, Hadronic Journal Supplements 19(3), 2004.

• Peter V. Golubtsov and Stepan S. Moskaliuk, Method of additional structures on the objects of a monoidal Kleisli category as a background for information transformers theory, Hadronic Journal 25(2), 2002.

• Jean Goubault-Larrecq and Xiaodong Jia, Algebras of the extended probabilistic powerdomain monad, ENTCS 345, 2019

• Reinhold Heckmann, Spaces of valuations, Papers on General Topology and Ap-plications, 1996 (doi:10.1111/j.1749-6632.1996.tb49168.x,pdf)

• Younesse Kaddar and Sam Staton, A model of stochastic memoization and name generation in probabilistic programming: categorical semantics via monads on presheaf categories, Proceedings of MFPS, 2023. (arXiv)

• Chris Heunen, Ohad Kammar, Sam Staton and Hongseok Yang, A convenient category for higher-order probability theory, Proceedings of LICS 2017. (arXiv)

• Bart Jacobs, Drawing from an Urn is Isometric, Proceedings of FoSSaCS, 2024. (pdf)

• Bart Jacobs, Pearl’s and Jeffrey’s Update as Modes of Learning in Probabilistic Programming (arXiv:2309.07053)

• Bart Jacobs, Urns & Tubes, Compositionality 4(4), 2022. (arXiv)

• Bart Jacobs, Sufficient statistics and split idempotents in discrete probability theory, Proceedings of MFPS, 2023. (arXiv)

• Bart Jacobs, Multinomial and Hypergeometric Distributions in Markov Categories, Proceedings of MFPS 2021. (arXiv)

• Bart Jacobs, From Multisets over Distributions to Distributions over Multisets, Proceedings of LICS, 2021. (arXiv)

• Bart Jacobs, From probability monads to commutative effectuses, Journal of Logical and Algebraic Methods in Programming 94, 2018.

• Bart Jacobs, Categorical aspects of parameter learning, 2018. (arXiv)

• Bart Jacobs, A Channel-based Exact Inference Algorithm for Bayesian Networks, 2018. (arXiv)

• Bart Jacobs, A Channel-Based Perspective on Conjugate Priors, 2017. (arXiv:1707.00269)

• Bart Jacobs, Hyper Normalisation and Conditioning for Discrete Probability Distributions, LMCS 13, 2017. (arXiv)

• Bart Jacobs, Aleks Kissinger, Fabio Zanasi, Causal Inference by String Diagram Surgery, (arXiv:1811.08338)

• Bart Jacobs, Sam Staton, De Finetti’s construction as a categorical limit, Proceedings of CMCS, 2021. (arXiv:2003.01964)

• Bart Jacobs and Dario Stein?, Overdrawing Urns using Categories of Signed Probabilities, Proceedings of Applied Category Theory, EPTCS 397, 2023. (arXiv)

• Bart Jacobs, Fabio Zanasi, The Logical Essentials of Bayesian Reasoning, (arXiv:1804.01193)

• Bart Jacobs, Fabio Zanasi, and Octavio Zapata, Bayesian Factorisation as Adjoint, abstract

• Claire Jones and Gordon Plotkin, A probabilistic powerdomain of evaluations, Procedings of LICS, 1989. (doi)

• Klaus Keimel, The monad of probability measures over compact ordered spaces and its Eilenberg-Moore algebras, Topology and its Applications, 2008 (doi:10.1016/j.topol.2008.07.002)

• Dexter Kozen, Kim G. Larsen, Radu Mardare, Prakash Panangaden, Stone duality for Markov processes, Proceedings of LICS, 2013. (pdf)

• Dexter Kozen, Radu Mardare, Prakash Panangaden, Stone duality for Markov processes, Proceedings of MFCS, 2013. (pdf)

• Dexter Kozen, Alexandra Silva, Erik Voogd, Joint Distributions in Probabilistic Semantics, MFPS 2023. (arXiv)

• Peter Kristel, Benedikt Peterseim, A topologically enriched probability monad on the cartesian closed category of CGWH spaces. (arXiv)

• Bill Lawvere, The category of probabilistic mappings, ms. 12 pages, 1962

• Tom Leinster, A short characterization of relative entropy, Journal of Mathematical Physics 60, 2019. (arXiv)

• Tom Leinster, Entropy and Diversity, Cambridge University Press, 2021.

• Radu Mardare, Prakash Panangaden, Gordon Plotkin, Free complete Wasserstein algebras, LMCS 14, 2018. (pdf)

• Radu Mardare, Prakash Panangaden, Gordon Plotkin, Quantitative algebraic reasoning, Proceedings of LICS, 2016. (pdf)

• Cristina Matache, Sean Moss, Sam Staton, Ariadne Si Suo, Denotational semantics for languages for inference: semirings, monads, and tensors, Proceedings of LAFI, 2023. (arXiv)

• Eugenio Moggi, Computational lambda-calculus and monads, Proceedings of LICS, 1989. (doi)

• Sean Moss and Paolo Perrone, A category-theoretic proof of the ergodic decomposition theorem, Ergodic Theory and Dynamical Systems, 2023. (arXiv:2207.07353)

• Sean Moss, Paolo Perrone, Probability monads with submonads of deterministic states, LICS 2022. (arXiv:2204.07003)

• Prakash Panangaden, The category of Markov kernels, ENTCS, 1999. (full text)

• Prakash Panangaden, Labelled Markov processes, Imperial College Press, 2009.

• Prakash Panangaden, A categorical view of conditional expectation, (slides)

• Arthur J. Parzygnat, A functorial characterization of von Neumann entropy, Cahiers de Topologie et de Géométrie Différentielle Catégorique LXIII(1), 2022. (arXiv)

• Arthur J. Parzygnat, Conditional distributions for quantum systems, EPTCS 343, 2021. (arXiv)

• Arthur J. Parzygnat, Inverses, disintegrations, and Bayesian inversion in quantum Markov categories, 2020. (arXiv)

• Arthur J. Parzygnat, Stinespring’s construction as an adjunction, Compositionality 1(2), 2019. (arXiv)

• Arthur J. Parzygnat, Discrete probabilistic and algebraic dynamics: a stochastic commutative Gelfand-Naimark Theorem, 2017. (arXiv)

• Arthur J. Parzygnat, Francesco Buscemi, Axioms for retrodiction: achieving time-reversal symmetry with a prior, Quantum 7(1013), 2023. arXiv

• Arthur J. Parzygnat, Benjamin P. Russo, Non-commutative disintegrations: existence and uniqueness in finite dimensions, Journal of Noncommutative Geometry 17(3), 2023. (arXiv)

• Arthur J. Parzygnat and Benjamin P. Russo, A noncommutative Bayes theorem, Linear Algebra Applications 644, 2022. (arXiv)

• Paolo Perrone, Markov Categories and Entropy, IEEE Transactions on Information Theory 70(3), 2024. (arXiv)

• Paolo Perrone and Ruben Van Belle, Convergence of martingales via enriched dagger categories, 2024. (arXiv)

• Paolo Perrone, Lifting couplings in Wasserstein spaces, 2021. (arXiv)

• Paolo Perrone, Categorical Probability and Stochastic Dominance in Metric Spaces, (thesis)

• Marcin Sabok, Sam Staton, Dario Stein, Michael Wolman, Probabilistic Programming Semantics for Name Generation, Proceedings of POPL, 2021. (arXiv)

• Alex Simpson, Probability Sheaves and the Giry Monad, (pdf)

• Sam Staton and Ned Summers, Quantum de Finetti Theorems as Categorical Limits, and Limits of State Spaces of C-algebras_, Proceedings of Quantum Physics and Logic, 2022. (arXiv)

• Dario Stein and Richard Samuelson, A Category for unifying Gaussian Probability and Nondeterminism, Proceedings of CALCO, LIPIcs 10, 2023. (arXiv)

• Dario Stein and Sam Staton, Probabilistic Programming with Exact Conditions, JACM, 2023. (arXiv)

• T. Swirszcz, Monadic functors and convexity, Bulletin de l’Academie Polonais des Sciences 22, 1974 (pdf)

• Ruben Van Belle, A categorical treatment of the Radon-Nikodym theorem and martingales, 2023. (arXiv)

• Ruben Van Belle, A categorical proof of the Carathéodory extension theorem, 2022. (arXiv)

• Ruben Van Belle, Probability monads as codensity monads, Theory and Applications of Categories, 38(21), 2022. (arXiv)

• Steve Vickers, A monad of valuation locales, 2011. Link here.

• Nathaniel Virgo, Unifilar Machines and the Adjoint Structure of Bayesian Filtering, Proceedings of ACT, 2023. (arXiv)

• Yimu Yin, Jiji Zhang ,_Markov categories, causal theories, and the do-calculus_, 2022. (arXiv)

(…more to add…)

category: probability

Last revised on July 21, 2024 at 16:49:37. See the history of this page for a list of all contributions to it.