超越局部损失函数的预测-优化方法

1 文章信息  

文章名为Leaving the Nest : Going Beyond Local Loss Functions for Predict-Then-Optimize。发表在第38届AAAI Conference on Artificial Intelligence. 作者来自哈佛大学。

2 摘要  

预测-优化是一种利用机器学习在不确定性下进行决策的方法框架。其核心研究问题是：“本文如何利用决策任务的结构，针对该特定任务定制机器学习模型？”为此，近期的研究提出了学习任务特定的损失函数，以捕捉这一潜在结构。然而，当前的方法对这些损失函数的形式及其对机器学习模型行为的影响做出了限制性假设。这些假设不仅导致了高计算成本的方案，而且当它们在实际中被违反时，还会导致性能较差。本文提出了解决这些问题的方法，避免了上述假设，并利用机器学习模型的特征提高学习损失函数的样本效率。本文通过实验证明，本文的方法在文献中的四个领域中实现了最先进的结果，通常比过去的类似方法所需的样本量少一个数量级。此外，当局部性假设被打破时，本文的方法比现有的最佳方法提高了近200%的性能。

3 简介 

预测-优化（PtO）是一个利用机器学习（ML）在不确定性下进行决策的框架。顾名思义，它分为两个步骤：首先，使用机器学习模型对不确定的量进行预测；然后，将这些预测结果聚合，并用于参数化一个优化问题，其解提供了待做决策。许多实际应用需要同时进行预测和优化，因此被视为预测-优化问题。例如，推荐系统需要预测用户与物品的亲和度，以确定显示哪些标题，而投资组合优化则使用股票价格预测来构建高绩效的投资组合。在社会公益领域，PtO已被用于规划干预策略，通过预测不同子群体对干预措施的反应。

PtO的核心研究问题是：“本文如何利用优化问题的结构来学习能够在特定决策任务中表现更好的预测模型？”在本文中，本文将用于实现这一目标的广泛方法称为决策聚焦学习（DFL）。最近，多篇论文提出了用于DFL的任务特定损失函数。这些方法的直觉可以用安娜·卡列尼娜原则来概括——完美的预测导致完美的决策，而不同类型的 imperfect 预测对下游决策有不同的影响。因此，这些损失函数尝试使用可学习的参数来捕捉不同类型的预测错误对决策任务的影响。例如，均方误差（MSE）损失可以通过可调参数来加权不同的真实标签。这样，训练于这种损失函数的模型就不太可能犯那些影响下游决策质量的错误。

学习任务特定损失函数面临两个主要挑战。首先，学习预测与决策之间的关系是具有挑战性的。为了使学习这一关系更易于处理，过去的方法为每个决策任务的实例学习不同的损失函数，每个损失函数在局部上近似优化任务的行为。然而，无法跨不同实例利用训练样本可能会使学习损失函数的样本效率低下，尤其是对于需要大量样本才能学习的方案。这尤其成问题，因为为学习这些损失函数创建数据集是整体方法中最昂贵的部分。本文中，本文并不为每个决策任务实例学习单独的损失函数，而是学习从预测模型的特征空间到不同局部损失函数参数的映射。这种“基于特征的参数化”使本文能够兼得两者的优势——在保持局部损失函数学习简洁性的同时，还能在不同决策任务实例间进行泛化。

除了提高效率外，这种重新参数化还确保了学习到的损失函数是费舍尔一致的——这是一个基本的理论属性，确保在无限数据和模型容量的极限下，优化损失函数能够导致最优的决策。过去的损失函数学习方法甚至没有满足这个基本的理论属性！

学习损失函数的第二个挑战是它提出了一个“先有鸡还是先有蛋”的问题——为了获得学习损失函数必须准确逼近真实决策质量的预测分布，首先需要一个预测模型，而要获得这样一个模型，则需要一个损失函数来训练它。不同的干预措施使本文能够摆脱基于局部性的简化假设，本文将本文的损失函数称为“高效全局损失”（EfficientGlobal Losses，简称EGLs）。

本文中本文不仅证明了EGLs的理论费舍尔一致性，还通过实验证明EGLs的优点，通过在四个领域与过去的工作进行比较。首先，本文展示了在本文一个关键领域中，基于模型的采样对于良好性能至关重要，EGLs甚至比最好的基准方法提高了近200%的性能。该领域的关键特征是，它打破了局部性假设，导致过去的方法灾难性地失败。其次，本文展示了EGLs在文献中剩余的三个领域中实现了最先进的性能，尽管在其中两个领域的样本量比可比方法少一个数量级。这种样本效率的提升转化为学习任务特定损失函数所需时间的减少，从而实现了数量级的加速。总的来说，本文认为这些改进使得决策聚焦学习（DFL）在实践中变得更加可行。

4 问题描述

