Pushing forward marginal map with best-first search
Radu Marinescu, Rina Dechter, Alexander Ihler · 2015
Marginal MAP is known to be a difficult task for graphical models, particularly because the evalu-ation of each MAP assignment involves a condi-tional likelihood computation. In order to minimize the number of likelihood evaluations, we focus in this paper on best-first search strategies for explor-ing the space of partial MAP assignments. We an-alyze the potential relative benefits of several best-first search algorithms and demonstrate their effec-tiveness against recent branch and bound schemes through extensive empirical evaluations. Our re-sults show that best-first search improves signifi-cantly over existing depth-first approaches, in many cases by several orders of magnitude, especially when guided by relatively weak heuristics. 1