Exact MAP Inference by Avoiding Fractional Vertices
Exact MAP Inference by Avoiding Fractional Vertices
复制标题
通过避免分数顶点进行精确的 MAP 推断
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Adam R. Klivans
中科院分区：
文献类型：
--
作者：
Erik M. Lindgren;A. Dimakis;Adam R. Klivans
给定一个图模型，一个基本问题是MAP推理，即根据模型找到最可能的状态配置。虽然这个问题是NP难的，但在实践中可以解决大型实例。一个主要的悬而未决的问题是解释为什么这是真的。我们给出了一个自然的条件下，我们可以证明在多项式时间内进行MAP推理。我们要求LP松弛中超过最优解的分数阶顶点的数量在问题大小上受多项式的限制。这解决了Dimakis、Gohari和温赖特提出的一个悬而未决的问题。相比之下，对于整数规划的一般LP松弛，已知技术只能处理其值超过最优解的分数顶点的恒定数目。我们通过实验验证了这一条件，并展示了如何有效的各种整数规划方法是在消除分数的解决方案。
Given a graphical model, one essential problem is MAP inference, that is, finding the most likely configuration of states according to the model. Although this problem is NP-hard, large instances can be solved in practice. A major open question is to explain why this is true. We give a natural condition under which we can provably perform MAP inference in polynomial time. We require that the number of fractional vertices in the LP relaxation exceeding the optimal solution is bounded by a polynomial in the problem size. This resolves an open question by Dimakis, Gohari, and Wainwright. In contrast, for general LP relaxations of integer programs, known techniques can only handle a constant number of fractional vertices whose value exceeds the optimal solution. We experimentally verify this condition and demonstrate how efficient various integer programming methods are at removing fractional solutions.