PoP Seminar Talk

Computability and Symmetry in Probabilistic Programming

Cameron Freer, Research Scientist, Massachusetts Institute of Technology
Friday, 20 September, 2024; 2:00pm
GHC 6501
Host: Feras Saad

Abstract

We consider the computable content of several key theorems in probability theory, and discuss their implications for the design of probabilistic programming languages.

A random variable is said to be exchangeable when its distribution does not depend on the ordering of the underlying elements. Sequences, arrays, graphs, and other data structures satisfying this symmetry condition are models for homogeneous data sets and serve as building blocks in Bayesian nonparametric statistics. Representation theorems by de Finetti, Aldous, Hoover, and Kallenberg show that exchangeability gives rise to conditional independence. We establish both positive and negative computable versions of these results, and explore the consequences for sequential and parallel implementations of exchangeable objects in code.

Bayes’ theorem describes conditional probabilities, and is fundamental in probabilistic inference. We show that not every computable joint distribution admits a computable conditional distribution, and examine the implications for automating Bayesian inference.

This talk is based on joint work with Nathanael Ackerman, Jeremy Avigad, Daniel Roy, and Jason Rute.

Bio

Cameron Freer is a Research Scientist in the Department of Brain and Cognitive Sciences at the Massachusetts Institute of Technology and a member of the MIT Probabilistic Computing Project. His research explores interactions of randomness and computation, and focuses on the foundations of probabilistic computing, efficient samplers and testing methods for probabilistic inference, and the mathematics of random structures. Cameron received his PhD in Mathematics from Harvard University advised by Gerald Sacks, and has held positions at the University of Hawaii, Keio University, and several industry research labs.