Computing the most probable explanation is an important inference problem in
graphical models, such as Bayesian networks and Markov random fields (MRFs).
I have done some research on Stochastic Local Search (SLS) algorithms for solving
this problem (see my papers), and this webpage
contains my code and the MPE instances I used..
Here's the data sets (all in my own super-simply input format .simple):
| Random networks, generated with the generator from Rina Dechter's group | random.tar (7.7MB) |
| Random grid networks, generated with the generator from Rina Dechter's group | grid.tar (24.4MB) |
|
Random networks, generated with BNGenerator from Fabio Cozman's group |
iwscaling-rand.tar (5.8MB) |
| Bayesian network repository instances | bnrep.tar (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) |
Here's the version of my MPE solver GLS+ used to generate the results in our IJCAI-05 paper: gls+.tar.gz (36KB). It only reads my .simple format.
The newest version (not online yet) is a bit faster by using a heap to keep track of the most promising variable flips, and it can solve the MPE problem in general factor graphs (including Markov random fields !).
Since it was minimal overhead, I also support reading in SAT instances. Since GLS+ builds an N-dimensional potential with 2^N entries for every clause over N variables, it performs really poorly for instances with large clauses. But it's not all that bad for random 3-SAT. It should also be pretty good for weighted 2-SAT (which is still NP-hard).
I'm currently extending this solver to compute the M most probable explanations
by keeping track of the best solutions encountered so far.
This version will be online soon, along with some MRFs.