Systematic vs. Non-systematic Algorithms for Solving the MPE Task
This addresses the problem of efficiently solving the MPE task in Bayesian Networks, which is incremental as it builds on prior work comparing systematic and non-systematic methods.
The paper compares systematic Branch and Bound algorithms (BBBT and BBMB) against local search algorithms for solving the Most Probable Explanation task in Bayesian Networks, showing empirically that BBBT/BBMB are superior, especially with larger domain sizes, and are currently the best-performing algorithms for this task.
The paper continues the study of partitioning based inference of heuristics for search in the context of solving the Most Probable Explanation task in Bayesian Networks. We compare two systematic Branch and Bound search algorithms, BBBT (for which the heuristic information is constructed during search and allows dynamic variable/value ordering) and its predecessor BBMB (for which the heuristic information is pre-compiled), against a number of popular local search algorithms for the MPE problem. We show empirically that, when viewed as approximation schemes, BBBT/BBMB are superior to all of these best known SLS algorithms, especially when the domain sizes increase beyond 2. This is in contrast with the performance of SLS vs. systematic search on CSP/SAT problems, where SLS often significantly outperforms systematic algorithms. As far as we know, BBBT/BBMB are currently the best performing algorithms for solving the MPE task.