Expectation Programming: Adapting Probabilistic Programming Systems to Estimate Expectations Efficiently

Tim Reichelt, Adam Golinski, Luke Ong, Tom Rainforth

Abstract

We show that the standard computational pipeline of probabilistic programming systems (PPSs) can be inefficient for estimating expectations and introduce the concept of expectation programming to address this. In expectation programming, the aim of the backend inference engine is to directly estimate expected return values of programs, as opposed to approximating their conditional distributions. This distinction, while subtle, allows us to achieve substantial performance improvements over the standard PPS computational pipeline by tailoring computation to the expectation we care about. We realize a particular instance of our expectation programming concept, Expectation Programming in Turing (EPT), by extending the PPS Turing to allow so-called target-aware inference to be run automatically. We then verify the statistical soundness of EPT theoretically, and show that it provides substantial empirical gains in practice.

Introduction

In many scientific and engineering applications, the ultimate goal of probabilistic modeling is not to obtain the full posterior distribution, but rather to compute an expectation. For instance, in Bayesian decision theory, one often seeks to minimize an expected loss. Standard Probabilistic Programming Systems (PPSs) typically follow a "target-unaware" pipeline: they first approximate the posterior distribution and then average the function of interest over samples drawn from this approximation.

This approach can be highly inefficient, especially when the function of interest is concentrated in low-probability regions of the posterior. This paper proposes Expectation Programming, a paradigm shift where the inference engine is made "target-aware," directly optimizing for the estimation of the expectation.

Methodology: Expectation Programming in Turing (EPT)

The authors introduce Expectation Programming in Turing (EPT), which implements this concept through source-code transformations.

The TABI Framework

EPT leverages Target-Aware Bayesian Inference (TABI). The core mathematical insight is to decompose the expectation $\mathbb{E}_{\pi(x)}[f(x)]$ into three marginal likelihoods (normalization constants): $Z_1^+$ (where $f$ is positive), $Z_1^-$ (where $f$ is negative), and $Z_2$ (the standard evidence).

Source-Code Transformation

Using a new @expectation macro, EPT automatically rewrites a user's probabilistic program into three separate Turing models. By inserting terms like @addlogprob!(log(max(f(x), 0))), the system forces the inference engine to focus its computational budget on regions that contribute most to the expectation. This transformation makes the inference process inherently aware of the target function $f$.

Inference Engine

Since the method relies on marginal likelihood estimation, the authors implemented an Annealed Importance Sampling (AnIS) engine for Turing. This choice is particularly effective for high-dimensional spaces where standard MCMC might struggle to capture the relevant tails of the distribution.

Experimental Evaluation

EPT was evaluated against standard "target-unaware" baselines (standard AnIS and MCMC) on three benchmarks:

  • Gaussian Posterior Predictive: A synthetic case with analytical ground truth.
  • SIR Epidemiology Model: Estimating the expected "cost" of an outbreak based on reproduction rates.
  • Radon Hierarchical Model: A real-world Bayesian model for household radon levels.

Results

The empirical results demonstrate that EPT provides orders-of-magnitude improvements in both accuracy and reliability.

Relative Squared Error (RSE) and Effective Sample Size (ESS) comparison. EPT (blue) shows significantly lower error and higher sample efficiency than standard AnIS (red) and MCMC (green).

As shown in the figures, EPT consistently achieves a lower Relative Squared Error (RSE) for the same computational cost. Furthermore, the Effective Sample Size (ESS) for the target quantity is significantly higher, indicating that the samples generated by EPT are much more informative for the specific expectation being calculated.

Performance comparison on a benchmark where standard MCMC fails. EPT maintains low RSE and high ESS, while MCMC (green) fails to reduce error significantly.

In challenging scenarios like the Radon hierarchical model, standard Hamiltonian Monte Carlo (MCMC) often fails to capture high-cost regions, leading to estimates that are significantly biased. In contrast, EPT's target-aware approach provides stable and accurate results even when standard methods struggle.

Conclusion

Expectation Programming represents a significant advancement for PPSs used in decision-making and risk assessment. By making the inference engine aware of the final goal, EPT achieves substantial gains in efficiency and accuracy. Future work includes extending this framework to handle complex dynamic return types and exploring automatic synthesis of control variates for further variance reduction.

Summary updated

Abstract

We show that the standard computational pipeline of probabilistic programming systems (PPSs) can be inefficient for estimating expectations and introduce the concept of expectation programming to address this. In expectation programming, the aim of the backend inference engine is to directly estimate expected return values of programs, as opposed to approximating their conditional distributions. This distinction, while subtle, allows us to achieve substantial performance improvements over the standard PPS computational pipeline by tailoring computation to the expectation we care about. We realize a particular instance of our expectation programming concept, Expectation Programming in Turing (EPT), by extending the PPS Turing to allow so-called target-aware inference to be run automatically. We then verify the statistical soundness of EPT theoretically, and show that it provides substantial empirical gains in practice.
BibTeX
@inproceedings{reichelt2022expectation,
  author = {Tim Reichelt and Adam Golinski and Luke Ong and Tom Rainforth},
  title = {{Expectation Programming: Adapting Probabilistic Programming Systems to Estimate Expectations Efficiently}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=H0gOIL8j9xc},
}
Figure