From Predictive to Prescriptive Analytics

在本文中,我们结合了机器学习 (ML) 和运筹学和管理科学 (OR/MS) 的思想,开发了一个框架以及特定方法,用于使用数据来制定 OR/MS 问题的最佳决策。与数据驱动优化的其他工作不同,并反映了我们在 OR/MS 应用中可用数据的实践经验,我们认为数据不仅包括直接 e ↵影响成本/收入,例如需求或回报,但主要是对相关辅助数量的观察。感兴趣的主要问题是条件随机优化问题,给定不完美的观察,其中指定问题的联合概率分布是未知的。我们证明了我们提出的解决方法受到 ML 方法的启发,例如局部回归 (LOESS)、分类和回归树 (CART) 以及随机森林 (RF),通常适用于广泛的决策问题。我们证明,即使数据不是独立和同分布 (iid),甚至对于删失观察,它们在温和条件下在计算上也是易处理的和渐近最优的。我们将这些结果扩展到某些决策变量可以直接↵在未知的方式,如定价ECT不确定性’本身↵ ECT在联合定价和规划问题的需求。作为决定系数 R2 的类比,我们开发了一个称为规范系数的度量 P,用于从操作的角度衡量数据的规范内容和政策的有效性。为了在现实世界中展示我们的方法的威力,我们研究了一家国际媒体集团的分销部门所面临的库存管理问题,该公司平均每年出货 10 亿部。我们利用从 IMDb、Rotten Tomatoes 和 Google 收集的内部数据和公共在线数据来制定优于基准措施的运营决策。具体而言,根据我们的规范系数衡量,我们收集的数据(通过我们的方法利用)提高了 88%。

1

在今天“丰富数据的世界中,操作的许多问题的研究和管理学(OR / MS)可通过三个原始的特征:a)数据{Y1,…,YN}利息Y 2的Y不确定量⇢ rdy如同时需求。

b) 相关协变量 X 2 X ⇢ Rdx 的辅助数据 {x1, …,xN }例如最近的销售数据、Google 搜索产品或公司的数量、新闻报道或用户评论,其中 xi 与义 。

c)在一些观察 X = x 之后做出的限制在 Z ⇢ Rdz 中的决策 z以最小化不确定成本 c(z;Y ) 为目标。

传统上,OR/MS 中不确定性下的决策主要集中在问题上

等于1

及其多周期概括,并在关于 Y 的分布 μY 的先验假设下解决其解决方案(参见 Birge 和 Louveaux (2011)),或者有时在存在数据 {y1, …, yn}假设形式的独立同分布 (iid) 观测值来自 µY(参见 Shapiro (2003)、Shapiro 和 Nemirovski (2005)、Kleywegt 等人 (2002))。(我们将在 1.1 节中讨论 (1) 的示例。)总的来说,辅助数据 {x1,…,xN} 尚未广泛纳入 OR/MS 建模,尽管它在实践中的影响越来越大。

另一方面,机器学习 (ML) 从其基础开始,主要侧重于监督学习,或基于数据 {(x1, y1), 预测数量 Y(通常是单变量)作为 X 的函数。 …, (xN , yN )}。总的来说,ML 没有解决适合 OR/MS 问题的不确定性下的最佳决策。

与此同时,数据可用性和可访问性的爆炸式增长以及机器学习的进步使应用程序能够预测,例如,基于在线网络搜索查询 (X) 的消费者对视频游戏的需求 (Y) (Choi 和 Varian ( 2012)) 或票房门票销售 (Y) 基于 Twitter 喋喋不休 (X) (Asur 和 Huberman (2010))。ML 的许多其他应用以类似的方式进行:使用大规模辅助数据生成对 OR/MS 应用感兴趣的数量的预测(Goel 等人(2010 年)、Da 等人(2011 年) ),格鲁尔等人。

(2005 年,2004 年),卡卢斯(2014 年))。然而,目前尚不清楚如何从一个好的预测变成一个好的决定。一个好的决定必须考虑到任何存在的不确定性。例如,在没有辅助数据的情况下,基于数据 {y1, …, yn} 求解(1)但仅使用样本均值 y = 1 N PN i=1 yi ⇡ E[Y ] 而忽略所有其他数据的各个方面通常会导致对 (1) 的解决方案不充分,以及对良好数据的不可接受的浪费。

在本文中,我们结合了 ML 和 OR/MS 的想法,开发了一个框架以及特定方法,以使用数据在利用辅助观察的 OR/MS 问题中制定最佳决策。具体来说,感兴趣的问题是

等于2

其中底层分布未知,只有数据 SN = {(x1, y1),…, (xN , yN )} 可用。解 z⇤(x) 到 (2) 表示全信息最优决策,它通过对 (X, Y ) 的未知联合分布 µX,Y 的完全了解,最大限度地利用观察 X = x在最小化成本方面。我们对任何函数 z(x) 使用术语预测处方,该函数在给定观察 X = x 的情况下规定了对未来的预期决策。

我们的任务是利用SN来构建一个数据驱动的预测处方ZN(X)。 我们的目标是,其在实践中表现,E ⇥ C( ZN(X); Y)X = X ⇤ ,靠近全信息最佳,V ⇤ (X)。

我们的主要贡献包括:1)我们提出了构建预测处方各种方式ZN(x)将本文的重点是具有形式的预测处方

等于3

其中 wN,i(x) 是从数据中导出的权重函数。我们激发了受各种预测 ML 方法启发的特定结构,包括例如随机森林(RF; Breiman (2001))。我们在下面简要总结了我们认为最有效的这些结构的选择。

b) 我们还考虑了由传统经验​​风险最小化 (ERM) 方法驱动的 ML 构造。这种结构具有形式

等于4

其中 F 是某类函数。我们将 ERM 的样本外保证的标准 ML 理论扩展到 OR/MS 问题中遇到的多变量值决策的情况。

然而,我们发现,在 OR/MS 问题的特定背景下,结构 (4) 受到一些限制,这些限制不会影响从 (3) 得出的预测处方。

c) 我们表明我们的提议在温和条件下在计算上是易于处理的。

d) 我们通过利用 Walk (2010) 的普遍大数定律结果,在比 iid 更一般的抽样假设下研究我们的提议的渐近性。在适当的条件和某些预测处方 ˆzN (x) 下,我们证明了相对于真实分布的成本收敛到完整信息最优,即 limN!1 E ⇥ c(ˆzN (x);Y ) X = x ⇤ = v⇤(x),并且处方收敛到真正的全信息优化器,即 limN!1 infz2Z⇤(x) ||z zˆN (x)|| = 0,对于几乎所有的 x 并且几乎肯定。我们将结果扩展到审查数据的情况(例如通过销售观察需求)。

e) 我们将上述结果扩展到某些决策变量可能以未知方式影响不确定变量的情况,而不是封装在已知成本函数中。在这种情况下,不确定变量 Y (z) 将根据决策不同而不同,感兴趣的问题变为 minz2Z E ⇥ c(z;Y (z)) X = x ⇤ 。然而,使数据驱动的预测处方的构建复杂化的是,数据仅包括对应于历史决策的实现 Yi = Yi(Zi)。例如,在涉及定价决策(例如同时计划和定价)的问题中,价格具有未知的需求因果效应,必须确定该因果效应以优化完整决策 z,其中包括价格和生产或发货计划,以及数据仅包括以特定历史价格实现的需求。我们表明,在某些条件下,我们的方法可以扩展到这种情况,同时保持有利的渐近特性。

f) 我们引入了一个新的度量 P,称为规定系数,以衡量预测处方的有效性并评估协变量 X 的规定内容,即观察 X 有助于降低成本的程度。类似于预测分析的决定系数 R2,P 是一个无单位量,(最终)在 0(非规定性)和 1(高度规定性)之间。

g) 我们在现实世界中展示了我们方法的力量。我们研究了一家国际媒体集团的分销部门面临的库存管理问题。该实体在全球约 50,000 个零售点管理超过 50 万件独特的商品,并与这些零售点签订了供应商管理库存 (VMI) 和基于扫描的交易 (SBT) 协议。

平均每年出货约 10 亿台。我们既利用公司内部数据,又本着上述 ML 应用程序的精神,利用从在线资源(包括 IMDb、Rotten Tomatoes 和 Google Trends)收集的大规模公共数据。我们的方法利用这些数据相结合,与基线测量相比,带来了巨大的改进,特别是对确定性完美预见对应物的改进 88%。

我们提出的预测处方结构的ZN(x)的,那些我们觉得是一般是最广泛的,切实Ë ↵ ective如下:a)在K-近邻回归的推动下(k近邻;奥特曼(1992年) ),

