May, 2019

置信传播算法中的准确度 - 内存平衡及相变

PDF
TL;DR我们证明了 Evans，Kenyon，Peres 和 Schulman（2000）的猜想，该猜想表明有限内存的消息传递算法在重构问题上在统计上比置信传播要弱得多，并且通过将递归重构、信息论和最优输送的工具结合起来，还建立了 BP 和其他消息传递算法临界阈值附近的渐近正常性结果。
发现论文，激发创造
  • 信念传播快速收敛于全局最优解：超越相关性衰减

    研究图模型中 “信念传播” 的收敛性及其在 Ising 模型中的应用。

    May, 2019

  • 树和低次多项式重构

    本文探究了基于树结构的重建问题上低项式多项式的性能，并显示了与基于多项式的算法相比其存在的限制，此外还提出了相关的开放性问题.

    Sep, 2021

  • 贝叶斯推断问题中的相变类型学

    本文通过对稀疏图上的推理问题的描述和分析，研究了随机块模型的相变以及在信息论上最优化问题变得容易但是在计算上仍具挑战性的的混合硬相位，并阐明了消息传递算法的贝叶斯最优性及其在这些问题中的作用，并通过数值模拟验证了该方法的有效性。

    Jun, 2018

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

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

    Apr, 2010

  • 随机信念传播：一种低复杂度替代乘积和算法的选择

    本文提出了一种低复杂度的信念传播算法 —— 随机信念传播（SBP）算法，该算法是一种自适应随机的 BP 信息传递版本，其信息传递减少了计算复杂度和通讯复杂度，并在各种图形模型中证明了收敛性和计算复杂度降低的理论格局。

    Nov, 2011

  • 多聚类随机块模型中的检测：实现猜想的证明，无环 BP 和信息计算差距

    该论文证明了随机块模型的一个猜想，提出了一种非对称的社区检测算法，并将其与信念传播和谱方法联系起来，同时展示了信息论计算差距在其中的应用。

    Dec, 2015

  • 基于信念传播的众包分类最优推断

    本文研究了在众包标注过程中，利用 Dawid-Skene 模型恢复错误标注并输出正确标注问题，提出了一种更紧密的下限和 Belief Propagation （BP） 算法来解决这一问题。实验结果表明，BP 是所有算法中最优的。

    Feb, 2016

  • 循环置信传播用于近似概率推断

    Circular Belief Propagation (CBP) 是 Belief Propagation (BP) 的扩展，通过学习检测和取消虚假相关性和置信度放大来限制循环引起的消息回声的负面影响，实验结果表明 CBP 在二进制概率图的数值实验中远远超过了 BP，并且与先前提出的算法相比表现良好。

    Mar, 2024

  • 剩余置信传播：异步消息传递的通知调度

    探讨了如何在异步传播中安排消息以实现更快且更频繁地达到固定点，并通过提出残留置信传播（RBP）算法来解决此问题，该算法相对于现有方法在多种挑战性的合成和实际问题中具有更高的收敛率和更短的收敛时间。

    Jun, 2012

  • 连续状态空间的信念传播：具有定量保证的随机传递消息

    本文引入一种新的技术 —— 随机正交序列消息传递（SOSMP）—— 用于计算具有连续随机变量模型中的 BP 固定点，通过对信息的正交级数展开的确定性近似和基础系数的积分更新的蒙特卡洛估计的随机近似 贴近 BP 固定点，此技术已被证明在任何树形图和满足缩小条件的任何图形中的 BP 更新都会收敛到唯一的 BP 固定点的 δ 邻域。同时，我们演示了如何根据所需的近似精度 δ 和兼容性函数的平滑度来选择基础系数的数量，并通过模拟实例和光流估计应用证明了我们理论的正确性。

    Dec, 2012