Encoding Probabilistic Graphical Models into Stochastic Boolean Satisfiability
Journal
IJCAI International Joint Conference on Artificial Intelligence
ISBN
9781956792003
Date Issued
2022-01-01
Author(s)
Hsieh, Cheng Han
Abstract
Statistical inference is a powerful technique in various applications. Although many statistical inference tools are available, answering inference queries involving complex quantification structures remains challenging. Recently, solvers for Stochastic Boolean Satisfiability (SSAT), a powerful formalism allowing concise encodings of PSPACE decision problems under uncertainty, are under active development and applied in more and more applications. In this work, we exploit SSAT solvers for the inference of Probabilistic Graphical Models (PGMs), an essential representation for probabilistic reasoning. Specifically, we develop encoding methods to systematically convert PGM inference problems into SSAT formulas for effective solving. Experimental results demonstrate that, by using our encoding, SSAT-based solving can complement existing PGM tools, especially in answering complex queries.
Type
conference paper