美团配送 2022KDD 论文：Applying Deep Learning Based Probabilistic Forecasting to Food Preparation Time for On-Demand Delivery Service
概要
在即时配送零碎中，精确预估订单的商家出餐工夫对用户和骑手体验都十分有价值。该问题次要有两个技术挑战，即样本标签不残缺（局部订单只有出餐工夫的大抵范畴）和数据不确定性大，惯例的点估计回归办法很难解决。
本工作首次利用概率预计刻画订单出餐工夫的不确定性，提出了一种基于深度学习的非参数化办法，并在特色构建和模型设计中充分利用范畴标签的数据样本。在概率预计中，本文提出了 S -QL 损失函数，并证实了其与 S -CRPS 的数学关系，基于此对 S -CRPS 进行分位数离散化以优化模型参数。基于实在的配送数据评估以及线上 A / B 试验均证实了该办法的劣势和有效性，该办法的预估后果已在美团即时配送零碎中的多个外围模块中利用。
简介
外卖出餐工夫（FPT），指商家收到订单到实现外卖筹备的工夫。备餐工夫在订单指派和取餐工夫举荐两个产品性能上非常重要。
FPT 预测是一个典型的回归问题，存在两方面的难点：
-
label 不齐备性。label 分为两类，实在 label（precise label，PL）和区间 label（range-label，RL）。
- 商家被动上报的出餐工夫，或者，骑手在商家期待一段时间后才取到外卖的取餐工夫，咱们将这一部分认为是 PL，大略占总订单的不到 70%。
- 对于残余的 30% 以上的订单，咱们只能获取到其上下界。首先，咱们能够认为取餐工夫是订单出餐工夫的上界。其次，咱们能够依据业务特点，获取局部订单的下界，e.g. 骑手因为长时间的期待放弃取餐而来到商家，咱们就能够将来到商家的工夫看作是下界（如果没有明确断定理由，下界设置为 0）。
-
数据不确定性。受到上面 3 个因素的影响，传统单预计预测形式很难保障准确性。
- 商家供应：咱们没有渠道具体获取商家厨房的信息，e.g. 厨师、器皿、食材
- 食物筹备的流程：每个商家都有其特有的食物筹备工序，e.g. 筹备流程，并行处理订单的能力
- 到餐环境：线下店内就餐状况会极大的影响线上订单
因而，本文尝试预测 FPT 的概率分布，给决策带来更多有用的信息。目前，PF 曾经广泛应用于强不确定性的场景，e.g. 地震，风力，电价；以及波及区间数据的问题，例如，留存预测。同时，概率预测也被认为是最优决策的根本组成部分。回归问题的目标应该是校准和锐化应变量与自变量的条件概率分布。校准，指的是预测散布与观测后果的统计一致性，例如，当预测下雨概率为 30% 时，抽取 10 条样本应该大概有 3 条样本为下雨；锐化，表征了预测散布的集中水平，为决策提供了更多的信息。SF 重点关注的是响应变量的条件期望 / 中值，但它将高阶矩视为固定值，这在事实世界中通常是有效的。
本文的翻新点：
本文首次将 PF 利用于 FPT，提出了一种基于深度学习的非参数办法来预测一系列累积密度的分位数。该模型通过最小化 S -CRPS(生存间断排序概率分数)来解决 [2] 中被宽泛采纳的区间截尾数据，该模型由宽泛采纳的 CRPS 推广而来。在实现过程中，采纳分位数离散化，防止了 S -CRPS 中积分计算的复杂性。[2] S-CRPS 概念来自于吴恩达 2020 论文：「Countdown regression: sharp and calibrated survival predictions」.
相干工作
Regression for Interval Censored Data
在生存剖析中，曾经在应用回归办法剖析事件产生的工夫。概率预测（PF）算法次要通过最大似然预计（MLE）优化，即，最大化区间内产生的概率，而不预测具体的工夫点，e.g. 非参数化 MLE、比例危险模型和参数化模型等。基于同样的思维，S-CRPS 由 CRPS 推广而来。同样，咱们对未知的准确 FPT 也不做任何假如，解决 RL 订单时充分利用上下界。
probabilistic forecasting
Bayesian vs. non-Bayesian approach
解决 PF 的问题能够分为贝叶斯办法和非贝叶斯办法 2 类。
- 前者做先验假如，并基于数据做后验推理；
- 后者，对不确定性间接建模，在实践中更加灵便。
本文重点放在非贝叶斯办法。
Parametric vs. non-parametric approach
参数办法和非参数办法是结构概率分布的两种次要办法。
- 前者假如密度散布的形态（如高斯分布、伽马散布），并专一于散布参数的预测。XGBoostLSS is proposed as an extension of XGBoost, which models all moments of a paramet- ric distribution [18]；Duan 等人 [4] 将 boosting 算法与天然梯度相结合，对假如散布的参数进行预计；Salinas 等人 [20] 在深度学习的根底上提出了 DeepAR，通过训练自回归递归神经网络模型，对高斯似然进行参数估计。
- 后者不对概率分布形态做假如，间接对散布的无限点位做预计。分位数回归是一种典型的非参数回归办法，通常对多个分位数回归模型进行独立训练来计算散布，这可能导致分位数的穿插（crossing quantiles）；Hasson 等人 [10] 设计了一种 level-set PF 办法，将数据点分组到不同的分区，并计算每个分区内的散布；此外，基于 dropout 的集成办法 [15] 也属于非参数办法。
一般来说，非参数办法比参数办法更灵便，但只有无限的预测点数量，而不是散布函数。然而，参数估计办法的有效性取决于假如的散布是否与理论散布极其匹配。
非参数模型（non-parametric model）和参数模型（parametric model）作为数理统计学中的概念，当初也罕用于机器学习畛域中。在统计学中：
参数模型通常假如总体遵从某个散布，这个散布能够由一些参数确定，如正态分布由均值和标准差确定，在此基础上构建的模型称为参数模型；
非参数模型对于总体的散布不做任何假如或者说是数据分布假如自在，只晓得其散布是存在的，所以就无奈失去其散布的相干参数，只能通过非参数统计的办法进行推断。
所以说，参数模型和非参数模型中的“参数”并不是模型中的参数，而是数据分布的参数。须要留神，有参数模型它的参数是无限的，而非参数模型也并不是没有参数，而是参数的数目很多。
问题定义
解决办法
不同订单的聚合（Aggregation of FPT for Different Orders）
实际中，为了特征分析和特征提取，咱们通常须要对历史订单统计计算。针对 label 明确的个别状况，只须要计算 label 的平均值和方差即可。然而，咱们面对的是蕴含 PL（准确值）和 RL（区间值）两种类型的订单汇合，上述计算平均值和方差的形式变得有效，而只思考 PL 订单会导致样本偏差的问题。因而，本文设计了离散累计概率 DCP (Discrete Cumulative Probabilities）聚合两类数据集，代表了等间隔散累计概率取值的汇合，其中，下标 z 代表了离散值对应的工夫点。
计算时，PL 订单直接参与计算；RL 订单，当上下界穿梭 z 时不参加计算，上下界位于同侧时参加计算。对应的，近似平均值计算形式如下：
留神，近似平均值能够对 FPT 的平均值进行近似刻画，仅仅是为了不便剖析，并不能间接应用。
特征提取
总体包含环境特色、商家特色、餐品特色 3 类。
S-CRPS and S-Quantile Loss
该局部次要用于如何评估拟合散布的好坏，便于后续再模型构建和训练中应用。
在上面篇 paper 中曾经证实，绝对于 MLE，CRPS 更加鲁棒并在求解 PF 问题中广泛应用。
Calibrated probabilistic forecasting using ensemble model output statistics and minimum CRPS estimation.2005.
Comparingdensityforecastsusing threshold-and quantile-weighted scoring rules.2011.
CRPS 的两种等价写法如下：
其中，F 指代 CDF（累计散布函数），y 指代观测值。当指标是最小化 CRPS，须要在 x <y 时升高 F(x)，x>y 时减少 F(x)。极其状况下，概率密度集中在 y 时，CRPS=0。公式 3 则在 CRPS 和分位数 loss 之间建设了间接分割。其中，分位数 loss 用于分位数回归模型，定义如下：
\(F^{-1} \)指代 CDF 的逆函数，\(F^{-1}(q) \)指将 q 分位数作为参数进行计算。
为了防止简单的积分计算，通常采纳式 3 的离散化模式，例如，将公式 3 中的积分替换为对 QLq 的求和，q = 0.01，…，0.99，称为分位数离散化。
借鉴 CRPS 并同时解决区间删失数据场景，Avati 等人提出 S -CRPS，绝对于 MLE 该办法更加适合且可能产生更加清晰锐化（sharper）的散布。
Countdown regression: sharp and calibrated survival predictions.2020.
针对 FPT-PF 工作，PL 订单，S-CRPS 与 CRPS 解决形式相似；RL 订单，S-CRPS 则定义为如下模式：
针对 RL 订单，S-CRPS 不做任何准确 label 的假如，仅仅充沛利用高低边界。（应该还没有针对区间删失数据的分位数 S -CRPS，这应该是这篇文章的独创）本文提出了 S -QL 的分位数 loss，公式如下：
文中做了证实，S-CRPS 能够形容为如下模式：
基于此，在后续模型优化时能够将 S -CRPS 的分位数离散化模式作为 loss。
模型
预处理
文章提出了一种针对 FPT-PF 工作的非参数化深度学习模型。首先，咱们对提取到的环境特色、商家特色、餐品特色进行预处理。其次，咱们引入了 Attention 机制捕捉同一个订单中不同餐品的奉献差别。最初，咱们对 FPT 的累计密度函数分位数进行预测，并通过最小化 S -CRPS 分位数离散值对模型进行优化。
为了高阶特色与低阶特色充沛穿插，咱们引入了 DCN 网络对特色进行编码（留神，这里是两个 DCN 网络）：
X_c、X_r 别离示意环境特色和商家特色，X_d 示意餐品特色，v_cr、v_d 别离示意编码后的两个向量，维度均为 k。DCN 计算细节如下。
Attention
在该文中，attention 次要计算餐品对于出餐工夫的影响权重。
对一个订单里的不同餐品向量进行聚合时，咱们应该以后订单以及之前订单中不同餐品的制作工序。然而，不同商家的不同餐品的制作工序差异性较大。例如，奶茶的制作工序通常固定，且筹备工作的并行化程度较高；相同，领有简单烹饪过程的餐品，当商家供应能力有余时，餐品的筹备工作变成串行的。在齐全并行的状况下，一个订单的出餐工夫次要由最晚餐品决定；在串行的状况下，由所有餐品筹备工夫的总和决定。所以，一个餐品对订单的影响是十分复杂的，与环境信息、商家信息有十分大的相关性，由此咱们想到了应用 Attention 机制解决信息聚合（如图 fig4 C 所示）。
w_cr 和 w_d 均为 k 维参数，sigma(x)=1/(1+e^{-x})。相比于传统 Attention 机制应用 softmax 计算加权均匀，这里采纳 sigmoid 函数更容易捕捉并行性。【why?】所有餐品的聚合特征向量如下，其中，a_i∈(0,1)，代表了 d_i 餐品的奉献权重：
最终，咱们将 v_D 和 v_cr 拼接在一起，实现特色 encoding（如图 fig4 B 所示）。
Probability forecast
如上文所述，概率预测分为参数化和非参数化两大类办法。其中，非参数化办法不须要假如概率分布形态，是最灵便的建模办法。针对以后利用，采纳 S -CRPS 的分位数离散化模式作为模型的建模指标（如图 fig4 A 所示）。为了解决穿梭分位数的问题，咱们须要保障随着分位数的减少，预测概率同步减少。在本文中，采纳全连贯网络搭载 softplus 激活函数，softplus(x)=log(1+e^x)。通过这种办法，每个分位数失去一个非正数，而后在 Cumsum 环节对前置各两头后果进行累加。最终输入 F^{-1}(q_i)。
Model Training
依据公式 3 和公式 7 的分位数离散化模式，损失函数如下所示：
其中，θ 对应神经网络模型参数，delta_q=0.01，n_q=99。训练中采纳 Adam 优化器优化模型，此外，采纳 BN 保障稳定性。
评估
概率预测的指标是在满足 calibration（校准）的前提下尽可能进步预测的 sharpness。所谓的 calibration 指的是预测散布和观测值在统计上的一致性，而 sharpness（锐度）则是指预测散布的集中水平。
评估指标
PF 的评估比 SF 的评估更具挑战性，PF 公认的指标是使概率分布的锐度最大化。无论锐度如何，未经校准的预测都是谬误的，而通过校准但锐度不高的预测是正确的，但用途不大。咱们遵循现有的大多数钻研，基于校准、锐度和回归精度来评估性能，即，评分规定和分位数损失。具体的指标将在以下局部给出，图 5 展现了三个例子来帮忙了解。
calibration
校对是预测散布与观测后果的统计一致性。在本文中，咱们遵循 [2] 中应用的雷同办法来评估预测散布的校准成果。咱们计算不超过每个累积密度预测分位数的观测频率。对于特定的累积密度 q，每个阶的 q 分位数由模型预测。
- 对于 PL 订单，当 y≤q 分位数时察看到该订单，否则不察看到。
-
对于 RL 订单
- 当 u≤q 分位数时察看订单
- 当 q 分位数≤l 时不察看该订单
- 如果 q 分位数∈(l,u)，则疏忽订单，因为无奈确定 FPT 是否大于 q 分位数。
图 5(a)和图 5(b)阐明了咱们提出的办法的两个预测散布，以帮忙了解。最初，通过观测数与所有思考订单 (不计疏忽订单) 的除法计算观测频率。当预测散布校对良好时，累积密度 q 的观测频率应靠近 q，本文对累积密度进行了 0.1 ~ 0.9 的评估。RL 订单的标定也放弃了对未知的准确 FPT 不做任何假如，充分利用上下界的准则。
sharpnass
锐度表征了预测散布的集中度。锐度只是预测散布的一个繁多性质，不思考察看后果。咱们应用核心预测区间的均匀宽度来评估锐度。模式上，区间 (a, b) 的均匀宽度由预测散布的 b 分位数减去 a 分位数计算。fig5 C 展现了两个预测散布在区间宽度 (0.2,0.8) 的集中度差别。
Regression accuracy
通过最小化 CRPS/S-CRPS，同时优化了校准和锐度。因而，采纳 S -CRPS 作为一个重要的评估指标，它能够捕捉预测散布绝对于观测后果的准确性。思考到计算复杂度和不同办法之间的可比性，咱们计算了 S -CRPS 的分位数离散化，即公式 11 中的损失函数。为了和传统回归精度放弃对立，这里思考应用 0.5 分位数 Loss 做剖析，即，PL 订单应用 QL_0.5，RL 订单应用 S -QL_0.5。QL_0.5 是 MAE(均匀绝对误差)的一半，通常在 SF 中用于准确性评估。
离线评估
参数化办法比照
假设 FPT 数据合乎高斯分布或伽马散布，离线评估环节比照了本文提出的非参数化模型与两种参数化模型的成果。其中，高斯分布罕用于自然科学和社会科学，对不晓得散布形态的随机变量进行刻画；伽马散布罕用于预估等待时间。
高斯分布的概率密度函数为
伽马散布的概率密度函数为
为了偏心起见，训练时模型构造不变，仅仅依据高斯分布、伽马散布调整神经网络最初一层。 模型输入高斯分布或伽马散布的模型参数（同样采纳 softplus 激活函数及公式 11 中的 loss）。从 table3 和 table4 能够看出，除了 0.2、0.3 的累计概率密度，在其余分位数上，该文提出的模型都具备比拟好的校准能力；同时，在锐度和回归精度方面，文中提出的模型也优于高斯分布和伽马散布。从起因来说，样本自身的实在散布与高斯分布、伽马散布的差别决定了后两者的成果下限，而文中提出的模型则更加灵便，更可能保障成果。
从第三行后果能够看出，咱们提出的办法是校对成果最好，观测到的频率靠近相应的累积密度（0.1~0.9）。
此外，对较大累积密度 (0.6 ~ 0.9) 的校准优于较小累积密度 (0.1 ~ 0.5) 的校准。
在锐度和回归精度方面，距离 (0.2,0.8) 的均匀宽度大于距离 (0.4,0.6)，别离为 349.42 和 105.80。PL/RL 订单的 S -CRPS(127.67/46.29) 和 0.5 分位数损耗(90.30/29.77)。
Comparison with spot forecasting
该局部尝试与传统办法比照回归精度指标（传统 SF 办法聚焦在 fixed value）。SF 模型输入的是一个负数标量，为了放弃比照公平性，仍然采纳 QL_0.5 作为 loss，特色与模型构造也放弃不变。从 table5 中能够看到比照后果。
（留神，训练时 SF 模型只应用 PL 订单)
能够看到，文中提出的办法在各 PL、RL 数据集上均好于 SF 模型。通过剖析，这部分收益次要来自于 RL 订单，应用 RL 订单能够带来更多有用的信息。