KDD2019交通系論文サーベイ（abstractメモ）
KDD2019で発表された論文のうち，"Traffic", "Transportation", "Travel", "Demand", "Urban", "Uber" のキーワードで引っかかった論文のメモです．
交通量予測
集中・発生量予測（どこで発生し，どこへ集中するか）
Urban Traffic Prediction from Spatio-Temporal Data Using Deep Meta Learning
(JD 他)
- 都市交通の予測のためには，時空間的な相関関係を扱う必要があるが，それはGPS上の位置や近くにあるPOI (Point of Interest：商業施設などの重要地点)，二点間の距離などによって異なってくる
- そこで，まずmeta learningにより抽象的な特徴・関係を抽出し，それをもとに時空間的な相関をモデル化する手法「ST-MetaNet」を提案
- 交通予測にmeta learning を用いたのはこれが初めて
- 発生・集中量と交通速度を予測する問題設定で，一般的な時系列モデルのARIMAや，Seq2Seqよりも小さい誤差で予測できることを示した
UrbanFM: Inferring Fine-Grained Urban Flows
(JD 他)
- 監視カメラなどの都市をモニタリングするデバイスを大量に使用するにはコストがかかるため，より少ないデバイスからの粗い情報で，できるだけ正確に都市のモニタリングをする技術が必要
- 都市をグリッド分割し，各グリッドに入ってくる交通量（集中量）を算出．そのデータを画像として扱い，天気などの他のデータと組み合わせて，より細かい粒度で交通集中量を推定する手法を提案
- タクシーの交通流と人流のそれぞれのデータセットで提案手法の評価実験を行い，既存手法よりも推定精度が向上したことを示した
OD推定（どこから，どこへの交通がどれくらいか）
DeepUrbanEvent: A System for Predicting Citywide Crowd Dynamics at Big Events
- 大規模なイベント（地震や台風，祭りなど）が行われるときは，人々の安全を守り，公共施設の運用を維持するために，群衆を管理する必要がある．しかしそのような大規模イベントでの人々の行動は日常的な行動とは異なるため，都市全体の群衆の行動を予測するのは難しい
- そこで直近１時間の人口密度，人流のデータから，1時間後の人口密度，人流を予測するオンラインシステム「DeepUrbanEvent」を提案
- 動画のフレーム予測などによく使われるConvLSTMをEncoderとDecoderとして扱うMulti-Task ConvLSTMを予測モデルとして用いている
- ARIMAや単純なConvLSTMよりも予測精度を向上した
Origin-Destination Matrix Prediction via Graph Convolution: a New Perspective of Passenger Demand Modeling
- OD行列を予測する際に課題となるデータのスパース性を克服するためにGrid-Embedding based Multi-task Learning (GEML)を提案
- 地図をグリッドに分割し，グリッドをノード，エッジをそのノード間の移動とすることで人の移動をグラフとして扱う．GCNによりエッジの重み（＝移動人数）をモデル化し，LSTMによりそれらの時系列的な変動を学習し，OD行列の予測を行う
- UCARとDiDi（中国のライドヘイリング企業）が収集した実際の乗客のODデータそれぞれ1ヶ月分を用いて学習し，1時間間隔のODおよび発生・集中量を予測．グリッドは2~3kmで分割されている（わりと広い範囲に感じるが，車で5分の距離だから許容範囲という主張）
- LSTMやGCRN (Graph Convolutional Recurrent Network) などの既存手法よりもOD行列の予測精度を向上した
Co-Prediction of Multiple Transportation Demands Based on Deep Spatio-Temporal Neural Network
- タクシーとバイクシェアのpick-upとdrop-off (OD) を推定する問題設定．従来はタクシーやバイクシェア，ライドヘイリングのODを別々に推定していたが，これらは相互に関係し合っているため，まとめて推定する方針をとった
- 地図をグリッド分割し，OD行列を作成し，それを画像データとして入力．CNN Autoencoder でEncodeし，時刻毎にLSTMに入れて，その後Decodeし，次時刻のOD行列を推定する
- この提案手法 CoST-Net (Co-prediction method based on Spatio-Temporal neural Network) は複数交通手段の移動の特徴を統合することで既存手法よりも良い精度でNYのタクシーとバイクシェアのODを予測できることを示した
配分量予測（どの経路をどれくらい利用するか）
Predicting Path Failure In Time-Evolving Graphs
(香港中文大学, Huawei)
- 道路ネットワークはノード（センサ局）とエッジ（道路）からなるグラフとして表現できるが，ハードウェアの故障や事故・自然災害による道路閉鎖によりグラフの構造は時間とともに変化する
- グラフ構造による交通流の違い，時空間的な関係（通勤時間帯は混雑するなどの時間依存性，ノード間の相関）を扱うために，Long Short-Term Memory R-GCN (LRGCN) を提案
- LRGCNで動的に変化するグラフを扱い，Self-Attentive Path Embedding（←Self-Attentive Sentence Embedding）により，固定長ベクトルに落とし込み，そのベクトルをもとに経路が混雑しているかを分類
- グラフを動的に扱うことで分類予測精度が向上することを示した
Graph-based Semi-Supervised & Active Learning for Edge Flows
- グラフのエッジの流れ（交通流）が部分的にわかっているときに全体の交通流を推定する半教師あり学習 graph-based semi-supervised learning (SSL) を提案
- 従来のGraph-based SSLは，ノードがデータ点で，エッジはそのノード間の類似度を表すに過ぎなかったが，提案手法はエッジ情報に着目し，全体の交通量の保存などの制約を入れることでエッジ情報を扱えるようにし，かつSSLという問題設定に取り組んだ
- Appendixには，Julia での実装コードがある
イベント予測
Deep Mixture Point Processes: Spatio-temporal Event Prediction with Rich Contextual Information
(NTT サービス，コミュニケーション)
- イベント（タクシーのpick-upなど）が発生する確率を，天気や地理情報，交通規制・社会イベントのスケジュールなどの要素から予測する
- 地理情報はマップ＝画像で，交通規制・社会イベントのスケジュールはテキストで与えられる
- それらを組み込むために深層学習と混合モデルをベースとした点過程モデルDMPP (Deep Mixture Point Processes) を提案．深層学習(CNN+Attention)で画像・テキストから特徴抽出し，それをもとに混合モデルを構築
- 従来手法より高い精度でシカゴ市の犯罪を予測している
Learning Dynamic Context Graphs for Predicting Social Events
- 時系列的なイベントの文書を動的なグラフで表現し，GCN (Graph Convolutional Network) で将来のイベントを予測する手法を提案
- ロジスティック回帰＋TF-IDFや時系列データを用いないGCNよりも，Dynamic GCNは精度良くイベント予測できることを示した
Short and Long-term Pattern Discovery Over Large-Scale Geo-Spatiotemporal Data
- 天気や交通のデータから短期的および長期的なパターンを発見する手法を提案
- 短期的なパターンとしては雨→事故→渋滞のような伝搬するものを，長期的なパターンとしては道路の建設→交通の変化のようなものを扱っており，ノードが事故，渋滞などのラベル，エッジがそれらの依存関係を表す木構造を構築し，頻出するものを短期的なパターンとして抽出．また時間，場所，タイプの観点から長期的なパターンを抽出．
- アメリカでの2年間のデータから90の短期的なパターンを発見し，また長期の混雑，雪，雨，霧などの発生が最も交通流に遅れの影響を与えることを発見した
信号制御
PressLight: Learning Max Pressure Control to Coordinate Traffic Signals in Arterial Network
- 強化学習による信号制御の研究が増えているが，報酬と状態の設計が経験的であり， 報酬の要素の重みによって結果が異なってくる，交差点での状態の複雑化が学習時間を増加させるという問題があった
- 交通分野では，Max Pressure (MP)という，各交差点の圧力（詰まり具合）を最小化することにより交通ネットワーク全体の流れを最大化する分散型交通信号制御戦略がSOTAとなっているが，最適化は貪欲法を用いている
- そこで強化学習の，報酬はMPと同じ設定にし，状態はMPで状態遷移の定式化に使われている発展方程式の変数を用いて定義することで，上記の問題を解決する信号制御の手法を提案
- 交通工学で使われていた手法や強化学習を適用した既存手法よりも移動時間を短縮する信号制御ができることを示した
Time Critic Policy Gradient Methods for Traffic Signal Control in Complex and Congested Scenarios
- 先行研究よりもより複雑な交差点の状況での信号制御を深層強化学習により行っている研究
- 信号制御の問題をエピソードベースの設定にし，方策勾配ベースのREINFORCEで方策を学習
- 交通シミュレーションSUMOで複雑な状況による信号制御をシミュレーションし，提案手法がトータルの待ち時間，排気量を減らし，交通渋滞を減らすことを示した
配車アルゴリズム
A Deep Value-network Based Approach for Multi-Driver Order Dispatching
(DiDi AL Labs 他)
- 複数のドライバーの長期的な報酬を最大化するような配車アルゴリズムを提案．セミマルコフ決定過程として配車問題を定式化
- cerebellar embedding でダウンタウン，郊外，コミュニティパークなど空間的な範囲に応じて階層的になっている位置情報を表現する（階層的な感じが小脳の構造と似ているから？）
- 価値関数の更新の際に最小化するLoss関数にリプシッツ定数を加えることで価値関数が大幅に変化するのを防ぎ，学習を安定させる
- 転移学習で他の都市でも使えることを示している
Two-Sided Fairness for Repeated Matchings in Two-Sided Markets: A Case Study of a Ride-Hailing Platform
- UberやLyft, Ola, DiDiなどのシェアリングエコノミーのエコシステムが成長するにつれて，より多くのドライバーが生活を確保するためにオンラインプラットフォームとそのアルゴリズムに財政的に依存することになるが，そのようなプラットフォームでの収入の分配はドライバー毎に差がある状態である
- そこでライドヘイリングプラットフォームにおけるマッチング機能の公平性を最適化するフレームワークを提案
- あるドライバーがあるユーザーとマッチするか否かを0-1変数で表し，ドライバー毎の収入の差，ユーザー毎の待ち時間の差を目的関数とする，整数最適化問題として定式化している（ソルバーはGurobi）
レコメンデーション
Hydra: A Personalized and Context-Aware Multi-Modal Transportation Recommendation System
(Baidu 他)
- 既存の経路検索システムではタクシー，バス，自転車などは別々に扱い，単一交通手段による経路が推薦され，またその時の状況は考慮されていなかった．しかし状況によってはタクシーでバス停まで行ってそこからバスに乗るというような経路が良い場合もあり，ユーザーを十分に満足させる経路推薦はできていなかった
- そこで複数の交通手段を組合せた経路を，POI (Point of Interest：商業施設などの重要地点)や天気，個人の嗜好を考慮し状況に応じて推薦するシステム「Hydra」を構築
- Baiduの経路検索サービスやBaidu search, Baidu Appの利用データから，交通手段の好みやODペア，ユーザーのprofileを抽出．graph embeddingを用いてユーザーの交通手段の好みを表現
- 抽出した特徴をもとに勾配ブースティング木(XGBoost)で多クラス分類し，複数経路（自家用車，タクシー，バス，自転車，徒歩，タクシー＆バス，バス＆自転車）のうちユーザーに合っているものを推薦している
- なおBaidu Mapでは実際にタクシー＆バス，バス＆自転車の経路も推薦され，Hydraは実サービスとして稼働している模様
Effective and Efficient Reuse of Past Travel Behavior for Route Recommendation
- 経路検索で推薦する経路は基本的に最短経路であるが，その経路だと移動しづらいために実際には使われていない場合がある．また同じような嗜好を持つユーザーは同じような経路，場所を好む傾向にある．
- そこでGoogle Map などの経路検索サービスやモバイルGPSで得られる使用経路のデータをもとに，よりユーザーにとって効率的で意味のある経路を推薦する手法を提案
- 使用経路データを分割し，目的地・POIをできるだけ経由する経路に合成する．全ての組合せを考えると計算量が膨大になるので，並列計算できるように工夫している
チュートリアル
Deep Reinforcement Learning with Applications in Transportation
(DiDi AI Labs)
- 交通課題に対して深層強化学習をどう使っているかのチュートリアル．（スライドはこちら．AAAI2019のものとほぼ同じ）
- DiDi AI Labs のJieping Ye らは，KDD2018やACML2018, IJCAI2019など国際会議でよくチュートリアルを行っており，KDD2019では他にも，Transportation: A Data Driven Approach というタイトルでInvited Talk を行っている
- DiDi は，ドライバーの乗客へのリアルタイムの割当や経路計画，信号制御などに対して深層強化学習を用いた研究を行っている
個人的感想
- DiDi, Baidu, Huawei, JDなど中国の企業，大学からの発表が多いです．JD DigitsのYu ZhengはMSRA時代からずっと都市交通に関わる研究をしていますし，DiDi AI LabsのJieping YeなどとともにUrbCompというワークショップをKDDで開催しています．CV系と同様に中国勢が強い印象で，この状況は数年変わらないのかなと思います．
- 内容としてはKDDですのでデータマイニングの要素が強い，交通量予測の研究が多かったです．逆に信号制御や配車アルゴリズムなどの強化学習や最適化手法を用いた研究は比較的少なかったです．
- 地図をグリッド分割しデータを画像として扱いディープのSOTAの手法で予測する，道路ネットワークをグラフとして扱いGCNで予測する，といった流れが多いように感じました．その中でもmeta learningを適用したり，複数交通手段を扱ったり，新しい流れもできつつあるように感じました．
