Summary
This paper proposes a new approach to exact inference in probabilistic programs. Existing approaches to exact inference attempt to compute marginal and normalized probabilities by efficiently computing the necessary (finite) sums, or using computer algebra to recognize and solve tractable integrals. By contrast, the present work constructs the moment-generating function ($G(x) = \mathbb{E}_{X \sim \mu}[x^X]$) for the distribution represented by the program, and takes its (higher-order) derivatives (using AD) to compute exact posterior marginal probabilities, as well as exact moments. This enables automated exact inference in a broader class of models than handled by existing techniques. The approach is implemented in Rust, and experiments in four example models show that their implementation typically computes exact answers in less time than it takes for Anglican’s generic Monte Carlo algorithms (e.g., sequential Monte Carlo with the prior as the proposal) to converge to accurate estimates.
Strengths
The key strengths I see in this paper are:
- It introduces a significant new approach to PPL inference (automatic differentiation on compositionally constructed moment-generating functions), and I believe it’s important enough that most people working in PPLs will want to understand the new technique. The exposition is clear and should be accessible to a broad probabilistic programming audience.
- The generating function approach resolves a key limitation of other exact inference methods: it can marginalize latent variables with infinite support.
- Limitations of the language, and performance concerns, are clearly outlined (e.g., in the Restrictions paragraph on L147, and the Limitations paragraph on L83).
- The appendix contains rigorous correctness proofs and further exposition of the generating function semantics. There is also a Rust implementation that helps clarify the actual implementation of the technique (e.g., the data representation of Taylor polynomials used by the AD algorithm).
Weaknesses
The key weaknesses I notice are:
- The novel capabilities (and limitations) with respect to the line of work by Klinkenberg et al. could be more clearly described. It would also be good to cite and explain the differences with their recent LAFI abstract, “Exact Probabilistic Inference Using Generating Functions” (https://arxiv.org/pdf/2302.00513.pdf). That workshop abstract is non-archival and much less thorough than the present work, so I don’t mean this as a critique of your work’s novelty. But I think readers will appreciate a clear-eyed description of exactly how their proposed approach differs from yours.
- It is unclear to what extent the limitations of the language are fundamental limitations of the generating function technique, vs. concessions made to get to a simple first publication/implementation of the idea. Could the technique be extended to programs with loops, or does that seem unlikely? What about compound distributions with more than one random parameter (e.g., Binomial where both $n$ and $p$ is also random)? What about ‘score statements’ that multiply a non-negative (affine?) expression into the likelihood? (It seems this should be possible for scores < 1, because we can `observe 1 ~ Bernoulli(X)`, but can it be made to work for more general scores?)
- The experiments are all on programs for which existing exact inference methods fail. But it would be nice to understand how the new approach compares to existing methods on the programs that both approaches can handle. (Even if it is much less efficient, I believe the method still warrants publication, but it would be useful to readers to understand the expressiveness / efficiency trade-offs clearly.)
- L310-312 incorrectly state that WebPPL does not support SMC or particle MCMC. See the SMC and PMCMC implementations here: https://github.com/probmods/webppl/tree/master/src/inference.
Questions
1. Are you 100% sure that systems like Hakaru and $\lambda$PSI cannot handle your examples? I don’t have a great handle on their capabilities, but I expect Maple’s computer algebra simplifications can handle at least some infinite sums and integrals. Have you tried implementing the example programs and seeing what these tools spit out?
2. What are the prospects for a generating-function semantics of a functional (rather than imperative) source language, such as Anglican (but suitably restricted)?
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The paper is up-front about both the expressiveness limitations of the probabilistic language they support, and the factors in which their algorithm scales exponentially.