国际数据挖掘领域的顶级会议 KDD 2018 在伦敦举行，今年 KDD 吸引了全球范围内共 1480 篇论文投递，共收录 293 篇，录取率不足 20%。其中滴滴共有四篇论文入选 KDD 2018，涵盖 ETA 预测 ( Estimated Time of Arrival, 预估到达时间) 、智能派单、大规模车流管理等多个研究领域。

四篇论文分别是（文末附论文打包下载地址）

本文是对滴滴 KDD 2018 Poster 论文《Learning to Estimate the Travel Time》的详细解读，在这篇文章中，滴滴技术团队设计了一种使用深度神经网络来预测预估到达时间（ETA）的方案，通过将 ETA 建模成一个时空回归问题，构建了一个丰富有效的特征体系，进一步提出 Wide-deep-recurrent（WDR）模型，能在给定出发时间和路线的情况下更加准确地预测。这一事件在雷锋网(公众号：雷锋网)学术频道 AI 科技评论旗下数据库项目中有相应加分。

 从规则模型到完整的机器学习方案

Service，LBS）中至关重要、又极具复杂性和挑战性的问题。它不仅需要考虑交通系统的空间特性，比如途径红绿灯的个数、道路的限速、是否可以绕远走快速路；还要考虑交通系统的时间特性，比如早晚高峰的规律性拥堵和交通事故导致的偶发性拥堵等。同时，因为交通系统的运行需要人和车作为主体来参与，也少不了外部因素的影响，因此时间预估问题还需要引入对个性化特征和外部特征的建模，比如司机驾驶习惯、雨天雾天对行车速度的干扰等。

在滴滴平台，ETA 是一项必不可少的基础服务。无论是行程前的预估接驾时间、预估价格显示，还是派单、调度、拼车等系统决策，亦或是行程中的预计到达终点的时间计算等，离不开高精度 ETA 的辅助。滴滴每天有约 700 亿次的 ETA 请求，峰值时每秒要处理约 400 万次。

用规则模型计算 ETA 是此前地图行业通用做法之一。即分别计算各段路的行驶时间，全部加起来再根据红绿灯时间做一个偏移修正。用数学来描述，预估时间可以表达为

其中，是第 i 个路段的预估行驶时间，而 是第 j 个红绿灯的预估等待时间。下图更为直观地展示了这种计算方法：

这是完全根据物理结构构建起来的模型，而其中最关键的部分在于每一路段的时间和每一个红绿灯时间的获取。考虑到路段的通行状态每时每刻都在动态变化，一个比较实际的做法是利用最新的历史数据（比如，刚刚过去的 5 分钟）来估计路段的实时通行时间，而把历史平均通行时间作为默认值来填充信息缺失的路段（若一个路段在最近没有滴滴车辆经过，此时它的通行状态是未知的）。红绿灯亦可采用类似的做法从数据中去挖掘每个红绿灯的历史平均等待时间，用作.

规则模型虽然在线服务计算量小，易于实现，但其使用大量基于经验和直觉的人为规则，不仅缺乏科学的探索方法；局限多、扩展差，也容易遗漏了很多重要信息，比如个性化特征等；此外，简单的统计量也不足以分析出复杂的交通模式，核心指标往往容易面临瓶颈，无法再靠添加新规则进行优化。

为了更好地发挥海量出行数据的潜力，滴滴于 2015 年首创了一整套机器学习系统来解决 ETA 问题。从类型上看，ETA 是一个很典型的回归问题：给定输入特征，模型输出一个实数值，代表了预测的行程时间。滴滴探索和构建了一套系统的地图领域的特征和表达集合，包括空间信息、时间信息、交通信息、个性化信息、扩展信息等几个方面，能充分考虑连通起点和终点的全部路径、涉及的路段、路口和红绿灯，以及所经过区域的 POI、行程对应的时间属性、实时路况、司机的驾车行为以及天气、交通管制情况等。

考虑到用户对误差的敏感程度更多的和相对值有关，滴滴将 MAPE（mean absolute percentage error）选择为目标函数，对应于 MAPE 的优化问题为：

Arrival，ATA），而是预估时间，代表了回归模型。为了防止 over-fitting，还可以加上正则项

而在回归模型上，滴滴先后考虑过两种在业界比较流行的模型，Tree Based model 和 Factorization Machine。其中，树模型的最终输出是多棵树的集成结果，可以写成：

