Guaranteed Bounds for Posterior Inference in Universal Probabilistic Programming

Beutner, Raven and Ong, C.H. Luke and Zaiser, Fabian
(2022) Guaranteed Bounds for Posterior Inference in Universal Probabilistic Programming.
In: PLDI 2022, San Diego, CA, USA.
Conference: PLDI ACM-SIGPLAN Conference on Programming Language Design and Implementation
(In Press)

[img] Text
main.pdf - Accepted Version
Restricted to Registered users only

Download (893kB)


We propose a new method to approximate the posterior distribution of probabilistic programs by means of computing guaranteed bounds. The starting point of our work is an interval-based trace semantics for a recursive, higher-order probabilistic programming language with continuous distributions. Taking the form of (super-/subadditive) measures, these lower/upper bounds are non-stochastic and provably correct: using the semantics, we prove that the actual posterior of a given program is sandwiched between the lower and upper bounds (soundness); moreover, the bounds converge to the posterior (completeness). As a practical and sound approximation, we introduce a weight-aware interval type system, which automatically infers interval bounds on not just the return value but also the weight of program executions, simultaneously. We have built a tool implementation, called GuBPI, which automatically computes these posterior lower/upper bounds. Our evaluation on examples from the literature shows that the bounds are useful, and can even be used to recognise wrong outputs from stochastic posterior inference procedures.


Actions (login required)

View Item View Item