Divide, Conquer, and Combine: a New Inference Strategy for Probabilistic Programs with Stochastic Support

Abstract

Universal probabilistic programming systems (PPSs) provide a powerful framework for specifying rich probabilistic models. They further attempt to automate the process of drawing inferences from these models, but doing this successfully is severely hampered by the wide range of non--standard models they can express. As a result, although one can specify complex models in a universal PPS, the provided inference engines often fall far short of what is required. In particular, we show that they produce surprisingly unsatisfactory performance for models where the support varies between executions, often doing no better than importance sampling from the prior. To address this, we introduce a new inference framework: Divide, Conquer, and Combine, which remains efficient for such models, and show how it can be implemented as an automated and generic PPS inference engine. We empirically demonstrate substantial performance improvements over existing approaches on three examples.

Published at the 37th International Conference on Machine Learning (ICML 2020)

References in corpus (17)

• MCMC using Hamiltonian dynamics
• Church: a language for generative models
• Structure Discovery in Nonparametric Regression through Compositional Kernel Search
• Layered Adaptive Importance Sampling
• Deep Probabilistic Programming
• Automated Variational Inference in Probabilistic Programming
• Deep Amortized Inference for Probabilistic Programs
• C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching
• Bayesian Inference in Monte-Carlo Tree Search
• Interacting Particle Markov Chain Monte Carlo
• Learning Probabilistic Programs
• Time Series Structure Discovery via Probabilistic Program Synthesis
• Inference Trees: Adaptive Inference with Exploration
• Probabilistic structure discovery in time series data
• On Exploration, Exploitation and Learning in Adaptive Importance Sampling
• Maximum a Posteriori Estimation by Search in Probabilistic Programs
• Output-Sensitive Adaptive Metropolis-Hastings for Probabilistic Programs

Cited by in corpus (3)

• Scaling Exact Inference for Discrete Probabilistic Programs
• Densities of Almost Surely Terminating Probabilistic Programs are Differentiable Almost Everywhere
• Control-Data Separation and Logical Condition Propagation for Efficient Inference on Probabilistic Programs