论文标题
通过将组合搜索与LP放松限制在地图推导
Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation
论文作者
论文摘要
我们考虑图形模型的地图 - 推荐问题，这是一个有价值的约束满意度问题，该问题在实际数字上定义了自然求和操作。我们提出了一个放松家族（与著名的Sherali-Adams层次结构不同），该家庭自然定义了其最佳限制的下限。这个家庭总是包含一个紧张的放松，我们给出了一种能够找到它的算法，因此解决了最初的非放松的NP-HARD问题。 我们考虑的放松将原始问题分解为两个非重叠部分：简单的LP密度部分和一个困难的部分。对于后一部分，必须使用组合求解器。正如我们在实验中显示的那样，在许多应用中，第二个困难部分仅构成了整个问题的一小部分。该属性可以显着减少组合求解器的计算时间，从而解决以前无法解决的问题。
We consider the MAP-inference problem for graphical models, which is a valued constraint satisfaction problem defined on real numbers with a natural summation operation. We propose a family of relaxations (different from the famous Sherali-Adams hierarchy), which naturally define lower bounds for its optimum. This family always contains a tight relaxation and we give an algorithm able to find it and therefore, solve the initial non-relaxed NP-hard problem. The relaxations we consider decompose the original problem into two non-overlapping parts: an easy LP-tight part and a difficult one. For the latter part a combinatorial solver must be used. As we show in our experiments, in a number of applications the second, difficult part constitutes only a small fraction of the whole problem. This property allows to significantly reduce the computational time of the combinatorial solver and therefore solve problems which were out of reach before.
