摘要翻译：
本文通过一个统一的消息传递算法体系结构，讨论了概率推理的两种形式，即估计联合分布的边际概率和寻找最大概率分配。我们推广了信度传播(BP)和积与最大积算法和树重迭(TRW)和积与最大积算法(TRBP),并引入了一组基于“无凸能量”和线性规划(LP)松弛作为无凸能量零点的新收敛算法。本文的主要思想来自于对现有的BP和TRBP算法的全面考察，同时注意到它们都是对基本优化公式$F+\sum_i H_i$的约简，其中函数$F$是一个扩展值函数，严格凸但非光滑，函数$H_i$是扩展值函数（不一定是凸的）。我们利用凸对偶的工具给出了“原始-对偶上升”算法，它是Bregman逐次投影格式的推广，旨在处理一般类型$f+\sum_i h_i$的优化问题。将分数自由能变分原理映射到这个框架中引入了“范数积”消息传递。特例包括和积和最大积（BP算法）和TRBP算法。当分数自由能是凸的（凸自由能）时，范数积在估计边际概率和逼近LP松弛方面是全局收敛的。我们还介绍了范数积的另一个分支--凸极大积。凸极大积是收敛的（与极大积不同），其目的是解决LP-松弛问题。
---
英文标题：
《Norm-Product Belief Propagation: Primal-Dual Message-Passing for
  Approximate Inference》
---
作者：
Tamir Hazan and Amnon Shashua
---
最新提交年份：
2010
---
分类信息：

一级分类：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        计算机科学
二级分类：Information Theory        信息论
分类描述：Covers theoretical and experimental aspects of information theory and coding. Includes material in ACM Subject Class E.4 and intersects with H.1.1.
涵盖信息论和编码的理论和实验方面。包括ACM学科类E.4中的材料，并与H.1.1有交集。
--
一级分类：Mathematics        数学
二级分类：Information Theory        信息论
分类描述：math.IT is an alias for cs.IT. Covers theoretical and experimental aspects of information theory and coding.
它是cs.it的别名。涵盖信息论和编码的理论和实验方面。
--

---
英文摘要：
  In this paper we treat both forms of probabilistic inference, estimating marginal probabilities of the joint distribution and finding the most probable assignment, through a unified message-passing algorithm architecture. We generalize the Belief Propagation (BP) algorithms of sum-product and max-product and tree-rewaighted (TRW) sum and max product algorithms (TRBP) and introduce a new set of convergent algorithms based on "convex-free-energy" and Linear-Programming (LP) relaxation as a zero-temprature of a convex-free-energy. The main idea of this work arises from taking a general perspective on the existing BP and TRBP algorithms while observing that they all are reductions from the basic optimization formula of $f + \sum_i h_i$ where the function $f$ is an extended-valued, strictly convex but non-smooth and the functions $h_i$ are extended-valued functions (not necessarily convex). We use tools from convex duality to present the "primal-dual ascent" algorithm which is an extension of the Bregman successive projection scheme and is designed to handle optimization of the general type $f + \sum_i h_i$. Mapping the fractional-free-energy variational principle to this framework introduces the "norm-product" message-passing. Special cases include sum-product and max-product (BP algorithms) and the TRBP algorithms. When the fractional-free-energy is set to be convex (convex-free-energy) the norm-product is globally convergent for estimating of marginal probabilities and for approximating the LP-relaxation. We also introduce another branch of the norm-product, the "convex-max-product". The convex-max-product is convergent (unlike max-product) and aims at solving the LP-relaxation.
---
PDF链接：
https://arxiv.org/pdf/0903.3127