From Exact to Anytime Solutions for Marginal MAP
From Exact to Anytime Solutions for Marginal MAP
复制标题
从精确到随时的边际 MAP 解决方案
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Ihler
中科院分区：
文献类型：
--
作者：
Junkyu Lee;Radu Marinescu;R. Dechter;A. Ihler
本文探讨了基于搜索的算法解决边缘MAP任务的图形模型的任何时候的性能。解决这一挑战性任务的现有技术是基于最佳优先搜索，在基于小桶和变分成本转移原理的逻辑学指导下探索AND/OR图。然而，这些方案是不妥协的，因为它们完全解决了问题，或者根本没有解决问题，并且经常遭受内存问题。在这项工作中，我们探讨了众所周知的原则加权搜索转换为最佳优先搜索解算器随时计划。加权最佳优先搜索方案报告的解决方案早期的过程中使用不可接受的启发式，并随后改善解决方案。虽然最近证明加权方案可以为纯MAP任务产生有效的随时行为，但边际MAP更具挑战性（例如，必须对每个解计算条件和）。然而，在广泛的实证分析中，我们表明加权方案对于边际MAP确实非常有效，从而产生了迄今为止针对该任务最有竞争力的方案。
This paper explores the anytime performance of search-based algorithms for solving the Marginal MAP task over graphical models. The current state of the art for solving this challenging task is based on best-first search exploring the AND/OR graph with the guidance of heuristics based on mini-bucket and variational cost-shifting principles. Yet, those schemes are uncompromising in that they solve the problem exactly, or not at all, and often suffer from memory problems. In this work, we explore the well known principle of weighted search for converting best-first search solvers into anytime schemes. The weighted best-first search schemes report a solution early in the process by using inadmissible heuristics, and subsequently improve the solution. While it was demonstrated recently that weighted schemes can yield effective anytime behavior for pure MAP tasks, Marginal MAP is far more challenging (e.g., a conditional sum must be evaluated for every solution). Yet, in an extensive empirical analysis we show that weighted schemes are indeed highly effective for Marginal MAP yielding the most competitive schemes to date for this task.