A compositional approach to probabilistic knowledge compilation

International Journal of Approximate Reasoning, vol. 138, pp. 38–66

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(nexp⁡(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.

Authors 4

1. Giso H. Dal corresponding

   Radboud University Nijmegen

   Affiliation as printed

   Institute for Computing and Information Sciences, Radboud University, the Netherlands

2. Alfons Laarman Aachen Leiden Institute of Advanced Computer Science

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science, Leiden University, the Netherlands

3. Arjen Hommersom

   Radboud University Nijmegen · Open University of the Netherlands

   Affiliation as printed

   Faculty of Science, Open University, the Netherlands

   Institute for Computing and Information Sciences, Radboud University, the Netherlands

4. Peter Lucas

   Radboud University Nijmegen · University of Twente

   Affiliation as printed

   Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, the Netherlands

   Institute for Computing and Information Sciences, Radboud University, the Netherlands