Anytime Recursive Best-First Search for Bounding Marginal MAP

  • Radu Marinescu IBM
  • Akihiro Kishimoto IBM Research
  • Adi Botea IBM Research
  • Rina Dechter University of California, Irvine
  • Alexander Ihler University of California, Irvine

Abstract

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.

Published
2019-07-17
Section
AAAI Technical Track: Reasoning under Uncertainty