A compositional approach to probabilistic knowledge compilation

Giso H. Dal, Alfons W. Laarman, Arjen Hommersom, Peter J. F. Lucas

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Bayesian networks (BN) are a popular representation for reasoning under uncertainty. The analysis of many real-world use cases, that in principle can be modeled by BNs, suffers however from the computational complexity of inference. Inference methods based on Weighted Model Counting (WMC) reduce the cost of inference by exploiting patterns exhibited by the probabilities associated with BN nodes. However, these methods require a computationally intensive compilation step in search of these patterns, which effectively prohibits the handling of larger BNs. In this paper, we propose a solution to this problem by extending WMC methods with a framework called Compositional Weighted Model Counting (CWMC). CWMC reduces compilation cost by partitioning a BN into a set of subproblems, thereby scaling the application of state-of-the-art innovations in WMC to scenarios where inference cost could previously not be amortized over compilation cost. The framework supports various target representations that are less or equally succinct as decision-DNNF. At the same time, its inference time complexity O(n exp(w)), where n is the number of variables and w is the tree-width, is comparable to mainstream algorithms based on variable elimination, clustering and conditioning.
Original languageEnglish
Pages (from-to)38-66
Number of pages29
JournalInternational Journal of Approximate Reasoning
Volume138
DOIs
Publication statusPublished - Nov 2021

Keywords

  • Bayesian inference
  • Knowledge compilation
  • Partitioning
  • Model counting
  • CAUSAL INDEPENDENCE
  • BAYESIAN NETWORKS
  • DECISION DIAGRAMS
  • INFERENCE

Fingerprint

Dive into the research topics of 'A compositional approach to probabilistic knowledge compilation'. Together they form a unique fingerprint.

Cite this