摘要翻译：
最大乘积算法是一种局部消息传递方案，它试图计算给定概率分布的最可能赋值(MAP)，已成功地作为一种近似推理方法应用于编码理论、计算机视觉和机器学习等领域。然而，最大乘积算法不能保证收敛到映射分配，即使收敛，也不能保证恢复映射分配。为了克服这些困难，人们提出了一些可供选择的收敛消息传递方案。本文系统地研究了这类消息传递算法，通过展示收敛到局部和/或全局最优的新的充分条件，提供了基于图覆盖的这些最优的组合特征，并描述了一种新的收敛和正确的消息传递算法，该算法的推导统一了许多已知的收敛消息传递算法。虽然收敛和正确的消息传递算法在分析最大乘积类型的消息传递算法方面向前迈进了一步，但保证收敛到全局最优所需的条件在理论和实践中都过于限制性。收敛和正确消息传递方案的这种限制用图覆盖来刻画，并用实例加以说明。
---
英文标题：
《Message-Passing Algorithms: Reparameterizations and Splittings》
---
作者：
Nicholas Ruozzi, Sekhar Tatikonda
---
最新提交年份：
2012
---
分类信息：

一级分类：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有交集。
--
一级分类：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中的材料。
--
一级分类：Mathematics        数学
二级分类：Information Theory        信息论
分类描述：math.IT is an alias for cs.IT. Covers theoretical and experimental aspects of information theory and coding.
它是cs.it的别名。涵盖信息论和编码的理论和实验方面。
--

---
英文摘要：
  The max-product algorithm, a local message-passing scheme that attempts to compute the most probable assignment (MAP) of a given probability distribution, has been successfully employed as a method of approximate inference for applications arising in coding theory, computer vision, and machine learning. However, the max-product algorithm is not guaranteed to converge to the MAP assignment, and if it does, is not guaranteed to recover the MAP assignment.   Alternative convergent message-passing schemes have been proposed to overcome these difficulties. This work provides a systematic study of such message-passing algorithms that extends the known results by exhibiting new sufficient conditions for convergence to local and/or global optima, providing a combinatorial characterization of these optima based on graph covers, and describing a new convergent and correct message-passing algorithm whose derivation unifies many of the known convergent message-passing algorithms.   While convergent and correct message-passing algorithms represent a step forward in the analysis of max-product style message-passing algorithms, the conditions needed to guarantee convergence to a global optimum can be too restrictive in both theory and practice. This limitation of convergent and correct message-passing schemes is characterized by graph covers and illustrated by example.
---
PDF链接：
https://arxiv.org/pdf/1002.3239