Probabilistic inference in pairwise Markov Random Fields (MRFs), i.e. computing the partition function or computing a MAP estimate of the variables, is a foundational problem in probabilistic graphical models. Semidefinite programming relaxations have long been a theoretically powerful tool for analyzing properties of probabilistic inference, but have not been practical owing to the high computational cost of typical solvers for solving the resulting SDPs. In this paper, we propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF by instead exploiting a recently proposed coordinate-descent-based fast semidefinite solver. We also extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver. We show that the method substantially outperforms (both in terms of solution quality and speed) the existing state of the art in approximate inference, on benchmark problems drawn from previous work. We also show that our approach can scale to large MRF domains such as fully-connected pairwise CRF models used in computer vision.


翻译:在配对的Markov随机字段(MRFs)中,计算分区函数或计算对变量的MAP估计值(MRFs)是概率图形模型的一个基本问题。半无限制编程放松长期以来一直是分析概率推断特性的一个具有理论效力的工具,但由于典型解算器解决由此产生的 SDP 的计算成本高,因此不切实际。在本文中,我们提出了一个在配对式MRF中计算分区函数或MAP估计值的有效方法,办法是利用最近提议的基于协调的世系快速半成型解答器。我们还将半无限制从典型的二进制MRF扩展至整个多级设置,并开发一个能够再次用解析器有效解决的小型半成型放松。我们表明,该方法大大偏离了(在溶解质量和速度方面)关于从先前工作中得出的基准问题的近似推论状态。我们还表明,我们的方法可以将大型MRF模型从典型的二进到完全相联式的计算机模型中,作为完全相联式通用报告格式。

0
下载
关闭预览

相关内容

马尔可夫随机场(Markov Random Field),也有人翻译为马尔科夫随机场,马尔可夫随机场是建立在马尔可夫模型和贝叶斯理论基础之上的,它包含两层意思:一是什么是马尔可夫,二是什么是随机场。
和积网络综述论文,Sum-product networks: A survey,24页pdf
专知会员服务
23+阅读 · 2020年4月3日
【快讯】CVPR2020结果出炉,1470篇上榜, 你的paper中了吗?
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Arxiv
5+阅读 · 2020年3月16日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Top
微信扫码咨询专知VIP会员