Sep, 2017

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

PDF
TL;DR本文提出使用具有两个创新的二进制 SDP 松弛，同时聚焦于计算效率的 SOS 层次结构进行 MAP 推理，该算法在实际问题如图像去噪和 Ising 自旋玻璃方面表现优于 BP 和 GBP。
maximum a posteriori probabilitygraphical modelssum-of-squares hierarchysdpbinary sdp relaxations
发现论文，激发创造
  • 用于最大后验估计的可扩展半定松弛方法

    本文介绍了一种基于新的半定松弛形式 (SDR) 的最大后验推理方法，用于在大规模马尔科夫随机场上求解 MAP 问题，并采用 SDPAD-LR 交替方向乘法加速算法，取得了显著的可扩展性和计算效率。

    May, 2014

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

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

    Apr, 2020

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

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

    Aug, 2015

  • 对于块模型的半定松弛

    提出了一种新的半定规划解决方案（SDP-1）以适应随机块模型（SBM）中的社区检测问题，可以放宽之前提出的 SDP 方法中的一些条件，并且是适合拟合网络直方图的理想工具。

    Jun, 2014

  • 半定松弛中的相变

    这篇论文主要探讨了应用于信号处理、数据挖掘和机器学习中的统计推理问题，当数据的维度很高时，常常导致较难处理的组合优化问题。文中提出了通过构建这些组合优化问题的凸松弛来解决问题的热门思想。其中，半定规划松弛是该家族中最有力的方法之一，并且出人意料地适用于形如矩阵或图形的数据问题。作者对几个经典的半定规划松弛模型进行了研究，尤其是适用于图同步和网络中的社区检测等统计问题的模型。通过将这些优化问题映射到带有向量自旋的统计力学模型中，使用统计力学中的非严谨技术来描述相应的相变，以期阐明半定规划松弛在高维统计问题中解决问题的有效性。

    Nov, 2015

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

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

    Sep, 2007

  • 稀疏结构预测的可微松弛优化：LP-SparseMAP

    本文介绍了 LP-SparseMAP，这是 SparseMAP 的一个扩展，它通过本地多面体松弛来解决 SparseMAP 的一个限制。LP-SparseMAP 使用因子图的领域特定语言来定义和回溯任意隐藏结构，支持粗分解，硬逻辑约束和高阶相关性。在三个结构化预测任务中的实验显示了与 SparseMAP 和结构化 SVM 相比的优势。

    Jan, 2020

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

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

    Oct, 2014

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

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

    Jun, 2012

  • 解决二元二次问题的快速半正定方法

    本文介绍了一种针对大规模问题的新型 SDP 公式，具有类似于传统 SDP 公式的松弛界限及较高的计算效率，可用于解决各种应用程序，包括聚类，图像分割，共同分割和注册。

    Apr, 2013