Guaranteed Bounds for Posterior Inference in Universal Probabilistic Programming

(2022) Guaranteed Bounds for Posterior Inference in Universal Probabilistic Programming. (In Press)

Text main.pdf - Accepted Version Restricted to Registered users only Download (893kB)

Abstract

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.

Item Type:	Conference or Workshop Item (A Paper) (Paper)
Conference:	PLDI ACM-SIGPLAN Conference on Programming Language Design and Implementation
Depositing User:	Raven Beutner
Date Deposited:	01 Jun 2022 08:15
Last Modified:	01 Jun 2022 08:15
Primary Research Area:	NRA1: Trustworthy Information Processing
URI:	https://publications.cispa.saarland/id/eprint/3704

Actions

Actions (login required)

View Item