摘要翻译:
在图形模型中计算最大后验概率(MAP)估计是一个重要的推理问题,有着广泛的应用。本文给出了二次规划(QP)的消息传递算法,两两马尔可夫随机场的MAP估计公式。特别地,我们利用凹凸过程(CCCP)得到了非凸QP公式的局部最优算法。用类似的方法导出了映射的凸QP松弛的全局收敛算法。我们还表明,从CCCP的角度可以导出最近发展的MAP的QP公式的期望最大化(EM)算法。在综合问题和实际问题上的实验证实,我们的新方法与最大乘积及其变体相比是有竞争力的。与CPLEX相比,我们在最优解凸QP松弛问题上获得了一个数量级以上的加速。
---
英文标题:
《Message-Passing Algorithms for Quadratic Programming Formulations of MAP
Estimation》
---
作者:
Akshat Kumar, Shlomo Zilberstein
---
最新提交年份:
2012
---
分类信息:
一级分类:Computer Science 计算机科学
二级分类:Artificial Intelligence 人工智能
分类描述:Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域,除了视觉、机器人、机器学习、多智能体系统以及计算和语言(自然语言处理),这些领域有独立的学科领域。特别地,包括专家系统,定理证明(尽管这可能与计算机科学中的逻辑重叠),知识表示,规划,和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类:Computer Science 计算机科学
二级分类:Data Structures and Algorithms 数据结构与算法
分类描述:Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
一级分类:Statistics 统计学
二级分类:Computation 计算
分类描述:Algorithms, Simulation, Visualization
算法、模拟、可视化
--
---
英文摘要:
Computing maximum a posteriori (MAP) estimation in graphical models is an important inference problem with many applications. We present message-passing algorithms for quadratic programming (QP) formulations of MAP estimation for pairwise Markov random fields. In particular, we use the concave-convex procedure (CCCP) to obtain a locally optimal algorithm for the non-convex QP formulation. A similar technique is used to derive a globally convergent algorithm for the convex QP relaxation of MAP. We also show that a recently developed expectation-maximization (EM) algorithm for the QP formulation of MAP can be derived from the CCCP perspective. Experiments on synthetic and real-world problems confirm that our new approach is competitive with max-product and its variations. Compared with CPLEX, we achieve more than an order-of-magnitude speedup in solving optimally the convex QP relaxation.
---
PDF链接:
https://arxiv.org/pdf/1202.3739