Oct, 2012

M-Best MAP 问题的高效消息传递算法

PDF
TL;DR本文提出了一种基于信息传递的算法，用于解决最优概率配置的问题，即 M-Best MAP 问题，该算法可以通过研究问题的一个部分拉格朗日松弛问题来暴露问题的组合结构。
map inferenceprobabilistic random field modelm-best map problemmessage-passing algorithmlagrangian relaxation
发现论文，激发创造
  • 利用消息传递来加紧 MAP 的 LP 松弛

    使用双重消息传递算法对线性规划进行松弛，通过迭代选择具有保证改进的集群，解决集群选择问题，成功地在蛋白质侧链放置、蛋白质设计和立体化问题中找到了最有可能的 MAP 配置。

    Jun, 2012

  • 通过（超）树协议达成的 MAP 估计：消息传递和线性规划

    研究了一种计算 Markov 随机场上最大后验概率的最优配置的方法，通过将原始分布分解为树形分布的凸组合来得到上限，提出了两种尝试获得紧密上限的方法，并建立了模式搜索问题 LP 松弛和最大乘积（最小和）消息传递算法之间的联系。

    Aug, 2005

  • 消息传递算法：重新参数化和分割

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

    Feb, 2010

  • 边缘 MAP 的变分算法

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

    Feb, 2012

  • 概率逻辑编程的 MAP 推断

    本文探讨了在概率逻辑编程中计算最大后验概率和最可能解释的问题，并提出了一种将问题表示为二叉决策图并在其上应用动态规划过程的新算法，与 ProbLog 在多个合成数据集上的实验结果相比，PITA 的性能更佳。

    Aug, 2020

  • MAP 复杂性结果和近似方法

    本文研究了贝叶斯网络中最可信赖实例化的计算问题，证明在多种情形下该问题为 NP 完全问题，在多叉树限制下也难以有效近似，采用置信传播的局部搜索方法可提供较准确的估计。

    Dec, 2012

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

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

    Mar, 2024

  • 最大权独立集的消息传递

    探讨在图中找到最大独立集的最大权重问题中使用信息传递算法的方法，并介绍了经典的 max-product 信念传播算法的性能，以及最大化固定点的自然初始化方法对算法收敛的影响。同时发现，在概率分布的 MAP 估计问题中，可以将任何问题都简化为 MWIS 问题，从而为 MAP 估计提供新的洞见和算法。

    Jul, 2008

  • 退火最大后验概率

    提出了一种基于模拟退火的最大后验概率算法 AnnealedMAP，用于解决在大复杂贝叶斯网络中出现的 NP 难问题，结果表明该算法在保持最大后验概率的优良结果的同时，也能解决许多以前的方法无法解决的问题。

    Jul, 2012

  • 具凸性自由能的 MAP 估计，线性规划和信念传播

    本文提出了一种凸型置信传播算法，可以在满足一定条件下，使用单循环图或重加权树的置信传播算法，在准确性上更加理论化地实现最大概率赋值 (MAP)。并且在实验中证明了该方法对一些无法使用传统算法的大型图具有较高的准确率。

    Jun, 2012