TY - JOUR AU - Marinescu, Radu AU - Kishimoto, Akihiro AU - Botea, Adi AU - Dechter, Rina AU - Ihler, Alexander PY - 2019/07/17 Y2 - 2024/03/29 TI - Anytime Recursive Best-First Search for Bounding Marginal MAP JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 33 IS - 01 SE - AAAI Technical Track: Reasoning under Uncertainty DO - 10.1609/aaai.v33i01.33017924 UR - https://ojs.aaai.org/index.php/AAAI/article/view/4792 SP - 7924-7932 AB - <p>Marginal MAP is a difficult mixed inference task for graphical models. Existing state-of-the-art solvers for this task are based on a hybrid best-first and depth-first search scheme that allows them to compute upper and lower bounds on the optimal solution value in an anytime fashion. These methods however are memory intensive schemes (via the best-first component) and do not have an efficient memory management mechanism. For this reason, they are often less effective in practice, especially on difficult problem instances with very large search spaces. In this paper, we introduce a new recursive best-first search based bounding scheme that operates efficiently within limited memory and computes anytime upper and lower bounds that improve over time. An empirical evaluation demonstrates the effectiveness of our proposed approach against current solvers.</p> ER -