多位作者提出了为深度学习（DFL）学习任务特定损失函数的方法。这些方法通过向标准损失函数（例如，均方误差MSE）添加可学习的参数并对其进行调优，使得最终的损失函数能够逼近“典型”预测的DQ（决策质量）中的“遗憾”值。具体来说，对于模型的预测分布，目标是选择一个损失函数，并调整其参数，使得：

其中，

DQ 定义如下：

                          

其中为预测值，y为真实标签，为在预测值下做出的决策，是评价决策的函数

需要注意的是，中的第一项对于是常数，因此最小化等价于最大化 DQ。然而，添加 DQ(y, y) 项后，使得更像一个损失函数——这是一个最小化目标，其最小值为 0（当时）。

因此，带参数的简单损失函数版本可以学习（从而学习 DQ）的结构。

使用任务特定损失函数学习预测模型的元算法如下：

1.采样：生成K个候选预测，例如，通过向每个真实标签添加高斯噪声。这一策略是基于“预测的局部性”假设，即预测将接近真实标签。

2.生成数据集：对采样的预测运行优化求解器，以获得相应的决策质量值。这将产生一个数据集，形式为，其中每个实例y来自训练和验证集。

3.学习损失函数：学习损失函数，使其最小化第二步中数据集的均方误差 (MSE)。为每个实例重新加权 MSE 损失：

同时还有两类损失函数，称为“局部优化决策损失”（LODLs）。第一类为每个预测添加可学习的权重，第二类则更为一般——它是由预测组成的任意二次函数，其中学习的参数是每个多项式项的系数：

加权均方误差 (WMSE)：

二次损失 (Quadratic)：

这些损失的参数和受到约束，以确保所学习的损失是凸的。它们还提出了“定向”变体的每个损失函数，其中学习的参数取决于与否。这些参数随后可以为每个实例y学习，例如，使用梯度下降法。对于预测模型：在前一步学习的损失函数上训练预测模型，例如，使用随机森林.

<1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;text-wrap: wrap;">1><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;text-wrap: wrap;">5 算法改进1>

第一部分：基于特征的参数化

EGL（高效全局损失）学习一个映射，该映射将数据集中任何预测的特征x映射到对应的凸构造的 LODL 损失族中的参数，如下所示：

加权均方误差 (WeightedMSE)：本文学习一个映射，将优化参数y的特征x映射到其关联的“权重”。直观地说，权重编码了给定预测的重要性，因此，EGL 学会预测不同预测误差对的影响。

二次损失 (Quadratic)：对于每一对预测和，本文学习一个映射 ，其中是参数化损失函数的矩阵。

定向变体 (Directed Variants)：本文不再学习一个从特征x到单一参数的映射，而是学习从的映射用于“定向加权均方误差（Directed WeightedMSE）”，以及从的映射用于“定向二次损失（Directed Quadratic）”。

接下来，本文按过去的工作方式优化学习到的损失函数的最优参数：

其中,是学习到的损失函数。对于本文的实验，模型是一个 4 层的前馈神经网络，隐藏层维度为 500，通过梯度下降进行训练。由于本文学习一个从给定预测的特征x到相应损失函数参数的映射，本文的方法称为基于特征的参数化（FBP）。

第二部分 基于模型的采样

过去的工作假设预测会接近实际标签y，以有效地生成潜在预测。然而，如果这个假设不成立，使用高斯采样可能无法产生良好的结果。因此，在本文中，本文提出了一个替代方案：基于模型的采样（MBS）。在这种方法中，为了生成潜在预测的分布，本文首先在标准损失函数（例如，均方误差MSE）上训练一个预测模型。然后，在训练过程中按等间隔使用中间模型为数据集中每个问题实例生成预测。这些预测形成了潜在预测的集合，基于这些预测，本文创建数据集并学习损失函数。

与此方法相关的超参数有：

模型数量：本文不仅从一个模型中采样预测，还可以训练多个模型以增加生成预测的多样性。在本文的实验中，本文选择了 {1, 5, 10} 个预测模型。

学习率和训练步骤数：学习率从{ 10^-6, 10^-5, …, 1 }中选择，可能使用周期性调度。本文在所有模型上使用最多 50000 次更新。

<1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;text-wrap: wrap;">6实验验证1>

6.1实验设置

本文在四个不同领域中进行了实验验证

(i) 立方Top-K：学习一个模型，使得其Top-k预测具有较高的对应真实标签。

(ii) 网络广告：该领域的目标是预测不同 (用户,网站) 对的点击率 (CTR)，从而选择合适的网站进行广告投放。

(iii)投资组合优化：基于Markovitz模型，目标是预测未来股价，以创建一个具有高回报但低风险的投资组合。

(Ⅳ)（困难）立方Top-K：数据规模较大的立方Top-K案例

6.2实验结果

本文的方法与文献中的以下基线方法进行了比较：

MSE：标准回归损失。

专家手工制作的代理模型：端到端方法，需要为每个领域分别手工设计可微分的代理优化问题。

L&Z：Lawless和Zhou的方法，用于学习损失函数。

