Aug, 2015

通过基于图模型的迭代松弛推断达到最大持久性

PDF
TL;DR本文提出了一种用于找到 NP 难问题下离散图像模型 MAP 推理的部分最优解的算法，并通过使用一个线性规划松弛的精确求解器，标记出一些标签作为其最大可能的标签。
发现论文，激发创造
  • 通用图模型 MAP 推断的剪枝部分最优化

    本文提出了一种新的多项式时间算法来解决最小化无向图模型的能量问题，利用凸松弛方法得到部分最优非松弛积分解，并采用迭代修建策略优化算法，相较之前的方法表现更好。

    Oct, 2014

  • 通过 LP 松弛约束组合搜寻实现精确 MAP 推断

    针对基于图模型的最大后验概率推断问题，本研究提出了一系列不同于 Sherali-Adams 层次结构的松弛方法，将问题分解为一个简单的 LP-tight 部分和一个困难的组合求解器部分，实验证明对小部分问题可以显著降低计算时间。

    Apr, 2020

  • 半定规划层次结构在图模型推断中的应用

    本文提出使用具有两个创新的二进制 SDP 松弛，同时聚焦于计算效率的 SOS 层次结构进行 MAP 推理，该算法在实际问题如图像去噪和 Ising 自旋玻璃方面表现优于 BP 和 GBP。

    Sep, 2017

  • 图形模型中的 MAP 估计的 Lagrangian 松弛

    采用拉格朗日松弛技术，将不可解的估计问题重新定义为更可处理的图上问题，通过相应约束的松弛最大化优化问题，并应用于离散和高斯图模型的 MAP 估计及优化问题中。

    Sep, 2007

  • 任意时间边缘最大后验推理

    提出了一种新的任何时间算法解决图模型中的边际 MAP 问题，该算法可以在多项式时间内运行且当模型的图具有有限的树宽时，可以提供下限和上限保证。实验表明它可以在具有多个 MAP 变量和中等树宽的问题中表现得很好，并且相比 Park 和 Darwiche 的系统搜索而言有更好的表现。

    Jun, 2012

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

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

    Aug, 2005

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

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

    Jun, 2012

  • 离散图模型 -- 优化视角

    本文说明了离散图形模型的离散能量最小化问题及其多种优化解法，其中包括多种精确优化方法和基于信息传递和图割技术的近似方法。

    Jan, 2020

  • 概率逻辑编程的 MAP 推断

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

    Aug, 2020

  • 基于图形的无递归语义解析

    本文提出了一种新的基于图的方法来进行语义解析，解决了文献中观察到的两个问题：(1) seq2seq 模型无法完成组合泛化任务；(2) 使用短语结构解析器的先前工作无法涵盖树库中观察到的所有语义解析。我们证明了两个优化算法的正确性，用基于约束平滑和条件渐变的方法近似解决这些推断问题。实验证明，我们的方法在 Geoquery、Scan 和 Clevr 上都具有最先进的效果，包括在测试组合泛化的过程中。

    Feb, 2023