TL;DR
This paper introduces "expectation programming," a new paradigm for probabilistic programming systems that directly estimates expected values of program outputs, rather than approximating the full conditional distribution. By adapting inference engines to be "target-aware" of the specific expectation being computed, they achieve significant performance improvements over standard methods.
What Problem Does This Paper Address?
Estimating expectations is a fundamental task in many scientific and statistical workflows, from Bayesian decision theory to model evaluation. Probabilistic Programming Systems (PPSs) are powerful tools for encoding these problems, but their standard computational pipeline often involves first approximating the full conditional distribution of variables and then using that approximation to estimate the expectation. This two-step process can be inefficient and suboptimal, especially when the target function for the expectation is known. The authors argue that this standard approach fails to leverage information about the target function itself, leading to missed opportunities for substantial performance gains. They propose a new approach that directly targets the expectation, making the inference process "target-aware."
Methods
The core innovation is the concept of expectation programming. Instead of defining a probabilistic program that outputs a distribution, an "expectation program" is defined to directly output a value whose expectation is desired. This is achieved by:
- Target-Aware Inference: Adapting inference engines to exploit knowledge of the target function $f(x)$ for which the expectation $E[\pi(x)[f(x)]]$ is being computed. This is inspired by the Target-Aware Bayesian Inference (TABI) framework, which breaks down the expectation into estimating normalization constants of related densities.
- Expectation Programming in Turing (EPT): A specific implementation that extends the Turing probabilistic programming language. EPT uses a new
@expectationmacro. This macro automatically transforms the user-defined expectation program into three separate Turing programs, each designed to estimate a specific normalization constant related to the original expectation. These transformed programs can then leverage existing inference algorithms within Turing (like Annealed Importance Sampling - AnIS) to compute the necessary estimates. - Program Transformations: The
@expectationmacro performs source-code transformations to create the specialized Turing programs. For example, to estimate $E[\pi(x)[f(x)]]$, it generates programs to estimate normalization constants for densities proportional to $\gamma(x) \max(0, f(x))$, $\gamma(x) \min(0, f(x))$, and $\gamma(x)$ itself.
Datasets
The paper evaluates their approach on three problems:
- Synthetic Numerical Example: A Gaussian posterior predictive experiment.
- SIR Epidemiological Model: A standard model for disease spread.
- Hierarchical Concentration Model: A Bayesian hierarchical model for radon concentration.
No new benchmarks are introduced; instead, existing models are adapted to the expectation programming framework.
Key Insights and Ideas
- The "Standard" PPS Pipeline is Suboptimal for Expectations: The common practice of approximating a full distribution before estimating an expectation is a missed opportunity. Information about the target function $f(x)$ can and should be used directly by the inference engine.
- Target-Awareness is Key: By tailoring the inference process to the specific expectation, significant efficiency gains are possible. This is analogous to how importance sampling uses a proposal distribution that is informed by the target distribution; here, the "target" is the expectation itself.
- Decomposition for Efficiency: The TABI framework's idea of breaking down the expectation into estimating normalization constants of related densities is crucial. This allows for specialized estimators for each component, leading to better overall performance.
- Program Transformations as a Powerful Tool: EPT demonstrates that program transformations can be used to automatically adapt existing probabilistic programming systems for new inference tasks like expectation programming, without requiring fundamental changes to the core language or inference algorithms.
Key Results
- Substantial Empirical Gains: EPT consistently outperforms standard approaches (like MCMC and non-target-aware AnIS) in terms of Relative Squared Error (RSE) and Effective Sample Size (ESS) across the tested problems.
- Gaussian Posterior Predictive: EPT achieved a lower RSE than AnIS and MCMC.
- SIR Model: EPT showed significant improvements over MCMC, with AnIS also performing better than MCMC. The paper highlights that EPT's samples for $Z_1$ (related to positive parts of $f(x)$) effectively explore regions where the target function has mass.
- Radon Model: EPT significantly outperformed standard AnIS, and MCMC (both Turing's and Stan's) failed to produce meaningful estimates, likely because it did not sample from regions where $f(x)$ was significant. EPT's estimates had a small standard deviation relative to their mean.
- Banana Experiment: EPT showed improved RSE over AnIS, which failed to generate samples in regions where the target function $f(x)$ was large.
Limitations and Future Work
- Dependence on Marginal Likelihood Estimator: The performance of EPT is tied to the performance of the underlying marginal likelihood estimator used by the PPS. The paper implements a new AnIS engine for Turing to address this.
- Integration with Existing PPS: While EPT is built on Turing, the core concept of expectation programming is general and could be applied to other PPSs.
- Future Work: The authors suggest that other implementations of expectation programming could focus on different approaches, such as automatic synthesis of control variates. They also note that their current implementation assumes programs return a single scalar value, but generalization to multiple return values is straightforward. The interface design could also be extended to allow users to specify the target function $f(x)$ externally.
Summary updated