SPPL: Probabilistic Programming with Fast Exact Symbolic Inference

Abstract

We present the Sum-Product Probabilistic Language (SPPL), a new probabilistic programming language that automatically delivers exact solutions to a broad range of probabilistic inference queries. SPPL translates probabilistic programs into sum-product expressions, a new symbolic representation and associated semantic domain that extends standard sum-product networks to support mixed-type distributions, numeric transformations, logical formulas, and pointwise and set-valued constraints. We formalize SPPL via a novel translation strategy from probabilistic programs to sum-product expressions and give sound exact algorithms for conditioning on and computing probabilities of events. SPPL imposes a collection of restrictions on probabilistic programs to ensure they can be translated into sum-product expressions, which allow the system to leverage new techniques for improving the scalability of translation and inference by automatically exploiting probabilistic structure. We implement a prototype of SPPL with a modular architecture and evaluate it on benchmarks the system targets, showing that it obtains up to 3500x speedups over state-of-the-art symbolic systems on tasks such as verifying the fairness of decision tree classifiers, smoothing hidden Markov models, conditioning transformed random variables, and computing rare event probabilities.

References in corpus (16)

• Church: a language for generative models
• A Knowledge Compilation Map
• Sum-Product Networks: A New Deep Architecture
• Complexity of Inference in Graphical Models
• Scaling Exact Inference for Discrete Probabilistic Programs
• Automated Variational Inference in Probabilistic Programming
• Inference in Probabilistic Logic Programs using Weighted CNF's
• SPFlow: An Easy and Extensible Library for Deep Probabilistic Learning using Sum-Product Networks
• Bayesian Synthesis of Probabilistic Programs for Automatic Data Modeling
• A Dynamic Programming Algorithm for Inference in Recursive Probabilistic Programs
• Bayesian Learning of Sum-Product Networks
• Discrete-Continuous Mixtures in Probabilistic Programming: Generalized Semantics and Inference Algorithms
• Probabilistic Data Analysis with Probabilistic Programming
• Temporally-Reweighted Chinese Restaurant Process Mixtures for Clustering, Imputing, and Forecasting Multivariate Time Series
• Detecting Dependencies in Sparse, Multivariate Databases Using Probabilistic Programming and Non-parametric Bayes
• Probabilistic Search for Structured Data via Probabilistic Programming and Nonparametric Bayes

Cited by in corpus (9)

• This Is the Moment for Probabilistic Loops
• Inference of Probabilistic Programs with Moment-Matching Gaussian Mixtures
• Exact Recursive Probabilistic Programming
• Bit Blasting Probabilistic Programs
• GenSQL: A Probabilistic Programming System for Querying Generative Models of Database Tables
• Guaranteed Bounds on Posterior Distributions of Discrete Probabilistic Programs with Loops
• Scaling Optimization Over Uncertainty via Compilation
• GradInf: Gradient Estimation as Probabilistic Inference
• Random Variate Generation with Formal Guarantees