标题： 块稳定性用于MAP推断 显示英文标题

标题： Block Stability for MAP Inference

摘要： 为了理解近似MAP推断的实证成功，近期的研究（Lang等，2018）表明，当输入实例是稳定的时，一些流行的近似算法表现非常好。最简单的稳定性条件假设当某些成对势能被（对抗性地）扰动时，MAP解完全不会改变。不幸的是，这种强条件在实践中似乎并不满足。在本文中，我们引入了一个显著更宽松的条件，该条件仅要求输入实例的块（部分）是稳定的。在这一块稳定性条件下，我们证明成对LP松弛在稳定块上是持久的。我们通过计算机视觉中的实际MAP推断实例进行经验评估来补充我们的理论结果。我们设计了一个算法来找到稳定块，并发现这些实际实例具有大的稳定区域。我们的工作为这种LP松弛的广泛实证现象提供了理论解释。 显示英文摘要

摘要： To understand the empirical success of approximate MAP inference, recent work (Lang et al., 2018) has shown that some popular approximation algorithms perform very well when the input instance is stable. The simplest stability condition assumes that the MAP solution does not change at all when some of the pairwise potentials are (adversarially) perturbed. Unfortunately, this strong condition does not seem to be satisfied in practice. In this paper, we introduce a significantly more relaxed condition that only requires blocks (portions) of an input instance to be stable. Under this block stability condition, we prove that the pairwise LP relaxation is persistent on the stable blocks. We complement our theoretical results with an empirical evaluation of real-world MAP inference instances from computer vision. We design an algorithm to find stable blocks, and find that these real instances have large stable regions. Our work gives a theoretical explanation for the widespread empirical phenomenon of persistency for this LP relaxation.