May, 2012

收敛的信息传递算法 - 统一视角

PDF
TL;DR本文介绍了一种统一的收敛信息传递算法，称为 tree-consistency bound optimization (TCBO), 它可以在变分推理问题的 sum 和 max product forms 中都被证明是收敛的，并且将已有的算法中的极大化和求和进行交换后，可以获得新的收敛算法，特别是当树是单调链时，Wainwright 的非收敛 sum-product 算法实际上是收敛的。
message-passing algorithmsconvergencegraphical modelsvariational formulationssum and max product forms
发现论文，激发创造
  • 消息传递算法：重新参数化和分割

    本文系统研究了局部和 / 或全局最优解的收敛充分条件，提供了基于图覆盖的这些最优解的组合特征，并描述了一种新的收敛合理的消息传递算法，其推导统一了许多已知的收敛消息传递算法。

    Feb, 2010

  • 一些凸型消息传递算法的收敛到一个固定点

    该研究提出了一种基于坐标下降的方法来解决图模型中的 MAP 推理问题，并证明了该方法的迭代会收敛到算法的一个固定点，且在 O (1/ε) 次迭代内达到精度 ε>0。

    Mar, 2024

  • 二次优化问题的最小总和消息传递收敛性

    该论文研究了在满足凸分解条件的广义二次目标函数下，最小 - 和消息传递算法的收敛性，同时也适用于高斯置信传播算法的收敛性问题。

    Mar, 2006

  • 定向树的收敛传播算法

    本文介绍了一种基于树分解算法的信息传递方法，用于解决基于图的模型中的优化问题，并保证收敛于全局最优解。

    Jun, 2012

  • 一般图上具有凸自由能的收敛消息传递算法推断

    论文介绍了两种高效的基于 BP 算法的算法，保证收敛到凸自由能的全局最小值，提出了一种基于图的结构自动设置凸自由能参数的启发式方法。

    Jun, 2012

  • 分布式系统中的健壮概率推断

    本文研究了概率推断问题在分布式系统中的应用，提出了一种新的基于消息传递的算法，相较于传统的 sum-product 算法，该算法对节点故障和通信失效有更好的稳健性，且在网络拓扑复杂时具有更优的计算复杂度，并用传感器网络定标任务进行了实验验证。

    Jul, 2012

  • 边缘 MAP 的变分算法

    本文针对图像模型的边缘 MAP 问题，提出了一种变分框架，运用 Bethe、tree-reweighted、mean field 逼近等方法得出 mixed message passing algorithm 和使用 CCCP 解决 BP-type 逼近的算法，并在实验中证明了我们的算法优于相关方法。此外，本文还表明 EM 和 variational EM 组成我们框架的一个特殊情况。

    Feb, 2012

  • 基于范数乘积的置信度传播算法：用于近似推理的原始对偶消息传递

    本文介绍了一种统一的消息传递算法架构来处理概率推断的两种形式：估计联合分布的边缘概率和找到最可能的分配，通过推广和介绍新的收敛算法，如 “凸自由能” 和线性规划松弛.

    Mar, 2009

  • 一种基于残差的约束满足问题信息传递算法

    在约束满足问题（CSPs）的上下文中，我们将基于残差的更新步骤引入到消息传递算法中，解决了算法在迭代过程中产生的振荡问题，提高了算法的收敛性和在解决最优化问题时的成功率。

    Feb, 2022

  • 最小费用网络流的置信传播：收敛性与正确性

    本研究证明了置信传播算法在容量约束最小费用网络流问题上的全多项式运行时间，还证明了算法的随机逼近方案，这提供了理论依据支持置信传播算法成为解决一类重要的优化问题的有吸引力的方法。

    Apr, 2010