KDD2022:Applying Deep Learning Based Probabilistic Forecasting to Food Preparation Time for On-Demand Delivery Service

参考资料：2022KDD论文解读：深度学习订单出餐时间概率预测

摘要

On-demand food delivery service has widely served people’s daily demands worldwide, e.g., customers place over 40 million online orders in Meituan food delivery platform per day in Q3 of 2021. Predicting the food preparation time (FPT) of each order accurately is very significant for the courier and customer experience over the platform. However, there are two challenges, namely incomplete label and huge uncertainty in FPT data, to make the prediction of FPT in practice. In this paper, we apply probabilistic forecasting to FPT for the first time and propose a non-parametric method based on deep learning. Apart from the data with precise label of FPT, we make full use of the lower/upper bound of orders without precise label, during feature extraction and model construction. A number of categories of meaningful features are extracted based on the detailed data analysis to produce sharp probability distribution. For probabilistic forecasting, we proposeS-QLandproveitsrelationship with S-CRPS for interval-censored data for the first time, which serves thequantilediscretization of S-CRPSandoptimizationforthe constructed neural network model. Extensive offline experiments over the large-scale real-world dataset, and online A/B test both demonstrate the effectiveness of our proposed method.

引言

动机

订单的食品准备时间占整体配送周期时长的30%，平台通常要求骑手在菜品准备好的时候到达餐厅。但从骑手的角度来看，过早到达餐厅意味着等待时间长，会影响他们的配送体验，因为骑手还有其他订单需要等待太久才能完成。同时，顾客也不希望自己的订单被延误太久而影响菜品的味道。因此，准确预测每个订单的食品准备时间（food preparation time，FPT）对骑手和客户来说是非常重要的。

挑战

FPT预测是一个典型的回归问题，作者认为这个问题的主要挑战有两方面：

1.不完整的标签问题

精准标签订单：如果餐厅员工每次都在食物准备好时立即报告给系统，那么系统就会得到精确的FPT数据。比如，你点了一份炒饭，餐厅告诉你“您的炒饭将在15分钟后准备好”，然后实际上15分钟后确实完成了。这时系统就记录了准确的FPT是15分钟，这算作是一个精准标签（ precise-label，PL）订单。但很多情况下，餐厅可能不会每次都及时报告，因此，只有部分订单（不超过70%）有精确的FPT值。
范围标签订单：剩余的非PL订单是区间删失数据，只能得到FPT的下限和上限，称为“范围标签”（RL）订单。例如，配送员到达餐厅准备取餐时，发现食物还没做好，等了10分钟才拿到餐品。这时我们知道FPT至少为10分钟（下限），而上限则是配送员实际等待的时间加上合理的额外时间。假如配送员最终等待了20分钟才拿到餐品，那么FPT的真实值就在10到20分钟之间。

tips
骑手因为长时间的等待放弃取餐而离开商家，我们就可以将离开商家的时间看作是下界（如果没有明确判定理由，下界设置为0）

2.FPT数据的巨大不确定性

即使我们有部分准确的数据，由于下面三种实时因素的存在，使得对FPT进行精确预测变得非常困难

厨房供应情况：餐厅厨房内的原料库存、设备状态或厨师人数等都会影响准备时间。
食物准备程序：不同菜品的制作过程复杂度不一，有的菜可能几分钟就能完成，而有的则需要更长的时间。
堂食情况：如果餐厅同时有很多堂食顾客，可能会优先处理这些订单，从而影响到外卖订单的准备时间。

贡献

作者首次将概率预测（Probabilistic Forecasting, PF）应用于食品准备时间（Food Preparation Time, FPT）的预测，并定义了FPT-PF任务。
提出了S-QL（S-Quantile Loss）并证明了它与S-CRPS（Survival Continuous Ranked Probability Score）的关系，这是首次为区间截断数据提出的S-CRPS的分位数离散化和优化方法。
提出了一个基于深度学习的非参数模型，通过预测一系列累积密度的分位数来构建概率分布，使用分位数离散化以避免S-CRPS积分计算的复杂性

tips
参数模型和非参数模型中的“参数”并不是指模型中的参数，而是数据分布的参数。值得注意的是，无论数据集大小，参数模型假设数据分布的参数是固定的，而非参数模型不假设固定的数据分布形式，参数数量可以随着数据量的增加而增加。

概率预测（Probabilistic Forecasting, PF）

作者首次将概率预测（PF）应用于FPT，PF广泛应用于具有强烈不确定性的情景和区间删失数据，例如吴恩达团队曾在2020年提出将PF应用于预测病患的死亡时间（生存预测），即通过评价未来时间的概率分布来预测事件发生时间。

