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

从Deep Mind的博客看到他们关于交通预测的文章，看完后整理一下。文章很粗糙，只给了一个大体的思路。


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


主要核心思想是：

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

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

把道路切割成超级路段

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

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

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

预测模型

Deepmind也尝试了几个模型：

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

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

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

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

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

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

从研究到生产力

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

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

DeepMind也尝试了几个技术：

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

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

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

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

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

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

1. 模型权重的正则化因子；
2. 全局遍历时间上的 L2 和 L1 损失；
3. 图中每个节点的 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+强化学习+交通预测作为主题，所以姑且就快速一览吧。