A compositional approach to probabilistic knowledge compilation

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. (C) 2021 The Author(s). Published by Elsevier Inc.

Automated summary

Bayesian networks are a popular choice for reasoning under uncertainty, but the computational complexity of inference can be a challenge for real-world applications. Weighted Model Counting (WMC) methods aim to reduce the cost of inference by exploiting patterns in the probabilities associated with BN nodes, but require a computationally intensive compilation step. The proposed Compositional Weighted Model Counting (CWMC) framework addresses this issue by partitioning BNs into subproblems, allowing for more efficient application of WMC innovations.