Jim Myers' doctoral dissertation work achieved considerable speedup
in performance over standard Metropolis-Hastings by using a
population of samplers to estimate properties of the target
distribution and then using the results to inform the proposal
distribution. This has the advantage of being a fixed proposal
distribution sampler on the *population* of samplers, thus satisfying
ergodicity and geometric convergence conditions, but behaving at the
individual level like an adaptive sampler (i.e., the proposal
distribution for an individual sampler depends on the state of the
other samplers in the population). In testing our approach on
learning BNs, we got better log-posterior probabilities in 500
iterations using our popMCMC than we did in 3000 iterations using a
non-adaptive Metropolis-Hastings sampler.
BTW, we also tried evolutionary algorithms. The log-posterior
probabilities increased about as fast as for our adaptive sampler,
but the EA homed in quickly on a single "good" structure (a different
one on each run) and then just sampled over missing values, whereas
popMCMC maintained a population with many different structures. This
reflects a well-known tendency of EAs not to have sufficient
"population diversity." It seems that the Metropolis-Hastings
algorithm counteracts this tendency.
We also found that the Gelman convergence metric indicated that our
non-adaptive MH sampler had converged when it hadn't. Watch out for
convergence diagnostics!
See
http://ite.gmu.edu/~klaskey/papers/Laskey_Myers_popMCMC.pdf
Kathy
At 10:44 AM -0700 5/10/01, Rina Dechter wrote:
>Gordon,
>
>>From our (perhaps limited) experience with Gibbs sampling, in practice
>it often exhibits very poor perfomance as a function of time (namely
>as an anytime algorithm). Convergence takes too long and is
>unpredictale.
>And, if one can effort to spend huge amounts of times to get
>convergence,
>it seems better to spend that time on running the exact algorithm,
>instead.
>
>I wonder if there are any empirical studies of
>Gibbs sampling. I understand that in practice enhancement such as
>likelihood weighting seems to be far better.
>
>----Rina.
>
>Rina Dechter [EMAIL PROTECTED]
>Information and Computer Science Dept. (949) 824-6556
>University of California, Irvine fax: (949)-824-4056
>Irvine, CA 92717
>http://www.ics.uci.edu/~dechter
