Scalable Semidefinite Relaxation for Maximum A Posterior Estimation
Scalable Semidefinite Relaxation for Maximum A Posterior Estimation
复制标题
最大后验估计的可扩展半定松弛
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
L. Guibas
中科院分区：
文献类型：
--
作者：
Qi;Yuxin Chen;L. Guibas
离散马尔可夫随机场上的最大后验 (MAP) 推理是一项涵盖广泛现实世界应用的基本任务，众所周知，这对于一般图来说是 NP 困难的。在本文中，我们提出了一种新颖的半定松弛公式（称为 SDR）来估计 MAP 分配。在算法上，我们开发了乘法器交替方向方法的加速变体（称为 SDPAD-LR），可以有效地利用新松弛的特殊结构。令人鼓舞的是，所提出的过程允许解决大规模问题的 SDR，例如，包含数十万个变量且每个节点具有多个状态的网格图上的问题。与之前的 SDP 求解器相比，SDPAD-LR 能够获得相当的精度，同时表现出显着提高的可扩展性，这与普遍认为半定松弛只能应用于小规模 MRF 问题相反。我们在解决方案的质量和计算时间方面评估了 SDR 在包括 OPENGM2 和 PIC 在内的各种基准数据集上的性能。实验结果表明，对于一大类问题，SDPAD-LR 在以有效的方式产生更好的 MAP 分配方面优于最先进的算法。
Maximum a posteriori (MAP) inference over discrete Markov random fields is a fundamental task spanning a wide spectrum of real-world applications, which is known to be NP-hard for general graphs. In this paper, we propose a novel semidefinite relaxation formulation (referred to as SDR) to estimate the MAP assignment. Algorithmically, we develop an accelerated variant of the alternating direction method of multipliers (referred to as SDPAD-LR) that can effectively exploit the special structure of the new relaxation. Encouragingly, the proposed procedure allows solving SDR for large-scale problems, e.g., problems on a grid graph comprising hundreds of thousands of variables with multiple states per node. Compared with prior SDP solvers, SDPAD-LR is capable of attaining comparable accuracy while exhibiting remarkably improved scalability, in contrast to the commonly held belief that semidefinite relaxation can only been applied on small-scale MRF problems. We have evaluated the performance of SDR on various benchmark datasets including OPENGM2 and PIC in terms of both the quality of the solutions and computation time. Experimental results demonstrate that for a broad class of problems, SDPAD-LR outperforms state-of-the-art algorithms in producing better MAP assignment in an efficient manner.
通过组合优化实现大规模离散计算机视觉问题的高效准确 MAP 推理
DOI：
10.1109/cvpr.2013.229
发表时间：
2013
期刊：
2013 IEEE Conference on Computer Vision and Pattern Recognition
影响因子：
--
作者：
Kappes;M. Speth;G. Reinelt;C. Schnörr
通讯作者：
C. Schnörr