LODL：Shah等人的方法，用于学习损失函数。使用32个和2048个样本进行训练。

本文发现本文的方法在所有文献中的领域中都达到了最先进的性能。事实上，本文看到，在三个领域中的两个领域，EGLs的性能与LODLs相似，但样本数少了一个数量级。

6.3计算复杂度实验

在第6.2中，本文看到EGLs在样本数量少一个数量级的情况下，表现与LODLs相当。在下表中，本文展示了这种样本效率的提升是如何转化为运行时间差异的。本文发现，大部分时间在学习LODLs时都花费在本文元算法的第2步。因此，尽管EGLs在执行第1步和第3步时需要更多时间，但样本效率的提升导致EGLs相比LODLs具有数量级的加速。

6.4消融实验

<1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="text-wrap-style: initial;"><1><1 style="text-wrap-style: initial;">在本节中，本文将EGLs与来自文献中的最强竞争对手——LODLs（Shah et al. 2022）进行比较。具体而言，本文关注低样本情境——即每个实例使用32个样本来训练这两种损失函数——并在下表中呈现本文的结果。本文发现，几乎在每种损失函数家族和领域的选择中，EGLs都提高了决策质量。本文进一步分析下表中的内容。1>1>1>1>1>

<1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="text-wrap-style: initial;"><1><1 style="text-wrap-style: initial;">基于特征的参数化（FBP）：1>1>1>1>1>

<1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="text-wrap-style: initial;"><1><1 style="text-wrap-style: initial;">鉴于这是低样本情境，'LODL + FBP' 几乎总是比仅使用LODL表现更好。特别是在添加更多样本可以改善LODL表现的情况下，这种改进尤为明显——例如在立方Top-K领域的“Directed”变体和网络广告领域的“Quadratic”方法中。1>1>1>1>1>

<1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="text-wrap-style: initial;"><1><1 style="text-wrap-style: initial;">基于模型的采样（MBS）：1>1>1>1>1>

<1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="text-wrap-style: initial;"><1><1 style="text-wrap-style: initial;">这一贡献在立方Top-K领域尤为有用，因为在该领域中局部性假设被打破。有趣的是，尽管局部性假设在其他两个领域似乎没有被打破，但MBS仍然提高了性能（见附录D.1中的表4）。本文假设，MBS在这里通过以下两种不同方式帮助提高性能：1>1>1>1>1>

<1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="text-wrap-style: initial;"><1><1 style="text-wrap-style: initial;">提高有效样本效率：本文看到，在FBP最有效的情况下，MBS带来的增益与FBP叠加。这表明MBS有助于提高样本效率。本文的假设是，基于模型的采样使本文能够专注于那些能够导致“训练轨迹的分叉”的预测，从而使得在样本较少的情况下提高性能。1>1>1>1>1>

<1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="text-wrap-style: initial;"><1><1 style="text-wrap-style: initial;">帮助加权MSE模型：MBS还帮助提高了这些领域中表现最差的加权MSE模型，结合FBP后，甚至超过了使用2048个样本的LODLs。这表明，MBS不仅仅是提高了样本效率。本文假设，MBS还通过限制样本集 y~\tilde{y}y~ 为“现实预测”，从而减少了搜索空间，允许即使是参数较少的加权MSE模型在实践中也能表现良好。1>1>1>1>1>

<1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;text-wrap: wrap;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;text-wrap: wrap;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;text-wrap: wrap;">1>1>1><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;text-wrap: wrap;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;text-wrap: wrap;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;text-wrap: wrap;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;text-wrap: wrap;">7 1>1>1>1><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;text-wrap: wrap;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;text-wrap: wrap;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;text-wrap: wrap;">总结1>1>1>

<1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="text-wrap-style: initial;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="text-wrap-style: initial;">1>1>1>1><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="text-wrap-style: initial;"><1><1 style="text-wrap-style: initial;">本文提出的增强学习损失函数（EGL）方法在多个领域中表现出色，通过提高样本效率显著减少了所需训练样本的数量，同时保持或超越了现有方法（如LODL）的性能。EGL结合了模型驱动采样（MBS）和基于特征的参数化（FBP），能够有效生成潜在的预测，并通过学习损失函数改善决策质量。实验表明，EGL在“Cubic Top-K”、“Web广告”和“投资组合优化”等多个任务中，尤其是在低样本情况下，表现优异，且在计算时间上比LODL获得了显著加速。MBS通过优化样本生成过程，进一步提高了样本效率并降低了搜索空间，使得即使在较少样本的情况下，加权MSE模型也能表现良好。总体来看，EGL方法在低样本、高计算需求的情境下展现了显著的性能优势和应用潜力。1>1>1>1>1><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="text-wrap-style: initial;"><1 style="color: rgb(0, 0, 0);font-family: 微软雅黑;font-size: 15.04px;letter-spacing: 1px;"><1 style="text-wrap-style: initial;">1>1>1>1>