参考资料：吴恩达团队提出倒计时回归模型：用AI技术预测病患死亡时间

问题定义

FPT（Food Preparation Time，FPT）

每个订单 $o$ 包含 $m^{o}$ 种不同的菜品，用集合 $D^{o} = {(d_{i}^{o}, n u m_{i}^{o}) ∣ i = 1, 2, \dots, m^{o}}$ 来表示，其中 $n u m_{i}^{o}$ 是菜品 $d_{i}^{o}$ 的数量。订单 $o$ 的信息可以用五元组 $(X^{o}, y^{o}, l^{o}, u^{o}, c^{o})$ 来表示。食品准备时间 $t^{o}$ 由等待前一订单完成的排队时间和当前订单中所有菜品的亨饪时间两部分构成。

FPT的任务目标是将每个订单的FPT建模为概率分布，假设我们采用一种参数化方法，使得FPT遵循正态分布。目标是根据上述特征 $X^{o}$ 预测出这个正态分布的均值和方差。即得到一个完整的CDF或PDF函数，此函数能够告诉我们任何给定时间内订单完成的概率。例如，该订单在15分钟内完成的概率为60%，在20分钟内完成的概率为90%。

若选择非参数化方法，比如核密度估计(KDE)或者直方图方法，FPT的任务目标则是预测出一系列离散点上的概率值。例如，可以预测在10分钟、15分钟、20分钟、25分钟等特定时间点上订单完成的概率。这样不需要假定数据符合某种特定的分布形式，可以直接从数据中学习这些概率值。

主要方法

不同订单的聚合（Aggregation of FPT for Different Orders）

本实验需要计算从历史订单中统计的FPT来进行特征分析和提取。对于所有标签都是精确标签（PL）的情况，一般采用会采用数据中的的均值和方差作为统计指标。但FPT问题包含两种类型的订单，只考虑PL订单是不合理的，对于RL订单，由于其不确定性，直接计算它们的均值和方差是不可行的。

因此作者全面考虑了PL和RL两种类型的订单，设计了一个离散累积概率分布（DCP）方法来聚合一组订单的FPT，DCP的定义如下

DCP = {{dcp}_{z} ∣ z \in Z}

其中 $Z$ 是一系列等距的离散时间点，其表达式为

{z_{i} = i \times Δ z ∣ 1 \leq i \leq n_{z}}

$Δ z$ 的选取依据统计精度需求设定，且 $n_{z} \times Δ z$ 一般是一个相对较大的值，确保几乎所有的FPT都不会超过这个范围。

${dcp}_{z}$ 的含义是不超过特定时间点 $z$ 的订单的比例。对于PL订单， ${dcp}_{z}$ 的计算是直观的；而对于RL订单，只有当 $z \leq l$ 或 $z \geq u$ （ $l, u$ 分别代表RL订单的下限和上限）时，才能确定FPT是否超过了 $z$ 。如果 $l < z < u$ ，即RL订单的时间区间跨越了 $z$ ，那么无法确定FPT是否超过了 $z$ ，此时不对这些订单做任何假设并忽略它们。此外，作者还基于DCP计算了一个近似的平均值，这个近似均值可以粗略地描述平均FPT的情况，但并不是数值上的精确结果，主要用于辅助数据分析。公式为

\sum_{i = 1}^{n_{z}} ({dcp}_{z_{i}} - {dcp}_{z_{i - 1}}) \times (z_{i} + z_{i - 1}) / 2

特征提取（Feature Extraction）

作者主要提取了这三类特征（环境特征、商家特征、餐品特征）

环境特征

按需配送任务存在明显的时间周期性。从下图中可以看出，在每个曲线中有两个明显的峰值，人们主要在中午和晚上进行订单。在高峰期，由于排队时间较长，餐厅需要更多的时间来准备食物。除了时间段外，FPT在一周内的不同天数之间也会发生变化，尤其是对于工作日和周末。在周末，客户下订单更多，尤其是在非高峰时段。

餐厅特征

不同餐厅可能存在差异，作者提取了一系列相关特征来描述每个餐厅的特点

**基本信息：**每个餐馆注册了它主要经营的一般菜系类别，如小吃、甜点、饺子和热点。不同类别的烹饪程序和时间变化很大。作者计算了每种餐馆类别中订单的DCP。如下图所示：从粥、饺子、汉堡包、热点到烧烤，FPT逐渐增加。

