Share
Embed
KDD2020 論文紹介
社内の輪講で発表したスライドです。
・ HetETA: Heterogeneous Information Network Embedding for Estimating Time of Arrival
・ CompactETA: A Fast Inference System for Travel Time Prediction
・ ConSTGAT: Contextual Spatial-Temporal Graph Attention Network for Travel Time Estimation at Baidu Maps
・ Personalized Prefix Embedding for POI Auto-Completion in the Search Engine of Baidu Maps
satorin1204
November 20, 2020
Transcript
58 slides
-
confidential Mobility Technologies Co., Ltd. • 名前 ◦ 佐藤 倫(@rincha_sr)
• 経歴 ◦ 東京工業大学院 卒業 ◦ 2020/04 DeNA 入社、その後MoT に出向中 • Kaggle ◦ Master( ) 自己紹介 2 -
confidential Mobility Technologies Co., Ltd. • 8/23-27 に開催(日本時間の0:00 から) •
全てリモートでの開催 • Zoom で録画済みの講演が流され質疑 • 時間外でもChat により質問ができる KDD2020 4 -
confidential Mobility Technologies Co., Ltd. • 1,353 件のSubmission (過去最高) •
217 件のAcceptance(採択率17%) Research Track 5 -
confidential Mobility Technologies Co., Ltd. • Graph Mining やRepresentation Learning、Recommender
system などが並ぶ Research Track 6 -
confidential Mobility Technologies Co., Ltd. • 到着時間を予測する問題 • 始点、終点、(通った経路)から到着時間を予測する ◦
経路は細かくセグメントという単位に分割できる • 高精度なETA はユーザーの利益になるだけでなくVRPや乗り合いなど様々な問題に 寄与する重要な要素である ETA とは 10 -
confidential Mobility Technologies Co., Ltd. HetETA: Heterogeneous Information Network Embedding
for Estimating Time of Arrival 11 HetETA | Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining -
confidential Mobility Technologies Co., Ltd. • 既存のETA手法はHeterogeneous network を考慮したものはほぼなかった •
Heterogeneous network を用いるHetETAを提案 • Heterogeneous な情報(時空間での異質)を時空間畳み込みで学習 Summray 12 -
confidential Mobility Technologies Co., Ltd. • 時間方向での3種類 ◦ 直近・日単位・週単位の交通状況 •
空間方向の2種類 ◦ 普通の道路ネットワーク ◦ 乗務員軌跡からよく通るパスの間にエッジを張ったネットワーク Heterogeneous Network の概要 13 -
confidential Mobility Technologies Co., Ltd. ある時刻t に関して道路ネットワークG を以下のように定義する
グラフの定義 14 • V: 道路セグメントのノード • E: セグメント間のエッジ • R: エッジの関係性(右折など) • X: 道路セグメントの特徴量 ◦ 静的特徴(長さ・幅など) ◦ 動的特徴(その時刻の交通状況) エッジの関係性 -
confidential Mobility Technologies Co., Ltd. • 3つの時間配列を用いる(LR・LD・LW、それぞれ直近・日・週) • 以下のようにそれぞれのtime period
ごとの特徴を用いる ◦ time period は5分 時間方向 15 -
confidential Mobility Technologies Co., Ltd. • Gate を設けた畳み込みで時間方向のダイナミクスを得る ◦ sigmoid
かけてそれの要素積をとる Gated CNN 16 -
confidential Mobility Technologies Co., Ltd. • 乗務員はより良い道路を知っている可能性がある • 乗務員軌跡によるネットワークを構築する
• あるノードから β hop 以内で頻度top k の間にエッジを結ぶ ◦ 今回は β = 3, k = 5 ◦ 関係性は “likely going to” 空間方向 17 -
confidential Mobility Technologies Co., Ltd. • 疎な道路ネットワークから高速に周辺からの特徴を得る • ChebNet が考えられる
• しかしChebNet は多関係には使えない ◦ 関係性から得られるattention を使う ◦ また無向グラフであるために、反対エッジを追加し関係性にもそれを付与 ▪ turn-left -> out-going when turn-left Het-ChebNet 18 -
confidential Mobility Technologies Co., Ltd. • 最後のCNN を経た出力から各セグメントごとのETAを以下の式で求める ◦ sigmoid
をかけて最高速度(120km/h) で道路距離S を割ることで出す 出力 19 -
confidential Mobility Technologies Co., Ltd. • 出発・到着地点、時刻、軌跡のパスを入力
• 軌跡上のセグメント毎に予測されるETAとのMAPEで学習する 学習方法 20 -
confidential Mobility Technologies Co., Ltd. • 比較手法 ◦ GRU: 道路ネットワークが使わない、パスをGRU
に入れる ◦ DCRNN, STGCN: 時空間を扱うモデル、多関係が扱えない ◦ GWN, ASTGCN: 大きなグラフを扱うことが困難なため変更を加えたもの • それぞれ5-30 分後のスピードを予測 交通状況予測の比較結果 21 -
confidential Mobility Technologies Co., Ltd. • HetETA がETAにとって良い特徴が抽出できていることを確かめる ◦ SoTA
であるWDR[1] の動的道路特徴にHetETA から抽出されるものを用いる • HetETA を用いることで大きく精度が向上した ETAとしての性能 23 [1]: Wang, Z. et al. Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min. 858–866 (2018) -
confidential Mobility Technologies Co., Ltd. CompactETA: A Fast Inference System
for Travel Time Prediction 24 CompactETA | Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining -
confidential Mobility Technologies Co., Ltd. • ETA(到着時間予測)は1日数10億クエリ叩かれる、高速化が必要 • 時空間を捉えたGNNやPosition embedding
によりMLPのみで推論可能 • 精度を保ちながら100倍以上の高速化を実現 Summary 25 -
confidential Mobility Technologies Co., Ltd. • Wide-Deep-Recurrent Learning[1](SoTA) ◦ リコメンドで用いられるWide
& Deep Learning[2] にReccurent を足したモデル • X は経路の特徴、g は天気などの全体的な特徴を表す • Recurrent に入力される経路シーケンスは数100を超える ◦ 推論速度の低下につながる Baseline (WDR) 26 [1]: Wang, Z. et al. Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min. 858–866 (2018) [2]: Karatzoglou, A. et al. RecSys 2017 - Proc. 11th ACM Conf. Recomm. Syst. 396–397 (2017) -
confidential Mobility Technologies Co., Ltd. • RNNは時間がかかるからなくしたい ◦ positional encoding
により経路の特徴を得る • リアルタイムな交通状況はある程度の時間は変わらない(今回は120 sec.) ◦ 一定間隔で道路の埋め込みを更新、予測時は経路の埋め込みを取得 Proposed method 27 -
confidential Mobility Technologies Co., Ltd. • Graph Attention Network で各セグメント毎の埋め込みを出力する
• 経路上のセグメントの埋め込みを取得してそれとg(全体的な特徴)を用いてETAを学 習する 学習 28 Graph Attention Block -
confidential Mobility Technologies Co., Ltd. • 経路の時系列は重要だがRNNを避けたい • 正弦波をを用いたpositional encodingにより系列特徴を得る
• 各segment の埋め込みにかけて和を取る Positional Encoding 29 -
confidential Mobility Technologies Co., Ltd. • 比較手法 ◦ WDR: ベースライン
◦ RouteETA: 道路ごとのリアルタイム通行速度の平均値の合計 ◦ MLP-ETA: Position Encoding、GCN ありなし • CompactETA は遜色ない精度を達成 ◦ GA, PEともに貢献している Result(オフライン) 30 -
confidential Mobility Technologies Co., Ltd. • CompactETA による影響を14日間A/B テストする ◦
control : WDR (既存手法) • 3時間ごとにcontrol とtreatment を交換する • また天気等のランダム性の影響の大きさをみるために14日間A/A テスト ◦ どちらもControl • 多くの指標でA/A と大差がなかった • 一方で特にpickup badcase では大きく改善 ◦ 幅の広い予測(1sec. ~ 1000sec. )では LSTMと違い加算するから良くなっている A/B test 31 -
confidential Mobility Technologies Co., Ltd. • QPS とLatency で評価 •
1リクエストに60クエリとして異なる同時実行リクエスト数で評価する • どちらの指標でもCompactETA は100倍性能が良い 速度評価 32 x 軸は同時実行されるリクエスト数 -
confidential Mobility Technologies Co., Ltd. ConSTGAT: Contextual Spatial-Temporal Graph Attention
Network for Travel Time Estimation at Baidu Maps 33 ConSTGAT | Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining -
confidential Mobility Technologies Co., Ltd. • 既存手法には2つの問題点がある ◦ 時空間を分離してネットワークが扱っている ◦
時系列モデルの推論が遅い • 道路セグメント毎の予測を事前に計算し、その和によって推論することで高速に行う フレームワークを提案 ◦ 経路の文脈をwindowing によって取得 Summary 34 -
confidential Mobility Technologies Co., Ltd. • 3つのモジュールからなる ◦ Contextual Information
▪ 軌跡の系列情報 ◦ Traffic Prediction ▪ 時空間グラフのためのattention 機構を含んだモデル ◦ Integration ▪ 各segment と全体の マルチタスク学習 Framework 35 -
confidential Mobility Technologies Co., Ltd. • 軌跡上にまたがったwindow size で切り取ったものを結合する (window
size = 1) Contextual information module 36 -
confidential Mobility Technologies Co., Ltd. • 過去の情報から未来の交通状況を予測する ◦ time slot
(5 分ごとの速度の統計量) • 過去のTh 個のtime slot のグラフC から未来のTf 個のtime slot を予測する ◦ 提案手法ではTh=12, Tf=12 • 交通状況は欠損することがある ◦ 学習時に10% マスクすることでモデルを堅牢にするように学習した Traffic Prediction module 37 -
confidential Mobility Technologies Co., Ltd. • ST-tensor は下図のように近接ノードと時間方向の特徴を3D-tensor にしたもの (3DGATとよぶ)
ST-tensor (Spatial-Temporal tensor) 38 -
confidential Mobility Technologies Co., Ltd. • ST-tensor とcontextual information、background information
のアテンションにより特徴 を捉える ◦ background information: 時刻などの特徴 ◦ Concat したものをQuery としたアテンションを用いる Traffic Prediction module 39 -
confidential Mobility Technologies Co., Ltd. • segment 毎の出力は • route
全体の出力はその総和 • segment にはhuber-loss、route にはAPE を用いる Integration module 40 -
confidential Mobility Technologies Co., Ltd. • 毎日数百億のリクエストを高速に処理したい • 事前にsegment 毎のETAを計算してlookup
table を作成する ◦ ありえる全てのsub-path を用いる ◦ また候補となる出発時刻全てに対しても行う • リクエストが来た際にtable を参照してその総和を返す Inference 41 -
confidential Mobility Technologies Co., Ltd. • あるセグメントについて a. attention weight
b. segment のレコード数 c. segment の通過時間中央値 • カウント数が多いところの 重みが大きい Attention weight と統計値の関係 44 -
confidential Mobility Technologies Co., Ltd. • Window size は0 よりは良くなる(周辺情報の重要性)
◦ 最適なのはデータセット依存 • 交通状況の欠損考慮によるマスクをすることでロバストになった 他のdiscussion 45 -
confidential Mobility Technologies Co., Ltd. Personalized Prefix Embedding for POI
Auto-Completion in the Search Engine of Baidu Maps 47 Personalized Prefix Embedding for POI Auto-Completion in the Search Engine of Baidu Maps | Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining -
confidential Mobility Technologies Co., Ltd. • ユーザーの入力文字(Prefix)を用いたPOI Auto-complete (POI-AC) の開発
• Prefix やPOI情報の特徴を工夫し、Tripletloss で埋め込みを学習 • 既存のフレームワークに特徴量として追加し精度向上 Summary 48 -
confidential Mobility Technologies Co., Ltd. • 2段階構成になっている ◦ PrefixとPOI 情報から数100件に候補を絞る
◦ POI情報やユーザー特徴からGBRank でランクを予測する 既存のBaidu Map のPOI-AC 49 -
confidential Mobility Technologies Co., Ltd. • ユーザーの入力するprefix p = (c1,c2,…cn)
• prefix にユーザー特徴ベクトルを結合してBi-LSTM に入力 • 双方向から得られた各characters のembedding をattention を加えて和を取る Personalized prefix embedding 50 -
confidential Mobility Technologies Co., Ltd. • 以下の3要素のembedding の和を用いる ◦ POI
の名前と住所をCNN でembed を得る ◦ POI のカテゴリから得られるembed ◦ POI のGeoHash で得られるembed Enriched POI Embedding 51 -
confidential Mobility Technologies Co., Ltd. • 得られたembedding をtriplet loss で学習する
◦ prefix embed がクリックされたPOI embed と近くなるように ◦ prefix embed がクリックされなかったPOI embed と遠くなるように ◦ 距離はcosine 類似度を用いる • Loss にはhinge loss を用いる Triplet ranking loss 52 -
confidential Mobility Technologies Co., Ltd. • ver1.0 ◦ ユーザーの人口統計情報・POI人気の統計情報など(GBRank) •
ver1.1 ◦ 時間・地域を考慮した特徴を追加(GBRank) • ver2.0 ◦ ユーザーのPOIの履歴特徴を追加(GBRank) ◦ POI の特徴はword2vec like に得る • ver2.1 ◦ POI のGeohash などの特徴を追加(GBRank) • ver3.0 ◦ 提案手法(cosine類似度) • ver3.1 ◦ ver3.0 のcosine類似度をver2.1 に追加(GBRank) 比較モデル (POI-AC verx.x) 53 -
confidential Mobility Technologies Co., Ltd. • レコメンド等の指標を用いる ◦ SR@n :
top nに正解POIがあるかどうか ◦ MRR: 適合POIの順位の逆数 ◦ nDCG@N: topN のnDCG ◦ AVG. #(KS): ユーザーの平均打鍵数 ◦ AVG. Sp.@KS: ユーザーの平均打鍵速度(かかった時間を表している) 評価指標 54 -
confidential Mobility Technologies Co., Ltd. • Baidu Map では新しいモデルのリリース前にA/Bテストをしている ◦
最低1週間、ランダムに5% のtraffic に適用 • KS の指標はユーザー体験の向上を表している ◦ Offline に比べSR の指標が悪いのはユーザーがPOI-AC を無視することを表す Online 実験結果 56 -
confidential Mobility Technologies Co., Ltd. • 提案手法で得られた埋め込みの重要性を評価する • 得られた埋め込みを追加したGBRank (ver3.1)
の特徴量重要度を見る ◦ f 2(緑)が重要度2番目に来ている 考察 57