Pushing Forward Marginal MAP with Best-First Search
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. 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.
@inproceedings{ijcai2015p104,
title = {Pushing Forward Marginal MAP with Best-First Search},
author = {Marinescu, Radu and Dechter, Rina and Ihler, Alexander},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {696--701},
year = {2015},
month = {7},
note = {Main Track},
url = {https://ijcai.org/proceedings/2015/104},
}
TY - CPAPER TI - Pushing Forward Marginal MAP with Best-First Search AU - Marinescu, Radu AU - Dechter, Rina AU - Ihler, Alexander T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 696 EP - 701 UR - https://ijcai.org/proceedings/2015/104 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
