A Dynamic Programming Algorithm for Inference in Recursive Probabilistic Programs
This work addresses a specific bottleneck in probabilistic programming for researchers and practitioners in fields like cognitive science and game theory, but it appears incremental as it builds on existing dynamic programming and sum-product network concepts.
The authors tackled the problem of computing marginal distributions in discrete probabilistic programs with recursion by developing a dynamic programming algorithm that constructs a factored sum-product network to handle cyclic dependencies and solves the resulting equations via fixed-point iteration. They demonstrated the algorithm's applicability in teaching probabilistic models, computational cognitive science, and game theory, though no concrete performance numbers were provided.
We describe a dynamic programming algorithm for computing the marginal distribution of discrete probabilistic programs. This algorithm takes a functional interpreter for an arbitrary probabilistic programming language and turns it into an efficient marginalizer. Because direct caching of sub-distributions is impossible in the presence of recursion, we build a graph of dependencies between sub-distributions. This factored sum-product network makes (potentially cyclic) dependencies between subproblems explicit, and corresponds to a system of equations for the marginal distribution. We solve these equations by fixed-point iteration in topological order. We illustrate this algorithm on examples used in teaching probabilistic models, computational cognitive science research, and game theory.