智能预测优化硬组合优化问题
提出了一种新的框架 —— Smart Predict, then Optimize (SPO),该框架直接利用优化问题的结构,即目标和约束,来设计更好的预测模型。实验表明,使用 SPO 框架可以显著提高预测 - 优化范例下的性能。
Oct, 2017
该研究探讨了在 “先预测,再优化” 框架下使用决策树进行决策问题的决策,并提出了一种可观的方法称为 SPO Trees (SPOTs) 用于训练决策树,该方法具有较高的解释性。实验结果表明,SPOTs 可提供更高质量的决策,并显著降低了模型复杂性。
Feb, 2020
本文发展了第一个能够在 “预测 - 优化” 框架中进行主动学习的方法,该方法在决策问题的优化模型参数对应的标注样本的无标注数据流中逐步决定是否请求特征样本的 “标签”,其中标签是指决策模型参数的参数。我们的主动学习方法是第一个受预测参数引起的决策误差直接影响的方法,也就是所谓的 SPO 损失。根据 SPO 丢失的结构,我们的算法采用基于间隔的标准,利用退化距离概念最小化从收集的数据得到的 SPO 代理,开发了一种既有硬性拒绝变种又有软性拒绝变种的高效主动学习算法,每种算法都具有理论上的超额风险(即泛化)保证。此外,我们推导了标注成本的界限,这是指为了实现所需的 SPO 风险水平而获得标签的样本数。在一些自然低噪声条件下,我们展示了这些边界可以比标签所有样本的朴素监督学习方法更好。此外,当使用 SPO + 损失函数时,这是 SPO 损失的一个专门的代理,我们在可分离条件下推导出了显着较小的标注复杂度。我们还介绍了数字证据,显示我们所提出的算法在个性化定价和最短路径问题的设置中具有实际价值。
May, 2023
我们提出了一个集成的预测 - 优化(PredOpt)框架,通过预测二进制决策变量在最优解中的值,高效地解决顺序决策问题。我们通过循环神经网络和滑动注意机制捕捉组合优化问题的顺序特性,并将基于注意力的编码器 - 解码器神经网络架构与消除不可行性和泛化框架相结合,以学习高质量的适用于时间相关优化问题的可行解。我们的结果表明,可以成功地使用在较短和较小维度实例上训练的模型来预测更长更大维度的问题。优化解决时间可缩短三个数量级,平均最优性差距小于 0.1%。我们将 PredOpt 与各种专门设计的启发式方法进行比较,并证明我们的框架表现优于它们。PredOpt 对于需要立即且重复求解的动态 MIP 问题具有优势。
Nov, 2023
我们提供了一个新的更简单更强大的框架称为 Two-Stage Predict+Optimize,可用于预测和优化的设置中,通过训练算法涵盖了所有混合整数线性程序,并且实验证明我们的训练框架在所有传统和最先进方法上具有卓越的预测性能。
Nov, 2023
我们提出了软偏好优化(SPO)方法,它能够使生成模型(如大型语言模型 LLMs)与人类偏好对齐,无需奖励模型。SPO 通过一种自然损失函数,在整个模型的输出分布中最大程度地优化模型输出,包括偏好损失和正则化项。虽然 SPO 不需要假设现有的基础奖励模型,但我们证明,在布拉德利 - 特里(BT)模型的假设下,它收敛于缩放奖励的 softmax,通过调整 softmax 指数,可以调节分布的 “软度”。我们展示了 SPO 的方法论、其理论基础以及在简单性、计算效率和对齐精度方面的比较优势。
Apr, 2024
本文提出了一个新的 Predict+Optimize 框架,可以处理既有在优化目标又有在约束条件中的未知参数,引入了校正函数和惩罚项来解决相关问题,同时提出了一种可处理所有 packing 和 covering 线性方程的算法,实验证明该方法比传统方法表现优秀。
Sep, 2022
通过顺序优化方法,本研究提出了一种解决大规模语言模型对齐人类偏好多维度问题的方法,避免了显式奖励建模,并在人类偏好的多个维度上实现了对齐,实验证明其优于基线模型。
May, 2024
从观测特征中通过预测模型直接学习最优解的方法被提出,该方法是泛化的,基于学习优化范式,能够提供高效、准确和灵活的解决方案给一系列具有挑战性的预测优化问题。
Nov, 2023
该研究论文提供了现有方法的综合分类和整合,建立了统一的评估基准,并阐明了端到端训练在不同场景下的改进情况及其表现不佳的背景。此外,还介绍了一个用于工业组合式广告问题的新数据集,以帮助更方便的评估和部署,鼓励在学术界和工业界进一步的改进。
Nov, 2023