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.
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:
- Logical Preprocessing: Utilizing techniques like Unit Resolution to simplify formulas before bounding.
- Canonical Representation: Standardizing variable appearances to streamline the mathematical derivation of bounds.
- 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.
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