In this book we provide comprehensive coverage of the primary exact algorithms for reasoning with graphical models (e.g., Bayesian and constraint networks, influence diagrams, and Markov decision processes) which have become a central paradigm for knowledge representation and reasoning in both artificial intelligence and computer science in general. The target audience of this book is researchers and students in the AI and machine learning area. ISBN 9781627051972, 191 pages.

Mixed probabilistic and deterministic graphical models are ubiquitous in real-world applications. Unfortunately, Gibbs sampling, a popular MCMC technique, does not converge to the correct answers in presence of determinism and therefore cannot be used for inference in such models. In this paper, we propose to remedy this problem by combining Gibbs sampling with SampleSearch, an advanced importance sampling technique which leverages complete SAT/CSP solvers to generate high quality samples from hard deterministic spaces. We call the resulting algorithm, GiSS. Unlike Gibbs sampling which yields unweighted samples, GiSS yields weighted samples. Computing these weights exactly can be computationally expensive and therefore we propose several approximations. We show that our approximate weighting schemes yield consistent estimates and demonstrate experimentally that GiSS is competitive in terms of accuracy with state-of-the-art algorithms such as SampleSearch, MC-SAT and Belief propagation.