摘要翻译：
树重加权最大乘积(TRW)消息传递是对普通最大乘积算法的一种改进形式，它试图在带循环的马尔可夫随机场中寻找最小能量配置。对于满足强树一致性条件的TRW不动点，该算法输出可证明最优的配置。本文研究了二元变量两两耦合的情形，建立了只满足弱树协议(WTA)较温和条件的TRW不动点的较强性质。首先，我们证明了如何在不知道完全解的情况下识别出部分最优解，即一个节点子集的可证最优解。其次，我们证明了对于子模函数，WTA不动点总是产生全局最优解。我们证明了对于二元变量，任何WTA不动点总是达到TRW方法下的线性规划松弛的全局最大值。
---
英文标题：
《On the optimality of tree-reweighted max-product message-passing》
---
作者：
Vladimir Kolmogorov, Martin Wainwright
---
最新提交年份：
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中的材料。
--

---
英文摘要：
  Tree-reweighted max-product (TRW) message passing is a modified form of the ordinary max-product algorithm for attempting to find minimal energy configurations in Markov random field with cycles. For a TRW fixed point satisfying the strong tree agreement condition, the algorithm outputs a configuration that is provably optimal. In this paper, we focus on the case of binary variables with pairwise couplings, and establish stronger properties of TRW fixed points that satisfy only the milder condition of weak tree agreement (WTA). First, we demonstrate how it is possible to identify part of the optimal solution|i.e., a provably optimal solution for a subset of nodes| without knowing a complete solution. Second, we show that for submodular functions, a WTA fixed point always yields a globally optimal solution. We establish that for binary variables, any WTA fixed point always achieves the global maximum of the linear programming relaxation underlying the TRW method.
---
PDF链接：
https://arxiv.org/pdf/1207.1395