Abstract
Weighted model counting (WMC) is a powerful computational technique for a variety of problems, especially commonly used for probabilistic inference. However, the standard definition of WMC that puts weights on literals often necessitates WMC encodings to include additional variables and clauses just so each weight can be attached to a literal. This paper complements previous work by considering WMC instances in their full generality and using recent state-of-the-art WMC techniques based on pseudo-Boolean function manipulation, competitive with the more traditional WMC algorithms based on knowledge compilation and backtracking search. We present an algorithm that transforms WMC instances into a format based on pseudo-Boolean functions while eliminating around 43% of variables on average across various Bayesian network encodings. Moreover, we identify sucient conditions for such a variable removal to be possible. Our experiments show signicant improvement in WMC-based Bayesian network inference, outperforming the current state of the art.
Original language | English |
---|---|
Title of host publication | Theory and Applications of Satisfiability Testing – SAT 2021 |
Publisher | Springer |
Pages | 134-151 |
Number of pages | 18 |
ISBN (Electronic) | 978-3-030-80223-3 |
ISBN (Print) | 978-3-030-80222-6 |
DOIs | |
Publication status | Published - 2 Jul 2021 |
Event | 24th International Conference on Theory and Applications of Satisfiability Testing - Barcelona, Spain Duration: 5 Jul 2021 → 9 Jul 2021 https://www.iiia.csic.es/sat2021/ |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 12831 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 24th International Conference on Theory and Applications of Satisfiability Testing |
---|---|
Abbreviated title | SAT 2021 |
Country/Territory | Spain |
City | Barcelona |
Period | 5/07/21 → 9/07/21 |
Internet address |
Keywords / Materials (for Non-textual outputs)
- Weighted model counting
- Probabilistic inference
- Bayesian networks