Exploiting structure in weighted model counting approaches to probabilistic inference

DOI10.1613/JAIR.3232MaRDI QIDQ2996915zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 4 May 2011

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.3886

Mathematics Subject Classification ID

Bayesian inference (62F15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: Previous studies have demonstrated that encoding a Bayesian network into a SAT formula and then performing weighted model counting using a backtracking search algorithm can be an effective method for exact inference. In this paper, we present techniques for improving this approach for Bayesian networks with noisy-OR and noisy-MAX relations---two relations that are widely used in practice as they can dramatically reduce the number of probabilities one needs to specify. In particular, we present two SAT encodings for noisy-OR and two encodings for noisy-MAX that exploit the structure or semantics of the relations to improve both time and space efficiency, and we prove the correctness of the encodings. 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 for networks with noisy-OR/MAX relations and scaled up to larger networks. As well, our techniques extend the weighted model counting approach for exact inference to networks that were previously intractable for the approach.

Recommendations

• On probabilistic inference by weighted model counting
• Weighted positive binary decision diagrams for exact probabilistic inference
• scientific article; zbMATH DE number 2096817
• A compositional approach to probabilistic knowledge compilation
• Solving \#SAT and Bayesian inference with backtracking search

Cited in

(13)

• A compositional approach to probabilistic knowledge compilation
• ProCount: weighted projected model counting with graded project-join trees
• On probabilistic inference by weighted model counting
• Efficient probabilistic inference in Bayesian networks with multi-valued NIN-AND tree local models
• Probabilistic inference with noisy-threshold models based on a CP tensor decomposition
• The hidden elegance of causal interaction models
• Approximate model counting via extension rule
• Solving \#SAT and Bayesian inference with backtracking search
• scientific article; zbMATH DE number 2096817 (Why is no real title available?)
• Two approximate algorithms for model counting
• Comparing and Weighting Imperfect Models Using D-Probabilities
• Leveraging belief propagation, backtrack search, and statistics for model counting
• Enhancing SMT-based weighted model integration by structure awareness

This page was built for publication: Exploiting structure in weighted model counting approaches to probabilistic inference

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2996915)