等于5

其中 Nk(x) = {i = 1,…,N : PN j=1 I[||x xi|| ||x xj ||]  k} 是最接近 x 的 k 个数据点的邻域。

b) 受局部线性回归 (LOESS; Cleveland and Devlin (1988)) 的启发,zˆLOESS* N (x) 2 arg minz2Z Pn i=1 ki(x) max{1 Pn j=1 kj (x)(xj x) T ⌅(x)1(xi x), 0}c(z; yi ), (6) 其中 ⌅(x) = Pn i=1 ki(x)(xi x)(xi x)T , ki(x) ) = (1 (||xi x|| /hN (x))3) 3 I[||xi x||  hN (x)],并且 hN (x) > 0 是从 x 到 k 最近点的距离。尽管这种形式可能看起来很复杂,但它(几乎)对应于通过x 中的线性函数局部逼近 E ⇥ c(z;Y ) X = x ⇤的简单想法,我们将在第 2 节中详细讨论。

c) 受分类和回归树驱动(CART;Breiman 等人(1984)),

d) 受随机森林的启发(RF; Breiman (2001)),

其中 Rt (x) 是在数据 SN 上训练的随机森林中的第 t 棵树所隐含的分箱规则。在第 2 节和第 8 节中给出了进一步的细节和其他结构。

图 1 !回归树在数据 (x1, y1), …, (x10, y10) 上进行训练,并将 X 数据划分为叶子定义的区域。Y 预测 mˆ (x) 是 mˆ j ,即 X = x 结束的叶子上 Y 数据的平均值。

隐式分箱规则是 R(x),它将 x 映射到它结束的叶子的标识。

1.1

在本节中,我们讨论问题 (2) 的不同方法,并在两阶段线性决策问题中比较它们,说明辅助数据的价值和要解决的方法差距。我们用合成数据来说明这一点,但在第 6 节中,我们研究了一个现实世界的问题并使用了现实世界的数据。

我们考虑的具体问题是两阶段装运计划问题。我们有一个 dz 仓库网络,我们使用它来满足 dy 地点对产品的需求。我们考虑问题的两个阶段。在第一阶段,提前一段时间,我们选择数量 zi 0 的产品在每个仓库 i 生产和存储,每生产单位的成本为 p1 > 0。在第二阶段,需求 Y 2 Rdy 在地点实现,我们必须运送单位以满足它。我们可以以每单位运输的 cij 成本(资源变量 sij 0)从仓库 i 运送到位置 j,并且我们可以选择以每单位 p2 > p1 的成本(资源变量 ti)使用最后一刻的生产。整体问题有代价函数和可行集

平等的

其中 Q(z,y) = {(s, t) 2 R(dz⇥dy)⇥dz : t 0, s 0, Pdz i=1 sij yj 8j, Pdy j=1 sij  zi + ti 8i}。

关键的问题是我们不知道 Y 或其分布。我们考虑这样一种情况:我们只有数据 SN = ((x1, y1),…, (xN , yN )) 由对 Y 的观察以及对可能与未来值相关的一些辅助量 X 的并发观察组成的 Y 。

例如,在投资组合分配问题中,X 可能包括过去的证券收益、标的证券的行为、分析师评级或谷歌搜索公司的数量以及诸如“合并”之类的关键字。”在运输规划问题,X可以包括,例如,在每个迪过去的产品销售数字↵ erent零售点,天气预报的位置,或一个产品的谷歌搜索量衡量消费者的关注。

我们考虑了两种可能的现有数据驱动方法来利用此类数据做出决策。一种方法是随机优化(简称SAA)的样本平均近似。SAA 只关心 Y 的边际分布,从而忽略 X 上的数据,解决以下数据驱动优化问题

等于9

其目标近似于 E[c(z;Y )]。

另一方面,机器学习利用 X 上的数据,因为它试图在给定观测值 X = x 的情况下预测 Y。例如,考虑在数据 SN 上训练的随机森林。当 X = x 时,它为 Y 的值提供点预测 ˆmN (x)。给定这个预测,一种可能性是考虑随机变量 Y 通过我们的最佳猜测值 ˆmN (x) 的近似值,并解决相应的优化问题,

等于10

目标近似于 c z;E ⇥ Y X = x ⇤。我们称 (10) 为点预测驱动的决策。

如果我们知道 Y 和 X 的完整联合分布,那么观察到 X = x 的最优决策由(2)给出。让我们将 SAA 和点预测驱动的决策(使用随机森林)与提出的两个决策问题中的最佳决策进行比较。让我们还考虑我们的建议 (5)-(8) 以及将在第 2 节中介绍的其他建议。

我们考虑 dz = 5 个仓库和 dy = 12 个位置的两阶段装运计划问题的一个特定实例,我们观察到一些预测需求的特征。在这两种情况下,我们都考虑 dx = 3 和数据 SN,而不是 iid,它是从多维进化过程中采样的,以模拟现实世界的数据收集。我们在补充部分 13 中给出了问题的特定参数。在图 2a 中,我们报告了各种解决方案相对于真实分布的平均性能。

正如预期的那样,全信息最优显然在真实分布方面做得最好。SAA 和点预测驱动的决策具有快速收敛到次优值的性能。前者是因为它没有使用对 X 的观测,后者是因为它没有考虑观测 X = x 后剩余的不确定性。

1 相比之下,我们发现我们的建议收敛于给定足够数据的全信息最优解。在第 4.3 节中,我们研究了我们建议的一般渐近性,并证明这里凭经验观察到的收敛通常只在温和的条件下得到保证。

进一步检查该图,似乎忽略 X 并仅使用 Y 上的数据(如 SAA 所做的那样)在数据很少时是合适的;在这两个例子中,SAA 在 N 小于⇠64 的情况下优于其他数据驱动的方法。在那一点之后,我们构建的预测处方,特别是 (5)-(8),有效地利用辅助数据并实现更好的,最终是最佳的性能。由 RF 驱动的预测处方尤其值得注意,因为在小 N 范围内的表现不比 SAA 差,而在大 N 范围内表现更好。

在这个例子中,观测值 x 的维度 dx 在 dx = 3 时相对较小。在许多实际问题中,这个维度很可能更大,可能会抑制性能。例如,在我们在第 6 节的实际应用中,我们有 dx = 91。为了研究 x 的维度对我们建议的性能的影响,我们考虑用作为独立法线分布的无信息成分的附加维度污染 x . 结果(如图 2b 所示)表明,虽然一些预测方法的性能随着维度 dx 的增加而恶化,但基于 CART 和 RF 的预测方法基本上没有受到影响,似乎能够检测到特征的 3 维子集真的很重要。在补充部分 13.2 中,我们还考虑了该实验的另一种设置,其中附加维度具有边际预测能力。

1.2. 相关的文献

(1) 中的随机优化长期以来一直是 OR/MS 问题不确定性下决策的重点(参见 Birge 和 Louveaux (2011)),其多周期泛化通常称为动态规划(参见 Bertsekas (1995) ))。在存在感兴趣数量的数据 {y1, …, yN } 的情况下,如 (1) 中的随机优化问题的解决方案是一个活跃的研究主题。传统方法是样本平均近似 (SAA),其中真实分布被经验分布取代(参见 Shapiro (2003)、Shapiro 和 Nemirovski (2005)、Kleywegt 等人 (2002))。其他方法包括随机近似(参见 Robbins 和 Monro(1951)、Nemirovski 等人(2009))、稳健 SAA(参见 Bertsimas 等人(2014))和数据驱动的均值方差分布稳健优化(参见Delage 和 Ye (2010)、Calafiore 和 El Ghaoui (2006))。在 OR/MS 问题的不确定性下做出决策的一个值得注意的替代方法是稳健优化(参见 Ben-Tal 等人(2009)、Bertsimas 等人(2011))及其数据驱动的变体(参见 Bertsimas 等人) .(2013 年)、卡拉菲奥雷和坎皮(2005 年))。根据迄今为止收集的数据(参见 Robbins(1952)、Lai 和 Robbins(1985)、Besbes 和 Zeevi(2009)),关于数据收集和优化之间的权衡↵也有大量文献。在所有这些在不确定性下进行数据驱动决策的方法中,重点是对感兴趣的参数 Y 的 iid 观测假设形式的数据。另一方面,ML 非常重视监督学习的问题,其中给定辅助观察 X = x 的目标量 Y 的条件期望(回归)或模式(分类)是有趣的(cf.

特雷弗等人。(2001), Mohri 等。(2012))。

