The Support Method of Computing Expectations

Pfeffer, A.

Extended abstract for the Probabilistic Program Semantics Workshop associated with the Principles of Programming Languages (POPL) conference, Los Angeles, CA (January 2018).

A standard method for computing the expectation of a function on a probabilistic program is to sample values from the generative model and approximate the integral. An alternative approach is to deterministically enumerate a set of values, give each point a weight, and numerically approximate the integral. If the points and weights are well chosen, this can lead to a more efficient computation than Monte Carlo sampling. For programs with small finite support, we can simply enumerate all values and give each a weight of 1 to obtain the standard definition of expectation. However, this method can also work well for programs with very large or infinite support.

Although this method is conceptually simple and well known, it is surprisingly tricky to implement. It has a long history in search-based approaches for graphical models, going back to the work of Henrion, Poole, and Dechter and colleagues. However, these methods have generally been restricted to discrete models and simpler languages than probabilistic programming. One challenge is to develop a good method for enumerating the support of continuous variables with infinite support. Another challenge is to avoid double counting values in models with multiple variables.

For More Information

To learn more or request a copy of a paper (if available), contact Avi Pfeffer.

(Please include your name, address, organization, and the paper reference. Requests without this information will not be honored.)