Simple MAP Inference via Low-Rank Relaxations
Simple MAP Inference via Low-Rank Relaxations
复制标题
通过低阶松弛的简单 MAP 推理
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Christopher D. Manning
中科院分区：
文献类型：
--
作者：
Roy Frostig;Sida I. Wang;Percy Liang;Christopher D. Manning
我们专注于在具有二进制变量和成对相互作用的马尔可夫随机字段中最大后验（MAP）推断的问题。对于这种推理任务的常见子类，我们考虑了低级别的放松，这些放松在离散问题及其全等级半叶片放松之间插值。我们开发了新的理论界限，研究等级的效果，表明随着等级的增长，放松的客观增加但饱和，并且圆形离散解决方案保留的客观值中的比例会减少。在实践中，我们展示了两种算法，用于优化易于实施的低级目标，与基础理论联系，并在基准图映射推理任务上超越现有方法。
We focus on the problem of maximum a posteriori (MAP) inference in Markov random fields with binary variables and pairwise interactions. For this common subclass of inference tasks, we consider low-rank relaxations that interpolate between the discrete problem and its full-rank semidefinite relaxation. We develop new theoretical bounds studying the effect of rank, showing that as the rank grows, the relaxed objective increases but saturates, and that the fraction in objective value retained by the rounded discrete solution decreases. In practice, we show two algorithms for optimizing the low-rank objectives which are simple to implement, enjoy ties to the underlying theory, and outperform existing approaches on benchmark MAP inference tasks.