Probabilistic programming is a programming paradigm for expressing flexible probabilistic models. Implementations of probabilistic programming languages employ a variety of inference algorithms, where sequential Monte Carlo methods are commonly used. A problem with current state-of-the-art implementations using sequential Monte Carlo inference is the alignment of program synchronization points. We propose a new static analysis approach based on the 0-CFA algorithm for automatically aligning higher-order probabilistic programs. We evaluate the automatic alignment on a phylogenetic model, showing a significant decrease in runtime and increase in accuracy.
Naturally, the work most closely related to ours can be found in papers on universal probabilistic programming languages using smc , such as WebPPL @cite_23 , Anglican @cite_19 , and Birch @cite_7 . Both WebPPL and Anglican are higher-order, functional ppl , while Birch is an imperative, object-oriented ppl . Anglican includes many smc algorithms, including different variations of @cite_19 . Anglican also includes various mcmc methods. WebPPL includes fewer inference algorithms, but both smc and mcmc methods are available. Birch performs smc inference in combination with using closed-form optimizations at runtime, automatically yielding a more optimized version of smc taking advantage of and . None of the languages above, however, address the alignment issue presented in this article. In essence, the programmer needs to be aware of the internals of the smc inference algorithm to write efficient models---. Optimally, we would like the model and the inference to be as independent as possible. This is the goal of the work in this paper.
@cite_19 @cite_7 @cite_23
2950113781 2745919252
We introduce and demonstrate a new approach to inference in expressive probabilistic programming languages based on particle Markov chain Monte Carlo. Our approach is simple to implement and easy to parallelize. It applies to Turing-complete probabilistic programming languages and supports accurate inference in models that make use of complex control flow, including stochastic recursion. It also includes primitives from Bayesian nonparametric statistics. Our experiments show that this approach can be more efficient than previously introduced single-site Metropolis-Hastings methods. We introduce a dynamic mechanism for the solution of analytically-tractable substructure in probabilistic programs, using conjugate priors and affine transformations to reduce variance in Monte Carlo estimators. For inference with Sequential Monte Carlo, this automatically yields improvements such as locally-optimal proposals and Rao-Blackwellization. The mechanism maintains a directed graph alongside the running program that evolves dynamically as operations are triggered upon it. Nodes of the graph represent random variables, edges the analytically-tractable relationships between them. Random variables remain in the graph for as long as possible, to be sampled only when they are used by the program in a way that cannot be resolved analytically. In the meantime, they are conditioned on as many observations as possible. We demonstrate the mechanism with a few pedagogical examples, as well as a linear-nonlinear state-space model with simulated data, and an epidemiological model with real data of a dengue outbreak in Micronesia. In all cases one or more variables are automatically marginalized out to significantly reduce variance in estimates of the marginal likelihood, in the final case facilitating a random-weight or pseudo-marginal-type importance sampler for parameter estimation. We have implemented the approach in Anglican and a new probabilistic programming language called Birch.