Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
AND/OR Search for Marginal MAP
Radu Marinescu, Rina Dechter, Alexander Ihler
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.
Pages: 563-572
PS Link:
PDF Link: /papers/14/p563-marinescu.pdf
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)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "563--572"

hosted by DSL   •   site info   •   help