DPSampler: Exact Weighted Sampling Using Dynamic Programming

Jeffrey M. Dudek, Aditya A. Shrotri, Moshe Y. VardiIJCAI 2022 · DOI

TL;DR

This paper introduces DPSampler, a novel algorithm for exact weighted sampling of Boolean formulas. By leveraging dynamic programming and Algebraic Decision Diagrams (ADDs) with tree decompositions, DPSampler offers a more scalable and versatile approach compared to existing state-of-the-art methods, particularly for problems with low treewidth.

What Problem Does This Paper Address?

The paper tackles the problem of exact weighted sampling of solutions to Boolean formulas. This is crucial in various domains like Bayesian inference, testing, and verification, where we need to randomly select an assignment that satisfies a given formula, with the probability of selecting an assignment being proportional to its assigned weight. Existing methods often rely on compiling the formula into a data structure called d-DNNF, which can be computationally expensive. While recent work in the related field of model counting has shown success using dynamic programming and Algebraic Decision Diagrams (ADDs) for problems with low treewidth, these techniques hadn't been effectively applied to weighted sampling. The paper aims to bridge this gap by developing a dynamic programming-based sampler that exploits tree decompositions and ADDs.

Methods

DPSampler employs a three-phase approach:

  1. Planning: This phase computes an "execution plan" in the form of a project-join tree. This tree structure is derived from a tree decomposition of the input formula and serves as a blueprint for subsequent steps. This planning phase leverages existing techniques from model counting.
  2. Compilation: The input formula is compiled into a tree-of-ADDs representation based on the project-join tree. This is a novel compilation process that differs from previous approaches by not abstracting out variables at internal nodes, which is crucial for the sampling phase.
  3. Sampling: A random sample is generated by traversing the compiled tree-of-ADDs. A key innovation here is a new "in-place" ADD-sampling algorithm that avoids expensive dynamic memory allocation required by prior methods. This algorithm performs a top-down random walk on the ADDs.

The decoupling of these phases allows for the use of specialized libraries for each step, enhancing modularity.

Datasets

The paper evaluates DPSampler on benchmark sets from previous work on model counting and sampling, specifically:

  • 'DPV' (1945 instances) from [Dudek et al., 2020b].
  • 'GSRM' (773 instances) from [Gupta et al., 2019].
  • A combined set of unique instances from both.

No new benchmarks were introduced.

Key Insights and Ideas

  • Dynamic Programming for Sampling: The core idea is that dynamic programming, successful in model counting for low-treewidth problems, can be effectively adapted for exact weighted sampling.
  • Tree Decompositions as a Blueprint: Using tree decompositions to construct project-join trees provides a structured way to decompose complex Boolean formulas for efficient processing.
  • Tree-of-ADDs for Sampling: Compiling the formula into a tree-of-ADDs allows for a recursive, piece-wise sampling process that is more efficient than monolithic representations.
  • Top-Down ADD Sampling Efficiency: The novel top-down ADD-sampling algorithm significantly outperforms bottom-up approaches, demonstrating the importance of efficient traversal and avoiding expensive intermediate computations.
  • Low Treewidth Advantage: The paper confirms that DPSampler, like its model-counting counterparts, excels on instances with low treewidth, a common characteristic in real-world problems.

Key Results

  • Speedup: DPSampler is significantly faster than the state-of-the-art weighted sampler WAPS. Table 1 shows an average speedup, with DPSampler being faster on the majority of instances (Table 3).
  • Scalability: DPSampler solves more benchmarks overall than WAPS, especially when considering unique instances (Table 2).
  • ADD-Sampling Performance: The new top-down ADD-sampling algorithm is approximately 19.6 times faster than the bottom-up approach from prior work, and it successfully completes 23.8% more benchmarks.
  • Low Treewidth Performance: Figure 1 illustrates that DPSampler's performance advantage over WAPS is most pronounced for treewidths up to 55.
  • Distribution Quality: The generated samples from DPSampler were found to be indistinguishable from an ideal sampler (Jensen-Shannon distance of 0.003).

Limitations and Future Work

  • Planning Bottleneck: The planning phase, specifically the construction of tree decompositions, is identified as the biggest bottleneck for DPSampler. Out of 182 benchmarks where WAPS succeeded and DPSampler failed, 137 were due to the inability to construct a tree decomposition.
  • Extensibility: The modular design of DPSampler allows for easy integration with other tree-decomposition tools or off-the-shelf heuristics for constructing project-join trees, which could address the planning bottleneck.
  • Future Directions:
    • Exploring alternative tree-decomposition methods or heuristics.
  • Integrating dynamic variable ordering for ADD construction to further enhance sampling performance.
  • Extending DPSampler for projected sampling using graded project-join trees.
  • Investigating the use of other data structures beyond ADDs for the tree-of-ADDs representation.

Summary updated

BibTeX
@inproceedings{dudek2022dpsampler,
  author = {Jeffrey M. Dudek and Aditya A. Shrotri and Moshe Y. Vardi},
  title = {{DPSampler: Exact Weighted Sampling Using Dynamic Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/250},
}
Figure