A Dynamic Programming Algorithm for Inference in Recursive Probabilistic Programs
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Probabilistic ProgrammingSimilar Papers 제목 키워드 기반
Program Analysis of Probabilistic Programs
Probabilistic programming is a growing area that strives to make statistical analysis more accessible, by separating probabilistic modelling from probabilistic inference. In practice this decoupling is difficult. No sing…
Probabilistic ProgrammingAn Introduction to Probabilistic Programming
This book is a graduate-level introduction to probabilistic programming. It not only provides a thorough background for anyone wishing to use a probabilistic programming system, but also introduces the techniques needed …
Probabilistic ProgrammingOn Scaling Neurosymbolic Programming through Guided Logical Inference
Probabilistic neurosymbolic learning seeks to integrate neural networks with symbolic programming. Many state-of-the-art systems rely on a reduction to the Probabilistic Weighted Model Counting Problem (PWMC), which requ…
Matrix Factorisation with Linear Filters
This text investigates relations between two well-known family of algorithms, matrix factorisations and recursive linear filters, by describing a probabilistic model in which approximate inference corresponds to a matrix…
Image RestorationA Unified View of Algorithms for Path Planning Using Probabilistic Inference on Factor Graphs
Even if path planning can be solved using standard techniques from dynamic programming and control, the problem can also be approached using probabilistic inference. The algorithms that emerge using the latter framework …