From Weighted to Unweighted Model Counting.

Supratik Chakraborty, Dror Fried, Kuldeep S. Meel, Moshe Y. VardiIJCAI 2015 · OpenReview

Abstract

The recent surge of interest in reasoning about probabilistic graphical models has led to the development of various techniques for probabilistic reasoning. Of these, techniques based on weighted model counting are particularly interesting since they can potentially leverage recent advances in unweighted model counting and in propositional satisfiability solving. In this paper, we present a new approach to weighted model counting via reduction to unweighted model counting. Our reduction, which is polynomial-time and preserves the normal form (CNF/DNF) of the input formula, allows us to exploit advances in unweighted model counting to solve weighted model counting instances. Experiments with weighted model counters built using our reduction indicate that these counters performs much better than a state-of-the-art weighted model counter.

Introduction

Probabilistic reasoning is a cornerstone of modern artificial intelligence, underpinning applications from medical diagnostics to natural language processing. Many of these tasks are fundamentally instances of Weighted Model Counting (WMC), which involves calculating the sum of weights of all satisfying assignments to a Boolean formula. While WMC is computationally intensive (#P-complete), its unweighted counterpart, Unweighted Model Counting (UMC), has benefited from significant performance breakthroughs in recent years due to highly optimized solvers like sharpSAT.

Historically, researchers have attempted to solve WMC by manually adapting UMC algorithms. This approach is labor-intensive and difficult to maintain as solvers evolve. This paper proposes a different paradigm: instead of modifying the solver to fit the problem, we transform the problem to fit existing, high-performance solvers through a polynomial-time reduction.

Methodology

The core of our approach is a reduction that translates a literal-weighted WMC instance into a UMC instance using "chain formulas."

Chain Formulas and Weight Encoding

We construct a specific type of Boolean formula, $\phi_{k,m}$, designed to have exactly $k$ satisfying assignments out of $2^m$ possible assignments. For every variable with a weight represented as a fraction $k/2^m$, the algorithm introduces auxiliary variables and a corresponding chain formula. The final UMC instance is satisfied only when the original constraints are met and the auxiliary variables satisfy the chain formulas.

Form Preservation

A critical feature of our reduction is that it preserves the normal form of the input formula—either Conjunctive Normal Form (CNF) or Disjunctive Normal Form (DNF). This preservation is vital because state-of-the-art solvers are often highly specialized for specific formats. By maintaining the structure, we can use off-the-shelf UMC solvers as "black boxes" without modifying their source code.

Experimental Evaluation

We evaluated our tool, WeightCount, on a suite of 79 diverse CNF benchmarks, including grid networks, Ising models, plan recognition networks, and program synthesis examples. We compared WeightCount (using sharpSAT and DSharp as back-end solvers) against SDD, a state-of-the-art exact weighted model counter.

Results

Our experiments demonstrate that the reduction approach provides significant performance advantages. On the majority of benchmarks, WeightCount (via sharpSAT) outperformed SDD by one to three orders of magnitude. Furthermore, WeightCount proved more robust; while SDD timed out or exceeded memory on 30 of the 79 instances, WeightCount failed on only one.

Table 1: Performance comparison of WeightCount (using sharpSAT and DSharp) against SDD on various benchmarks. The table shows the overhead of the reduction (Final #vars/claus) and the significant speedups achieved.

As shown in Table 1, the transformation time is typically negligible (often less than 0.1 seconds), even for large formulas. The structural complexity added by the auxiliary variables is a small price to pay for the efficiency gains provided by modern UMC solvers. For instance, in the BN_47 benchmark, sharpSAT completed the count in 0.11 seconds compared to SDD's 170.92 seconds.

Conclusion

By bridging the gap between weighted and unweighted model counting, we enable probabilistic reasoning to benefit directly from the rapid progress in SAT and UMC solver technology. Future work includes extending this approach to approximate counting and optimizing reductions for ConstraintWMC, where weights are tied to complex constraints rather than individual literals.

Summary updated

Abstract

The recent surge of interest in reasoning about probabilistic graphical models has led to the development of various techniques for probabilistic reasoning. Of these, techniques based on weighted model counting are particularly interesting since they can potentially leverage recent advances in unweighted model counting and in propositional satisfiability solving. In this paper, we present a new approach to weighted model counting via reduction to unweighted model counting. Our reduction, which is polynomial-time and preserves the normal form (CNF/DNF) of the input formula, allows us to exploit advances in unweighted model counting to solve weighted model counting instances. Experiments with weighted model counters built using our reduction indicate that these counters performs much better than a state-of-the-art weighted model counter.
BibTeX
@inproceedings{chakraborty2015from,
  author = {Supratik Chakraborty and Dror Fried and Kuldeep S. Meel and Moshe Y. Vardi},
  title = {{From Weighted to Unweighted Model Counting.}},
  booktitle = {IJCAI},
  year = {2015},
  url = {https://openreview.net/forum?id=2_UHDT6Qn7I},
}

Loading related content...

Figure