Proceedings

Efficient Stochastic Local Search for MPE Solving

Frank Hutter, Holger H. Hoos, Thomas Stützle

Download BibTeX Cite

Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 169-173.

Abstract

Finding most probable explanations (MPEs) in graphical models, such as Bayesian belief networks, is a fundamental problem in reasoning under uncertainty, and much effort has been spent on developing effective algorithms for this N P-hard problem. Stochastic local search (SLS) approaches to MPE solving have previously been explored, but were found to be not competitive with state-of-theart branch & bound methods. In this work, we identify the shortcomings of earlier SLS algorithms for the MPE problem and demonstrate how these can be overcome, leading to an SLS algorithm that substantially improves the state-of-the-art in solving hard networks with many variables, large domain sizes, high degree, and, most importantly, networks with high induced width.

Frank Hutter, Holger H. Hoos, and Thomas Stützle. 2005. Efficient Stochastic Local Search for MPE Solving. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05. IJCAI, 169–173. https://ijcai.org/proceedings/2005/210
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards