Publication
Exploiting Structure in Weighted Model Counting Approaches to Probabilistic Inference
AbstractPrevious 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.
Download publicationRelated Resources
See what’s new.
2025
Curompt: A Spatially Situated Interface for Generative AI in 3D Design SoftwareCurompt, Cursor + Prompt, an AI tool that explores how to integrate AI…
2025
Connect with our Research Connections: 4D Printing for Bioinspired and Biobased DesignLearn about 4D-printing for bioinspired and biobased design…
2022
A force-mediated controller for cooperative object manipulation with independent autonomous robotsWe consider cooperative manipulation by multiple robots assisting a…
2017
Nature-based Hybrid Computational Geometry System for Optimizing Component StructureThis paper describes a novel computational geometry system developed…
Get in touch
Something pique your interest? Get in touch if you’d like to learn more about Autodesk Research, our projects, people, and potential collaboration opportunities.
Contact us