摘要翻译：
最大乘积信念传播是一种局部迭代算法，用于寻找概率分布的模式/地图估计。虽然它已经成功地应用于各种不同的应用中，但对于可能有许多短圈的一般环图，收敛性和正确性的理论保证相对较少。其中，提供确切的“必要和充分”特征的就更少了。本文研究了在任意边权图中用极大积求最大权匹配的问题。这是通过首先构造一个模式对应于最优匹配的概率分布，然后运行max-product来实现的。加权匹配也可以作为一个整数规划，对它有一个LP松弛。这种放松并不总是紧绷的。本文证明了当LP松弛是紧的时，\begin{enumerate}\item,则max-product总是收敛，并且也收敛到正确答案。如果LP松弛松弛，则max-product不收敛。\end{enumerate}这提供了对最大乘积性能的精确的、依赖于数据的表征，以及与LP松弛的精确联系，LP松弛是一种研究得很好的优化技术。另外，由于二部图的LP松弛是紧的，我们的结果推广了最近关于用最大乘积求二部图中加权匹配的其他结果。
---
英文标题：
《Equivalence of LP Relaxation and Max-Product for Weighted Matching in
  General Graphs》
---
作者：
Sujay Sanghavi
---
最新提交年份：
2007
---
分类信息：

一级分类：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中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Machine Learning        机器学习
分类描述：Papers on all aspects of machine learning research (supervised, unsupervised, reinforcement learning, bandit problems, and so on) including also robustness, explanation, fairness, and methodology. cs.LG is also an appropriate primary category for applications of machine learning methods.
关于机器学习研究的所有方面的论文（有监督的，无监督的，强化学习，强盗问题，等等），包括健壮性，解释性，公平性和方法论。对于机器学习方法的应用，CS.LG也是一个合适的主要类别。
--
一级分类：Computer Science        计算机科学
二级分类：Networking and Internet Architecture        网络和因特网体系结构
分类描述：Covers all aspects of computer communication networks, including network architecture and design, network protocols, and internetwork standards (like TCP/IP). Also includes topics, such as web caching, that are directly relevant to Internet architecture and performance. Roughly includes all of ACM Subject Class C.2 except C.2.4, which is more likely to have Distributed, Parallel, and Cluster Computing as the primary subject area.
涵盖计算机通信网络的所有方面，包括网络体系结构和设计、网络协议和网络间标准（如TCP/IP）。还包括与Internet体系结构和性能直接相关的主题，如web缓存。大致包括除C.2.4以外的所有ACM主题类C.2，后者更有可能将分布式、并行和集群计算作为主要主题领域。
--
一级分类：Mathematics        数学
二级分类：Information Theory        信息论
分类描述：math.IT is an alias for cs.IT. Covers theoretical and experimental aspects of information theory and coding.
它是cs.it的别名。涵盖信息论和编码的理论和实验方面。
--

---
英文摘要：
  Max-product belief propagation is a local, iterative algorithm to find the mode/MAP estimate of a probability distribution. While it has been successfully employed in a wide variety of applications, there are relatively few theoretical guarantees of convergence and correctness for general loopy graphs that may have many short cycles. Of these, even fewer provide exact ``necessary and sufficient'' characterizations.   In this paper we investigate the problem of using max-product to find the maximum weight matching in an arbitrary graph with edge weights. This is done by first constructing a probability distribution whose mode corresponds to the optimal matching, and then running max-product. Weighted matching can also be posed as an integer program, for which there is an LP relaxation. This relaxation is not always tight. In this paper we show that \begin{enumerate} \item If the LP relaxation is tight, then max-product always converges, and that too to the correct answer. \item If the LP relaxation is loose, then max-product does not converge. \end{enumerate} This provides an exact, data-dependent characterization of max-product performance, and a precise connection to LP relaxation, which is a well-studied optimization technique. Also, since LP relaxation is known to be tight for bipartite graphs, our results generalize other recent results on using max-product to find weighted matchings in bipartite graphs.
---
PDF链接：
https://arxiv.org/pdf/0705.0760