Source-linked AI summary
A New Approach to Probabilistic Programming Inference
Frank Wood, Jan Willem van de Meent, Vikash Mansinghka
TL;DR
Inference in expressive probabilistic programs must handle execution traces shaped by dynamic control flow and stochastic computation. The paper combines particle Markov chain Monte Carlo with probabilistic-program interpretation, yielding an easily parallelized approach that supports complex models and converges faster than single-site Metropolis-Hastings in the reported tests.
Problem
Probabilistic-program inference must characterize execution-trace distributions in expressive languages whose traces can involve complex dependencies and dynamic control flow.
Method
The approach uses particle Markov chain Monte Carlo, specifically Particle-Gibbs, with sequential Monte Carlo proposals for exploring execution traces.
Results
PMCMC converged faster than single-site Metropolis-Hastings for expressive models with dense conditional dependencies, even after normalizing for computational time.
Takeaways & Limitations
The approach supports accurate inference with complex control flow, stochastic recursion, and Bayesian nonparametric primitives while remaining easy to implement and parallelize.
Takeaways & Limitations
Finite-particle SMC is not directly viable for all probabilistic-program inference because of particle degeneracy and inefficiency with global, continuous parameters.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces a particle Markov chain Monte Carlo approach for exploring probable probabilistic-program execution traces. It supports expressive models and can be more efficient than earlier single-site Metropolis-Hastings samplers.
- The approach combines probabilistic programming with particle Markov chain Monte Carlo to explore and characterize probable execution traces.It is based on repeated simulation of the probabilistic program, making it easy to implement and parallelize.
- The updated paper reflects changes in the latest version of the Anglican language.
- It supports accurate inference in models with complex control flow, including stochastic recursion, and Bayesian nonparametric primitives.
- Experiments show that the approach can be more efficient than previously introduced single-site Metropolis-Hastings samplers.
2 Language
The language provides probabilistic-program constructs for random variables, observations, predictions, recursion, branching, and random processes. Its updated compiled syntax integrates with Clojure, while inference produces lazy sequences of execution states for downstream analysis.
- Language Evolution: The updated compiled Anglican version changes syntax and execution model without changing the paper’s substance or claims, but changes absolute inference times.The compiled version is generally ten to one hundred times faster than its interpreted ancestor.
- Original Venture-Style Syntax: The original Anglican syntax extends Scheme/Lisp with assume, observe, and predict directives for declarations, conditioning, and trace reporting.Assume declares generative random variables; observe constrains outputs using observed data; predict reports values from explored traces.
- Original Venture-Style Syntax: Anglican supports recursive evaluation, branching control flow, lambda-created procedures, and application counting as a computational cost proxy.
- Original Venture-Style Syntax: Random primitives include i.i.d. samplers such as normal and exchangeable stateful procedures such as crp and beta-bernoulli.
- Original Venture-Style Syntax: The interpreted language restricts observed expressions to built-in random primitives whose output likelihoods can be computed exactly.
- New Clojure-Style Syntax: The newer Anglican syntax integrates with Clojure through defquery, while supporting basic Clojure forms, selected macros, and selected higher-order functions.
- New Clojure-Style Syntax: The sample and observe forms operate on programmable distribution objects, and random processes represent non-i.i.d. sequences through produce and absorb operations.Produce returns the next-variable distribution; absorb updates the process after associating a value with that variable.
- New Clojure-Style Syntax: The predict form generates labeled output values, while doquery constructs lazy execution-state sequences containing predictions and optionally importance weights.These states can be consumed and analyzed by outer Clojure or Java programs.
3 Inference
The paper develops PMCMC inference for probabilistic programs by using SMC proposals to explore execution traces, including traces with variable numbers of random applications. Particle-Gibbs repeatedly reruns SMC while retaining a particle trace, enabling joint trace updates and parallel implementation.
- 3 Inference: Execution traces are sequences of memory states produced by program function applications, with random procedures creating branches in a many-worlds trace tree.The trace space can include different values and branching outcomes across independent program interpretations.
- 3 Inference: Trace probabilities accommodate observe likelihoods and random procedure outputs whose number and type may vary across program traces.Variable references define conditional dependencies, so each random result need not depend on every earlier application.
- 3 Inference: SMC targets the distribution of random procedure outputs conditioned on observations, but finite-particle SMC alone suffers from particle degeneracy and inefficiency with global continuous parameters.The method constructs intermediate distributions leading to the conditional trace distribution.
- 3.1 A New Approach: PMCMC uses SMC proposals inside an MH algorithm, allowing updates to potentially many trace variables rather than only one variable at a time.The paper focuses on Particle-Gibbs, which reinserts a retained particle trace during later SMC sweeps and is always accepted as an MH transition.
- 3.1 A New Approach: Particle-Gibbs reruns SMC over program lines, forks interpreter states, interprets lines, and resamples weighted particle states while retaining the selected trace and its weight.The algorithm’s retained-particle bookkeeping preserves the outermost observe likelihood weights for the next sweep.
- 3.1 A New Approach: The algorithm is presented expositionally even though more efficient PMCMC implementations can avoid forking unless an observe has just been interpreted.The paper describes interpreter copying and line-by-line execution as part of the algorithmic presentation.
- 3.2 Random Database: RDB instead performs single-site MH updates by resampling one random variable in an execution trace and comparing the old and new trace joint distributions.Its data structure stores trace variables, draw parameters, and log probabilities, while interpretation is deterministic conditional on the variables.
4 Testing
The paper uses a three-level testing methodology to check probabilistic program interpreters and samplers, culminating in conditional measure tests that compare inference engines. Figure 1 compares PMCMC with 100 particles against RDB on conditional measure test performance.
- 4 Testing: Correctness testing covers unit tests, measure tests, and conditional measure tests for both interpreters and general-purpose samplers.The methodology addresses software correctness at progressively more inference-relevant levels.
- 4 Testing: Unit tests verify deterministic interpretation, while measure tests compare unconditioned assume-and-predict outputs against exhaustive, analytic, or other ground truth.Measure tests produce ancestral samples without observe statements.
- 4.2 Conditional Measure Tests: Conditional measure tests add observe statements that constrain or weight execution traces and engage the full inference machinery.Their performance is measured like measure-test performance and used to compare probabilistic programming inference engines.
- 4.2 Conditional Measure Tests: Figure 1 compares conditional measure test performance for PMCMC with 100 particles versus RDB.The supplied caption identifies the two inference engines and the particle count.
5 Inference Engine Comparison
The comparison evaluates PMCMC against RDB across conditional-measure programs, finding faster convergence for expressive models with rich conditional dependencies and, for some programs, in direct computational-cost comparisons.
- PMCMC converges faster than RDB for conditional-measure programs corresponding to expressive probabilistic graphical models with rich conditional dependencies.
- The four tests cover HMM state estimation, Dirichlet-process Gaussian mixtures, branching recursion, and Marsaglia rejection sampling.The first two are expressive models; the latter two test correctness, completeness, and performance on simpler programs.
- PMCMC uses 100 particles in a single-threaded interpreter, with results summarized by percentile curves over 25 runs.Distances are computed from running averages against ground truth, and lower values are better.
- For some programs, PMCMC converges faster than RDB in wall-clock time and relative to function-application counts.Equivalent results were obtained relative to evaluation counts.
Original (deprecated)
The HMM and Dirichlet-process mixture examples evaluate inference over latent states and cluster counts, using program-specific posterior comparisons against ground truth.
- HMM: The HMM program performs latent-state inference for a three-state model with one-dimensional Gaussian observations and known parameters.Its observations are organized in temporal order through the observe statements.
- HMM: The KL* distance sums divergences between running estimated state occupancies and true marginal probabilities across HMM time steps.The comparison includes the initial state and one trailing predictive state.
- HMM: RDB produces a reasonable HMM posterior approximation but converges more slowly and retains greater residual error than the comparison target.
Original (deprecated)
The DP mixture and branching examples probe inference under nonparametric clustering, recursion, and variable execution paths, with PMCMC outperforming RDB in the antagonistic mixture setting.
- DP mixture: The DP mixture ground truth over cluster counts was computed by exhaustively enumerating all data partitions.
- DP mixture: The DP mixture program intentionally retained continuous likelihood parameters and nonoptimal observe ordering, making it antagonistic to PMCMC.
- DP mixture: Despite those design choices, PMCMC outperforms RDB per simulation, wall-clock time, and apply count.
- Branching: The branching implementation uses recursive Fibonacci computation, sampled branching logic, a Poisson observation, and a prediction of the sampled count.
Original (deprecated)
The branching program tests inference in a model without a corresponding graphical model, where control logic and execution paths vary in sampled values.
- The branching program has no corresponding graphical model and tests inference with control logic and variable-length execution paths.
- Its fourth plot examines a large mismatch between prior and posterior distributions, a setting where rejection and importance sampling are likely to be ineffective.
- With one observation and one named random variable, PMCMC and RDB achieve essentially indistinguishable performance when normalized to simulation.
5.4 Marsaglia
The Marsaglia test program uses recursive rejection sampling to generate an unknown number of internal random variables. It illustrates a case where PMCMC may not be more efficient than RDB because exploring rejected traces incurs computational cost.
- Test program: The Anglican implementation samples x and y uniformly, accepts when their squared radius is below one, and otherwise recurses.The recursive implementation applies the Marsaglia transformation after acceptance.
- Test program: Marsaglia infers an unknown Gaussian mean generated by an Anglican implementation of the rejection-form Box–Muller algorithm.The program uses recursive calls and can generate an unknown number of internal random variables.
- Limitation: Marsaglia may require many recursive calls because rejection sampling can produce unnecessarily long execution traces.This recursive structure is the stated source of the program’s computational difficulty.
- Limitation: RDB may be faster than PMCMC on Marsaglia because RDB’s implicit geometric prior on trace length avoids excess computation from rejected traces.The paper presents this explanation as a conjecture.
5.5 Line Permutation
Line ordering can affect PMCMC inference efficiency, whereas RDB performance is reported as independent of ordering. In the DP Mixture tests, PMCMC outperformed RDB for every reordering, and the original ordering was not optimal for PMCMC.
- Line permutation experiment: PMCMC and RDB were compared across random permutations of the HMM and DP Mixture program lines.The comparison included the unmodified and reversed orderings and used median results over twenty-five PMCMC runs per permutation.
- DP Mixture: PMCMC outperformed RDB on all DP Mixture program reorderings.
- DP Mixture: The original DP Mixture program ordering was not optimal for PMCMC inference.
- Optimization: Performance can be manually influenced by moving observe statements near the program front or generating latent variables lazily rather than eagerly.
6 Discussion
PMCMC appears to converge faster than single-site Metropolis–Hastings for expressive models with dense conditional dependencies, even after accounting for particle-execution computation. The discussion also identifies computational and language-level limitations and possible hybrid inference strategies.
- Main result: PMCMC appears to converge faster than single-site Metropolis–Hastings for expressive models with dense conditional dependencies.
- Main result: The convergence comparison remains favorable after normalizing for computational time, including computation performed across all particle executions.
- Limitations: Optimal parallelism remains unresolved because suboptimal memory organization causes excessive locking overhead.
- Limitations: Forcing observe statements to be noisy requires language- and interpreter-level restrictions and checks.
- Future directions: Inference performance might improve by partitioning variables and assigning some to plain MH and others to conditional SMC.The paper also identifies combining conditional SMC with RDB MH as one simple option.