Linguistic Approaches to Probabilistic Programming: Monads of Measures and Symbolic Bayesian Inference.

Abstract

Probabilistic inference is a form of backward reasoning: from observations of the effects of a probabilistic process, it infers information about causes. The task of inference can be greatly eased by using a probabilistic programming language, which requires only a purely forward description of a probabilistic computational process. Although inference maps effects to causes, a forward description need only map causes to effects. Using a simple example involving only discrete values, we'll illustrate inference from such descriptions, then go on to talk semantics.

The semantics of probabilistic computation is best described by underlying mathematical structures that capture both measure-theoretic and statistical interpretations. We'll look at the probability monad and the monad of measures, mentioning advantages and disadvantages of each.

Semantics becomes much harder when we introduce continuous probability. The major challenge is how to account for exact, point-like observations of continuous variables. Such observations, by definition, have zero probability, making the obvious Bayesian computations unhelpful. Problems created by zero-probability observations will be illustrated using a form of Borel's paradox. We handle such observations using a new method of inference that changes the paradigm of what it means to observe data. Using this changed paradigm, we have developed a new method of exact Bayesian inference that avoids Borel's paradox and produces exact results. The new method, called automatic disintegration, works purely by symbolic manipulation.

The work presented is joint work with Chung-Chieh Shan of Indiana University and Mitchell Wand of Northeastern University. It is funded by the PPAML program of the Defense Advanced Research Projects Agency (DARPA).

Bio

Norman Ramsey earned the PhD in computer science at Princeton in 1993. He is Associate Professor of Computer Science at Tufts, which he joined after eight years as Assistant and Associate Professor at Harvard. He has also held faculty appointments at the University of Virginia and at Purdue, as well as research positions at Bellcore, Bell Labs, and Microsoft Research. He was a Hertz Fellow and an Alfred P. Sloan Research Fellow.

Professor Ramsey has served repeatedly on program committees for three of the four major conferences in programming languages---the International Conference on Functional Programming (ICFP), the Conference on Programming Language Design and Implementation (PLDI), and the Symposium on Principles of Programming Languages (POPL)---as well as for other conferences and workshops. He was Program Chair of ICFP 2007 and has served two terms on the SIGPLAN Executive Committee. He is a member of the editorial board of the Journal of Functional Programming and also a member of IFIP Working Group 2.8 (Functional Programming).

Professor Ramsey's work spans the range from theory to practice and covers topics in both programming languages and software engineering. He has published in POPL, PLDI, ICFP, ICSE, FSE, JFP, and TOPLAS. He is best known for work on low-level programming-language infrastructure: code generation, debugging, linking, binary translation, register allocation, and so on.