Stochastic Local Search for the Most Probable Explanation Problem (SLS4MPE)Bioinformatics, and Empirical
& Theoretical Algorithmics Laboratory (ß-Lab) |
July 25, 2005 |
Version 1.0.0 of the SLS4MPE code is now online. |
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 NP-hard problem. In different communities, the MPE problem has different names; it is also known as the maximum a posteriori (MAP) problem, or simply max-product. The problem is to find thecomplete instantiation of all variables in the graphical model that has maximal probability.
Stochastic local search (SLS) approaches to MPE often find optimal solutions surprisingly effectively, but they can never prove optimality. This property makes them especially useful for anytime scenarios as they appear frequently, e.g. in sketch recognition and computer vision. The implementations you will find on this website often optimally solve problems with hundreds of variables in milliseconds, regardless of their induced width !
SLS algorithms for MPE solving have previously been explored, but were found to be not competitive with state-of-the-art branch & bound methods. We improved on these previous algorihms by a variety of means (see IJCAI'05 paper and Frank's MSc. thesis for details), yielding two new powerful algorithms that challenge and often substantially improve the state-of-the-art in solving MPE problems. These two algorithms are called ILS (Iterated Local Search) and GLS+ (Guided Local Search+).
Iterated Local Search (ILS) performs a biased random walk over
locally optimal solutions by the following means: Starting from some initial
solution, it applies a basic local search that leads to a local minimum. From
here, it iterates the following steps:
1) pertubation: escape from the local optima region by perturbing the current
solution (this often just flips a number of variables at random)
2) basic local search: steer straight into the next locally optimal solution
(this is often just greedy hill-climbing)
3) accepance criterion: decide whether to accept the new local optimum or reject
it and return to the previous one (this often always accepts improved solutions
and rejects declined solutions with a high probability)
Guided Local Search+ (GLS+) is a particular kind of Dynamic Local Search algorithm. It combines a basic local search (mostly greedy hill-climbing) with a penalty mechnism that is applied in local optimum. Solution features that appear in the current local optimum (but also in other solutions) are penalized to make them less desirable. The subsequent basic local search method uses a modified evaluation function that takes the penalties into account, such that the previous local optimum is not a local optimum anymore and the search can espace. For MPE, this mechanism can be thought of adding new temporary factors to the problem in order to escape from locally optimal solutions.
Here's factor graphs from two different domains. If you use Matlab, you can just call SLS4MPE from there, too (see the MEX interface above).
Two sample factor graphs from Chen Yanover'S
side-chain prediction MRFs.
A sample factor graph
from Martin Szummer's sketch prediction CRFs.
Here's all the data sets we used for the IJCAI paper (all in our own super-simple input format .simple):
Random networks, generated with the generator from Rina Dechter's group | random.tar.gz (7.7MB) |
Random grid networks, generated with the generator from Rina Dechter's group | grid.tar.gz (24.4MB) |
Random networks, generated with BNGenerator from Fabio Cozman's group |
iwscaling-rand.tar.gz (5.8MB) |
Random networks like the above, generated with BNGenerator from Fabio
Cozman's group |
iwscaling-struc.tar.gz (1.5MB) |
Bayesian network repository instances | bnrep.tar.gz (0.7MB) |
Converter from Bayesian network interchange format to .simple (this reads networks into Java Bayes and outputs them in .simple format - it works for all formats Java Bayes can read in) | converter.zip (0.7MB) |
Ruby script for controlled generation of many networks with BNGenerator. This requires BNGenerator. | generate_bns.rb (3KB) |
Please send any questions, concerns or comments to Frank Hutter