GiSS: Combining Gibbs Sampling and SampleSearch for Inference in Mixed Probabilistic and Deterministic Graphical Models

Deepak Venugopal, Vibhav GogateAAAI 2013 · OpenReview

Abstract

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 Sample Search, MC-SAT and Belief propagation.

Introduction

Probabilistic Graphical Models (PGMs) are essential for reasoning under uncertainty, yet real-world domains frequently involve deterministic dependencies—logical constraints that must always be satisfied. Standard Gibbs sampling, a cornerstone of approximate inference, fails in these scenarios. Deterministic constraints "fracture" the probability space into isolated clusters of valid assignments. Since Gibbs sampling typically modifies one variable at a time, it becomes trapped within a single cluster, unable to traverse the zero-probability regions to reach other valid states. This lack of ergodicity leads to significantly biased and incorrect results. While alternatives like MC-SAT exist, they often struggle with scalability or efficiency in massive, highly constrained state spaces.

The GiSS Algorithm

To address these limitations, we introduce GiSS (Gibbs + SampleSearch), a hybrid inference algorithm that partitions variables into deterministic ($X_d$) and non-deterministic ($X_p$) sets. The core innovation lies in its "divide and conquer" approach:

  1. SampleSearch for Logic: The algorithm utilizes SampleSearch to generate valid assignments for deterministic variables. By leveraging SAT/CSP solvers, it can effectively "jump" between isolated clusters of valid states that would otherwise trap a standard sampler.
  2. Gibbs for Probability: Once a valid cluster is identified for $X_d$, standard Gibbs sampling is employed to explore the non-deterministic variables ($X_p$) within that local space.
  3. Approximate Weighting: As an importance sampling method, GiSS requires weighted samples. Since exact weight calculation is #P-complete, we propose three approximation schemes: a computationally efficient Harmonic Mean Estimator, a lower-variance Product Estimator, and an Annealed Importance Sampling approach.
Conceptual overview of a PGM and its representation as a backtrack-free probability tree used in SampleSearch to navigate deterministic constraints.

Experimental Evaluation

We evaluated GiSS against state-of-the-art solvers including MC-SAT, SampleSearch (SS), and Belief Propagation (BP) across several benchmark domains from the UAI 2008 repository, such as Grid networks, Linkage Analysis (pedigree models), and Statistical Relational Models.

Our results demonstrate that GiSS is highly competitive, often outperforming existing methods in both accuracy and consistency. Notably, on the "pedigree" genetics datasets—where approximately 85% of functions are deterministic—GiSS achieved significantly higher accuracy than all other tested methods.

Average Hellinger distance over time for various algorithms on the or-chain-180 benchmark, showing GiSS (circles) consistently achieving lower error than competitors.

Discussion and Future Work

A key finding is that the computationally "cheapest" weighting method, the Harmonic Mean, often performed best in practice. Its low overhead allowed for a higher volume of samples, which compensated for individual weight inaccuracies.

While GiSS effectively breaks the ergodicity barriers of standard Gibbs sampling, its performance remains dependent on the quality of the initial proposal distribution. Future work will explore automated variable partitioning and "lifted" versions of the algorithm to operate directly on first-order logic representations, potentially offering further scalability for complex relational models.

Summary updated

Abstract

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 Sample Search, MC-SAT and Belief propagation.
BibTeX
@inproceedings{venugopal2013giss,
  author = {Deepak Venugopal and Vibhav Gogate},
  title = {{GiSS: Combining Gibbs Sampling and SampleSearch for Inference in Mixed Probabilistic and Deterministic Graphical Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  url = {https://openreview.net/forum?id=rJEAgJWdbr},
}
Figure