TY - JOUR
TI - Causal Inference by String Diagram Surgery
AU - Jacobs, Bart
AU - Kissinger, Aleks
AU - Zanasi, Fabio
T2 - arXiv:1811.08338 [cs, math]
AB - Extracting causal relationships from observed correlations is a growing area in probabilistic reasoning, originating with the seminal work of Pearl and others from the early 1990s. This paper develops a new, categorically oriented view based on a clear distinction between syntax (string diagrams) and semantics (stochastic matrices), connected via interpretations as structure-preserving functors. A key notion in the identification of causal effects is that of an intervention, whereby a variable is forcefully set to a particular value independent of any prior propensities. We represent the effect of such an intervention as an endofunctor which performs `string diagram surgery' within the syntactic category of string diagrams. This diagram surgery in turn yields a new, interventional distribution via the interpretation functor. While in general there is no way to compute interventional distributions purely from observed data, we show that this is possible in certain special cases using a calculational tool called comb disintegration. We demonstrate the use of this technique on a well-known toy example, where we predict the causal effect of smoking on cancer in the presence of a confounding common cause. After developing this specific example, we show this technique provides simple sufficient conditions for computing interventions which apply to a wide variety of situations considered in the causal inference literature.
DA - 2019/07/28/
PY - 2019
DP - arXiv.org
UR - http://arxiv.org/abs/1811.08338
Y2 - 2019/11/21/20:42:12
KW - Bayesianism
KW - Categorical probability theory
KW - Implementation
ER -
TY - JOUR
TI - A Probability Monad as the Colimit of Spaces of Finite Samples
AU - Fritz, Tobias
AU - Perrone, Paolo
T2 - arXiv:1712.05363 [cs, math]
AB - We define and study a probability monad on the category of complete metric spaces and short maps. It assigns to each space the space of Radon probability measures on it with finite first moment, equipped with the Kantorovich-Wasserstein distance. This monad is analogous to the Giry monad on the category of Polish spaces, and it extends a construction due to van Breugel for compact and for 1-bounded complete metric spaces. We prove that this Kantorovich monad arises from a colimit construction on finite power-like constructions, which formalizes the intuition that probability measures are limits of finite samples. The proof relies on a criterion for when an ordinary left Kan extension of lax monoidal functors is a monoidal Kan extension. The colimit characterization allows the development of integration theory and the treatment of measures on spaces of measures, without measure theory. We also show that the category of algebras of the Kantorovich monad is equivalent to the category of closed convex subsets of Banach spaces with short affine maps as morphisms.
DA - 2019/03/12/
PY - 2019
DP - arXiv.org
UR - http://arxiv.org/abs/1712.05363
Y2 - 2019/11/28/14:36:14
KW - Categorical probability theory
KW - Purely theoretical
ER -
TY - JOUR
TI - Disintegration and Bayesian Inversion via String Diagrams
AU - Jacobs, Bart
AU - Cho, Kenta
T2 - Mathematical Structures in Computer Science
AB - The notions of disintegration and Bayesian inversion are fundamental in conditional probability theory. They produce channels, as conditional probabilities, from a joint state, or from an already given channel (in opposite direction). These notions exist in the literature, in concrete situations, but are presented here in abstract graphical formulations. The resulting abstract descriptions are used for proving basic results in conditional probability theory. The existence of disintegration and Bayesian inversion is discussed for discrete probability, and also for measure-theoretic probability --- via standard Borel spaces and via likelihoods. Finally, the usefulness of disintegration and Bayesian inversion is illustrated in several examples.
DA - 2019/08//
PY - 2019
DO - 10/ggdf9v
DP - arXiv.org
VL - 29
IS - 7
SP - 938
EP - 971
J2 - Math. Struct. Comp. Sci.
SN - 0960-1295, 1469-8072
UR - http://arxiv.org/abs/1709.00322
Y2 - 2019/11/21/20:35:15
KW - Bayesianism
KW - Categorical probability theory
ER -
TY - JOUR
TI - Categorical Aspects of Parameter Learning
AU - Jacobs, Bart
T2 - arXiv:1810.05814 [cs]
AB - Parameter learning is the technique for obtaining the probabilistic parameters in conditional probability tables in Bayesian networks from tables with (observed) data --- where it is assumed that the underlying graphical structure is known. There are basically two ways of doing so, referred to as maximal likelihood estimation (MLE) and as Bayesian learning. This paper provides a categorical analysis of these two techniques and describes them in terms of basic properties of the multiset monad M, the distribution monad D and the Giry monad G. In essence, learning is about the reltionships between multisets (used for counting) on the one hand and probability distributions on the other. These relationsips will be described as suitable natural transformations.
DA - 2018/10/13/
PY - 2018
DP - arXiv.org
UR - http://arxiv.org/abs/1810.05814
Y2 - 2019/11/21/20:38:28
KW - Bayesianism
KW - Categorical ML
KW - Categorical probability theory
KW - Machine learning
ER -
TY - JOUR
TI - The Logical Essentials of Bayesian Reasoning
AU - Jacobs, Bart
AU - Zanasi, Fabio
T2 - arXiv:1804.01193 [cs]
AB - This chapter offers an accessible introduction to the channel-based approach to Bayesian probability theory. This framework rests on algebraic and logical foundations, inspired by the methodologies of programming language semantics. It offers a uniform, structured and expressive language for describing Bayesian phenomena in terms of familiar programming concepts, like channel, predicate transformation and state transformation. The introduction also covers inference in Bayesian networks, which will be modelled by a suitable calculus of string diagrams.
DA - 2018/04/27/
PY - 2018
DP - arXiv.org
UR - http://arxiv.org/abs/1804.01193
Y2 - 2019/11/21/20:39:51
KW - Bayesianism
KW - Categorical probability theory
ER -
TY - JOUR
TI - From probability monads to commutative effectuses
AU - Jacobs, Bart
T2 - Journal of Logical and Algebraic Methods in Programming
AB - Eﬀectuses have recently been introduced as categorical models for quantum computation, with probabilistic and Boolean (classical) computation as special cases. These ‘probabilistic’ models are called commutative eﬀectuses, and are the focus of attention here. The paper describes the main known ‘probability’ monads: the monad of discrete probability measures, the Giry monad, the expectation monad, the probabilistic power domain monad, the Radon monad, and the Kantorovich monad. It also introduces successive properties that a monad should satisfy so that its Kleisli category is a commutative eﬀectus. The main properties are: partial additivity, strong aﬃneness, and commutativity. It is shown that the resulting commutative eﬀectus provides a categorical model of probability theory, including a logic using eﬀect modules with parallel and sequential conjunction, predicate- and state-transformers, normalisation and conditioning of states.
DA - 2018/01//
PY - 2018
DO - 10/gct2wr
DP - Crossref
VL - 94
SP - 200
EP - 237
LA - en
SN - 23522208
UR - https://linkinghub.elsevier.com/retrieve/pii/S2352220816301122
Y2 - 2019/11/28/14:39:17
KW - Categorical probability theory
KW - Effectus theory
ER -
TY - JOUR
TI - Denotational validation of higher-order Bayesian inference
AU - Ścibior, Adam
AU - Kammar, Ohad
AU - Vákár, Matthijs
AU - Staton, Sam
AU - Yang, Hongseok
AU - Cai, Yufei
AU - Ostermann, Klaus
AU - Moss, Sean K.
AU - Heunen, Chris
AU - Ghahramani, Zoubin
T2 - Proceedings of the ACM on Programming Languages
AB - We present a modular semantic account of Bayesian inference algorithms for probabilistic programming languages, as used in data science and machine learning. Sophisticated inference algorithms are often explained in terms of composition of smaller parts. However, neither their theoretical justification nor their implementation reflects this modularity. We show how to conceptualise and analyse such inference algorithms as manipulating intermediate representations of probabilistic programs using higher-order functions and inductive types, and their denotational semantics. Semantic accounts of continuous distributions use measurable spaces. However, our use of higher-order functions presents a substantial technical difficulty: it is impossible to define a measurable space structure over the collection of measurable functions between arbitrary measurable spaces that is compatible with standard operations on those functions, such as function application. We overcome this difficulty using quasi-Borel spaces, a recently proposed mathematical structure that supports both function spaces and continuous distributions. We define a class of semantic structures for representing probabilistic programs, and semantic validity criteria for transformations of these representations in terms of distribution preservation. We develop a collection of building blocks for composing representations. We use these building blocks to validate common inference algorithms such as Sequential Monte Carlo and Markov Chain Monte Carlo. To emphasize the connection between the semantic manipulation and its traditional measure theoretic origins, we use Kock's synthetic measure theory. We demonstrate its usefulness by proving a quasi-Borel counterpart to the Metropolis-Hastings-Green theorem.
DA - 2017/12/27/
PY - 2017
DO - 10.1145/3158148
DP - arXiv.org
VL - 2
IS - POPL
SP - 1
EP - 29
J2 - Proc. ACM Program. Lang.
SN - 24751421
UR - http://arxiv.org/abs/1711.03219
Y2 - 2019/10/10/11:49:49
ER -
TY - JOUR
TI - Quantum effect logic in cognition
AU - Jacobs, Bart
T2 - Journal of Mathematical Psychology
AB - This paper illustrates applications of a new, modern version of quantum logic in quantum cognition. The new logic uses ‘effects’ as predicates, instead of the more restricted interpretation of predicates as projections — which is used so far in this area. Effect logic involves states and predicates, validity and conditioning, and also state and predicate transformation via channels. The main aim of this paper is to demonstrate the usefulness of this effect logic in quantum cognition, via many high-level reformulations of standard examples. The usefulness of the logic is greatly increased by its implementation in the programming language Python.
DA - 2017/12/01/
PY - 2017
DO - 10/gcnkcj
DP - ScienceDirect
VL - 81
SP - 1
EP - 10
J2 - Journal of Mathematical Psychology
LA - en
SN - 0022-2496
UR - http://www.sciencedirect.com/science/article/pii/S0022249617300378
Y2 - 2019/11/22/22:19:41
KW - Categorical probability theory
KW - Effectus theory
KW - Psychology
ER -
TY - JOUR
TI - A Convenient Category for Higher-Order Probability Theory
AU - Heunen, Chris
AU - Kammar, Ohad
AU - Staton, Sam
AU - Yang, Hongseok
T2 - arXiv:1701.02547 [cs, math]
AB - Higher-order probabilistic programming languages allow programmers to write sophisticated models in machine learning and statistics in a succinct and structured way, but step outside the standard measure-theoretic formalization of probability theory. Programs may use both higher-order functions and continuous distributions, or even define a probability distribution on functions. But standard probability theory does not handle higher-order functions well: the category of measurable spaces is not cartesian closed. Here we introduce quasi-Borel spaces. We show that these spaces: form a new formalization of probability theory replacing measurable spaces; form a cartesian closed category and so support higher-order functions; form a well-pointed category and so support good proof principles for equational reasoning; and support continuous probability distributions. We demonstrate the use of quasi-Borel spaces for higher-order functions and probability by: showing that a well-known construction of probability theory involving random functions gains a cleaner expression; and generalizing de Finetti's theorem, that is a crucial theorem in probability theory, to quasi-Borel spaces.
DA - 2017/01/10/
PY - 2017
DP - arXiv.org
UR - http://arxiv.org/abs/1701.02547
Y2 - 2019/10/10/11:48:09
ER -
TY - MANSCPT
TI - Pointless learning (long version)
AU - Clerc, Florence
AU - Danos, Vincent
AU - Dahlqvist, Fredrik
AU - Garnier, Ilias
AB - Bayesian inversion is at the heart of probabilistic programming and more generally machine learning. Understanding inversion is made difficult by the pointful (kernel-centric) point of view usually taken in the literature. We develop a pointless (kernel-free) approach to inversion. While doing so, we revisit some foundational objects of probability theory, unravel their category-theoretical underpinnings and show how pointless Bayesian inversion sits naturally at the centre of this construction .
DA - 2017/01//
PY - 2017
DP - HAL Archives Ouvertes
UR - https://hal.archives-ouvertes.fr/hal-01429663
Y2 - 2019/11/24/12:02:56
KW - Bayesianism
KW - Categorical probability theory
KW - Purely theoretical
ER -
TY - JOUR
TI - A Formal Semantics of Influence in Bayesian Reasoning
AU - Jacobs, Bart
AU - Zanasi, Fabio
T2 - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
AB - This paper proposes a formal deﬁnition of inﬂuence in Bayesian reasoning, based on the notions of state (as probability distribution), predicate, validity and conditioning. Our approach highlights how conditioning a joint entwined/entangled state with a predicate on one of its components has ‘crossover’ inﬂuence on the other components. We use the total variation metric on probability distributions to quantitatively measure such inﬂuence. These insights are applied to give a rigorous explanation of the fundamental concept of d-separation in Bayesian networks.
DA - 2017///
PY - 2017
DO - 10/ggdgbc
DP - DataCite
LA - en
UR - http://drops.dagstuhl.de/opus/volltexte/2017/8089/
Y2 - 2019/11/24/12:11:15
KW - Bayesianism
KW - Categorical probability theory
KW - Programming language theory
KW - Semantics
ER -
TY - JOUR
TI - A Predicate/State Transformer Semantics for Bayesian Learning
AU - Jacobs, Bart
AU - Zanasi, Fabio
T2 - Electronic Notes in Theoretical Computer Science
T3 - The Thirty-second Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXII)
AB - This paper establishes a link between Bayesian inference (learning) and predicate and state transformer operations from programming semantics and logic. Specifically, a very general definition of backward inference is given via first applying a predicate transformer and then conditioning. Analogously, forward inference involves first conditioning and then applying a state transformer. These definitions are illustrated in many examples in discrete and continuous probability theory and also in quantum theory.
DA - 2016/10/05/
PY - 2016
DO - 10/ggdgbb
DP - ScienceDirect
VL - 325
SP - 185
EP - 200
J2 - Electronic Notes in Theoretical Computer Science
LA - en
SN - 1571-0661
UR - http://www.sciencedirect.com/science/article/pii/S1571066116300883
Y2 - 2019/11/24/12:04:12
KW - Bayesianism
KW - Categorical ML
KW - Categorical probability theory
KW - Effectus theory
KW - Programming language theory
KW - Semantics
ER -
TY - JOUR
TI - An Introduction to Effectus Theory
AU - Cho, Kenta
AU - Jacobs, Bart
AU - Westerbaan, Bas
AU - Westerbaan, Abraham
T2 - arXiv:1512.05813 [quant-ph]
AB - Effectus theory is a new branch of categorical logic that aims to capture the essentials of quantum logic, with probabilistic and Boolean logic as special cases. Predicates in effectus theory are not subobjects having a Heyting algebra structure, like in topos theory, but `characteristic' functions, forming effect algebras. Such effect algebras are algebraic models of quantitative logic, in which double negation holds. Effects in quantum theory and fuzzy predicates in probability theory form examples of effect algebras. This text is an account of the basics of effectus theory. It includes the fundamental duality between states and effects, with the associated Born rule for validity of an effect (predicate) in a particular state. A basic result says that effectuses can be described equivalently in both `total' and `partial' form. So-called `commutative' and `Boolean' effectuses are distinguished, for probabilistic and classical models. It is shown how these Boolean effectuses are essentially extensive categories. A large part of the theory is devoted to the logical notions of comprehension and quotient, which are described abstractly as right adjoint to truth, and as left adjoint to falisity, respectively. It is illustrated how comprehension and quotients are closely related to measurement. The paper closes with a section on `non-commutative' effectus theory, where the appropriate formalisation is not entirely clear yet.
DA - 2015/12/17/
PY - 2015
DP - arXiv.org
UR - http://arxiv.org/abs/1512.05813
Y2 - 2019/11/23/16:39:44
KW - Effectus theory
ER -
TY - JOUR
TI - Towards a Categorical Account of Conditional Probability
AU - Jacobs, Bart
AU - Furber, Robert
T2 - Electronic Proceedings in Theoretical Computer Science
AB - This paper presents a categorical account of conditional probability, covering both the classical and the quantum case. Classical conditional probabilities are expressed as a certain "triangle-fill-in" condition, connecting marginal and joint probabilities, in the Kleisli category of the distribution monad. The conditional probabilities are induced by a map together with a predicate (the condition). The latter is a predicate in the logic of effect modules on this Kleisli category. This same approach can be transferred to the category of C*-algebras (with positive unital maps), whose predicate logic is also expressed in terms of effect modules. Conditional probabilities can again be expressed via a triangle-fill-in property. In the literature, there are several proposals for what quantum conditional probability should be, and also there are extra difficulties not present in the classical case. At this stage, we only describe quantum systems with classical parametrization.
DA - 2015/11/04/
PY - 2015
DO - 10/ggdf9w
DP - arXiv.org
VL - 195
SP - 179
EP - 195
J2 - Electron. Proc. Theor. Comput. Sci.
SN - 2075-2180
UR - http://arxiv.org/abs/1306.0831
Y2 - 2019/11/21/20:40:59
KW - Categorical probability theory
KW - Effectus theory
ER -
TY - JOUR
TI - Bayesian machine learning via category theory
AU - Culbertson, Jared
AU - Sturtz, Kirk
T2 - arXiv:1312.1445 [math]
AB - From the Bayesian perspective, the category of conditional probabilities (a variant of the Kleisli category of the Giry monad, whose objects are measurable spaces and arrows are Markov kernels) gives a nice framework for conceptualization and analysis of many aspects of machine learning. Using categorical methods, we construct models for parametric and nonparametric Bayesian reasoning on function spaces, thus providing a basis for the supervised learning problem. In particular, stochastic processes are arrows to these function spaces which serve as prior probabilities. The resulting inference maps can often be analytically constructed in this symmetric monoidal weakly closed category. We also show how to view general stochastic processes using functor categories and demonstrate the Kalman filter as an archetype for the hidden Markov model.
DA - 2013/12/05/
PY - 2013
DP - arXiv.org
UR - http://arxiv.org/abs/1312.1445
Y2 - 2019/11/22/17:32:35
KW - Bayesianism
KW - Categorical ML
KW - Categorical probability theory
KW - Purely theoretical
ER -
TY - JOUR
TI - Distributing probability over non-determinism
AU - Varacca, Daniele
AU - Winskel, Glynn
T2 - Mathematical Structures in Computer Science
DA - 2006/02/21/
PY - 2006
DO - 10/czs9sx
DP - Crossref
VL - 16
IS - 01
SP - 87
LA - en
SN - 0960-1295, 1469-8072
UR - http://www.journals.cambridge.org/abstract_S0960129505005074
Y2 - 2019/11/26/20:30:24
KW - Categorical probability theory
KW - Denotational semantics
KW - Programming language theory
ER -
TY - JOUR
TI - What is a statistical model?
AU - McCullagh, Peter
T2 - The Annals of Statistics
DA - 2002/10//
PY - 2002
DO - 10/bkts3m
DP - Crossref
VL - 30
IS - 5
SP - 1225
EP - 1310
LA - en
UR - http://projecteuclid.org/euclid.aos/1035844977
Y2 - 2019/11/22/17:39:10
KW - Bayesianism
KW - Categorical ML
KW - Categorical probability theory
KW - Compendium
KW - Purely theoretical
KW - Statistical learning theory
ER -
TY - CONF
TI - Bisimulation for probabilistic transition systems: A coalgebraic approach
AU - de Vink, E. P.
AU - Rutten, J. J. M. M.
A2 - Degano, Pierpaolo
A2 - Gorrieri, Roberto
A2 - Marchetti-Spaccamela, Alberto
T3 - Lecture Notes in Computer Science
AB - The notion of bisimulation as proposed by Larsen and Skou for discrete probabilistic transition systems is shown to coincide with a coalgebraic definition in the sense of Aczel and Mendier in terms of a set functor. This coalgebraic formulation makes it possible to generalize the concepts to a continuous setting involving Borel probability measures. Under reasonable conditions, generalized probabilistic bisimilarity can be characterized categorically. Application of the final coalgebra paradigm then yields an internally fully abstract semantical domain with respect to probabilistic bisimulation.
C1 - Berlin, Heidelberg
C3 - Automata, Languages and Programming
DA - 1997///
PY - 1997
DO - 10/fcqzmk
DP - Springer Link
SP - 460
EP - 470
LA - en
PB - Springer
SN - 978-3-540-69194-5
ST - Bisimulation for probabilistic transition systems
KW - Categorical probability theory
KW - Coalgebras
KW - Denotational semantics
KW - Probabilistic transition systems
KW - Transition systems
ER -
TY - CONF
TI - A categorical approach to probability theory
AU - Giry, Michèle
A2 - Banaschewski, B.
T3 - Lecture Notes in Mathematics
C1 - Berlin, Heidelberg
C3 - Categorical Aspects of Topology and Analysis
DA - 1982///
PY - 1982
DO - 10/dtx5t5
DP - Springer Link
SP - 68
EP - 85
LA - en
PB - Springer
SN - 978-3-540-39041-1
KW - Categorical probability theory
ER -