Population Markov Chain Monte Carlo

Kathryn Blackmond Laskey Department of Systems Engineering and Operations Research, MS 4A5 George Mason University Fairfax, VA 22030 klaskey@gmu.edu

James Myers Research and Evaluation Division Ballistic Missile Defense Organization Pentagon, DC 220330 james.myers@bmdo.osd.mil

Abstract

Stochastic search algorithms inspired by physical and biological systems are applied to the problem of learning directed graphical probabilistic models, also known as Bayesian networks, in the presence of missing observations and hidden variables. For this class of problems, greedy deterministic search algorithms tend to halt at local optima, usually requiring random restarts to obtain solutions of acceptable quality. We compare three stochastic search algorithms: a Metropolis-Hastings Sampler (MHS), an Evolutionary Algorithm (EA), and a new hybrid algorithm called Population Markov Chain Monte Carlo, or popMCMC. PopMCMC uses statistical information from a population of MHSs to inform the proposal distributions for individual samplers in the population. Experimental results show that popMCMC and EAs learn more efficiently than the MHS with no information exchange. Populations of MCMC samplers exhibit more diversity than populations evolving according to EAs not satisfying physics-inspired local reversibility conditions.

KEY WORDS: Markov Chain Monte Carlo, Metropolis-Hastings Algorithm, Graphical Probabilistic Models, Bayesian Networks, Bayesian Learning, Evolutionary Algorithms