研究了贝叶斯网络中 MAP 问题的复杂性,发现即使 MPE 和 Pr 可以轻松计算,MAP 仍然很难。为了找到一个接近最优解的算法,提出了一种通用的 MAP 近似框架,并给出了两个具体的实现,用于对那些即使 Pr 和 MPE 都难以计算的网络进行近似。实验结果表明,这些算法比标准技术提供更好的解决方案,并在许多情况下提供准确的 MAP 估计。
Jun, 2011
该论文介绍了一种新的、简单的 MAP 解的概率上限,并使用该上限提出了一种分支定界搜索算法,能够准确高效地解决一些网络的 MAP 问题,这些网络的约束树宽度超过了 40。
Oct, 2012
提出了一种基于模拟退火的最大后验概率算法 AnnealedMAP,用于解决在大复杂贝叶斯网络中出现的 NP 难问题,结果表明该算法在保持最大后验概率的优良结果的同时,也能解决许多以前的方法无法解决的问题。
Jul, 2012
本文探讨了在概率逻辑编程中计算最大后验概率和最可能解释的问题,并提出了一种将问题表示为二叉决策图并在其上应用动态规划过程的新算法,与 ProbLog 在多个合成数据集上的实验结果相比,PITA 的性能更佳。
Aug, 2020
本文提出了一种凸型置信传播算法,可以在满足一定条件下,使用单循环图或重加权树的置信传播算法,在准确性上更加理论化地实现最大概率赋值 (MAP)。并且在实验中证明了该方法对一些无法使用传统算法的大型图具有较高的准确率。
Jun, 2012
近似推理是通过使用神经网络来近似代表大型概率分布,该方法通过在查询变量上使用连续多线性函数来近似赋值的代价,并通过神经网络输出解决方案。本论文通过在多个基准数据集上的评估表明,该方法在求解概率电路中的最大边后验和边后验最大估计任务时优于竞争的线性时间近似方法。
Feb, 2024
本文介绍了 MAP - 独立性 的概念,探讨了它对最佳解释推理的合理化的作用,并基于该概念形式化了几个计算问题并评估了它们的计算复杂性。
Aug, 2022
本文提出了一种基于信息传递的算法,用于解决最优概率配置的问题,即 M-Best MAP 问题,该算法可以通过研究问题的一个部分拉格朗日松弛问题来暴露问题的组合结构。
研究了一种计算 Markov 随机场上最大后验概率的最优配置的方法,通过将原始分布分解为树形分布的凸组合来得到上限,提出了两种尝试获得紧密上限的方法,并建立了模式搜索问题 LP 松弛和最大乘积(最小和)消息传递算法之间的联系。
Aug, 2005
本文提出了新的度量区间不等式方法,用于估算低维度 MAP 扰动期望值所需的样本数量,通过将该通用结果应用于 MAP 扰动,可以产生更有效的算法以从 Gibbs 分布中近似采样。
Oct, 2013