20231110_【社内論文読み会】ETA Prediction with Graph Neural Networks in Google Maps

google slide: https://docs.google.com/presentation/d/1MIukVTwUGs-qVK6B9p6-n_MAbs_MxA5Y4cSfhH7_iX8/edit?usp=sharing

Transcript

1. 論文読み会 2023/11/10 ETA Prediction with Graph Neural Networks in Google Maps 金田 佑哉 ETA Prediction with Graph Neural Networks in Google Maps(arXiv ver.) ETA Prediction with Graph Neural Networks in Google Maps(ar5iv ver.) deepmindブログ
2. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps 2
3. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps どんな論文か? 3 • 車のETA(Expected Time Arrival: 到着時間予測)問題 扱う問題 • Graph Networkを用いた アプローチ • Google Mapで使われている 成果
4. アプローチ方法
5. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps ブログに置かれているバエる動画 5 deepmindブログ
6. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps 問題設定 道路を分割し、それらを通過するために何分かかるのか(通過予測時間)をそれぞれの分割成分で問い合わ せる(学習する)。通過予測時間の更新のためにあらかじめ時間幅を定めておき、次の時間幅まで進めると ころまで進ませる。進めるところまで進んで、次のステップの予測を逐次的に問い合わせて、ゴールま でに要する時間を算出する。ちなみに(たぶん)事象の地平線になぞらえて更新のための時間幅を 「horizon」と表現している。 6 ETA Prediction with Graph Neural Networks in Google Maps A B start 1step 2step 3step 3step Goal
7. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps 構成要素 • Supersegments ◦ 出発地点~到着地点を繋ぐノード(Segments)とエッジの集合 ◦ つまりグラフネットワーク全体 • Segments ◦ 左図のように交差点のみならず、道路も分割した分割要素を Segmentsと呼んでいる • Edge ◦ Segmentsを接続する存在 どうやって作っている? • 分割の方法論は記載がなく、謎。 ◦ 一応、下記の表の通りのようなスタッツ Supersegment Graph 下記のように道路を分割し、グラフ構造として捉えることで、Graph (Neural) Networkとして扱います 7
8. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps 用いる特徴量 グラフ要素の学習方法 登場する要素ごとの特徴量をベクトルとし、NN(MLP)で埋め込みおよび予測をします 8 要素 Supersegment(graph) Segment(node) Edge 特徴量 • travel time • travel speed • embedding vectors • travel speed • travel time • segmentの長さ • 優先度(要はクラス) • embedding vectors • 接続する Segment(node)の特徴 量 左記の数式に従い、逐次的に要素ごとに特徴量を更新し、将来のtravel time(horizon)に対する学習・予測をする 各地域ごと、horizonごとに別々のモデルを学習する feature vecの更新にはMLP(Multi Layer Perceptorons)を、集約パートで はsummationを使用したとのこと。しかし、MLPのhyper parmsなどの情報 は公開されていない。。。 feature vecの更新パート (隣接成分の) 集約パート 交互に更新
9. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps こちらの論文の紹介スライド (こういう公開資料ありがたい。。。) Relational inductive biases, deep learning, and graph networks 前述の定式化は別の論文をベースとしているようです(たぶん今回の論文だけでは理解できない)。 9 Relational inductive biases, deep learning, and graph networks https://www.slideshare.net/DeepLearningJP2016/dlrelational-inductive-biases-deep-learning-and-graph-networks-104442091 Kipf’s D Thesis こちらの論文に登場する数式 今回の論文とほぼ同じnotationであることがわかる
10. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps 【補足】物理の問題として扱ってみた例 10 Relational inductive biases, deep learning, and graph networks https://www.slideshare.net/DeepLearningJP2016/dlrelational-inductive-biases-deep-learning-and-graph-networks-104442091 Kipf’s D Thesis
11. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps 損失関数(1) Supersegment, Segment, ΣSegmentでのtravel timeをそれぞれ定義し、重みづけで線形和にしたものを 今回のlossとします。また、損失関数としてはHuber lossを用いて、外れ値にロバストに設計しているら しいです。 11 free-flow travel time(滞留がない状態での通過時間らしい: f)の長さによって重みを軽くしている(時間がかかる道で は誤差も大きめに外れがちなので、そのはずれ具合を調節しているようにしている……と読み取っています。Huber lossも同様の理由かと)。 https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.huber.html
12. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps 損失関数(2) 個別の損失関数は下記の説明の通りです。 12 : Huber loss : Supersegment-levelでのtravel time : Segment-levelでのtravel time : 2Segment間でのtravel time : free-flow travel time(seconds) : Supersegment-levelでのloss : Segment-levelでのloss : 2Segment間でのloss
13. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps 学習率の最適化: MetaGradient グラフの要素ごとにばらつきが激しく、学習がうまく収束しない課題があったが、強化学習で使われて いるMetaGradientという学習率の更新方法を採用することで学習がうまくいったようです。 13 「モデルの重み(θ)のみが学習率をはじめとするハイパーパラメータ(η)を引数として持つ」と仮定すると、損失関数(L) の微分は下記のようなChain ruleで記述される。 「(流石に詳しく追っていないけど)下記の式に近似できる」とMeta-Gradient Reinforcement Learningという論文で 示されているらしい。 Meta-Gradient Reinforcement Learning(NeurIPS論文) 上記の微分量でηを更新しつつモデルの重みを更新する学習を進める。
14. 実験
15. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps 従来の推定方法との比較 今回のアプローチによって、いくつかの地域でETAの精度が向上することが確認されたらしく、実際に現 在のGoogle Mapで使われているようです。 15
16. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps ベースラインモデル 16 ETA Prediction with Graph Neural Networks in Google Maps
17. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps 単純な予測精度比較 統計的にも有意な結果が出ているらしい(5つのランダムシードで検証しても有意差が確認できているよう です)。 17
18. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps Ablation study: 埋め込みベクトルの優位性 埋め込みベクトルの有無を調査するablation studyを実施。基本的にRMSEの改善に貢献することが確認 できたらしい。 18
19. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps Extended Supersegment 対象のSegmentに接続する経路とは別のSegmentも学習と推論に利用した実験を実施。精度向上につな がることが確認された……が、計算コスト的に無理っぽい。 19
20. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps 20 Variational Graph Auto-Encoders
21. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps オンラインモデル結果 21
22. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps 22
23. まとめ
24. 金田 佑哉 / 25 ETA Prediction with Graph Neural Networks in Google Maps まとめ 24 • 道路(車)での到着時間予測にGraph Networkを用いて、従来のベースラインモデルを上回る精度 が確認できた • 実際のGoogle Mapにデプロイされている • Graph Neural Networkを交通ネットワーク解析に活用することでGNNでの成功事例が一つ増え た
25. Appendix