美团配送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订单能够带来更多有用的信息。