  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.
