Exploiting Causal Independence Using Weighted Model Counting

Wei Li, Pascal Poupart, Peter Van Beek

AAAI Conference on Artificial Intelligence
2008

Abstract

Previous studies have demonstrated that encoding a Bayesian network into a SAT-CNF formula and then performing weighted model counting using a backtracking search algorithm can be an effective method for exact inference in Bayesian networks. In this paper, we present techniques for improving this approach for Bayesian networks with noisy-OR and noisy-MAX relations—two relations which are widely used in practice as they can dramatically reduce the number of probabilities one needs to specify. In particular, we present two space efficient CNF encodings for noisy-OR/MAX and explore alternative search ordering heuristics. We experimentally evaluated our techniques on large-scale real and randomly generated Bayesian networks. On these benchmarks, our techniques gave speedups of up to two orders of magnitude over the best previous approaches and scaled up to networks with larger numbers of random variables.

Related Publications

Loading...

Welcome ${RESELLERNAME} Customers

Please opt-in to receive reseller support

I agree that Autodesk may share my name and email address with ${RESELLERNAME} so that ${RESELLERNAME} may provide installation support and send me marketing communications.  I understand that the Reseller will be the party responsible for how this data will be used and managed.

Email is required Entered email is invalid.

${RESELLERNAME}