IEEE Trans Pattern Anal Mach Intell. 2015 Jul;37(7):1455-68. doi: 10.1109/TPAMI.2014.2363833.
Many inference tasks in pattern recognition and artificial intelligence lead to partition functions in which addition and multiplication are abstract binary operations forming a commutative semiring. By generalizing max-sum diffusion (one of convergent message passing algorithms for approximate MAP inference in graphical models), we propose an iterative algorithm to upper bound such partition functions over commutative semirings. The iteration of the algorithm is remarkably simple: change any two factors of the partition function such that their product remains the same and their overlapping marginals become equal. In many commutative semirings, repeating this iteration for different pairs of factors converges to a fixed point when the overlapping marginals of every pair of factors coincide. We call this state marginal consistency. During that, an upper bound on the partition function monotonically decreases. This abstract algorithm unifies several existing algorithms, including max-sum diffusion and basic constraint propagation (or local consistency) algorithms in constraint programming. We further construct a hierarchy of marginal consistencies of increasingly higher levels and show than any such level can be enforced by adding identity factors of higher arity (order). Finally, we discuss instances of the framework for several semirings, including the distributive lattice and the max-sum and sum-product semirings.
模式识别和人工智能中的许多推理任务都涉及到分区函数，其中加和乘是形成可交换半环的抽象二进制运算。通过推广最大和扩散（图形模型中用于近似 MAP 推理的收敛消息传递算法之一），我们提出了一种迭代算法，可以对可交换半环上的此类分区函数进行上界估计。该算法的迭代非常简单：改变分区函数的任意两个因子，使得它们的乘积保持不变，并且它们的重叠边缘变得相等。在许多可交换半环中，当每个因子对的重叠边缘相同时，重复此迭代对不同因子对进行操作，当重叠边缘相同时，算法会收敛到一个固定点。我们称此状态为边缘一致性。在此期间，分区函数的上界单调递减。该抽象算法统一了几种现有的算法，包括最大和扩散以及约束规划中的基本约束传播（或局部一致性）算法。我们进一步构建了一个越来越高级别的边缘一致性层次结构，并证明了通过添加更高阶（顺序）的恒等因子可以强制实施任何此类级别。最后，我们讨论了该框架在几个半环上的实例，包括分配格以及最大和和和积半环。
