Anytime Best+Depth-First Search for Bounding Marginal MAP
Anytime Best+Depth-First Search for Bounding Marginal MAP
复制标题
边界边缘地图的任何时间最佳深度优先搜索
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
R. Dechter
中科院分区：
文献类型：
--
作者：
Radu Marinescu;Junkyu Lee;A. Ihler;R. Dechter
我们引入了新的随时搜索算法，将最佳优先与深度优先搜索结合到图形模型中边缘 MAP 推理的混合方案中。主要目标是促进随时生成上限（通过最佳优先部分）和解决方案的下限（通过深度优先部分）。我们与当前最好的两种最先进的方案进行比较，结果表明，我们的最佳+深度搜索方案可以更快地产生更高质量的解决方案，同时也对其准确性产生限制，这可用于在搜索过程中衡量解决方案的质量。广泛的实证评估证明了我们新方法的有效性，该新方法具有最佳优先（搜索最优性）和深度优先（记忆鲁棒性）的优势，为以前的求解器甚至无法找到单个解决方案的困难情况提供了解决方案。
We introduce new anytime search algorithms that combine best-first with depth-first search into hybrid schemes for Marginal MAP inference in graphical models. The main goal is to facilitate the generation of upper bounds (via the best-first part) alongside the lower bounds of solutions (via the depth-first part) in an anytime fashion. We compare against two of the best current state-of-the-art schemes and show that our best+depth search scheme produces higher quality solutions faster while also producing a bound on their accuracy, which can be used to measure solution quality during search. An extensive empirical evaluation demonstrates the effectiveness of our new methods which enjoy the strength of best-first (optimality of search) and of depth-first (memory robustness), leading to solutions for difficult instances where previous solvers were unable to find even a single solution.