学习最大独立集的推迟策略
本文提出一种基于深度强化学习的通用方法,用于优化决策图的变量排序以获得更紧密的上下界,进而直接通过泛化的边界机制提高组合优化问题的解决效率。 在两个具体应用中,作者证明了该方法能够显著提高上下界的效果。
Sep, 2018
本文提出了一种基于动态规划的图神经网络(GNN)框架来解决最大独立集(MIS)问题,通过递归算法构建子图并预测具有较大 MIS 的子图,进而在下一个递归调用中使用。我们通过对不同图形之间的 MIS 大小进行注释比较来训练算法,注释比较的输出结果用于自我训练过程,以提高注释比较的准确性。我们提供了在多个合成和真实数据集中证明我们算法优越性的数值证据。
Oct, 2023
学习推迟(L2D)框架通过将困难决策交给人类专家,实现了自主系统的安全性和稳健性。我们在此工作中缓解了每个专家都是明确识别的假设,并设计了一个能够应对测试时从未遇到过的专家的 L2D 系统。我们使用元学习来实现这一目标,同时考虑了基于优化和基于模型的变种。通过给出用于描述当前可用专家的小的上下文集合,我们的框架可以快速适应其推迟策略。对于基于模型的方法,我们采用了一种注意机制,可以查找上下文集合中与给定测试点相似的点,从而更精确地评估专家的能力。在实验中,我们在图像识别、交通标志检测和皮肤病病变诊断基准上验证了我们的方法。
Mar, 2024
该研究介绍了一个名为 DWSL 的距离加权监督学习方法,用于从线下数据中学习目标条件策略,通过加权行动以估计最短路径距离,能够在高维图像领域中超过先前的目标条件 IL 和 RL 算法的性能。
Apr, 2023
本文研究了应用广泛的 NP-hard 问题之一,最大独立集问题( M IS),提出了局部搜索框架 ARIR 及其三种算法,采用三种不同的减少策略,在五组基准测试中显示出明显的优越性。
Aug, 2022
本研究提出了一种基于神经网络的无数据训练方法,用于解决组合优化问题,特别是最大独立集和最大团的问题,并提出了通用的图缩小过程来处理大规模图形。这种方法在无需数据的情况下,可与有监督学习、强化学习和基于机器学习的现有方法相媲美或更优,具有广泛的适用性。
Mar, 2022
利用机器学习与强化学习相结合的创新方法解决基于计算图的调度优化问题,提供优化性和确定性保证,同时保持启发式方法的运行时成本。
Aug, 2023
针对实际的车辆路径问题,研究了最大权独立集问题,通过开发一个新的本地搜索算法,该算法使用了先前文献中未描述的更广泛的简单局部搜索运算和数据结构,引入了路径重新链接的新变体来避免局部最优解以及一种新的交替增广路径局部搜索移动来提高算法性能。
Mar, 2022
学员分享学习(L2D)旨在改善人工智能协作系统,通过学习如何将决策推迟到人类在更可能比机器学习分类器更准确时。现有的 L2D 研究忽视了阻碍其实际应用的现实系统的关键要素,即:i)忽略了具有不同成本的类型 1 错误和类型 2 错误的成本敏感场景;ii)要求对训练数据集的每个实例进行并发的人类预测;iii)不处理人类工作能力的限制。为了解决这些问题,我们提出了成本和能力约束下的推迟框架(DeCCaF)。DeCCaF 是一种新的 L2D 方法,采用监督学习来建模人类错误的概率,满足更宽松的数据要求(每个实例只有一个专家预测),并使用约束编程来在工作负载限制下全局最小化错误成本。我们在一系列具有不同 9 名合成欺诈分析师团队和个体工作能力限制的成本敏感型欺诈检测场景中测试了 DeCCaF。结果表明,我们的方法在各种场景中比基准方案表现显著好,平均减少了 8.4% 的错误分类成本。
Mar, 2024