We present a general framework for defining priors on model structure and sampling from the posterior using the Metropolis-Hastings algorithm. The key idea is that structure priors are defined via a probability tree and that the proposal mechanism for the Metropolis-Hastings algorithm operates by traversing
this tree, thereby defining a cheaply computable acceptance probability. We
have applied this approach to Bayesian net structure learning using a number of
priors and tree traversal strategies. Our results show that these must be
chosen appropriately for this approach to be successful.