是模型中树的数量。每一棵树都会根据输入特征进行判断，决定输入数据所属的叶子节点，然后将叶子节点对应的分数作为单棵树的输出，也就是

代表了第 t 棵树全部叶节点构成的分数向量，是一个映射函数（通过一系列条件判断），决定了应该归属的叶子节点序号。对于模型，其复杂度是由树的结构和规模来控制的，即使用如下正则项

直观来看，第一项对叶子节点的数目进行了控制，而第二项通过 L2 范数来对叶子节点的输出 score 进行控制。用树模型做 ETA 任务的目标函数最终可以写成

而 FM 模型的核心思路是将特征交互的权重矩阵进行分解，表达为向量内积的形式，以此来减少参数数量。二阶 FM 的计算为

其中 d 是特征维度，通常在千万级别甚至更高。而参数向量的维度 m 相对很小，通常在几十的量级便能达到较好的预测精度。FM 同样可以对 ETA 进行回归建模，加上一些正则项，就得到了优化目标

其中表示 v 向量构成的矩阵的 Frobenius 范数。

虽然这一完整的机器学习解决方案，为滴滴带来了显著的 ETA 准确度提升，但由于大部分回归模型比如 XGBoost，能够接收的输入向量必须是固定长度的，而一段行程对应的路段（以下称为 link）数变动范围很大，因此在实际使用时，舍去了 link 级的特征，取而代之使用整体统计值。所以在细节信息层面，这一解决方案还有优化的空间。

为了最大化信息的无损，保留模型对 link 序列信息的建模能力，滴滴创新地将深度学习应用到 ETA 上。这一 ETA 模型的核心思路是 global model + recurrent model。其中 global model 的作用类似于上一代模型，针对行程的全局信息进行学习；而 recurrent model 则专注于对 link 序列等局部细节的学习。

在 global model 部分滴滴考虑了近年来在推荐系统领域受到关注的 Wide & Deep 模型，以保证所有模块都可以进行端到端的训练。其 Wide 分支其实和 FM 是源出一脉的，对特征进行二阶交叉，对历史数据拥有一定的记忆功能。而它的 Deep 分支就是传统的多层感知机结构，有较好的泛化能力。两个分支强强联手，能互取所长。

WD 模型的大体结构如下图所示：

可以看到，这一模型总共有三类特征：

• Dense feature：行程级别的实数特征，比如起终点球面距离、起终点 GPS 坐标等。

• Sparse feature：行程级别的离散特征，比如时间片编号、星期几、天气类型等。

• Sequential feature：link 级别的特征，实数特征直接输入模型，而离散特征先做 embedding 再输入模型。注意，这里不再是每个行程一个特征向量，而是行程中每条 link 都有一个特征向量。比如，link 的长度、车道数、功能等级、实时通行速度等。

其中，Wide 和 Deep 模块对行程的整体信息进行建模，而 Recurrent 模块对行程的轨迹进行细致的建模，可以捕捉到每条 link、每个路口的信息。在最终汇总时，Wide 模块通过仿射变换把输出变到合适维度，Deep 模块直接把顶层 hidden state 作为输出，而 Recurrent 模块将 LSTM 的最后一个 hidden state 作为输出。三个模块的输出向量被拼接起来，进入最终的 Regressor 进行预测，得到 ETA 值。全部参数都基于 MAPE loss 做梯度下降来训练。

系统架构如下图所示。最底层为数据源，分别是地图信息、GPS 轨迹、订单记录和其它必要的附加信息。然后，原始数据经过特定的处理，变为模型可用的格式，用于训练模型。注意这里有一个小分支，表示在训练完成之后还单独取出了一小批 up-to-date 数据进行 finetune，使得模型更倾向于最新收集的数据。线下训练好的模型，最后被推送到线上系统，对外服务。

线下实验中，滴滴对 2017 年前五月北京滴滴平台的数据进行了适当的过滤，发现无论是 pickup（司机去接乘客）还是 trip（司机送乘客前往目的地），其 WDR 模型有较大幅度的提升。

滴滴也进行了为期一周的线上评估，从曲线可以看到，其模型在线上实际系统中也有着领先的性能。

滴滴团队指出，虽然其 WDR 模型能进行更准确的预测，但仍然有很多问题需要进一步地探索，比如怎样引入路网的拓扑图结构，如何与路径规划进行融合，如何将路况算法与 ETA 联合起来进行端到端的学习，如何预测时间区间而不是单个时间，如何提高线上系统的服务性能等，然是需要深入研究的课题。

