|

R219
Pushing Forward Marginal MAP with Best-First Search
Radu Marinescu, Rina Dechter, and Alexander Ihler

Abstract
Marginal MAP is known to be a difficult task for graphical models, particularly because the evaluation of each MAP assignment involves a conditional likelihood computation. In order to minimize the number of likelihood evaluations, we focus in this paper on best-first search strategies for exploring the space of partial MAP assignments. We analyze the potential relative benefits of several best-first search algorithms and demonstrate their effectiveness against recent branch and bound schemes through extensive empirical evaluations. Our results show that best-first search improves signi´Čücantly over existing depth-first approaches, in many cases by several orders of magnitude, especially when guided by relatively weak heuristics.

[pdf]