在 MAP 推断中高效搜索受挫环

Oct, 2012

Efficiently Searching for Frustrated Cycles in MAP Inference

David Sontag, Do Kook Choe, Yitao Li

TL;DR本文介绍了双重分解及其在图形模型中的应用，以及解决在此框架下由于困惑循环而产生的整数相差较大的问题的方法，介绍了引入循环一致性和其他高阶一致性约束的基于簇的追踪算法，以及利用循环约束搜索算法和双重分解框架综合使用的算法，可以精确地解决由关系分类和立体视觉产生的 MAP 推断问题。

Abstract

dual decomposition provides a tractable framework for designing algorithms for finding the most probable (MAP) configuration in graphical models. However, for many real-world inference problems, the typical decom

dual decomposition graphical models cluster-pursuit algorithms cycle consistency map inference

发现论文，激发创造

边缘最大后验分解界限

该研究工作将双重分解泛化为通用幂和推理任务，包括边缘 MAP 推理、纯边缘化和 MAP 任务，并基于一个新的凸分解界限上的块坐标下降算法，证明其比之前的方法更快、更可靠。

Nov, 2015

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

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

Aug, 2015

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

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

Apr, 2020

图分解的端到端学习

提出了一种基于条件随机场的端到端可训练框架来解决图分解问题，用于图的二值化和特征表示学习，并在 MNIST 和真实世界中的多人姿态估计任务中进行了验证。

Dec, 2018

通用图模型 MAP 推断的剪枝部分最优化

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

Oct, 2014

利用消息传递来加紧 MAP 的 LP 松弛

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

Jun, 2012

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

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

Sep, 2007

广义序贯树 - 重新加权信息传递

本论文提出了一种基于 Junction chains 和线性规划的算法来处理图模型中的近似 MAP-MRF 推断问题，并且在计算机视觉领域取得了一定的性能提升。

May, 2012

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

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

Aug, 2005

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

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

Feb, 2023