Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
AND/OR Search for Marginal MAP
Radu Marinescu, Rina Dechter, Alexander Ihler
Abstract:
Marginal MAP problems are known to be very difficult tasks for graphical models and are so far solved exactly by systematic search guided by a join-tree upper bound. In this paper, we develop new AND/OR branch and bound algorithms for marginal MAP that use heuristics extracted from weighted mini-buckets enhanced with message- passing updates. We demonstrate the effective- ness of the resulting search algorithms against previous join-tree based approaches, which we also extend to accommodate high induced width models, through extensive empirical evaluations. Our results show not only orders-of-magnitude improvements over the state-of-the-art, but also the ability to solve problem instances well be- yond the reach of previous approaches.
Keywords:
Pages: 563-572
PS Link:
PDF Link: /papers/14/p563-marinescu.pdf
BibTex:
@INPROCEEDINGS{Marinescu14,
AUTHOR = "Radu Marinescu and Rina Dechter and Alexander Ihler",
TITLE = "AND/OR Search for Marginal MAP",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "563--572"
}


hosted by DSL   •   site info   •   help