实时供需信息：对于一个订单的FPT，需要考虑之前订单完成所需的等待时间，餐厅的实时供需状态对订单的完成时间有很大影响，作者统计了餐厅在过去一段时间内（如10/20/30分钟）收到的订单数量来捕捉实时客户需求的程度结果，如下图所示

菜品特征

订单是由几个独特的菜品组成，并且每个菜品都有相应的数量。作者对每道菜的特征进行分类和提取。作者使用每道菜的数量和价格作为基本特征。每道菜的数量和价格对FPT有影响。

通常相同的菜品可以一起烹饪，但当出现不能一次性烹饪多份的菜品时，时间会突然增加。
较高的价格往往意味着更复杂的烹饪程序和较长的时间。

S-CRPS and S-Quantile Loss

概率预测的目标是在满足校准（calibration）的前提下尽可能提高预测的锐利度（sharpness）

tips
校准：通常指预测分布与实际观测值之间的统计一致性，换句话说，它是衡量模型预测概率的可靠程度，只有校准好的模型（预测概率是可靠的才能用来做决策）
锐利度：预测分布的集中程度，锐利度越高说明数据聚集程度越高，准确度越高

连续分级概率评分（continuous ranked probability score, CRPS）

对于连续输出的预报，其预测结果通常是以概率密度函数（Probability Density Function, PDF） $f$ 的形式给出的，相应的累积分布函数记为 $F$ 。在实际情况中，我们会观察到一些实际的结果 $y$ 。设定一个评分法则 $S$ 用来计算预测分布和实际结果之间的误差，并返回一个损失值 $S (F, y)$ ，如果对于所有的可能分布 $G$ ， $S$ 都是一个合适评分法则，则有：

E_{y \sim \hat{F}} [S (\hat{F}, y)] \leq E_{y \sim \hat{F}} [S (G, y)]

CRPS证明是一种适当的评分规则，在PF中被广泛采用。两个著名的等价形式的CRPS如下所示：

\begin{aligned} CRPS (F, y) & = \int_{- \infty}^{y} F (x)^{2} d x + \int_{y}^{+ \infty} (1 - F (x))^{2} d x \\ = 2 \int_{0}^{1} {QL}_{q} (F, y) d q \end{aligned}

$F$ 是累计分布函数 (Cumulative Distribution Function, CDF)
$y$ 是观测值

第二个等式在CRPS和分位数损失之间建立了直接联系，分位数损失 ${QL}_{q} (F, y)$ 是一个关于分位数 $q$ 的函数，其中 $q$ 是一个介于 0 和 1 之间的值，表示我们感兴趣的具体分位数。