统计决策理论通常关注统计估计量的最佳选择(参见 Berger (1985)、Lehmann 和 Casella (1998))。在 Wald (1949) 的早期工作之后,指定了一个损失函数,例如平方误差的总和或绝对偏差的总和,并且相应的可接受性、极大极小最优或贝叶斯最优是主要关注点。统计决策理论和 ML 在通过经验风险最小化 (ERM) 的回归领域中最深刻地相交,其中根据最小化经验平均损失的标准选择回归模型。一系列 ML 方法源自应用于某些函数类的 ERM,并且已经开发了关于函数类复杂性的广泛理论来分析这些方法(参见 Bartlett 和 Mendelson(2003),Vapnik(2000,1992))。此类 ML 方法包括普通线性回归、岭回归、Tibshirani (1996) 的 LASSO、分位数回归以及 Belloni 和 Chernozhukov (2011) 的“1-正则化分位数回归”。ERM 还与 M-estimation Geer (2000) 密切相关,后者估计了一个分布参数,该参数通过最大化相应经验平均值的估计来最大化参数函数的平均值。与关注估计和推理的 Mestimation 理论不同,ERM 理论只关注样本外性能,并且可以更灵活地应用更少的假设。

在某些 OR/MS 决策问题中,可以使用 ERM 来选择决策策略,将损失视为成本。事实上,分位数回归中使用的损失函数正好等于库存管理报童问题的成本函数。Rudin 和 Vahn (2014) 考虑了这个损失函数和选择系数限制在`1-范数的单变量值线性函数,以解决带有辅助数据的报童问题,产生了一种类似于 Belloni 和 Chernozhukov (2011) 的方法)。高等人。(2009) 研究发现两个 ERM 解决方案的凸组合,最小成本决策和最小二乘预测器,他们发现当成本为二次方时很有用。在决策受限的更一般的 OR/MS 问题中,我们在补充第 8 节中表明 ERM 不适用。即使是这样,线性决策规则也可能不合适,正如我们通过示例展示的那样。对于适用 ERM 的有限问题,我们将标准函数类复杂性理论和样本外保证推广到多元决策规则,因为大多数 OR/MS 问题都涉及多元决策。

而不是 ERM,我们更多地受到基于本地学习的非参数 ML 方法的影响,其中预测是基于过去观察的均值或模式,在某种程度上类似于手头的观察。最基本的此类方法是 kNN(参见 Altman (1992)),它将预测定义为局部常数函数,具体取决于哪个 k 数据点最接近。一种相关的方法是 Nadaraya-Watson 核回归 (KR)(参见 Nadaraya (1964)、Watson (1964)),它以高度适用于理论分析而著称,但在实践中很少使用。Hanasusanto 和 Kuhn(2013 年)、Hannah 等人已经考虑使用 KR 加权来解决(2)中的条件随机优化问题。(2010) 但这些没有考虑与实践中使用的各种 ML 方法的更普遍的联系,也没有严格考虑渐近最优性。比 KR 更广泛使用的局部学习回归方法是局部回归(Cameron 和 Trivedi(2005)第 311 页),尤其是 Cleveland 和 Devlin(1988)的 LOESS 方法。更广泛使用的是递归分区方法,最常见的是树的形式,最著名的是 Breiman 等人的 CART。(1984)。众所周知,树的集合,最著名的是 Breiman (2001) 的 RF,非常灵活,并且在大量预测问题中具有竞争力。前者在基于数据(树的叶子)设计的分区上进行局部平均,而后者结合了许多这样的平均值。

虽然有许多基于树的方法和集成方法,但我们关注 CART 和 RF,因为它们在实践中很受欢迎且 e ↵ 有效。

2

回想一下,在观察 X = x 之后,我们对最小化不确定成本 c(z;Y) 的条件随机优化问题 (2) 感兴趣。关键困难在于指定问题 (2) 的真实联合分布 μX,Y 是未知的,并且只有数据 SN 可用。一种方法可能是通过数据 SN 上的经验分布 ˆµN 来近似 µX,Y,其中每个数据点 (xi , yi ) 分配的质量为 1/N。然而,除非 X 有小而有限的支持,否则这通常会失败;否则,要么未观察到 X = x 且条件期望对于 ˆµN 未定义,要么已观察到,对于某些 i,X = x = xi,并且条件分布是简并分布,在 yi 处有一个原子,没有任何不确定性。因此,我们需要某种方法来概括数据以合理估计任何 x 的条件预期成本。

在某些方面,这类似于预测问题,但比预测问题更复杂,其中 E[Y |X = x] 是根据任何可能的 x 2 X 的数据估计的。因此,我们有动力考虑预测方法及其对我们事业的适应。

在接下来的小节中,我们提出了一个选择预测处方结构的ZN(X),分别由当地的学习方法预测的动机。所有在本节中的结构将采取定义一些数据驱动权重的常见形式WN,I(X)和优化的决定Ž Ñ针对重新加权的数据,如在(3):

等于11

在某些情况下,权重是非负的,可以理解为对应于给定 X = x 的 Y 的估计条件分布。但是,在其他情况下,一些权重可能是负的,这种解释就失效了。

2.1knn

受 k-最近邻回归的启发,我们提出

等于12

产生预测处方(5)。等距数据点之间的联系被随机或由低指数优先规则打破。在没有预先计算的情况下找到 x 的 kNN 显然可以在 O(N d) 时间内完成。已经开发了以预计算为代价在查询时加速过程的数据结构(参见 Bentley (1975)),并且还有一些近似方案可以显着加快查询速度(参见 Arya 等人(1998)) )。

2.2

Nadaraya-Watson 核回归(KR;参见 Nadaraya (1964)、Watson (1964))估计 m(x) = E[Y |X = x]

平等的

K:路!R,称为内核,满足 RK < 1(通常是酉不变性)和 hN > 0,称为带宽。我们将注意力限制在以下常见内核上:K(x) = I[||x||  1] (天真),K(x) = (1 kxk2)I[kxk  1] (Epanechnikov),以及 K(x) = (1 kxk3)3I[kxk  1](三立方)。对于这些(非负)内核,KR 是由 µX、Y 和 µX(即它们的比率)的 Parzen 窗口密度估计(参见 Parzen (1962))产生的条件分布估计的结果。特别是,使用相同的条件分布估计,以下权重导致如 (3) 中的预测处方:

等于13

请注意,具有带宽 hN 的原始内核直接对应于对半径 hN 内的 x 的所有邻居进行均匀加权。

由 Devroye 和 Wagner (1980) 引入的替代核回归器驱动的对(13)的递归修改是

等于14

现在每个数据点选择带宽 hi 并且与 N 无关。 从理论的角度来看,与(13)相比,需要更弱的条件来确保(14)的良好渐近行为,正如我们将在下一节。

2.3

而 KR 通过内核加权的最佳局部常数预测(即加权平均值)估计 m(x),而局部线性回归通过内核加权的最佳局部线性预测估计 m(x):

平等的

在预测中,已知局部线性方法优于 KR(参见 Fan (1993))。使用它通过线性函数局部逼近条件成本 E ⇥ c(z;Y ) X = x ⇤ 我们将得到函数估计和预测处方,如(3)中的权重

等于15

其中 ⌅(x) = Pn i=1 ki(x)(xi x)(xi x)T 和 ki(x) = K ((xi x)/hN (x))。在 LOESS 回归 per (Cleveland and Devlin 1988) 中,K 是三三次核,hN (x) 是到 x 的 k 最近邻的距离,k 是固定的。在第 4.1 节中,当权重为非负时,我们建立了如(3)中的预测处方的计算易处理性。然而,权重 (15) 有时可能为负。尽管如此,随着 N 的增加,这些权重将始终变为非负。因此,我们建议修改权重 (15),以确保所有权重都是非负的,而不会牺牲渐近最优性(参见第 4.3 节):

等于16

2.4

在预测中,CART(Breiman 等人,1984 年)将样本 SN 沿轴对齐切割(单热超平面)递归地分成 X 中的区域,以便减少每个区域内响应变量 Y 中的杂质度量。常见的杂质度量是用于分类的基尼系数或熵和用于单变量回归的平方误差。多变量杂质测量是单变量杂质的组分平均值。一旦构建了一棵树,m(x) 的值通过与位于与 x 相同区域的 xi 相关联的 yi 的平均值来估计。

无论选择何种特定方法,最终分区都可以表示为分箱规则,该规则标识 X 中的点与不相交的区域 R : X !{1,…,r}。该分区则是不相交的并集 R1(1) t … t R1® = X 。树回归估计直接对应于对驻留在区域 R(x) 中的数据点的均匀分布取平均值。对于我们的处方问题,我们建议使用分箱规则为形式(3)的预测处方构造如下权重:

等于17

请注意,权重 (17) 在分区上是分段常数,因此推荐的最佳决策 ˆzN (x) 也是分段常数。因此,在递归划分过程之后解决r个优化问题,得到的预测处方可以完全编译成决策树,决策才是真正的决策。这也保留了 CART 广受赞誉的可解释性。 2

2.5

随机森林 (Breiman 2001) 是一组树,每个树都训练了数据的随机子样本,并在每个树节点考虑了 X 的随机分量子集。在训练了这样一个随机的树森林之后,我们可以提取分区规则 Rt t = 1,…,T,森林中的每棵树一个。我们建议使用这些来构建以下权重,用于形式 (3) 的预测处方:

等于18

在第 1.1 节中,我们证明了我们基于 RF 的预测处方,在等式中给出。(8),在两个不同的问题中,对于一系列样本大小和一系列维度 dx,总体表现良好。基于这种灵活性能的证据,我们为我们的实际应用选择了基于 RF 的预测处方,我们在第 6 节中进行了研究。

到目前为止,我们假设决策 z 对成本的影响完全封装在成本函数中,并且 z 的选择不直接影响不确定性 Y 的实现。

然而,在某些情况下,例如在定价决策存在的情况下,这一假设显然不成立——随着价格控制的增加,需求减少,并且定价的因果效应不是先验的(例如,可以在成本函数中抽象)并且必须从数据中导出。在这种情况下,我们必须考虑到电子↵我们对不定性y决定的z ECT考虑历史数据{(X1,Y1,Z1),…,(XN,YN,ZN)},在那里我们有还记录了变量 Z 的历史观察,它代表了在每个实例中做出的历史决策。使用潜在结果,我们让 Y (z) 表示如果选择决策 z 将观察到的不确定变量的值。对于每个数据点 i,仅显示与所选决策 zi 对应的实现,yi = yi (zi )。在任何其他决定 z 6= zi 下会观察到的反事实 yi (z) 不可用于测量。(有关潜在结果和历史的详细信息,请参阅 Imbens 和 Rubin 2015,第 1-2 章。)由于我们的决策中只有某些部分可能对不确定性有未知的影响↵ ,我们将我们的决策变量分解为具有未知 e ↵ 影响的部分(例如,定价决策)和知名电子↵ ECT(例如,生产决策)以下面的方式:假设1(决策分解)。对于某些分解 z = (z1, z2) 只有 z1 2 Rdz1 a ↵影响不确定性,即,

平等的

例如,在定价中,如果 z1 2 [0,1) 表示产品的价格控制,Y 表示已实现的需求,则 {(z1, Y (z1)) : z1 2 [0,1)} 表示随机需求曲线。如果在第 i 个数据点的价格是 zi 1,那么我们只观察到这条随机曲线上的单个点 (zi 1, yi (zi 1))。

例如,决策组件 z2 可以表示生产和装运计划,它不会影响需求,但会影响最终成本。

问题 (2) 的直接推广到这个设置 i

等于19

这个问题取决于对每个 z 2 Z 的 (X,Y (z)) 联合分布的理解,并且在这个完整的信息设置中,在给定观察 X = x 和 e↵ect z 的情况下,选择 z 作为最小预期成本关于不确定性 Y (z)。假设 1 通过让 z = z2 和 dz1 = 0 允许问题 (19) 包含标准条件随机优化问题 (2)。另一方面,假设 1 是非限制性的,因为它可以根据需要进行通用通过让 z = z1,即不分解为未知 e↵ect 和已知无 e↵ect 的部分。出于这些原因,我们保持符号 v⇤(x), z⇤(x), Z⇤(x)。

仅给定 (X,Y,Z) 上的数据 (xi , yi , zi ) 且没有任何假设,由于反事实数据缺失,问题 (19) 实际上并没有很好地说明。特别是,对于 (X,Y,Z) 的任何固定联合分布,对于每个 z 2 Z,都有许多可能的 (X,Y (z)) 分布,它们都与 (X,Y,Z) 的相同分布一致)通过变换Y = Y(Z),但可各自产生二↵ erent最优解ž ⇤ (x)的在(19)(见Bertsimas和Kallus 2016)。

因此,单独使用数据可能无法解决问题(19)。

为了消除这个问题,我们必须对数据做出额外的假设。在这里,我们作一个假设,在控制了X是sucient隔离电子↵ Y上的z等。

假设 2(可忽略性)。对于每个 z 2 Z,Y (z) 独立于以 X 为条件的 Z。

换句话说,假设 2 说,从历史上看,X 解释了与实例 {Y (z) : z 2 Z} 相关的所有可能影响管理决策的特征。在因果推断文献,这种假设是确保因果电子商务辨识标准↵学分(Rosenbaum和鲁宾1983)。

与处理潜在自我选择的因果推理中的许多情况形成鲜明对比的是,假设 2 在我们的特定环境中特别站得住脚。在我们考虑的设置中,Z 代表历史管理决策,就像未来由学习的预测处方做出的决策一样,这些决策必须是基于经理可用的可观察数量做出的。只要这些数量也被记录为 X 的一部分,那么假设 2 就可以保证成立。或者,如果决定 Z 是为了探索而随机做出的,那么假设 2 就不重要了。

3.1

我们现在展示如何概括第 2 节中的预测处方来解决问题(19),当决策影响基于(X,Y,Z)数据的不确定性时。我们从基于假设 1 和 2 的问题 (19) 重新表述开始。证明在 E-companion 中给出。

定理 1. 在假设 1 和假设 2 下,问题 (19) 等价于,

等于20

请注意,问题 (20) 仅取决于数据 (X, Y, Z) 的分布,不涉及未知的反事实,并且具有条件随机优化问题的形式。相应地,第 2 节中的所有预测性-规范性本地学习方法都可以通过简单地用 zi 1 增加数据 xi 来适应这个问题。特别是,我们可以考虑以下形式的数据驱动的预测性方法

等于21

其中 wN,i(x, z1) 是通过简单地采用与第 2 节相同的方法但将 z1 作为 X 数据的一部分从数据导出的权重函数。特别地,对于第 2 节中的每个方法,我们让~xi = (xi , zi 1),基于数据 S ~N = {( ~x1, y1),…构造权重 wN,i( ˜ x) , (〜XN,YN)},和插头WN,I( 〜X)代入(21),并计算ZN(X)。 例如,应用于 (19) 的 kNN 方法具有形式 (21),其权重为

平等的

正如我们在 4.2 节中讨论的那样,与我们在 4.4 节中展示的标准预测处方相比,当决策影响不确定性时,解决问题 (21) 的计算负担会增加。即使我们的决策对不确定性有未知的影响,也是最优的。

3.2

考虑第 1.1 节中我们的两阶段装运计划问题的定价变化。我们为我们销售产品的价格引入了一个额外的决策变量 z1 2 [0,1)。

dy 位置 Y (z1) 的不确定需求取决于我们设定的价格。在第一阶段,我们确定 dz2 仓库的价格 z1 和数量 z2。在第二阶段,我们可以随心所欲地发货,而不是从仓库发货以满足所有需求。我们的利润是价格乘以销量减去生产和运输成本。假设我们在第二阶段表现最佳,我们可以使用成本函数和可行集来编写问题

平等的

我们现在不仅考虑观察 X 和 Y,还考虑观察 Z1。我们考虑与第 1.1 节中相同的问题参数,并增加了未知的需求价格影响,因此较高的价格会导致较低的需求。特定参数在补充部分 13 中给出。

在图 3 中,我们报告了与真实分布相关的各种解决方案的平均负利润(生产和运输成本减去收入)。我们包括完整的信息优化 (19) 以及我们所有的本地学习方法,如第 3.1 节所述。我们再次与 SAA 和点预测驱动的决策(使用随机森林来拟合 ˆmN (x, z1),一个基于 x 和 z1 的预测模型)进行比较。

我们看到,随着更多数据可用,我们的本地学习方法收敛于全信息最优。另一方面,仅考虑数据 yi 的 SAA 将始终具有样本外利润 0,因为它会将 z1 驱动到无穷大,其中需求比线性更快地变为零。

对于小 N,点预测驱动的决策表现相对较好,可以快速学习定价的平均影响,但随着我们收集更多数据,不会收敛到全信息最优值。总的来说,我们使用 RF 的预测处方解决了不确定需求的定价决策的未知影响,效果最好。

4

在本节中,我们研究局部预测处方的两个重要特性:计算易处理性和渐近最优性。所有证明都在电子伴侣中给出

4.1

在第 2 节中,我们考虑了通过解决优化问题 (3) 计算出的各种预测处方 ˆzN (x)。一个重要的问题是,这个优化问题何时可以在计算上易于解决。作为优化问题,问题 (3) 与通过标准 SAA 方法 (9) 解决的问题不同,仅在于赋予不同观察值的权重。

因此,它的计算复杂度相似,我们可以参照 SAA 的计算研究,如 Shapiro 和 Nemirovski (2005) 来研究解决问题 (3) 的复杂度。为完整起见,我们为问题 (3) 开发了多项式时间可解的充分条件。

定理 2. 固定 x 和权重 wN,i(x) 0。假设 Z 是一个闭凸集,并为其提供一个分离预言机。还假设对于每个固定的 y,c(z; y) 在 z 中是凸的,并让 oracles 用于评估和 z 中的次梯度。然后对于任何 x,我们可以及时找到 (3) 的 ✏ 最优解,并且 oracle 在 N0, d, log(1/✏) 中调用多项式,其中 N0 = PN i=1 I[wN,i(x) > 0 ]  N 是有效样本量。

请注意,除了局部回归 (15) 之外,第 2 节中介绍的所有权重都是非负的,这是导致我们对其进行非负修改 (16) 的原因。

4.2

用一般权重 wi N (x, z1) 解决问题 (21) 通常很难,因为问题 (21) 的目标在 z 上可能是非凸的。在某些特定情况下,我们可以保持易处理性,而在其他情况下,我们可以设计专门的方法,使我们能够在实践中解决问题 (21)。在最简单的情况下,如果 Z1 = {z11,…,z1b} 是离散的,那么问题可以通过为 z1 的每个固定值优化一次来解决,让 z2 保持可变。

定理 3. 固定 x 和权重 wN,i(x, z1) 0. 假设 Z1 = {z11,…,z1b} 是离散的,并且 Z2(z1j ) 是每个 j = 1,… 的闭凸集.,b 并为其提供一个分离预言机。还假设 c((z1, z2); y) 对于每个固定的 y,z1 在 z2 中是凸的,并让 oracles 用于评估和 z2 中的次梯度。然后对于任何 x,我们可以及时找到 (21) 的 ✏ 最优解,并且 oracle 在 N0, b, d, log(1/✏) 中调用多项式,其中 N0 = PN i=1 I[wN,i(x) > 0]  N 是有效样本量。

请注意,z2 条件下的凸性弱于 z 中的凸性,这已经足够了。

或者,如果 Z1 不是离散的,我们可以使用离散化来解决问题,这会导致 z1 的维度 dz1 和精度 log(1/✏) 的指数依赖性。

定理 4. 固定 x 和权重 wN,i(x, z1) 0. 假设 c((z1, z2); y) 是 z1 中每个 z2 2 Z2 的 L-Lipschitz,Z1 是有界的,并且 Z2(z1 ) 是每个 z1 2 Z1 的闭凸集,并为其提供一个分离预言机。还假设 c((z1, z2); y) 对于每个固定的 y,z1 在 z2 中是凸的,并让 oracles 用于评估和 z2 中的次梯度。然后对于任何 x,我们可以及时找到 (21) 的 ✏ 最优解,并且 oracle 在 N0, b, d, log(1/✏), (L/✏)dz1 中调用多项式,其中 N0 = PN i=1 I [wN,i(x) > 0]  N 是有效样本量。

尽管 dz1 中的指数依赖和 1/✏ 中的超对数依赖出现问题,但这种方法在实践中仅适用于较小的 dz1 。例如,我们在 3.2 节的定价示例中使用这种方法,其中 dz1 = 1,以成功解决(21)的许多实例。

对于树权重的特定情况,我们可以精确地离散问题,从而在实践中产生一种特别有效的算法。假设我们给定了 CART 分区规则 R : X ⇥ Z1 !

{1,…,r},那么我们可以完全如下解决问题(21): 1. 给定 x 并修正 wCART N,i (x, z1) = I[R(x,z1)=R (xi,zi 1)] |{j:R(xj ,zj 1)=R(x,z1)}| .

  1. 找到包含 x 的分区,J = {j : 9z1, (x, z1) 2 R1(j)},计算每个部分对 z1 的约束,Z~1j = z1 : 9x, (x, z1 ) 2 R(1)(j)对于 j 2 J 。这很容易通过沿着树向下并在每个节点上完成,如果节点查询 x 的值,我们只取对应于我们给定 x 的值的分支,如果节点查询 z1 的组件的值,那么我们取两个分支并记录每侧 z1 上的约束。

  2. 对于每个 j 2 J ,求解 vj = minz2Z:z2Z~ 1j P i:R(xi,zi 1)=jc(z; yi ), zj = arg minz2Z:z2Z~ 1j P i:R(xi,zi 1)=jc(z;yi)。

(这些可以为每个 j = 1,…,r 提前求解,以减少查询时的计算量。) 4. 让 j(x) = arg minj2J vj 和 ˆzn(x) = zj(x)。

此过程完全针对权重 wCART N,i (x, z1) 求解 (21)。

4.3

在第 1.1 节中,我们看到随着样本大小 N 的增加,我们的预测处方 ˆzN (x) 收敛到全信息最优值。接下来,我们表明这个轶事证据得到了数学的支持,并且只有在温和的条件下才能保证这种收敛。我们将渐近最优性定义为 ˆzN (x) 的理想渐近行为。

定义 1. 我们说 ˆzN (x) 是渐近最优的,如果我们有概率 1,对于 µX-几乎无处不在的 x 2 X ,对于决策者来说,渐近最优性是最关键的限制属性,因为它说决策实施将使性能达到最佳。一致性是指 ˆzN (x) 作为全信息优化器 Z⇤(x) 的统计估计量的一致性,对于决策者来说可能不那么重要,但仍然会被证明是成立的。

渐近最优性取决于我们对 ˆzN (x) 的选择、决策问题的结构(成本函数和可行集)以及我们如何积累数据 SN 。数据收集的传统假设是它构成了一个 iid 过程。这是一个强有力的假设,通常只是一个建模近似值。现代数据收集的速度和多样性通常意味着历史观察通常不构成任何实际应用中的独立样本。

因此,我们有动力考虑数据收集的替代模型,即混合过程。这些包括诸如 ARMA、GARCH 和马尔可夫链之类的过程,这些过程可以对应于来自不断发展的系统的抽样,例如市场价格、日常产品需求或 Google 对某个主题的搜索量。虽然我们的许多结果通过广义强数定律(Walk 2010)扩展到此类设置,但我们在正文中仅呈现 iid 情况,以避免繁琐的阐述,并将这些扩展推迟到补充部分 9.2。

对于本节的其余部分,让我们假设 SN 是由 iid 采样生成的。

如前所述,渐近最优性还取决于决策问题的结构。

因此,我们还将要求以下条件。

假设 3(存在)。全信息问题 (2) 定义明确:E[|c(z;Y )|] < 1 for each z 2 Z and Z⇤(x) 6= ? 对于几乎每个 x。

假设 4(连续性)。c(z; y) 在 z 中是等连续的:对于任何 z 2 Z 且 ✏ > 0 存在> 0 使得 |c(z; y) c(z0 ; y)|  ✏ 对于所有 z0 和 ||z z0 || 和 y 2 Y。

假设 5(规律性)。Z 是封闭的且非空的,此外

  1. Z 是有界的或 2. liminf||z||!1 infy2Y c(z; y) > 1 并且对于每个 x 2 X ,存在 Dx ⇢ Y 使得 lim||z||!1 c(z ; y) !1 在 y 2 Dx 和 P y 2 Dx X = x > 0 上一致。

在这些条件下,我们有以下渐近最优性的充分条件,这些条件被证明是 Walk (2010), Hansen (2008) 的相关监督学习问题的普遍逐点收敛结果的结果。

定理 5 (kNN)。假设假设 3、4 和 5 成立。令 wN,i(x) 与 (12) 中的一样,其中 k = min dCNe, N 1对于某些 C > 0, 0 < < 1。让 zˆN (x) 与 (3) 中的一样。那么 zˆN (x) 是渐近最优且一致的。

定理 6(内核方法)。假设假设 3、4 和 5 成立并且 E[|c(z;Y )| 最大 {log |c(z;Y )| , 0}] < 1 对于每个 z。令 wN,i(x) 与 (13) 中的一样,其中 K 是第 2.2 节中的任何内核,并且对于 C > 0, 0 < < 1/dx ,hN = CN 。令 zˆN (x) 如 (3) 中所示。那么 zˆN (x) 是渐近最优且一致的。

定理 7(递归核方法)。假设假设 3、4 和 5 成立。令 wN,i(x) 与 (14) 中的一样,其中 K 是原始内核,并且 hi = Ci 对于某些 C > 0, 0 < < 1/(2dx)。

令 zˆN (x) 如 (3) 中所示。那么 zˆN (x) 是渐近最优且一致的。

定理 8(局部线性方法)。假设假设 3、4 和 5 成立,μX 是绝对连续的,并且在 X 的支持下具有远离 0 和 1 的密度并且两次连续可微,并且对于每个 z,成本在 y 上有界(即 | c(z; y)|  g(z)) 并且连续两次可区分。令 wN,i(x) 与 (15) 中的一样,其中 K 是第 2.2 节中的任何内核,并且对于某些 C > 0, 0 < < 1/dx ,hN = CN 。令 zˆN (x) 如 (3) 中所示。那么 zˆN (x) 是渐近最优且一致的。

定理 9(非负局部线性方法)。假设假设 3、4 和 5 成立,μX 是绝对连续的,并且在 X 的支持下具有远离 0 和 1 的密度并且两次连续可微,并且对于每个 z,成本在 y 上有界(即 | c(z; y)|  g(z)) 并且连续两次可区分。令 wN,i(x) 与 (16) 中的一样,其中 K 是第 2.2 节中的任何内核,并且对于某些 C > 0, 0 < < 1/dx ,hN = CN 。令 zˆN (x) 如 (3) 中所示。那么 zˆN (x) 是渐近最优且一致的。

虽然我们没有关于基于 CART(方程(7))和 RF(方程(8))的预测处方的渐近最优性的确切理论结果,但我们已经观察到它们在第 1.1 节中凭经验收敛。

4.4

当决策影响不确定性时,渐近最优性的条件微妙地不同。在恒等式 Y = Y (Z) 下,定义 1 没有准确反映渐近最优性,实际上方法没有考虑到决策的未知影响(例如,如果我们应用我们的方法而不考虑这个影响,忽略 Z1 上的数据将无法达到(19)给出的全信息最优值。相反,我们希望确保我们的决策在考虑其对不确定性的影响时具有最佳成本。当决策 a↵ect 不确定性时 ˆzN (x) 所需的渐近行为是下面给出的更一般的条件。

定义 2. 我们说 ˆzN (x) 是渐近最优的,如果概率为 1,我们对 µX-几乎无处不在的 x 2 X 有它,作为 N!1 以下定理基于核方法、局部线性方法或非负局部线性方法为我们的预测处方建立渐近最优性,以适应决策↵ 等不确定性的情况。在3.1节中,我们使用〜XI表示(XI,紫1)和S 〜N = {( 〜X1,Y1),…,( 〜XN,YN)}。为了避免存在的问题,我们专注于弱极小锌(21)(x)和渐近最优性。

定理 10. 假设假设 1、2、3、4 和 5(情况 1)成立,μ(X,Z1) 是绝对连续的,并且密度在 X,Z1 的支撑上远离 0 和 1 并且连续两次di ↵可计算,并且对于每个 z(即 |c(z; y)|  g(z)),成本在 y 上有界,并且连续两次 di ↵可计算。令 wN,i( ~ x) 如 (13)、(15) 或 (16) 中的那样应用于 S ~ N ,其中 K 是第 2.2 节中的任何内核,并且对于某些 C > 0, 0 ,hN = CN < < 1/(dx + dz1 )。那么对于任何✏ N !0,任何的Z- N(x)中✏ Ñ-minimizes(21)(具有内客观值✏下确界的N)是渐近最优的。

5

在本节中,我们开发了一个相对的、无单位的预测处方有效性的度量。

平等的

ecacy 的绝对衡量标准是边际预期成本,

如果 S~Nv 不相交且独立于训练集 SN ,则这是一个样本外估计,提供了 R(ˆzN ) 的无偏估计。虽然绝对测量允许人们比较相同问题和数据的两个预测处方,但相对测量可以量化数据的整体规定内容和通用尺度上的处方有效性。例如,在预测分析,判定R2的coecient -而非绝对根meansquared错误-是用于量化的预测和数据X. R2的预测内容的整体质量无单位量测量的方差的分数Y通过基于 X 的预测减少或“解释” 。另一种解释 R2 的方式是 X 和特定预测模型将我们从数据不足的预测(样本平均值)带到完美的预测- 提前知道 Y 的远见预测。

我们为预测处方问题定义了一个类似的量,我们将其称为处方系数。它涉及三个量。第一的,

等于22

规定性P的coecient是由1,一种低p表示上述限定的无量纲量是X提供很少的有用信息在手或规定的特定问题的最优决策的目的ZN(x)是INE ↵ ective在利用X中的高P表示信息,服用X考虑对降低成本显著影响,以及锌为e ↵ ective在杠杆X用于该目的。

特别地,如果X是独立Y的话,适当的条件下或LiMn,NV 1个R!NV(zSAA N)= minz2Z E [C(Z者除外; Y)] = E ⇥ minz2Zë ⇥ C(Z者除外; Y)X ⇤⇤ = LIMN,NV!1个R NV( ZN),从而N变,我们见p到达0。另一方面,如果Y是可测量的相对于X,即,Y是的一个函数X,然后,在适当的条件或LiMn,NV 1个R下!NV( ZN)= E ⇥ minz2Zë ⇥ C(Z者除外; Y)X ⇤⇤ = E [minz2Z C(Z者除外; Y)]!= 1 limNv R ˆ⇤ Nv ,所以随着 N 的增长,我们会看到 P 达到 1。另外值得注意的是,在极端情况下,Y 是 X 的函数,则 Y = m(X) 其中 m(x) = E ⇥ Y X = X ⇤使得E [minz2Z C(Z者除外; Y)] = E [minz2Z C(Z者除外; M(X))],因此,在这种极端的情况下,我们将看到对于P 1达到适当的条件下zpoint- 在独立的情况下,我们总能看到P的作用下达到非正数zpoint-预解码ñ。

让我们考虑第 1.1 节示例中的规定系数。对于我们的每个预测处方和每个 N,我们在大小为 Nv = 200 的验证集上测量样本外 P,并将结果绘制在图 4a 中。请注意,即使我们收敛到全信息最优值,随着 N 的增长,P 也不会接近 1。相反,我们看到对于收敛到全信息最优的相同方法,我们有一个接近 0.46 的 P。这个数字代表 X 在这个特定问题上必须降低成本的潜力程度。它是 X 的知识在正确利用的情况下,让我们从在完全不确定 Y 值的情况下做出决定到在完全确定性的环境中做出决定的方式的一小部分。与 R2 的情况一样,P 的大小表示成功应用取决于上下文。在第 6 节的实际应用中,我们发现样本外 P 为 0.88。

为了考虑 X 对 Y 的预测程度与规定系数之间的关系,我们考虑通过改变残余噪声的大小来修改示例,固定 N = 214。详细信息在补充部分 13 中给出。当我们改变噪声时,我们可以改变平均决定系数,

平等的

从 0 到 1。在原始示例中,R2 = 0.16。我们在图 4b 中绘制了结果,注意到该行为符合我们对上述极端情况的描述。特别是,当 X 和 Y 是独立的(R2 = 0)时,我们看到大多数方法的规范性系数为零,不太成功的方法 (KR) 有一些负系数,而点预测驱动的决策具有非常负的系数系数。当 Y 相对于 X 可测时(R2 = 1),最优决策的系数达到 1,大多数方法的系数接近 1,点预测驱动的决策也有接近 1 的系数并击败大多数其他方法. 虽然这两个极端在实践中都不合理,但在整个范围内,由 RF 驱动的预测处方表现得特别好。

6

在本节中,我们将我们的方法应用于国际媒体集团(供应商)的分销部门面临的现实问题,并证明我们的方法与广泛的数据收集相结合,带来了显着的优势。供应商要求我们对其身份以及销售数字和特定零售地点的数据保密。因此,一些数字以相对比例显示。

6.1

该供应商在美国和欧洲的 50,000 多家零售商处销售超过 50 万种 CD、DVD 和蓝光娱乐媒体节目。他们平均每年出货 10 亿台。零售商的范围从电子家居用品商店到超市、加油站和便利店。它们与供应商签订了供应商管理库存 (VMI) 和基于扫描的交易 (SBT) 协议。VMI 意味着库存由供应商管理,包括补货(他们每周执行一次)和货架规划。SBT 意味着供应商拥有所有库存,直到出售给消费者,此时零售商从供应商处购买单位并将其出售给消费者。这意味着零售商在持有供应商的库存方面没有资本成本。

单位娱乐媒体的成本主要包括内容的制作成本。媒*造和交付成本在影响中是次要的。因此,供应商的主要目标只是销售尽可能多的产品,主要限制因素是零售点的库存能力。例如,在许多这样的地点,供应商娱乐媒体的货架空间仅限于过道端盖显示器,并且没有可用的店后存储空间。因此,特定产品库存过多造成的主要损失在于另一种产品的潜在销售损失,该产品已售罄但本可以销售更多。在研究这个问题时,我们将只关注视频媒体的补货和销售以及欧洲的零售商。

除了有限的货架空间之外,造成问题困难的另一个主要原因是对新版本的初始需求所固有的特别高的不确定性。虽然已售出至少一个时期的物品在某种程度上可以预测需求衰减,但确定新版本的需求将从哪里开始是一项不那么简单的任务。同时,新版本为高需求和大量销售提供了最大的机会。

我们现在制定全信息问题。让 r = 1, …, R 索引位置,t = 1, …, T 索引补货周期,j = 1, …, d 索引产品。用 zj 表示产品 j 的订单数量决策,用 Yj 表示对产品 j 的不确定需求,用 Kr 表示位置 r 的整体库存能力。仅考虑上一段中讨论的对收入和成本的主要影响↵ ,问题在每个补货期、每个位置的基础上分解。因此,我们希望为每个 t 和 r 解决以下问题

等于23

其中 xtr 表示第 (t, r) 个问题中在周期 t 开始时可用的辅助数据。

请注意,如果问题 (23) 中没有容量限制并且添加了每单位订购成本,则该问题将分解为 d 个单独的报童问题,每个问题的解决方案都是回归量 xtr 上的分位数回归。事实上,问题是耦合的,但是,固定 xtr,容量约束可以通过拉格朗日对偶用等效的单位订购成本代替,并且通过将每个 zj 设置为 Yj 的第 th 个条件分位数来获得最佳解决方案。然而,减少到分位数回归并不成立,因为 的双重最优值同时取决于 j = 1 时 Yj 的所有条件分布,…,

6.2

在将我们的方法应用于问题 (23) 时,我们面临的问题是我们拥有销售数据,而不是需求数据。

也就是说,我们关于兴趣量 Y 的数据是右删失的。在本节中,我们将对我们的方法进行修改以纠正此问题。本节中的结果普遍适用。

假设 Y 上的数据不是 {y1,…,yN },而是 U = min {Y, V } 上的数据 {u1,…,uN },其中 V 是一个可观察的随机阈值,我们根据这些数据通过= I[U<V]总结。例如,在我们的应用程序中,V 是期初的现有库存水平。总的来说,我们的数据由 S~N = {(x1, u1, 1),…, (xN , uN , N )} 组成。

解决此问题的一种方法是将决策(袜子水平)视为影响不确定性(销售)的因素。

只要给定 X,需求和阈值条件独立,假设 2 将得到满足,我们可以使用第 3.1 节中开发的方法 (21)。然而,审查数据的特定设置有很多结构,我们实际上知道决策如何影响不确定性的机制。这使我们能够开发一种特殊用途的解决方案,避开学习这种依赖结构和计算上不太容易处理的方法的需要(第 4.2 节)。

为了纠正我们的观察实际上被审查的事实,我们开发了 Kaplan-Meier 方法的条件变体(参见 Kaplan 和 Meier(1958),Huh 等(2011))来适当地转换我们的权重。让 (i) 表示排序 u(1)  …  u(N) 。给定基于 yi = ui 的简单假设生成的权重 wN,i(x),我们将这些转换为权重

等于24

我们接下来表明变换(24)在某些条件下保持渐近最优性。证据在电子伴侣中。

定理 11. 假设 Y 和 V 条件独立,给定 X,Y 和 V 不共享原子,对于每 x 2 X,给定 X = x 时 V 的上支撑大于给定 X = x 时 Y 的上支撑,并且对于每个 z,成本在 y 上有界(即 |c(z; y)|  g(z))。

设 wN,i(x) 如 (12), (13), (14), (15), or (16) 并假设定理 5, 6, 7, (15), or (16) 的相应假设) 申请。令 zˆN (x) 与 (3) 中的一样,但使用转换后的权重 (24)。那么 zˆN (x) 是渐近最优且一致的。

Y 和 V 不共享原子的假设(如果其中一个是连续的,则尤其成立)提供了a.s.

= I[Y  V ] 以便可以观察到审查事件。在将此应用于问题 (23) 时,如果 X 至少捕获了在 Y 实现之前做出的过去库存决策可能基于的所有信息,则 Y 和 V 在给定 X 的情况下条件独立的假设将成立。有界成本的假设适用于问题 (23),因为成本(目标的负数)在 [Kr, 0] 中是有界的。

6.3

在本节中,我们描述收集的数据。为了获得最佳的数据驱动预测处方,我们结合了公司内部数据和从在线来源收集的公共数据。此类公共数据的预测能力已在文献中得到广泛记录(参见 Asur 和 Huberman(2010)、Choi 和 Varian(2012)、Goel 等(2010)、Da 等(2011)、Gruhl 等.

(2005 年,2004 年),卡卢斯(2014 年))。在这里,我们研究它的规定性力量。

内部数据。公司内部数据包括零售商网络中 4 年的销售和库存记录、每个地点的信息以及每个项目的信息。

我们按周(感兴趣的补货期)为每个可行的位置和项目组合汇总销售数据。如上所述,这些每周销售数据构成了对每周需求的右审查观察,其中审查发生在商品售罄时。我们开发了转换权重 (24) 来准确解决这个问题。图 5 显示了一系列游戏在推出家庭娱乐 (HE) 销售及以后的市场份额时的销售生命周期。由于新版本在发布的第一周可以吸引高达近 10% 的销售额,因此它们带来了巨大的销售机会,但同时也存在巨大的需求不确定性。有关零售点的信息包括该位置所属的连锁店和该位置的地址。为了解析地址并获得位置的精确位置,包括国家和细分,我们使用了谷歌地理编码 API(应用程序编程接口)。3 有关项目的信息包括媒体(例如 DVD 或蓝光)和项目“标题”。标题是由负责特定地区分销和销售的本地营销团队编写的简短描述,通常可能包含基础内容标题之外的信息。例如,一部名为 The Film 在法国出售的假想电影可能会被赋予项目标题“THE FILM DVD + LIVRET - EDITION FR”,暗示该产品是电影的法语版,以 DVD 形式出售,并附有小册子 (livret),而在德国以 BluRay 出售的同一部电影可能会被赋予项目标题“FILM, THE (2012) - BR SINGLE”,表明它以单张蓝光光盘出售。

公共数据:项目元数据、Box Oce 和评论。我们试图收集额外的数据来表征这些物品以及它们对消费者的吸引力。为此,我们求助于互联网电影数据库(IMDb;www.imdb.com)和烂番茄(RT;www.rottentomatoes.com)。IMDb 是一个在线电影和电视剧信息数据库。RT 是一个网站,汇集了来自报纸和在线媒体的专业评论以及用户对电影和电视剧的评分。

为了从这些来源获取有关供应商所售商品的信息,我们首先必须消除商品实体的歧义并从商品标题中提取原始内容标题。

这样做之后,我们从 IMDb 中提取了以下信息:类型(电影、电视、其他/未知);内容的美国原始发行日期(例如在影院中);平均 IMDb 用户评分(0-10);对评级进行投票的 IMDb 用户数量;获得的奖项数量(例如奥斯卡电影奖、电视艾美奖)和提名人数;主要演员(即先出票);情节概要(30-50字);流派(共 26 个;可以是多个);和 MPAA 等级(例如 PG-13、NC-17)(如果适用)。以及以下来自RT的信息:专业审稿人的总分;RT用户综合评分;对评级进行投票的 RT 用户数量;如果是一部电影,那么在影院上映时美国票房会很惨。

在图 6 中,我们提供了其中一些属性与 HE 发布第一周的销售数据的散点图。请注意,对标题评级进行投票的用户数量比这些投票的总分中报告的标题质量更能表明 HE 的销售情况。

公共数据:搜索引擎注意力。在上面,我们看到总收入对未来 HE 的销售数据提供了合理的信息。然而,我们能够获得的总票房是针对美国市场的,并且在各种欧洲游戏中也没有。因此,我们需要额外的数据来量化对不同标题的关注,并了解这种关注的本地性质。为此,我们求助于 Google 趋势 (GT; www.google.com/trends)。4 对于每个标题,我们测量了从 2011 年到 2014 年(包括) 在全世界、每个欧洲国家和每个国家/地区(德国各州、瑞士各州、西班牙自治社区等)。在每个这样的区域中,在针对我们的基线查询量进行归一化之后,测量结果可以解释为该区域内所有搜索中给定一周内 Google 搜索标题的比例,在任意但(大约)常见的情况下进行测量区域之间的规模。

在图 7 中,我们将搜索引擎关注度与德国两部未命名电影的销售数据进行了比较。 5 比较面板 (a) 和 (b),我们首先注意到整体销售规模与本地搜索引擎关注度的整体规模相关在影院上映时,而全球搜索引擎的关注意义不大(注意垂直轴比例,这在两个数字之间是常见的)。仔细观察面板 (b) 中区域之间的差异,我们看到,在电影院放映时,未命名电影 2 在北莱茵-威斯特法伦州 (NW) 比在巴登-符腾堡州 (BW) 和相应地,HE 发布后的前几周 NW 的 HE 销售额高于 BW。在面板 (a) 中,未命名的电影 1 在 NW 和 BW 以及类似的 HE 销售中都获得了类似的搜索引擎关注。在面板 (b) 中,我们看到搜索引擎对西北未命名电影 2 的关注在 HE 发布之前加速,这在 NW 尤其成功。在面板 (a) 中,我们看到 HE 销售 3 个月后搜索引擎关注度的轻微上升对应于销售额的轻微上升。这些观察结果表明,本地搜索引擎在本地影院上映时和最近几周的关注度可能预示着未来的销量

6.4. 构建辅助数据特征和随机森林预测对于问题 (23) 的每个实例 (t, r) 和每个项目 i,我们构建一个数值预测特征向量 xtri,该向量由项目 i 的销售量的反向累积总和组成过去 3 周在地点 r(可用;例如,新版本没有),过去 3 周地点 r 的总销售量的向后累计总和,地点 r 过去一年的总体平均销售量,自内容原始发行日期起的周数(例如,对于新发行,这是在影院首映到 DVD 发行之间的时间长度),位置 r 所在国家/地区的指标向量,指标位置 r 所属链的标识向量,在全球、该国家/地区以及位置 r 的国家/地区细分的本地影院上映前两周内对标题 i 的总搜索引擎注意力,向后累积总和 搜索引擎在过去 3 周内在全球、该国家/地区以及位置 r 的国家/地区细分中对标题 i 的关注,以及捕获从 IMDb 和 RT 收集的项目信息的功能。

从 IMDb 和 RT 收集的大部分信息都是非结构化的,因为它们不是数字特征,例如情节摘要、MPAA 评级和演员列表。为了将这些信息捕获为可用于我们框架的数字特征,我们使用了一系列聚类和社区检测技术,我们在补充部分 14 中对其进行了完整描述。

我们最终得到 dx = 91 个数字预测特征。在对这些数字进行总结后,我们训练了 500 棵树的 RF 来预测销售。在训练 RF 时,我们通过相应位置的训练集平均销售额对每个实例中的每个销售额进行归一化;我们在预测后反规范化。为了捕捉从商店发布时起的需求衰减,我们训练了一个单独的 RFs,用于 k = 1, …, 35 的货架上第 k 周的销售量,以及另一个用于“稳态”每周销售量的RFs 35 周后。

对于 k = 1,我们正在预测对新版本的需求,其不确定性,如第 6.1 节所述,构成了公司面临的最大难题之一。在预测质量方面,在测量样本外性能时,我们获得了 R2 = 0.67,用于预测新版本的销售量。该预测中的 25 个最重要的特征在图 8a 中给出。在图 8b 中,我们展示了 R2 也用于产品生命周期后期的预测,与始终预测下周需求的基线启发式算法的性能相比。

考虑到与新版本相关的不确定性,我们认为这是一个积极的结果,但同时真正重要的是问题中处方的表现。

我们接下来讨论这个。

6.5. 将我们的预测处方应用于问题 在上一节中,我们讨论了如何构建 RF 来预测销售,但我们感兴趣的问题是规定订单数量。为了解决我们的问题 (23),我们使用我们训练的森林中的树来构造权重 wN,i(x),与 (18) 中的完全一样,然后我们如 (24) 中那样对它们进行转换,最后我们规定了数据驱动订单数量ZN(X)如(8)。因此,我们使用我们的数据将各种辅助数据的观察 X = x 直接转化为订单补货决策。我们想测试我们的处方在样本外和作为实际实时政策的效果如何。

为此,我们考虑了从 2011 年 12 月 19 日到 2014 年 11 月 9 日(含)的 150 周内我们会做些什么。每周,我们只考虑该周之前时间的数据,根据这些数据训练我们的 RF,并将我们的处方应用到本周。然后我们观察实际发生的事情并对我们的表现进行评分。

这种评分方法存在一个问题:我们的历史数据仅包括销售额,而不是需求。虽然我们更正了不良é ↵ ECT上使用变换(24)我们的处方需求审查的,我们仍然留下了审查要求时,如上述的得分表现。为了合理衡量我们的方法有多好,因此我们考虑问题(23),其中容量 Kr 是其标称值的四分之一。通过这种方式,需求审查几乎不会成为绩效评分的问题。需要明确的是,这种更正对于反事实的表现评分是必要的;不是在实践中。

转换 (24) 已经纠正了对数量 Y 的审查观察训练的处方,该数量 Y 影响真实成本。

我们将我们的方法的性能与其他三个数量进行了比较。一个是完美预测策略的性能,它准确地知道未来的需求(无分布)。另一个是在不访问辅助数据(即 SAA)的情况下数据驱动策略的性能。因为在产品的生命周期内需求的衰减是显着的,为了公平比较,我们让这个策略取决于产品需求的分布,基于它在市场上的时间。

也就是说,它基于 T 个单独的数据集,其中每个数据集都包含在市场上 t 周后对产品的需求(同样,仅考虑过去的数据)。由于这个缺陷,我们以后将其称为 SAA++。最后一个基准是使用 RF 销售预测的点预测驱动策略的性能。因为如果我们让 Yj 是确定性的并且固定为我们的预测 ˆmN,j (x),那么 (23) 的最优解 zj 有很多,所以我们必须为点预测驱动的决策选择一个特定的。我们选择的一个设置订单水平以匹配需求和规模以满足容量约束: ˆzpoint-pred N,j (x) = Kr max{0,mˆ N,j (x)}/ Pd j0=1 max{0, m^ N,j0(x)}。

我们的表现与先见之明政策的表现之间的差异以及 SAA++ 与先见之明政策的表现之间的差异之比是规定性系数 P。当在 150-当这些政策做出实时决策时,我们得到 P = 0.88。换句话说,就我们的目标(销售量)而言,我们的数据 X 和我们的处方 ˆzN (x) 使我们从最好的数据匮乏决策到不可能的完美预见决策的方式达到了 88%。这平均超过 20,000 个地点。

在图 9 中,我们绘制了四个特定位置随时间变化的性能,并标出了其城市。每个图中的蓝色垂直虚线表示每个位置的 10 个最大的第一周卖家的发布日期,结果是相同的。这两对在同一周重合。这些图显示了我们的策略击败了点预测驱动的策略(但并不总是像图 9b 中的几天那样),这反过来又击败了 SAA++(但并不总是像在图 9b 中的几天那样)。图 9d)。我们针对这些位置的策略的 P 为 0.89、0.90、0.85 和 0.86。点预测驱动策略对应的P分别为0.56、0.57、0.50、0.40。点预测驱动的政策优于 SAA++(即使有障碍)并提供了由 P 衡量的显着改进,这可归因于第 6.3 节中收集的有关需求的数据的信息量。在大多数主要发布日期,点预测驱动策略的表现相对较差,这可以归因于对新版本的需求具有最大量的(剩余)不确定性,而点预测驱动策略忽略了这一事实。当我们使用我们的方法以适合库存管理的方式利用这些数据时,我们的改进几乎翻了一番。我们还看到,在大多数主要发布日期,我们的政策抓住机会匹配完美的预见性表现,但在少数情况下却不尽如人意。

在图 10 中,我们绘制了我们政策的 P 在欧洲所有零售点的总体分布。

7

在本文中,我们结合了 ML 和 OR/MS 的想法,开发了一个框架以及特定方法,以使用数据在利用辅助观察的 OR/MS 问题中制定最佳决策。我们基于 ML 的现有预测方法来激励我们的方法,但是,在 OR/MS 传统中,专注于决策的制定以及对成本、收入和风险的影响。我们的方法普遍适用、易于处理、渐近最优,并在现实世界中带来实质性和可衡量的改进。

我们认为,上述品质,以及越来越多的数据,特别是 OR/MS 应用中的辅助数据,使得我们提出的方法有可能对 OR/M 的实践产生重大影响

上一篇:利用python通过两点构成的空间直线和平面计算交点


下一篇:2021羊城杯 部分CRYPTO WP