使用系统搜索精确解决 MAP 问题
本文研究了贝叶斯网络中最可信赖实例化的计算问题,证明在多种情形下该问题为 NP 完全问题,在多叉树限制下也难以有效近似,采用置信传播的局部搜索方法可提供较准确的估计。
Dec, 2012
研究了贝叶斯网络中 MAP 问题的复杂性,发现即使 MPE 和 Pr 可以轻松计算,MAP 仍然很难。为了找到一个接近最优解的算法,提出了一种通用的 MAP 近似框架,并给出了两个具体的实现,用于对那些即使 Pr 和 MPE 都难以计算的网络进行近似。实验结果表明,这些算法比标准技术提供更好的解决方案,并在许多情况下提供准确的 MAP 估计。
Jun, 2011
提出了一种基于模拟退火的最大后验概率算法 AnnealedMAP,用于解决在大复杂贝叶斯网络中出现的 NP 难问题,结果表明该算法在保持最大后验概率的优良结果的同时,也能解决许多以前的方法无法解决的问题。
Jul, 2012
提出了一种新的任何时间算法解决图模型中的边际 MAP 问题,该算法可以在多项式时间内运行且当模型的图具有有限的树宽时,可以提供下限和上限保证。实验表明它可以在具有多个 MAP 变量和中等树宽的问题中表现得很好,并且相比 Park 和 Darwiche 的系统搜索而言有更好的表现。
Jun, 2012
研究了一种计算 Markov 随机场上最大后验概率的最优配置的方法,通过将原始分布分解为树形分布的凸组合来得到上限,提出了两种尝试获得紧密上限的方法,并建立了模式搜索问题 LP 松弛和最大乘积(最小和)消息传递算法之间的联系。
Aug, 2005
本文提出了一种基于信息传递的算法,用于解决最优概率配置的问题,即 M-Best MAP 问题,该算法可以通过研究问题的一个部分拉格朗日松弛问题来暴露问题的组合结构。
Oct, 2012
本文探讨了在概率逻辑编程中计算最大后验概率和最可能解释的问题,并提出了一种将问题表示为二叉决策图并在其上应用动态规划过程的新算法,与 ProbLog 在多个合成数据集上的实验结果相比,PITA 的性能更佳。
Aug, 2020
本文介绍了一种基于贝叶斯模型选择方法的新算法,通过在网络变量之间建立固定顺序的基础上逼近特征的贝叶斯后验概率,并使用马尔可夫蒙特卡罗方法,使得顺序空间更加平滑,对与其它方法进行了比较实验。
Jan, 2013
本文提出了新的度量区间不等式方法,用于估算低维度 MAP 扰动期望值所需的样本数量,通过将该通用结果应用于 MAP 扰动,可以产生更有效的算法以从 Gibbs 分布中近似采样。
Oct, 2013