Abstract

When is Bayesian reasoning possible? and when is it efficient?

There has been a recent surge of interest in probabilistic programming languages and general-purpose inference engines. By providing languages for specifying large, modular, potentially recursively-defined probabilistic models, these systems make it possible to tackle very complex inductive inference problems, opening up new avenues for AI and applications.

We present recent results elucidating aspects of the theoretical underpinnings of probabilistic programming systems, especially those whose underlying probabilistic languages have, in a technical sense, the same expressive power as probabilistic Turing machines. This algorithmic perspective on probability distributions, combined with new general purpose Monte Carlo inference strategies, presents a host of challenges and opportunities for theoretical computer science.

In particular, we investigate the class of computable probability distributions—-distributions for which there exists a probabilistic program for generating exact samples—-and explore the fundamental limitations on performing Bayesian reasoning with probabilistic program representations. We ask, when does a conditional distribution have such a representation and when can we compute it? In addition to highlighting some positive results demonstrating that Bayesian reasoning is possible when the prior distribution has additional structure such as exchangeability or noise, we prove the nonexistence of algorithms (even inefficient ones) for Bayesian reasoning in the general case. We close with some complexity-theoretic aspects.