Dissociation-Based Oblivious Bounds for Weighted Model Counting

Li Chou, Wolfgang Gatterbauer, Vibhav GogateUAI 2018

Introduction

Probabilistic inference is a foundational task in modern artificial intelligence, underpinning applications ranging from medical diagnostics to natural language processing. At its core, this often requires Weighted Model Counting (WMC), a generalization of the Boolean satisfiability problem (#SAT). WMC calculates the total weight of all satisfying assignments for a logical formula, which is equivalent to computing the partition function ($Z$) in graphical models. However, exact WMC is #P-complete, making it computationally intractable for large, complex models with high treewidth.

The Limitations of Current Bounding Methods

To address the intractability of exact inference, researchers often employ deterministic bounding algorithms. The industry standard, Mini-Bucket (MB) elimination, provides upper and lower bounds by partitioning variables into smaller subsets. While efficient, MB often produces loose bounds. In many practical scenarios, the lower bounds generated by MB collapse to zero, providing no useful information for the user. This creates a critical need for more robust deterministic approximation methods.

Methodology: Dissociation and Oblivious Weighting

This paper introduces a novel bounding framework based on dissociation. The fundamental idea is to simplify a complex logical formula by "splitting" variables that appear in multiple constraints into independent clones. This process transforms a cyclic, hard-to-solve graph into a simple tree structure that can be processed in linear time.

Oblivious Bounds

The researchers derive "oblivious" bounds by assigning weights to these clones based solely on local constraint structures. Unlike global optimization methods, these bounds are computationally inexpensive to calculate. To ensure the resulting counts remain valid upper or lower bounds, the authors established specific weight assignment rules and inequalities.

Local weight assignment tables for dissociated variables, illustrating the "oblivious" nature of the bounding scheme.

Extension to Non-Monotone Formulas

While previous dissociation techniques were limited to monotone formulas (where variables maintain a consistent sign), this work extends the theory to general non-monotone formulas. This is achieved through:

  1. Logical Preprocessing: Utilizing techniques like Unit Resolution to simplify formulas before bounding.
  2. Canonical Representation: Standardizing variable appearances to streamline the mathematical derivation of bounds.
  3. New Theoretical Guarantees: Proving conditions (Theorems 14 and 16) that ensure valid bounds even when variables appear in both positive and negative forms.

Experimental Evaluation

The proposed "DIS" algorithm was evaluated against Mini-Bucket elimination using two primary benchmarks:

  • Synthetic Grids: $m \times m$ grid-structured Markov networks (up to $20 \times 20$) with varying levels of determinism.
  • UAI 2008 Benchmarks: Real-world datasets including medical diagnostics (Promedas), computer vision (Segmentation), and social networks (Smokers).

Key Results

The experimental results demonstrate that the dissociation-based approach consistently outperforms Mini-Bucket elimination. On synthetic $20 \times 20$ grids, the DIS upper bound (DIS-U) was significantly tighter than its MB counterpart. More importantly, DIS provided meaningful, non-zero lower bounds in cases where MB failed.

Performance comparison of DIS and MB algorithms on synthetic grid networks. Plot (a) shows error bounds relative to grid size, while (b) and (c) illustrate the impact of determinism strength.

On the UAI benchmarks, DIS outperformed MB by a wide margin. For instance, in the segmentation (sg) datasets, the log-relative difference between DIS and MB reached into the hundreds, indicating a vastly more accurate estimation of the partition function.

Conclusion

Dissociation-based oblivious bounds offer a powerful alternative to traditional algebraic bounding methods. By integrating logical preprocessing with local weight assignment, the DIS algorithm provides tighter, more reliable bounds for WMC—particularly for lower bounds where existing methods struggle. Future research may explore higher-order dissociation to handle models with small but non-zero treewidth and the application of this framework to MAP and MMAP estimation tasks.

Summary updated

BibTeX
@inproceedings{chou2018dissociation,
  author = {Li Chou and Wolfgang Gatterbauer and Vibhav Gogate},
  title = {{Dissociation-Based Oblivious Bounds for Weighted Model Counting}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2018},
}
Figure