Physical Sciences and Mathematics Commons^™

Initialization And Restart In Stochastic Local Search: Computing A Most Probable Explanation In Bayesian Networks, Ole J. Mengshoel, David C. Wilkins, Dan Roth

Ole J Mengshoel

For hard computational problems, stochastic local search has proven to be a competitive approach to finding optimal or approximately optimal problem solutions. Two key research questions for stochastic local search algorithms are: Which algorithms are effective for initialization? When should the search process be restarted? In the present work, we investigate these research questions in the context of approximate computation of most probable explanations (MPEs) in Bayesian networks (BNs). We introduce a novel approach, based on the Viterbi algorithm, to explanation initialization in BNs. While the Viterbi algorithm works on sequences and trees, our approach works on BNs with arbitrary …