---
title: "Pushing Forward Marginal MAP with Best-First Search"
authors:
  - "Radu Marinescu"
  - "Rina Dechter"
  - "Alexander Ihler"
doi: ""
url: "https://ijcai.org/proceedings/2015/104"
pdf: "https://ijcai.org/proceedings/2015/0104.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "696-701"
track: "Main Track"
keywords:
---

# Pushing Forward Marginal MAP with Best-First Search

Radu Marinescu, Rina Dechter, Alexander Ihler

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 696-701.

## 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 significantly over existing depth-first approaches, in many cases by several orders of magnitude, especially when guided by relatively weak heuristics.