An Efficient Gibbs Sampler for Structural Inference in Bayesian Networks. CRiSM Working Paper 1121

We propose a Gibbs sampler for structural inference in Bayesian net-works. The standard Markov chain Monte Carlo (MCMC) algorithms used for this problem are random-walk Metropolis-Hastings samplers, but for problems of even moderate dimension, these samplers often exhibit slow mixing. The Gibbs sampler proposed here conditionally samples the complete set of parents of a node in a single move, by blocking to-gether particular components. These blocks can themselves be paired together to improve the efficiency of the sampler. The conditional distri-bution used for sampling can be viewed as a posterior distribution for a constrained Bayesian variable selection for the parents of a node. This view sheds further light on the increasingly well understood connection between Bayesian variable selection and structural inference. We empiri-cally examine the performance of the sampler using data simulated from the ALARM network.