论文标题
剪切始终找到Potts型号的全局最佳（带有捕获）
Graph cuts always find a global optimum for Potts models (with a catch)
论文作者
论文摘要
我们证明，用于地图推理的$α$ - 膨胀算法始终返回具有Potts成对电位的马尔可夫随机字段的全球最佳分配，并具有捕获：返回的分配只能保证在原始问题实例的小型扰动中对实例中的实例最佳。换句话说，关于扩展动作的所有局部最小值都是全球最小值，对于问题的略微扰动。在“现实世界”实例上，问题的小扰动的地图分配应与原始问题实例的地图分配非常相似。我们设计了一种算法，可以证明在实践中是否是这种情况。在来自计算机视觉的几个地图推理问题实例上，该算法证明将解决方案映射到所有这些扰动都非常接近原始实例的解决方案。这些结果共同完成了实践中“剪图”算法的良好性能的凝聚力解释。每个局部扩展最小值都是该问题的少量扰动的全球最小值，所有这些全球最小值都接近原始解决方案。
We prove that the $α$-expansion algorithm for MAP inference always returns a globally optimal assignment for Markov Random Fields with Potts pairwise potentials, with a catch: the returned assignment is only guaranteed to be optimal for an instance within a small perturbation of the original problem instance. In other words, all local minima with respect to expansion moves are global minima to slightly perturbed versions of the problem. On "real-world" instances, MAP assignments of small perturbations of the problem should be very similar to the MAP assignment(s) of the original problem instance. We design an algorithm that can certify whether this is the case in practice. On several MAP inference problem instances from computer vision, this algorithm certifies that MAP solutions to all of these perturbations are very close to solutions of the original instance. These results taken together give a cohesive explanation for the good performance of "graph cuts" algorithms in practice. Every local expansion minimum is a global minimum in a small perturbation of the problem, and all of these global minima are close to the original solution.
