AAAIDec, 2023

使用 CP-Nets 进行偏好聚合的近似算法

PDF
TL;DR该论文研究了设计和分析适用于将组合领域中使用条件偏好网络（CP-nets）表示的偏好进行聚合的近似算法。它侧重于对所谓的 “交换” 进行偏好聚合，其中已知的最优解通常具有指数规模。我们分析了一个简单的 2 近似算法，该算法仅输出给定输入偏好中的最佳解，并确定了一种结构条件，在此条件下改进了该算法的近似比率为 4/3。然后，我们提出了一种多项式时间逼近算法，其输出的解证明不会比简单算法差，但通常更好。我们提出了一族问题实例，对于这些问题实例，我们改进的算法产生最优解，而对于任何 ε 值，简单算法都不能获得（2-ε）近似解。这些结果可能导致首个在多项式时间内解决 CP-net 聚合问题的近似算法，其近似比率明显优于 2。
approximation algorithmsaggregating preferencesconditional preference networksswapspolynomial-time approximation algorithm
发现论文，激发创造
  • CP-nets: 表示和推理条件下等价偏好声明的工具

    本文提出一种 qualitatively graphical representation，可反映 under ceteris paribus 条件下偏好陈述语的条件依赖和独立性，进而用于多种推理任务。

    Jun, 2011

  • 组合分区问题算法配置的学习理论基础

    本研究提出了一种针对各种划分问题的机器学习算法，通过样本学习来获得适合特定应用场景的算法配置，同时也为算法配置的基础和学习理论的发展做出了贡献。

    Nov, 2016

  • P 问题的近似难度的分布式 PCP 定理

    这篇论文提出了一个新的概率可检验证明 (PCP) 的分布式模型，使用该模型，将 Strong Exponential Time Hypothesis (SETH) 归约到 P 问题的近似，尤其是对于 Bichromatic Maximum Inner Product 问题，我们获得了几乎多项式的因子，仅低于 SETH 的约束因子，这是首次实现此类归约。

    Jun, 2017

  • 图神经网络是否最优逼近算法？

    我们设计了图神经网络架构，利用半定规划的强大算法工具，来获得一类组合优化问题的最优逼近算法。通过研究，我们证明了多项式大小的消息传递算法可以表示 Max Constraint Satisfaction Problems 的最强多项式时间算法（基于 Unique Games Conjecture）。我们利用这一结果构建了高效的图神经网络架构 OptGNN，在最大割和最大独立集等经典组合优化问题上获得了高质量的近似解。我们的方法在各种真实和合成数据集上取得了强有力的实证结果，超过了神经基准和传统算法。最后，我们利用 OptGNN 捕捉凸松弛的能力，设计了一个从 OptGNN 学习的嵌入中产生对优解的对偶证明的算法。

    Oct, 2023

  • 基于部分排序的偏好值补全

    本文提出了一种协同偏好完成问题的高效算法，涉及在基于有限数量的观测关联值的情况下，针对一组实体在共享的项目集上联合估计个性化排名。该算法利用了一个观察结论，即虽然偏好通常被记为数字分数，但感兴趣的预测量实际上是底层排名，因此，直接拟合底层偏好顺序的估计器结合核范数约束来鼓励低秩参数。尽管具有广泛适用性，但该算法对于表示总体或区块总体顺序的监督的计算复杂度与基于核范数规则化估计的矩阵完成标准算法相差不大。此外，本文还提出了一项挑战性应用，即协同排名脑区与认知神经科学术语之间的关联。

    Nov, 2016

  • 张量网络快速计数

    本文提出了张量网络收缩算法的应用，使用图形理论方法确定一些有利的收缩顺序。此外，作者利用这种算法解决了 #P-hard counting 布尔可满足性问题，并发现其表现优于现有算法。

    May, 2018

  • 组合问题的图神经网络的近似比

    该论文从理论角度研究了如何利用图神经网络解决组合问题的近似算法，并提出了一种新的 GNN 类别，揭示了 GNN 的相对近似比，并证明了在节点特征中添加染色可以提高学习算法的近似比。

    May, 2019

  • 自适应伯努利概率的点对比较估计器

    该论文研究了一种灵活的框架下的成对比较数据聚合方法，使用强随机传递性（SST）引入了一个适应性指数来估计未来比较预测结果的概率，并探讨了不同算法的适应性指数。

    Mar, 2016

  • 随机决策网络中的相关性衰减

    在考虑决策网络在无向图上进行决策的过程中，使用 Cavity Expansion 算法，对某些模型的最优解进行去中心化的求解，从而将 NP 难问题转化为可解问题并寻求了具有潜在的统计物理学，组合优化和网络经济应用价值的趋势。

    Dec, 2009

  • Sum-Product Networks 的最大后验推断的近似复杂度

    探讨了在总和 - 乘积网络中近似最大后验推断的计算复杂性，证明了在高度为 2 和 3 的树状网络中，这一问题都是 NP 难问题，并提出了一种比传统算法更优秀的简单算法。

    Mar, 2017