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
12
論文読み会 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
ナレッジプロデューサーとしてのミドルマネージャー支援 - MIMIGURI「知識創造室」の事例の考察 -
chiemitaki
0
250
(NULLCON Goa 2025)Windows Keylogger Detection: Targeting Past and Present Keylogging Techniques
asuna_jp
1
310
PostgreSQLにおける分散トレーシングの現在 - 第50回PostgreSQLアンカンファレンス
seinoyu
0
290
o1 pro mode の調査レポート
smorce
0
150
Optimal and Diffusion Transports in Machine Learning
gpeyre
0
1.4k
Weekly AI Agents News! 11月号 論文のアーカイブ
masatoto
0
320
コーパスを丸呑みしたモデルから言語の何がわかるか
eumesy
PRO
11
3.3k
AIトップカンファレンスからみるData-Centric AIの研究動向 / Research Trends in Data-Centric AI: Insights from Top AI Conferences
tsurubee
3
2.1k
Weekly AI Agents News! 12月号 プロダクト/ニュースのアーカイブ
masatoto
0
360
ことばの意味を計算するしくみ
verypluming
10
2k
CARMUI-NET:自動運転車遠隔監視のためのバーチャル都市プラットフォームにおける通信品質変動機能の開発と評価 / UBI85
yumulab
0
110
情報処理学会関西支部2024年度定期講演会「自然言語処理と大規模言語モデルの基礎」
ksudoh
10
2.7k
Featured
See All Featured
StorybookのUI Testing Handbookを読んだ
zakiyama
28
5.6k
Building Your Own Lightsaber
phodgson
104
6.3k
The Language of Interfaces
destraynor
157
24k
GraphQLの誤解/rethinking-graphql
sonatard
70
10k
Stop Working from a Prison Cell
hatefulcrawdad
268
20k
Keith and Marios Guide to Fast Websites
keithpitt
411
22k
4 Signs Your Business is Dying
shpigford
183
22k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
129
19k
Rebuilding a faster, lazier Slack
samanthasiow
80
8.9k
Rails Girls Zürich Keynote
gr2m
94
13k
A Philosophy of Restraint
colly
203
16k
BBQ
matthewcrist
88
9.5k
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): 予測モデル これまでの手法と比較し、高精度で予測できている 他の手法は明確な予測モデルでもない気がするので、それはそう