Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Systematic vs. Non-systematic Algorithms for Solving the MPE Task
Radu Marinescu, Kalev Kask, Rina Dechter
Abstract:
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
Keywords:
Pages: 394-402
PS Link:
PDF Link: /papers/03/p394-marinescu.pdf
BibTex:
@INPROCEEDINGS{Marinescu03,
AUTHOR = "Radu Marinescu and Kalev Kask and Rina Dechter",
TITLE = "Systematic vs. Non-systematic Algorithms for Solving the MPE Task",
BOOKTITLE = "Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2003",
PAGES = "394--402"
}


hosted by DSL   •   site info   •   help