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.