Weighted Model Counting Without Parameter Variables

Paulius Dilkas, Vaishak Belle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationTheory and Applications of Satisfiability Testing – SAT 2021
PublisherSpringer
Pages134-151
Number of pages18
ISBN (Electronic)978-3-030-80223-3
ISBN (Print)978-3-030-80222-6
DOIs
Publication statusPublished - 2 Jul 2021
Event24th International Conference on Theory and Applications of Satisfiability Testing - Barcelona, Spain
Duration: 5 Jul 20219 Jul 2021
https://www.iiia.csic.es/sat2021/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12831
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Conference on Theory and Applications of Satisfiability Testing
Abbreviated titleSAT 2021
Country/TerritorySpain
CityBarcelona
Period5/07/219/07/21
Internet address

Keywords / Materials (for Non-textual outputs)

  • Weighted model counting
  • Probabilistic inference
  • Bayesian networks

Fingerprint

Dive into the research topics of 'Weighted Model Counting Without Parameter Variables'. Together they form a unique fingerprint.

Cite this