关于深度学习:滴滴ETA论文解读WDR模型

46次阅读

共计 2681 个字符，预计需要花费 7 分钟才能阅读完成。

paper：Learning to Estimate the Travel Time

读后感：整体中规中矩，将 WD 模型和 LSTM 相结合，解决理论的业务问题。

备注：ETA 是 Estimate Travel Time 的缩写，即，达到工夫预估。这个问题形容是，在某一个时刻，预计从 A 点到 B 点须要的工夫。对于滴滴，关注的是司机开车把乘客从终点送到起点须要的工夫。显然，ETA 就是一个时空相干的回归问题。

用规定模型计算 ETA 是此前地图行业通用做法之一。即别离计算各段路的行驶工夫，全副加起来再依据红绿灯工夫做一个偏移修改。用数学来形容，预估工夫能够表白为：

其中，$t_i、c_j$ 别离示意第 i 个路段、第 j 个红绿灯的耗时时长。思考到路段的通行状态每时每刻都在动态变化，利用最新的历史数据（比方，刚刚过来的 5 分钟）来预计路段的实时通行工夫，而把历史均匀通行工夫作为默认值来填充信息缺失的路段。红绿灯耗时时长计算亦然。

长处：计算量小，易于实现
毛病：依赖人工教训，可扩展性差，难以利用多种多样的特色

滴滴将 MAPE（mean absolute percentage error）抉择为指标函数，对应于 MAPE 的优化问题为：

为了避免过拟合，还加上了正则项：

在具体到模型层面，滴滴先后采纳了两种业界比拟支流的办法：Tree Based model 和 Factorization Machine。

Tree Based model

其中，树模型的最终输入是多棵树的集成后果，能够写成如下模式，其中，T 示意树的颗数：

每一棵树都会依据输出特色进行判断，决定输出数据所属的叶子节点，而后将叶子节点对应的分数作为单棵树的输入：$f_t(x)=w_{t}u(x)$。其中，$w_{t}$ 代表了第 t 棵树全副叶节点形成的分数向量；$u(x)$ 是一个映射函数（通过一系列条件判断），决定了 $x$ 应该归属的叶子节点序号。

针对于第 t 颗树，对应的正则项能够表白为如下模式，其中 L 为叶子节点的数目，第二项通过 L2 范数来对叶子节点的输入 score 进行管制，$γ$ 是超参数：

具体到 GBDT 模型，最终优化指标形式化表述为：

因为 mape 是不可微分函数，尽管指标函数是凸函数，然而指标函数是非平滑的。咱们能够应用 huber loss 近似 mape 函数，或者，采纳次梯度办法（subgradient method）求解该优化问题。

Factorization Machine

FM 的具备预测准确性高、特色工程灵便两个长处，广泛应用于举荐零碎和在线广告零碎畛域。FM 模型的外围思路是将特色交互的权重矩阵进行合成，表白为向量内积的模式，以此来缩小参数数量。二阶 FM 示意为：

其中 d 是特色维度，通常在千万级别甚至更高；而参数向量 v 的维度 m 绝对很小，通常在几十的量级便能达到较好的预测精度。

如果对 FM 减少正则项，能够形式化示意为如下模式，其中 $||V||_F$ 示意 V 向量形成的矩阵的 Frobenius 范数：

这个问题能够通过梯度办法进行求解。此外，还尝试了 online learning：应用自适应次梯度办法（AdaGrad)更新 V，应用 FTRL 更新 w。

惯例模型的缺点：大部分回归模型的输出向量必须是固定长度的，而一段行程对应的路段（以下称为 link）数变动范畴很大，因而在理论应用时，舍去了 link 级的特色，取而代之应用整体统计值。这样，就失落了细节方面的刻画。

新计划的外围思路是 global model + recurrent model。针对 global model，滴滴应用 wide-deep 模型替换掉了之前的树模型、FM 模型；recurrent model 则专一于对 link 序列等部分细节的学习。

recurrent model

WD 模型咱们按下不表，重点说下 recurrent model 局部。Recurrent model 的抉择则比拟丰盛，不仅仅限于 RNN（包含变种 GRU、LSTM、SRU 等），还能够是一维卷积 CNN，或者是纯正的 Attention model。以最风行的 LSTM 为例，它通过引入 additive memory 和 gate 来缓解简略 RNN 的梯度隐没问题：

LSTM 的内部结构如下所示：

WDR 构造

在 WDR 模型中，Wide 和 Deep 模块对行程的整体信息进行建模，而 Recurrent 模块对行程的轨迹进行粗疏的建模，能够捕捉到每条 link、每个路口的信息。在最终汇总时：

Wide 模块通过仿射变换把二阶穿插变换后果变到适合维度（256 维）；
Deep 模块首先将离散特色 embed 到 20 维，之后和间断特色做 concat，通过三层全连贯，间接把顶层 hidden state 作为输入（256 维）；
Recurrent 模块将 LSTM 的最初一个 hidden state 作为输入（256 维）。

三个模块的输入向量被拼接起来，进入最终的 Regressor 进行预测，失去 ETA 值。全副参数都基于 MAPE loss 做梯度降落来训练。因为整个模型由三局部形成，难以找到一个适合的全局 learning rate，论文中采纳了 Adam 优化模型，learning rate 设置为 0.001。其余超参初始化参考论文：Adam: A Method for Stochastic Optimization。

特色

在特色层面，能够看到，这一模型总共有三类特色：

Dense feature：行程级别的实数特色，比方起起点球面间隔、起起点 GPS 坐标等。
Sparse feature：行程级别的离散特色，比方工夫片编号、星期几、天气类型等。
Sequential feature：link 级别的特色，实数特色间接输出模型，而离散特色先做 embedding 再输出模型。留神，这里不再是每个行程一个特征向量，而是行程中每条 link 都有一个特征向量。比方，link 的长度、车道数、性能等级、实时通行速度等。

成果比照

文章最初比照了几种模型的成果，WDR 优化成果显著。特地留神 WDR 和 WD-MLP，会发现应用 LSTM 对部分特色建模是有不错的正向收益的；另外有意思的一点，WD-MLP 整体成果不迭 FM。（在 WD-MLP 中应用一个多层感知机替换掉 recurrent 模块. The MLP is applied to each link and the output vectors are then averaged through all links along the route. We use the same output size of the recurrent module for this MLP.）

正文完