TY - JOUR
TI - Reactive Probabilistic Programming
AU - Baudart, Guillaume
AU - Mandel, Louis
AU - Atkinson, Eric
AU - Sherman, Benjamin
AU - Pouzet, Marc
AU - Carbin, Michael
T2 - arXiv:1908.07563 [cs]
AB - Synchronous reactive languages were introduced for designing and implementing real-time control software. These domain-specific languages allow for writing a modular and mathematically precise specification of the system, enabling a user to simulate, test, verify, and, finally, compile the system into executable code. However, to date these languages have had limited modern support for modeling uncertainty -- probabilistic aspects of the software's environment or behavior -- even though modeling uncertainty is a primary activity when designing a control system. In this paper we extend Z\'elus, a synchronous programming language, to deliver ProbZ\'elus, the first synchronous probabilistic programming language. ProbZ\'elus is a probabilistic programming language in that it provides facilities for probabilistic models and inference: inferring latent model parameters from data. We present ProbZ\'elus's measure-theoretic semantics in the setting of probabilistic, stateful stream functions. We then demonstrate a semantics-preserving compilation strategy to a first-order functional core calculus that lends itself to a simple semantic presentation of ProbZ\'elus's inference algorithms. We also redesign the delayed sampling inference algorithm to provide bounded and streaming delayed sampling inference for ProbZ\'elus models. Together with our evaluation on several reactive programs, our results demonstrate that ProbZ\'elus provides efficient, bounded memory probabilistic inference.
DA - 2019/08/20/
PY - 2019
DP - arXiv.org
UR - http://arxiv.org/abs/1908.07563
Y2 - 2019/11/28/10:25:56
KW - Bayesian inference
KW - Denotational semantics
KW - Implementation
KW - Probabilistic programming
KW - Programming language theory
ER -
TY - CONF
TI - The Geometry of Bayesian Programming
AU - Dal Lago, Ugo
AU - Hoshino, Naohiko
DA - 2019/06/01/
PY - 2019
DO - 10/ggdk85
DP - ResearchGate
SP - 1
EP - 13
KW - Bayesian inference
KW - Denotational semantics
KW - Linear logic
KW - Probabilistic programming
KW - Programming language theory
KW - Rewriting theory
KW - Transition systems
ER -
TY - JOUR
TI - A Domain Theory for Statistical Probabilistic Programming
AU - Vákár, Matthijs
AU - Kammar, Ohad
AU - Staton, Sam
T2 - arXiv:1811.04196 [cs]
AB - We give an adequate denotational semantics for languages with recursive higher-order types, continuous probability distributions, and soft constraints. These are expressive languages for building Bayesian models of the kinds used in computational statistics and machine learning. Among them are untyped languages, similar to Church and WebPPL, because our semantics allows recursive mixed-variance datatypes. Our semantics justifies important program equivalences including commutativity. Our new semantic model is based on `quasi-Borel predomains'. These are a mixture of chain-complete partial orders (cpos) and quasi-Borel spaces. Quasi-Borel spaces are a recent model of probability theory that focuses on sets of admissible random elements. Probability is traditionally treated in cpo models using probabilistic powerdomains, but these are not known to be commutative on any class of cpos with higher order functions. By contrast, quasi-Borel predomains do support both a commutative probabilistic powerdomain and higher-order functions. As we show, quasi-Borel predomains form both a model of Fiore's axiomatic domain theory and a model of Kock's synthetic measure theory.
DA - 2018/11/10/
PY - 2018
DP - arXiv.org
UR - http://arxiv.org/abs/1811.04196
Y2 - 2019/10/10/11:49:16
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 - CHAP
TI - Commutative Semantics for Probabilistic Programming
AU - Staton, Sam
T2 - Programming Languages and Systems
A2 - Yang, Hongseok
AB - We show that a measure-based denotational semantics for probabilistic programming is commutative. The idea underlying probabilistic programming languages (Anglican, Church, Hakaru, ...) is that programs express statistical models as a combination of prior distributions and likelihood of observations. The product of prior and likelihood is an unnormalized posterior distribution, and the inference problem is to ﬁnd the normalizing constant. One common semantic perspective is thus that a probabilistic program is understood as an unnormalized posterior measure, in the sense of measure theory, and the normalizing constant is the measure of the entire semantic domain.
CY - Berlin, Heidelberg
DA - 2017///
PY - 2017
DP - Crossref
VL - 10201
SP - 855
EP - 879
LA - en
PB - Springer Berlin Heidelberg
SN - 978-3-662-54433-4 978-3-662-54434-1
UR - http://link.springer.com/10.1007/978-3-662-54434-1_32
Y2 - 2019/11/23/16:35:50
KW - Bayesianism
KW - Probabilistic programming
KW - Programming language theory
KW - Semantics
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 - Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints
AU - Staton, Sam
AU - Yang, Hongseok
AU - Heunen, Chris
AU - Kammar, Ohad
AU - Wood, Frank
T2 - Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science - LICS '16
AB - We study the semantic foundation of expressive probabilistic programming languages, that support higher-order functions, continuous distributions, and soft constraints (such as Anglican, Church, and Venture). We define a metalanguage (an idealised version of Anglican) for probabilistic computation with the above features, develop both operational and denotational semantics, and prove soundness, adequacy, and termination. They involve measure theory, stochastic labelled transition systems, and functor categories, but admit intuitive computational readings, one of which views sampled random variables as dynamically allocated read-only variables. We apply our semantics to validate nontrivial equations underlying the correctness of certain compiler optimisations and inference algorithms such as sequential Monte Carlo simulation. The language enables defining probability distributions on higher-order functions, and we study their properties.
DA - 2016///
PY - 2016
DO - 10/ggdf97
DP - arXiv.org
SP - 525
EP - 534
ST - Semantics for probabilistic programming
UR - http://arxiv.org/abs/1601.04943
Y2 - 2019/11/23/16:36:30
KW - Bayesianism
KW - Probabilistic programming
KW - Programming language theory
KW - Semantics
ER -