Previous studies have demonstrated that encoding a Bayesian network into aSAT formula and then performing weighted model counting using a backtrackingsearch algorithm can be an effective method for exact inference. In this paper,we present techniques for improving this approach for Bayesian networks withnoisy-OR and noisy-MAX relations---two relations that are widely used inpractice as they can dramatically reduce the number of probabilities one needsto specify. In particular, we present two SAT encodings for noisy-OR and twoencodings for noisy-MAX that exploit the structure or semantics of therelations to improve both time and space efficiency, and we prove thecorrectness of the encodings. We experimentally evaluated our techniques onlarge-scale real and randomly generated Bayesian networks. On these benchmarks,our techniques gave speedups of up to two orders of magnitude over the bestprevious approaches for networks with noisy-OR/MAX relations and scaled up tolarger networks. As well, our techniques extend the weighted model countingapproach for exact inference to networks that were previously intractable forthe approach.
展开▼
