A Dynamic Programming Algorithm for Inference in Recursive Probabilistic Programs

Abstract

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.

Second Statistical Relational AI workshop at UAI 2012 (StaRAI-12)

References in corpus (2)

• Church: a language for generative models
• Sum-Product Networks: A New Deep Architecture

Cited by in corpus (7)

• SPPL: Probabilistic Programming with Fast Exact Symbolic Inference
• Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
• Genetic algorithms with DNN-based trainable crossover as an example of partial specialization of general search
• Nesting Probabilistic Programs
• Model Checking Temporal Properties of Recursive Probabilistic Programs
• A Step from Probabilistic Programming to Cognitive Architectures
• Factor Graph Grammars