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
Neural combinatorial optimization with reinforc...
Search
Tsuboya Akane
February 17, 2025
Research
0
33
Neural combinatorial optimization with reinforcement learning 紹介
ICLR2017年で発表された"Neural combinatorial optimization with reinforcement learning"という論文の紹介です
Tsuboya Akane
February 17, 2025
Tweet
Share
More Decks by Tsuboya Akane
See All by Tsuboya Akane
BibTeX を Overleaf で活用しよう
p_suke
0
71
Curiosity-driven Exploration by self-supervised Predictionを読んでみた
p_suke
0
41
論文の読み方講座-研究室に配属された学部生へ-
p_suke
0
91
Other Decks in Research
See All in Research
SSII2025 [TS1] 光学・物理原理に基づく深層画像生成
ssii
PRO
3
2.2k
VAGeo: View-specific Attention for Cross-View Object Geo-Localization
satai
3
280
ノンパラメトリック分布表現を用いた位置尤度場周辺化によるRTK-GNSSの整数アンビギュイティ推定
aoki_nosse
0
300
2025年度人工知能学会全国大会チュートリアル講演「深層基盤モデルの数理」
taiji_suzuki
6
3.6k
Vision Language Modelと完全自動運転AIの最新動向
tsubasashi
2
570
EarthMarker: A Visual Prompting Multimodal Large Language Model for Remote Sensing
satai
3
250
Mathematics in the Age of AI and the 4 Generation University
hachama
0
150
Scale-Aware Recognition in Satellite images Under Resource Constraints
satai
3
250
ストレス計測方法の確立に向けたマルチモーダルデータの活用
yurikomium
0
150
NLP2025 WS Shared Task 文法誤り訂正部門 ehiMetrick
sugiyamaseiji
0
170
Dynamic World, Near real-time global 10 m land use land cover mapping
satai
3
270
SI-D案内資料_京都文教大学
ryojitakeuchi1116
0
1.4k
Featured
See All Featured
Mobile First: as difficult as doing things right
swwweet
223
9.6k
Fontdeck: Realign not Redesign
paulrobertlloyd
84
5.5k
Done Done
chrislema
184
16k
The Cost Of JavaScript in 2023
addyosmani
49
7.9k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
34
2.3k
No one is an island. Learnings from fostering a developers community.
thoeni
21
3.3k
Build your cross-platform service in a week with App Engine
jlugia
231
18k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
45
7.3k
Rails Girls Zürich Keynote
gr2m
94
13k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
3.8k
Balancing Empowerment & Direction
lara
0
70
Transcript
Neural combinatorial optimization with reinforcement learning 東京電機大学 先端科学技術研究科情報学専攻 坪谷朱音
基本情報 タイトル:Neural combinatorial optimization with reinforcement learning 著者:Irwan Bello, Hieu
Pham, Quoc V. Le, Mohammad Norouzi, Samy Bengio 発表:ICLR 2017 https://openreview.net/forum?id=Bk9mxlSFx (2/24)
概要 • 強化学習(RL) + ニューラルネットワーク(NN)を組合せ最適化問題に適用する ための枠組みを提案 ◦ 最適解を保持してなくても学習可能な強化学習 ◦ 機械翻訳など系列の学習能力が向上している
NN 結果: • 巡回セールスマン問題では、最大 100 ノードまでの 2 次元ユークリッド空間で 最適に近い成績を達成 • ナップサック問題では、最大 200 アイテムが与えられる設定で最適解を獲得 (3/24)
背景:巡回セールスマン問題(TSP) 設定:n 個の都市が与えられた時、各都市を必ず 1 回ずつ訪問する 目的:総移動コスト(e.g. ツアーの長さ)が最小となる巡回路の発見 1 2 3
4 例:n = 4 (4/24) 制約: • 全ノード訪問 • 訪問は一度 • 巡回路は 1 つ
背景:巡回セールスマン問題(TSP) 設定:n 個の都市が与えられた時、各都市を必ず 1 回ずつ訪問する 目的:総移動コスト(e.g. ツアーの長さ)が最小となる巡回路の発見 1 2 3
4 例:n = 4 解法 • TSPソルバー ◦ 厳密解 ◦ ヒューリスティクス • 機械学習 (5/24) 制約: • 全ノード訪問 • 訪問は一度 • 巡回路は 1 つ
背景:TSP における機械学習手法 機械学習を用いることで、学習データに基づく適切なヒューリスティクスを自律的に発見 できることが期待される 1. 教師あり学習 教師ラベル (正解ラベル ) から学習
△ 最適なツアーがないといけない 2. 強化学習 報酬のフィードバックから学習 ◎ 実際のツアー長で代用可能 (6/24)
本論文の目的 組合せ最適化で使用できる Deep RL 手法 → Actor-critic (RL) と pointer
network + Attention (DNN) ベンチマーク・教師あり学習手法・提案手法を用いて性能を比較 → TSP・ナップサック問題 提案 検証 (7/24)
下準備:2次元ユークリッド空間における TSP • グラフ s が与えられた時に順列 π を選択した時のツアー長 L s
= {x i }n i=1 • グラフ s が与えられた時に順列 π を選択する確率 x π (1) x π (2) x π (3) x π (4) 例:n = 4 p(π(1) | s) ニューラルネット (NN) の目的: 最短ツアーを選択する確率 p θ (π* | s) が高くなるような パラメータを学習 (8/24)
提案手法の推論機構: pointer network + Attention LSTM Encoder Decoder Attention 1都市ずつ入力
enc i dec i 1 つ前に選択した都市を入力 x 1 x 2 x 3 x 4 x 5 start p(π|s)を生成 引用:ゼロから作る Deep Learning 2 (9/24)
強化学習 (RL) の目的 目的:期待ツアー長を最小化するツアー π のパラメータ θ を学習したい 期待ツアー長 (目的関数)
目的関数の勾配 (θで偏微分) 上式にベースライン ※を追加 REINFORCE ※ ベースラインは分散を減らす役割を持つ B 個のグラフに対して それぞれ 1 つのツアーをサンプリング (モンテカルロ法) (10/24)
提案手法の学習機構: 強化学習手法 Actor-critic ツアー生成確率 p のパラメータ θ を学習 ベースライン b
のパラメータ θ v を学習 ツアー長の予測値 - 観測値 b θv (s i ) 全結合 (活性化関数はReLU) s i critic の NN 引用:Reinforcement Learning, second edition: An Introduction (11/24)
入力 s に対してある 1 つのツアー π を選択 → 複数のツアー候補を考え、その中から 1
つのツアーを選択 提案手法の推論時の探索機構: Sampling と Active Search p θ (・|s) に従って複数のツアー 候補をサンプリングし、 その中でも最短のツアーを 選択する ※ サンプリングは温度付きsoftmaxですることでラン ダム性をもたす 1. p θ (・|s) に従って複数のツアー候 補をサンプリングし、その中でも最 短のツアー長を L j とする 2. 過去サンプリングした中で最短のツ アー長 L より L j が短ければ、L j と ツアー π を用いて θ を更新 ※ b は シンプルな移動指数平均 Sampling Active Search (12/24)
提案手法のアーキテクチャまとめ ベースライン b のパラメータ θ v を学習 b θv (s
i ) 全結合 (活性化関数はReLU) s i critic の NN ツアー生成確率 p のパラメータ θ を学習 Attention p θ (π|s)を生成 actor の NN π を複数生成し、その中でも最短 のツアーを選択 θ 更新なし:Samling θ 更新あり:Active Search (13/24)
実験1:3 種類のノード数の TSP タスク: TSP20, 50, 100 の 3 つ
(ノードは単位正方形 [0,1]2 の中で一様ランダム) 評価方法: |S| = 1000のテストセットにおけるツアー長の平均 細かいハイパラ設定は論文参照 (14/24)
実験1:比較手法 • 教師ありの pointer network (1,000,000データで学習済) • RL-事前学習 (10,000で学習済) ◦
都市の選択は greedy。事前学習済モデルを 1, 16 個使用した場合の 2 種類 ◦ RL-事前学習-Sampling ◦ RL-事前学習-Active Search • Active Search (各データに対して100,000・200,000 step 学習) • ベースライン ◦ Christofides ◦ OR-Tools の車両経路ソルバー ◦ Optimal (Concorde と LK-Hの局所探索) (15/24)
結果:ツアー長の平均 • RL-事前学習が Christo-fides より良い成績 • RL-事前学習は教師あり学習手法 を大幅に改善 (16/24)
結果:実行時間の比較 (17/24) • RL-事前学習(モデル数16) でも OR-Tools より数%悪いぐらいで済む
結果:性能と時間のトレードオフ • ツアー候補数を増やすと実行時間は増加する ◦ しかしツアー候補数に限らず良い成績を安定的 に出せる ツアー候補の数 (18/24)
結果:最適なツアー長に対する割合 • 推論時に探索を行う RL-事前学習手法は最適に近いツアーを安定的に発見 • TSP50:Sampling は並列可能な面で効率が良く、成績も最も良い • TSP100:Active Search
は成績と実行時間のトレードオフが取れている※表4 良 1000 個のテストデータの 成績が昇順 良 悪 (19/24)
実験2:0-1ナップサック問題 設定:それぞれ重さ w i の n 個のアイテムを、容量 W のナップサックに詰める 目的:ナップサックに入っているアイテムの価値
v i の和の最大化 (20/24)
実験2:実験設定 タスク:KNA50, KNA100, KNA200 の 3 つ • アイテムの重荷と価値は [0,1]
で一様乱数で決定 • それぞれナップサックの容量は 12.5, 25, 25 評価方法: • |S| = 1000のテストセットにおける、ナップサックに入ったアイテムの総重量の平 均 比較手法: • RL-事前 greedy※次ページにて補足・Active Search • ベースラインとして greedy (重み対価値比)・ランダム・Optimal (21/24)
実験2:pointer network の適用 Attention 1. アイテムの重みと価値を 1 つずつ入力 (w i
, v i ) 2.入れるアイテムを指す 対象:RL-事前学習 greedy 3.アイテムの総重量が ナップサックの容量 W を超えたら終了 (22/24)
結果:ナップサック内アイテムの総重量の平均 • RL-事前学習 greedy は最適より数 % 少ない解を獲得 • Active Search
は Optimal と一致 (23/24)
まとめ Actor-critic (RL) と pointer network+Attention (DNN) の手法 TSP:最大 100
ノードの TSP で最適に近い成績 KNA:最大 200 アイテムの KNA で最適解 推論時に探索する Active Search と RL-事前学習の組み合わせが有効 提案 結果 (24/24)
おまけ:Seq2Seqベースの解法の問題点 先行研究 (Sutskever et al. 2014) に倣い、機械翻訳でよく使われる Seq2Seq ベースで解法を考える 入力:都市の座標の集合
s 出力:ツアー π 問題点: 1. n 都市 TSP で学習したモデルを n+1 都市 TSP へ一般化できない 2. NN のパラメータは条件付き対数尤 度で学習するため、教師信号が必要 引用:https://openreview.net/forum?id=Bk9mxlSFx (25/26)
おまけ:Seq2Seqベースの解法の改善 先行研究 (Sutskever et al. 2014) に倣い、機械翻訳でよく使われる Seq2Seq ベースで解放を考える 入力:都市の座標の集合
s 出力:ツアー π 問題点: 1. n 都市 TSP で学習したモデルを n+1 都市 TSP へ一般化できない 2. NN のパラメータは条件付き対数尤 度で学習するため、教師信号が必要 引用:https://openreview.net/forum?id=Bk9mxlSFx 提案手法: 1. 入力 (都市) の順列生成が得意な pointer network で p(π|s) を 学習 2. 教師信号を必要としない機械学習 手法である強化学習 (RL) (26/26)