Abstract
The paper presents a new sampling methodology for Bayesian networks called cutset sampling that samples only a subset of the variables and applies exact inference for the others. We show that this approach can be implemented efficiently when the sampled variables constitute a cycle-cutset for the Bayesian network and otherwise it is exponential in the induced-width of the network's graph, whose sampled variables are removed. Cutset sampling is an instance of the well known Rao-Blakwellisation technique for variance reduction investigated in [5, 2, 13]. Moreover, the proposed scheme extends standard sampling methods to non-ergodic networks with ergodic subspaces. Our empirical results confirm those expectations and show that cutset sampling is superior to Gibbs sampling for a variety of benchmarks, yielding a simple, yet powerful sampling scheme.