{QL}_{q} (F, y) = {\begin{cases} (y - F^{- 1} (q)) \cdot q, & F^{- 1} (q) < y \\ (F^{- 1} (q) - y) \cdot (1 - q), & F^{- 1} (q) \geq y \end{cases}

该定义分为两部分：

当 $F^{- 1} (q) < y$ 时，即预测的分位数 $F^{- 1} (q)$ 小于实际观测值 $y$ ，分位数损失为:

(y - F^{- 1} (q)) \cdot q

当 $F^{- 1} (q) \geq y$ 时，即预测的分位数 $F^{- 1} (q)$ 大于或等于实际观测值 $y$ ，分位数损失为:

(F^{- 1} (q) - y) \cdot (1 - q)

为了避免复杂的积分计算，通常采用公式5的离散化形式，例如，将公式3中的积分替换为对 $Q L_{q}$ 的求和，称为分位数离散化。

借鉴CRPS并同时解决区间删失数据场景，吴恩达团队提出了Survival-CRPS（S-CRPS），这种方法能够产生更加清晰锐化的分布。S-CRPS的方法定义如下：

S-CRPS (F, l, u) = \int_{- \infty}^{l} F (x)^{2} d x + \int_{u}^{+ \infty} (1 - F (x))^{2} d x .

针对RL订单，S-CRPS不做任何精确label的假设，没有针对区间删失数据的分位数S-CRPS，本文首次将CRPS中分位数离散化的方法引入到S-CRPS中。针对RL订单，S-CRPS不做任何精确label的假设，仅仅充分应用上下边界。S-QL的分位数损失公式如下:

S {QL}_{q} (F, l, u) = {\begin{array}{lr} (l - F^{- 1} (q)) \cdot q, & F^{- 1} (q) < l \\ 0, & l \leq F^{- 1} (q) < u \\ (F^{- 1} (q) - u) \cdot (1 - q), & F^{- 1} (q) \geq u \end{array}

与CRPS做相同的等价变化，则最终S-CRPS可被定义为

S-CRPS (F, l, u) = 2 \int_{0}^{1} S {QL}_{q} (F, l, u) d q

模型

作者提出了一种针对FPT-PF任务的非参数化深度学习模型。具体流程如下

1.对提取到的环境特征、商家特征、餐品特征进行预处理。

2.引入Attention机制捕获同一个订单中不同餐品对FPT的贡献差异。

3.对FPT的累计密度函数分位数进行预测，并通过最小化S-CRPS分位数离散值对模型进行优化。

特征预处理

首先对环境特征和商家特征同时编码，然后分别提取每道菜的特征，作者采用深度交叉网络（Deep Cross Network）对特征进行编码

\begin{aligned} v_{c r} & = DCN (X_{c}; X_{r}) \\ v_{d} & = DCN (X_{d}), d \in D \end{aligned}

$X_{c}, X_{r}$ 分别表示环境特征和商家特征， $X_{d}$ 表示餐品特征， $v_{c} r, v_{d}$ 分别表示编码后的两个向量。下面来详细解释一下DCN的编码过程

DCN模型如下图所示，由交叉网络和深层网络两部分组成

交叉网络模型：交叉网络的输出 $x_{i}$ 通过以下公式计算:

x_{i} = x_{0} x_{i - 1}^{T} w_{i - 1} + b_{i - 1} + x_{i - 1},

$x_{0}$ 表示原始特征，由密集特征和稀疏特征嵌入拼接而成
本文使用了三层交叉网络，即 $v_{cross} = x_{3}$

深层网络模型：

深层网络采用多层感知机模型，记为 $v_{deep}$ 。
深层网络的输出 $v_{deep}$ 通过以下公式计算：

v_{deep} = D N N^{3} (x_{0}), 。

FC层的计算公式为:

F C_{f} (x) = f (W x + b),

注：此处的激活函数 $f$ 为Leaky ReLU

注意力机制

不同商家的不同餐品的制作工序差异性较大。例如，奶茶的制作工序通常固定，且准备工作的并行化程度较高；相反，拥有复杂烹饪过程的餐品，当商家供给能力不足时，餐品的准备工作变成串行的。在完全并行的情况下，一个订单的出餐时间主要由最晚餐品决定；在串行的情况下，由所有餐品准备时间的总和决定。所以，一个餐品对订单的影响是十分复杂的，与环境信息、商家信息有非常大的相关性。由此作者使用注意力机制来计算不同餐品对于出餐时间的影响

a_{i} = σ (w_{c r} \cdot v_{c r} + w_{d} \cdot v_{d_{i}} + b)

聚合并计算加权注意力分数

v_{D} = \sum_{i = 1}^{m} a_{i} \cdot v_{d_{i}}

$a_{i} \in (0, 1)$ ，代表了餐品的贡献权重

概率预测

采用S-CRPS的分位数离散化形式作为模型的目标函数。为了防止过拟合问题，随着分位数的增加，预测概率也应同步增加。下面详细介绍概率预测的算法流程：将经过特征预处理的输入向量传递到第一个全连接层中（FC-Sofplus），经过Softplus激活函数 $s o f t p l u s (x) = l o g (1 + e^{x})$ 处理后，每个分位数得到一个非负数送入第二个全连接层（Cumsumum），在那里对前置各中间结果进行累加。最后得到一系列的输出值，分别对应于不同的分位数 $F^{- 1} (q_{i})$

模型训练

根据公式11的分位数离散化形式，损失函数为：

L (Θ) = {\begin{cases} 2 Δ q \cdot \sum_{i = 1}^{n_{q}} {QL}_{q_{i}} (F, y), & c = 0 \\ 2 Δ q \cdot \sum_{i = 1}^{n_{q}} S - {QL}_{q_{i}} (F, l, u), & c = 1 \end{cases}

KDD2022:Applying Deep Learning Based Probabilistic Forecasting to Food Preparation Time for On-Demand Delivery Service ​

摘要 ​

引言 ​

动机 ​

挑战 ​

贡献 ​

概率预测（Probabilistic Forecasting, PF） ​

问题定义 ​

FPT（Food Preparation Time，FPT） ​

主要方法 ​

不同订单的聚合（Aggregation of FPT for Different Orders） ​

特征提取（Feature Extraction） ​

环境特征 ​

餐厅特征 ​

菜品特征 ​

S-CRPS and S-Quantile Loss ​

连续分级概率评分（continuous ranked probability score, CRPS） ​

模型 ​

特征预处理 ​

注意力机制 ​

概率预测 ​

模型训练 ​

实验 ​