发帖
雷达卡
摘要翻译：
消息传递类算法，如信念传播算法，作为解决各种优化和推理问题的有吸引力的算法，近年来在统计学、信号处理和机器学习领域得到了广泛的关注。BP算法作为一种分散的、易于实现的、经验性较好的算法，在理论上值得关注，但目前还不多见。为了填补这一空白，我们在运筹学领域的经典问题--容量最小费用网络流问题中考虑了BP算法的性能。证明了BP算法在伪多项式时间内收敛于最优解，前提是潜在问题的最优解是唯一的，且问题输入是积分的。此外，我们对BP算法进行了一个简单的改进，给出了一个完全多项式时间随机逼近方案(FPRAS)，该方案不再要求最优解的唯一性。这是第一个BP被证明具有完全多项式运行时间的例子。因此，我们的结果为BP作为解决一类重要优化问题的一种有吸引力的方法的可行性提供了理论依据。
---
英文标题：
《Belief Propagation for Min-cost Network Flow: Convergence and
Correctness》
---
作者：
David Gamarnik, Devavrat Shah, Yehua Wei
---
最新提交年份：
2012
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Discrete Mathematics 离散数学
分类描述：Covers combinatorics, graph theory, applications of probability. Roughly includes material in ACM Subject Classes G.2 and G.3.
涵盖组合学，图论，概率论的应用。大致包括ACM学科课程G.2和G.3中的材料。
--
一级分类：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中的材料。
--
---
英文摘要：
Message passing type algorithms such as the so-called Belief Propagation algorithm have recently gained a lot of attention in the statistics, signal processing and machine learning communities as attractive algorithms for solving a variety of optimization and inference problems. As a decentralized, easy to implement and empirically successful algorithm, BP deserves attention from the theoretical standpoint, and here not much is known at the present stage. In order to fill this gap we consider the performance of the BP algorithm in the context of the capacitated minimum-cost network flow problem - the classical problem in the operations research field. We prove that BP converges to the optimal solution in the pseudo-polynomial time, provided that the optimal solution of the underlying problem is unique and the problem input is integral. Moreover, we present a simple modification of the BP algorithm which gives a fully polynomial-time randomized approximation scheme (FPRAS) for the same problem, which no longer requires the uniqueness of the optimal solution. This is the first instance where BP is proved to have fully-polynomial running time. Our results thus provide a theoretical justification for the viability of BP as an attractive method to solve an important class of optimization problems.
---
PDF链接：
https://arxiv.org/pdf/1004.1586
京公网安备 11010802022788号
