Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching
Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching
复制标题
通过重新加权完美匹配在 NP 困难二进制 MRF 中进行多项式时间精确推理
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
N. Schraudolph
中科院分区：
文献类型：
--
作者：
N. Schraudolph
我们开发了一种新的重权形式（Wainwright et al., 2005b），利用伊辛自旋玻璃和完美匹配之间的关系，将其转化为一种新技术，用于精确计算迄今为止难以处理的二元马尔可夫随机场中的MAP状态。我们的方法求解具有外场和随机耦合的nxn晶格的速度比最佳竞争算法快得多，并且对于较大的n。它的经验尺度为O(n)，尽管这个问题是np困难的，并且在多项式时间内不可近似。我们讨论了当前实现的局限性，并提出了克服它们的方法。
We develop a new form of reweighting (Wainwright et al., 2005b) to leverage the relationship between Ising spin glasses and perfect matchings into a novel technique for the exact computation of MAP states in hitherto intractable binary Markov random fields. Our method solves an n× n lattice with external field and random couplings much faster, and for larger n, than the best competing algorithms. It empirically scales as O(n) even though this problem is NP-hard and nonapproximable in polynomial time. We discuss limitations of our current implementation and propose ways to overcome them.