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.