Symbolic Exact Inference for Discrete Probabilistic Programs

Steven Holtzen, Todd D. Millstein, Guy Van den BroeckarXiv 2019 · OpenReview

TL;DR

This paper introduces a novel method for performing exact probabilistic inference on discrete probabilistic programs by compiling them into a symbolic representation called a weighted Boolean formula (WBF). This approach leverages techniques from Bayesian networks to efficiently exploit program structure and independencies, achieving competitive performance with specialized inference engines.

What Problem Does This Paper Address?

Probabilistic programming languages (PPLs) offer a powerful way to model complex probabilistic systems. However, performing exact inference (calculating probabilities of events) on these programs is computationally challenging, often requiring exponential time due to the need to explore all possible execution paths. Existing PPL inference systems lag behind specialized methods for graphical models, which excel at exploiting structural properties like independencies to decompose inference tasks. This paper aims to bridge this gap by enabling efficient exact inference for discrete, finite-domain imperative PPLs.

Methods

The core of this work is a symbolic compilation process. Probabilistic programs are first translated into a weighted Boolean formula (WBF). This WBF is a symbolic representation that captures the program's probabilistic semantics as a relation between input and output states. The key innovation is adapting techniques from Bayesian networks and probabilistic logic programming, specifically weighted model counting (WMC), to perform inference on this WBF. WMC efficiently computes probabilities by summing over models of the WBF, exploiting independencies. The WBF is further represented using binary decision diagrams (BDDs), which are highly effective at compactly representing and manipulating Boolean functions, implicitly exploiting conditional and context-specific independencies. The authors formalize this compilation, prove its correctness, and provide a denotational semantics for their language, DIPPL.

Datasets

Not discussed in the paper. The paper uses example probabilistic programs and benchmarks derived from existing work on Bayesian networks and probabilistic logic programs.

Key Insights and Ideas

  • Bridging PPLs and Graphical Models: The paper demonstrates a successful transfer of efficient inference techniques from graphical models (like Bayesian networks) to probabilistic programming languages.
  • Symbolic Representation is Key: Compiling programs into a symbolic form (WBF) is crucial for exposing and exploiting structural properties that are otherwise hidden in imperative code.
  • BDDs for Independence: Binary Decision Diagrams (BDDs) are shown to be an excellent choice for representing the compiled WBF, as they naturally exploit conditional and context-specific independencies, leading to compact representations and efficient inference.
  • Context-Specific Independence Matters: The authors highlight that exploiting context-specific independence (where variables are independent only under certain conditions) is particularly important for probabilistic programs, which often contain deterministic elements, and is not well-handled by many existing PPL inference methods.
  • WMC as a General Inference Engine: Weighted Model Counting is presented as a powerful, general-purpose technique that can be applied to these compiled symbolic representations for exact inference.

Key Results

  • The proposed symbolic compilation and inference approach is shown to be competitive with existing exact inference techniques for probabilistic programs (e.g., Psi, R2) and specialized Bayesian network inference algorithms.
  • For Markov chains, the method scales linearly with the chain length, whereas path-based methods scale exponentially, demonstrating the power of exploiting conditional independence.
  • Experiments on Bayesian networks encoded as probabilistic programs show performance comparable to specialized Bayesian network inference engines, even for complex models.
  • The approach effectively exploits context-specific independence in grid-like structures, leading to significant performance gains in the presence of determinism.

Limitations and Future Work

  • Unbounded Loops: The current compilation technique does not handle unbounded loops, which is a limitation they hope to address in future work.
  • Richer Program Constructs: Future work includes extending the approach to support richer program constructs like loops, procedures, and more complex data types.
  • Complexity Measures: The authors aim to develop precise complexity measures for probabilistic program inference, similar to tree-width for graphical models.
  • Symbolic Model Checking Techniques: Applying techniques from symbolic model checking (e.g., Bebop) is suggested as a promising avenue for future research.

Summary updated

Abstract

The computational burden of probabilistic inference remains a hurdle for applying probabilistic programming languages to practical problems of interest. In this work, we provide a semantic and algorithmic foundation for efficient exact inference on discrete-valued finite-domain imperative probabilistic programs. We leverage and generalize efficient inference procedures for Bayesian networks, which exploit the structure of the network to decompose the inference task, thereby avoiding full path enumeration. To do this, we first compile probabilistic programs to a symbolic representation. Then we adapt techniques from the probabilistic logic programming and artificial intelligence communities in order to perform inference on the symbolic representation. We formalize our approach, prove it sound, and experimentally validate it against existing exact and approximate inference techniques. We show that our inference approach is competitive with inference procedures specialized for Bayesian networks, thereby expanding the class of probabilistic programs that can be practically analyzed.
BibTeX
@misc{holtzen2019symbolic,
  author = {Steven Holtzen and Todd D. Millstein and Guy Van den Broeck},
  title = {{Symbolic Exact Inference for Discrete Probabilistic Programs}},
  year = {2019},
  eprint = {1904.02079},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.02079},
}
Figure