Scaling Exact Inference for Discrete Probabilistic Programs

Abstract

Probabilistic programming languages (PPLs) are an expressive means of representing and reasoning about probabilistic models. The computational challenge of probabilistic inference remains the primary roadblock for applying PPLs in practice. Inference is fundamentally hard, so there is no one-size-fits all solution. In this work, we target scalable inference for an important class of probabilistic programs: those whose probability distributions are discrete. Discrete distributions are common in many fields, including text analysis, network verification, artificial intelligence, and graph analysis, but they prove to be challenging for existing PPLs. We develop a domain-specific probabilistic programming language called Dice that features a new approach to exact discrete probabilistic program inference. Dice exploits program structure in order to factorize inference, enabling us to perform exact inference on probabilistic programs with hundreds of thousands of random variables. Our key technical contribution is a new reduction from discrete probabilistic programs to weighted model counting (WMC). This reduction separates the structure of the distribution from its parameters, enabling logical reasoning tools to exploit that structure for probabilistic inference. We (1) show how to compositionally reduce Dice inference to WMC, (2) prove this compilation correct with respect to a denotational semantics, (3) empirically demonstrate the performance benefits over prior approaches, and (4) analyze the types of structure that allow Dice to scale to large probabilistic programs.

References in corpus (16)

• The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo
• Pyro: Deep Universal Probabilistic Programming
• Context-Specific Independence in Bayesian Networks
• Church: a language for generative models
• A Knowledge Compilation Map
• TensorFlow Distributions
• Inference and learning in probabilistic logic programs using weighted Boolean formulas
• The PITA System: Tabling and Answer Subsumption for Reasoning under Uncertainty
• Inference in Probabilistic Logic Programs using Weighted CNF's
• Automated Variational Inference in Probabilistic Programming
• Automatic Variational Inference in Stan
• Approximate Bayesian Image Interpretation using Generative Probabilistic Graphics Programs
• Particle Gibbs with Ancestor Sampling for Probabilistic Programs
• Tensor Variable Elimination for Plated Factor Graphs
• Divide, Conquer, and Combine: a New Inference Strategy for Probabilistic Programs with Stochastic Support
• Hamiltonian Monte Carlo for Probabilistic Programs with Discontinuities

Cited by in corpus (18)

• SPPL: Probabilistic Programming with Fast Exact Symbolic Inference
• This Is the Moment for Probabilistic Loops
• Symbolic Execution for Randomized Programs
• Inference of Probabilistic Programs with Moment-Matching Gaussian Mixtures
• Exact Recursive Probabilistic Programming
• Bit Blasting Probabilistic Programs
• Learning Proposals for Probabilistic Programs with Inference Combinators
• Probabilistic Inference in the Era of Tensor Networks and Differential Programming
• Guaranteed Bounds on Posterior Distributions of Discrete Probabilistic Programs with Loops
• AIA: A Customized Multi-core RISC-V SoC for Discrete Sampling Workloads in 16 nm
• Inference Plans for Hybrid Particle Filtering
• Scaling Optimization Over Uncertainty via Compilation
• Tuning Random Generators: Property-Based Testing as Probabilistic Programming
• flip-hoisting: Exploiting Repeated Parameters in Discrete Probabilistic Programs
• GradInf: Gradient Estimation as Probabilistic Inference
• On the Independencies Hidden in the Structure of a Probabilistic Logic Program
• Tensor Probabilistic Model Checking of Finite-Horizon Markov Chains (Extended Version)
• Logical Abstractions for Noisy Variational Quantum Algorithm Simulation