2012/06/15 by Andreas Stuhlmüller, Noah D. Goodman, Stuhlmüller, Andreas +1 · 2 citations
Arts and Humanities · Computer Science · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Philosophy and History of Science #cs.AI #cs.DS
paper · pdf · doi:10.48550/arxiv.1206.3555
Second Statistical Relational AI workshop at UAI 2012 (StaRAI-12)
openalex publication_date 2012/06/15 · arxiv created 2012/09/10 · arxiv updated 2012/09/12 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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.