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.