Stochastic Local Search for Solving the Most Probable Explanation Problem in Probabilistic Graphical Models

By Frank Hutter

In this thesis, we develop and study novel Stochastic Local Search (SLS) algorithms for solving the Most Probable Explanation (MPE) problem in graphical models, that is, to find the most probable instantiation of all variables in the model, given evidence on a subset of variables.

SLS algorithms have been applied to the MPE problem before, but none of these previous SLS algorithms pays sufficient attention to such important concerns as algorithmic complexity per search step, search stagnation, and thorough parameter tuning. We remove these shortcomings of previous SLS algorithms for MPE, improving their efficiency by up to six orders of magnitude.
Next to previous SLS algorithms, we compare our algorithms against an anytime version of the prominent Mini-Buckets algorithm and an exact Branch-and-Bound algorithm with Mini-Buckets heuristic (BBMB).

Our experiments suggest that our algorithms outperform these approaches on most MPE instances we study, and that they scale much preferably in terms of a number of important instance characteristics, namely the number of variables, domain size, node degree, and especially the graphical model's induced width.

Back to the LCI Forum page