会员服务 ·

总结｜谷歌用GNN提高ETAs准确率

2020 年 9 月 27 日 AINLP

文 · 成森封面 · pixabay

总结｜谷歌用GNN提高ETAs准确率

这篇博文是Deep Mind和Google Maps合作的工作，主要是提高预计到达时间（ETAs）的准确率。

文章很粗糙，只给了一个大体的思路。看完后稍微整理一下。

主要核心思想是：

把道路切割成一个个的路段，每个路段视为一个节点，路段的相对位置构成节点间的边，形成路网的一个子图（文章称作Supersegments，超级路段）
然后使用GNN模型来对超级路段的行程时间进行预估。

原文链接：https://deepmind.com/blog/article/traffic-prediction-with-advanced-graph-neural-networks

把道路切割成超级路段

DeepMind把路网切割成一个个的路段，超级路段由多个相邻路段组成。也就是说，超级路段包含了几个路段，且每个路段都有特定的长度和相应的速度特征。每一个路段对应一个节点，一条路上的连续路段存在边，或者通过路口进行连接

<<< 左右滑动见更多 >>>

该系统专门有一个模块（route analyser，路由分析器）来专门处理大量的道路信息并构建超级路段。

而构建的模型则是用来预测每个超级路段的行程时间（travel time）。

预测模型

Deepmind也尝试了几个模型：

为每一个超级路段配上一个全连接网络，效果也不错；但超级路段的长度是动态的，所以需要单独为每个超级路段都训练一个模型，大规模下这显然不现实。
RNN模型能够处理变长序列；但是公路结构是复杂的，这一类模型难以处理；

所以最终选择了图神经网络，把局部路网视为一个图。也就是说，超级路段其实就是一个根据交通密度来随机采样形成的道路子图。

这也说明了每个路段的长度是不一致的，是根据流量密度来划分。

GNN不仅可以处理前后两段道路，还可以处理各种复杂的道路，比如交叉口。通过这种特性，DeepMind实验发现，通过把超级路段范围扩展到相邻道路，而不仅仅是只包含主道路，能够获得性能上的提升（比如说某条小巷的拥堵、甚至堵到了主干道）。

通过考虑多个路口的情况，模型可以考虑到转弯处、并道时的延误和走走停停情况下的总时间。

无论多长的超级路段（两个路段或者数百个路段组成的），都能用同一个GNN模型来处理。

从研究到生产力

DeepMind发现GNN对训练过程（training curriculum）的变化非常敏感，主要原因是训练过程中使用的图结构的差异太大。一个batch中每张图的节点数量从两个到一百多个都有。

在这里我有个疑惑，难道不是每个超级路网采样相同的节点，估计出每个路段的通行时间，然后再根据用户的起点终点来拼接出总时间？就算说全球路网巨大，难以为每一个路段都计算，但还是能根据历史记录来找出特定的“常用”路段。所以还是得等他们出论文再看看怎么处理的。

DeepMind也尝试了几个技术：

在监督条件下的新型强化学习技术。
在预定义训练阶段之后，DeepMind使用指数衰减学习率计划来稳定模型的参数。
还尝试了集成技术，从而观察是否可以减少训练过程中的模型差异。

这里原文写得挺乱的，所以我姑且把涉及到技术列出来，到底是组合使用还是依次尝试，还得琢磨琢磨。

最后，最成功的解决方案是使用 MetaGradient 来动态调整训练期间的学习率，从而可以有效地使系统学得自身最优的学习率计划。最终实现了更稳定的结果，使得该新型架构能够应用于生产。

MetaGradient 也是DeepMind提出的，具体阅读《Meta-Gradient Reinforcement Learning》

自定义损失函数实现模型泛化

DeepMind发现，线性组合多个损失函数（适当加权）能够极大地提升了模型的泛化能力，避免过拟合。具体来说，这个多损失目标使用了：

模型权重的正则化因子；
全局遍历时间上的 L2 和 L1 损失；
图中每个节点的 Huber 和负对数似然（negative-log likelihood, NLL）损失。

虽然没有提高训练的指标，但是能够更泛化地应用在测试集和端对端实验上。

目前，DeepMind 还在探索，在减少行程估计误差（travel estimate errors）为指导下， MetaGradient 技术是否可以改变训练过程中的损失函数的组合成分。这项研究受 MetaGradient 的启发，并且早期实验得到不错的结果。

最后

这篇博文隐藏了很多细节，所以细读后会有更多疑惑。

本质来说属于节点预测任务，利用直观的道路流量的邻接关系，和AAAI 2019的《Spatiotemporal Multi-Graph Convolution Network for Ride-hailing Demand Forecasting》有相似之处，不过这是预测某地点的出租车的需求量。同时文中没有提及如何利用好时间这一因素。

文中也没有说到DeepMind为了实时预测具体做什么工作。

文章一开头就说Google Maps其实已经可以精准对97%行程的ETA，这次工作是为了解决剩下的不高于3%行程的不准确，然而却没有提及为啥不准确。

如果是论文，我觉得DeepMind会把GNN+强化学习+交通预测作为主题，所以姑且就快速一览吧。

说个正事哈

由于微信平台算法改版，公号内容将不再以时间排序展示，如果大家想第一时间看到我们的推送，强烈建议星标我们和给我们多点点【在看】。星标具体步骤为：

（1）点击页面最上方"AINLP"，进入公众号主页。

（2）点击右上角的小点点，在弹出页面点击“设为星标”，就可以啦。

感谢支持，比心。

欢迎加入图神经网络交流群

进群请添加AINLP小助手微信 AINLPer（id: ainlper)，备注GNN

推荐阅读

这个NLP工具，玩得根本停不下来

征稿启示| 200元稿费+5000DBC（价值20个小时GPU算力）

完结撒花！李宏毅老师深度学习与人类语言处理课程视频及课件（附下载）

从数据到模型，你可能需要1篇详实的pytorch踩坑指南

如何让Bert在finetune小数据集时更“稳”一点

模型压缩实践系列之——bert-of-theseus，一个非常亲民的bert压缩方法

文本自动摘要任务的“不完全”心得总结番外篇——submodular函数优化

Node2Vec 论文+代码笔记

模型压缩实践收尾篇——模型蒸馏以及其他一些技巧实践小结

中文命名实体识别工具（NER）哪家强？

学自然语言处理，其实更应该学好英语

斯坦福大学NLP组Python深度学习自然语言处理工具Stanza试用

关于AINLP

AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLPer(id：ainlper)，备注工作/研究方向+加群目的。