雷锋网原创文章，未经授权禁止转载。详情见。

深度学习近年来对数据科学产生了革命性的影响。基于计算能力的提升、数据来源的延展及编程框架的进步，深度神经网络已经无处不在。目前深度学习的相关方法在如计算机视觉、语音识别及生成、自然语言处理等多个领域取得了领先进展，也正在将它的应用领域延展至其它研究当中，取得更大的应用优势。

而在 KDD 2018 大会同期举办的首个 key event——Deep Learning Day，毫无疑问成为了本次大会倍受关注的重点议程。据官方介绍，这个首次在 KDD 举办的「深度学习日」，是 KDD 大会历史以来第一个围绕深度学习所组织的全天议程，旨在对深度学习提供学术与工业融合的最新研究发展概述，包括如图卷积神经网络及计算最优传输等众多新兴的研究主题。

Deep Learning Day 的核心议程是十名特邀讲者的报告，包括三个 Keynote 演讲及七个主题演讲，每个演讲时长均为 45 分钟。同期收录的 32 篇论文也主要是以交流为主，不作专门的口头报告。「一个专注的主题，一个更大的空间，」Deep Learning Day 的组织者之一、德州农工大学助理教授胡侠博士（Hu "Ben" Xia）如是总结道，「我们可以把 Deep

据雷锋网 AI 科技评论了解，Deep Learning Day 实际上从去年就已经开始规划筹办，直到今年才正式与 3000 余名参会者见面。从学术大环境与大会规划上，增设 Deep Learning Day 这一议程有着两方面的重要考虑。

首先是深度学习的广泛应用有目共睹，KDD 组委会认为有必要增设一个单独环节专门对深度学习的相关研究进行讨论；其次，鉴于 KDD 本质还是一个基于知识发现与数据挖掘的顶级学术会议，组委会并不希望让深度学习的「风头」盖过多样化的数据挖掘研究方向，因此将深度学习的相关议程独立出来，也有益于数据挖掘领域的健康发展。

值得一提的是，特斯拉的 Andrej Karpathy 在演讲时也向观众们表示，这是他第一次受邀以讲者的身份参加 KDD 的首个 Deep Learning Day，着实颇具意义。

的十位讲者基本都是产学双栖的中青年讲者，他们作为研究的中坚一线力量，能为与会的观众们提供最新的思考。这一点得到了胡侠博士的证实，组织者们在邀请演讲嘉宾的过程中，也综合考虑了多方面的因素。「第一，我们希望讲者要有横跨工业界与学术界的丰富经验，即使是工业界大牛，也有着比较强的研究背景；其次，讲者们需要覆盖多个深度学习目前做得比较不错的主题，如视觉、健康、自动驾驶等；再者，还要兼顾深度学习的理论内容，做到理论应用相融合。」

而从现场的参会情况来看，Deep Learning Day 的首次「亮相」无疑颇具成效。场地选择的是用来举行 KDD 2018 开幕式的最大场馆，当天据雷锋网(公众号：雷锋网) AI 科技评论估计，有近千人参与了这个「超级 workshop」；而从组委会反馈的情况来看，也有一部分与会者就是专门冲着 Deep Learning Day 而注册参会的。这自然给予了

有了第一年的成功经验，在未来 Deep Learning Day 可能发展成为 KDD 的一个特色议程吗？胡侠博士向雷锋网 AI 科技评论分享了自己的一些观点。

KDD 2018 举办 Deep Learning Day，本质上是希望通过将与深度学习相关的内容剥离出来，让 KDD 更纯粹地成为一个数据挖掘的相关会议。「目前收到的正面反馈很多，我们也在考虑是否将 Deep Learning Day 的规模进一步扩大，但组委会对此还是表现得相当谨慎，至少不会在议程的比重上对深度学习的重要性进行『肯定』。」

其次，在 Deep Learning Day 的具体议程设置上，组委会也在考虑是否减少深度学习的理论分享，以强化数据挖掘的核心主题。这些思考也能够进一步地帮助下一年的 KDD 做更符合实际情况的议程制定，我们也期待明年 KDD 的 Deep Learning Day，可以给我们带来更多惊喜。

雷锋网原创文章，未经授权禁止转载。详情见。