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
8
論文読み会 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
論文読み会 KDD2024 | Relevance meets Diversity: A User-Centric Framework for Knowledge Exploration through Recommendations
cocomoff
0
9
論文読み会 KDD2022 | Multi-Behavior Hypergraph-Enhanced Transformer for Sequential Recommendation
cocomoff
0
10
論文読み会 AAAI2021 | Knowledge-Enhanced Top-K Recommendation in Poincaré Ball
cocomoff
0
46
論文読み会 WWW2022 | Learning Probabilistic Box Embeddings for Effective and Efficient Ranking
cocomoff
0
240
ClimaX: A foundation model for weather and climate
cocomoff
0
420
論文読み会 AAAI2022 | MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers
cocomoff
0
150
論文読み会 EMNLP2021 | Decision-Focused Summarization
cocomoff
0
160
論文読み会 AAAI2022 | Online Certification of Preference-based Fairness for Personalized Recommender Systems
cocomoff
0
400
論文読み会 HT2010 | Automatic Construction of Travel Itineraries Using Social Breadcrumbs
cocomoff
0
88
Other Decks in Research
See All in Research
Weekly AI Agents News! 6月号 論文のアーカイブ
masatoto
1
130
DiscordにおけるキャラクターIPを活用したUGCコンテンツ生成サービスの ラピッドプロトタイピング ~国際ハッカソンでの事例研究
o_ob
0
220
Minimum Bayes-Risk Decoding における性能変動の理解に向けて(2024年6月5日 第59回 NLPコロキウム)
atsumoto
0
310
SSII2024 [OS2] GPT-4Vで画像認識は終わるのか(オープニング)
ssii
PRO
0
750
SSII2024 [SS1] 拡散モデルの今 〜 2024年の研究動向 〜
ssii
PRO
2
2.1k
Как стать 10x экспертом
ikurochkin
1
110
日本語医療LLM評価ベンチマークの構築と性能分析
fta98
3
390
SSII2024 [PD] SSII、次の30年への期待
ssii
PRO
2
1.4k
出生抑制策と少子化
morimasao16
0
400
Language is primarily a tool for communication rather than thought
ryou0634
4
630
Isotropy, Clusters, and Classifiers
hpprc
3
500
"多様な推薦"はユーザーの目にどう映るか
kuri8ive
3
360
Featured
See All Featured
Raft: Consensus for Rubyists
vanstee
135
6.5k
Fontdeck: Realign not Redesign
paulrobertlloyd
80
5.1k
The Straight Up "How To Draw Better" Workshop
denniskardys
230
130k
[RailsConf 2023] Rails as a piece of cake
palkan
48
4.6k
Testing 201, or: Great Expectations
jmmastey
36
7k
Happy Clients
brianwarren
96
6.6k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
26
1.3k
Speed Design
sergeychernyshev
22
430
Visualization
eitanlees
142
15k
What's new in Ruby 2.0
geeforr
340
31k
It's Worth the Effort
3n
182
27k
The Invisible Side of Design
smashingmag
296
50k
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): 予測モデル これまでの手法と比較し、高精度で予測できている 他の手法は明確な予測モデルでもない気がするので、それはそう