论文标题
解决MAP-MRF问题的放松问题：组合弗兰克 - 沃尔夫方向
Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions
论文作者
论文摘要
我们考虑了解决MAP-MRF推理问题的LP松弛问题的问题，尤其是最近提出的方法（Swoboda，Kolmogorov，2019年； Kolmogorov，Kolmogorov，Pock 2021）。作为关键的计算子例程，它使用了Frank-Wolfe（FW）方法的变体来最大程度地降低组合型多层的光滑凸功能。我们提出了基于弗兰克·沃尔夫（Frank-Wolfe）的方向（Freund etal。2017）在不同背景下引入的该子普鲁丁的有效实施。更一般而言，我们为组合子问题定义了一个抽象数据结构，该结构可以启用fw fw方向，并描述其针对树结构化MAP-MRF推理子问题的专业化。实验结果表明，所得的方法是某些类别问题的当前最新LP求解器。我们的代码可在https://pub.ist.ac.at/~vnk/papers/in-face-fw.html上找到。
We consider the problem of solving LP relaxations of MAP-MRF inference problems, and in particular the method proposed recently in (Swoboda, Kolmogorov 2019; Kolmogorov, Pock 2021). As a key computational subroutine, it uses a variant of the Frank-Wolfe (FW) method to minimize a smooth convex function over a combinatorial polytope. We propose an efficient implementation of this subproutine based on in-face Frank-Wolfe directions, introduced in (Freund et al. 2017) in a different context. More generally, we define an abstract data structure for a combinatorial subproblem that enables in-face FW directions, and describe its specialization for tree-structured MAP-MRF inference subproblems. Experimental results indicate that the resulting method is the current state-of-art LP solver for some classes of problems. Our code is available at https://pub.ist.ac.at/~vnk/papers/IN-FACE-FW.html.
