Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
論文読み会 AISTATS2024 | Deep Learning-Based Alterna...
Search
cocomoff
September 02, 2024
Research
0
33
論文読み会 AISTATS2024 | Deep Learning-Based Alternative Route Computation
論文読み会の資料です.
(A slide for the paper-reading activity at my company, written in Japanese.)
cocomoff
September 02, 2024
Tweet
Share
More Decks by cocomoff
See All by cocomoff
論文読み会 NeurIPS2024 | UrbanKGent: A Unified Large Language Model Agent Framework for Urban Knowledge Graph Construction
cocomoff
1
13
論文読み会 AMAI | Personalized choice prediction with less user information
cocomoff
0
33
論文読み会 KDD2024 | Relevance meets Diversity: A User-Centric Framework for Knowledge Exploration through Recommendations
cocomoff
0
180
論文読み会 KDD2022 | Multi-Behavior Hypergraph-Enhanced Transformer for Sequential Recommendation
cocomoff
0
86
論文読み会 AAAI2021 | Knowledge-Enhanced Top-K Recommendation in Poincaré Ball
cocomoff
0
63
論文読み会 WWW2022 | Learning Probabilistic Box Embeddings for Effective and Efficient Ranking
cocomoff
0
270
ClimaX: A foundation model for weather and climate
cocomoff
0
540
論文読み会 AAAI2022 | MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers
cocomoff
0
190
論文読み会 EMNLP2021 | Decision-Focused Summarization
cocomoff
0
190
Other Decks in Research
See All in Research
AIトップカンファレンスからみるData-Centric AIの研究動向 / Research Trends in Data-Centric AI: Insights from Top AI Conferences
tsurubee
3
2.1k
Bluesky Game Dev
trezy
0
180
言語モデルの内部機序:解析と解釈
eumesy
PRO
32
13k
言語モデルによるAI創薬の進展 / Advancements in AI-Driven Drug Discovery Using Language Models
tsurubee
1
260
リモートワークにおけるパッシブ疲労
matsumoto_r
PRO
6
5k
Building Height Estimation Using Shadow Length in Satellite Imagery
satai
3
240
地理空間情報と自然言語処理:「地球の歩き方旅行記データセット」の高付加価値化を通じて
hiroki13
1
220
Neural Fieldの紹介
nnchiba
2
810
Weekly AI Agents News! 11月号 プロダクト/ニュースのアーカイブ
masatoto
0
320
Introduction of NII S. Koyama's Lab (AY2025)
skoyamalab
0
160
メタヒューリスティクスに基づく汎用線形整数計画ソルバーの開発
snowberryfield
3
820
Weekly AI Agents News! 12月号 論文のアーカイブ
masatoto
0
250
Featured
See All Featured
[RailsConf 2023] Rails as a piece of cake
palkan
53
5.4k
Code Review Best Practice
trishagee
67
18k
Statistics for Hackers
jakevdp
798
220k
Automating Front-end Workflow
addyosmani
1369
200k
RailsConf 2023
tenderlove
29
1k
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
40
2k
Why Our Code Smells
bkeepers
PRO
336
57k
How to Ace a Technical Interview
jacobian
276
23k
Building Applications with DynamoDB
mza
94
6.3k
Faster Mobile Websites
deanohume
306
31k
StorybookのUI Testing Handbookを読んだ
zakiyama
28
5.6k
Making the Leap to Tech Lead
cromwellryan
133
9.2k
Transcript
Deep Learning-Based Alternative Route Computation (AISTATS'24) 読む人: @cocomoff Jun. 25,
2024
概要 Googleの方々@AISTATS'24 一行感想: なんでAISTATSなんだろう Googleのページでは「Algorithms and Theory」の分類だったが… 内容はタイトルの通り Deep Learning-Basedの部分に興味があって読んだ
背景: Alternative Routes タスク: 代替経路を求める 普通のアプローチ: 距離と多様性を考慮した最適化問題を解く 例: 最短経路の 倍で、類似度が
以下の経路を 本求める 図は arXiv:2006.08475 (TKDE2021?) より
背景: Deep Learning-based XXX 学習ベース手法の基本的なアプローチ グラフ を決める いろいろな出発・目的地 に対する経路 を用意する
何かしらのモデルを学習する encoder-decoderで頂点を出してもいいし、経路を直接出してもいいし、 他には探索のヒューリスティック関数値 を学習しても良い 高速なアルゴリズム (e.g., A*) が後段にあるとき、その手がかりをデ ータから学習しておくと、うまく使えそう 新しいクエリ に対する経路を出力する 図は arXiv:2105.01480 より
やったこと: 古典的なアルゴリズムの概念に再度着目する 階層的な経路探索アルゴリズム 今日は説明しない 実験のところで、数値だけ出てきます 右図のようにグラフを改装分割し、 その地域に入る/出る部分 (境界•) を管理して 最短経路を高速に計算する構造
代替経路の評価指標 UBS (Uniformly Bounded Stretch) Stretch: 距離と最短経路の比 (経路 が最短なら1、 は辺重み での最短距 離、 は に沿った距離) 経路 のすべての部分経路を見たときの間延び度合いの最大値 計算しまくるので、コストが高い
UBSを低く保つモチベーション: カスピー Googleマップのモチベ 高速道路を一度降りて、もう一度乗る → 防ぎたい 考察 UBSがすごく悪い 角になっている部分がすごく伸びている →
Stretchが大きい UBSを低く保つために経由すべき頂点を探す データから学習する → 一度学習しておけば、高速に使える アイデア 経路検索するとき、ノード がやばいUBSを生じるかどうか?を予測する 経路を構築するとき、やばそうなノードを通らないようにする
アルゴリズム [Input] が予測スコアが入っている [L3-5] 階層構造を使った経路探索 [L7] カスピーを発見的に取り除く [L11-18] 多様な経路を保存する [L16]
個作ったら終わり
学習モデル グラフと階層構造 (= 頂点の分割 と境界 ) 埋め込みベクトル [1] クエリ: スコア問い合わせるときの入力
クエリの埋め込みモジュール は階層構造が 層あり、 と があるので2倍 [2] 予測ヘッド: 学習するときは を使う を経由したとき、どれだけストレッチしたか (小さくしたい) 入力: クエリの埋め込み ( 次元) とvia-nodeの埋め込み ( 次元) 出力: スコア
実装など 実装 [1] 、BERT Encoder + 注意機構 [2] 隠れ次元128、出力次元2のMLPにsoftmax (良い・悪い)
良い = ストレッチが1.5倍以下ぐらい (だったと思う) 学習 1000万組の をランダムに計算して、双方向探索する 見つかったvia-nodeの候補地を学習例に、ストレッチを真面目に計算 50エポックで収束 階層分割 (今回触れていないところ):大都市規模で実験した
比較手法、計算時間など Plateau (プラトーヒューリスティック) からの最短経路木と からの最短経路木がぶつかるところを使う T-test heuristic [Abraham 2013] UBSが議論されていたころの論文の手法
Uniform Stretch Filter 真面目に全部計算する手法、高品質だが、計算が重い Model Prediction 提案手法
結果(1): 得られた経路 品質はだいぶ良くなっている
結果(2): 予測モデル これまでの手法と比較し、高精度で予測できている 他の手法は明確な予測モデルでもない気がするので、それはそう