組み合わせ最適化問題に対する深層強化学習アプローチについて発表したが置き場が定まらないので、自分用に一旦内容こちらに置いておく。
目次
概要
組み合わせ最適化問題に対する深層強化学習アプローチ（要するに組み合わせ最適化問題もディープラーニングでなんとかしたい、という話）
話の元論文
組み合わせ最適化問題に対する深層強化学習アプローチの紹介と、組み合わせ最適化問題(今回は巡回セールスマン問題)の実装 結果
Abstract
様々な組み合わせ最適化問題は、実務上ではそれぞれ個別に線形緩和を施しヒューリスティクスに解くのが一般である。 しかし、ヒューリスティクスな解法で計算コストは削減されるものの、ドメイン知識を使った問題の定式化やソルバーの実装コス トがかかり、汎用化は難しい。 強化学習・RNNを利用したアプローチでは、このような問題を解決できる上に、設定次第で理論的にはより正確な解を得ることが できる。
目標
- 手法と実装結果の紹介
- 注目されている関連手法のざっくり紹介
手法
巡回セールスマン問題（traveling salesman problem, TSP）
二次元ユークリッド平面上のグラフ上でのTSPを、RNNを用いた強化学習で解ける形にする。
1. 総移動距離Lを次で定義
- グラフ(n個のノードからなる集合{x})が与えられたときに、総移動距離Lは{x}の置換πを用いて(1)のように表せる。
- 総移動距離Lが最小になるような置換π(訪れる順番)を探す
2. グラフsがあったときに、置換πが選ばれる確率p(学習対象)をチェーンルールで定義
- π(1),π(2), … π(i-1)を経由して i-1番目の地点にいるとき、置換π(i)に遷移する確率p(π(i)|π(<i),s)を連鎖することで全体の確率p を定義する
- 行動確率p(π|s)のパラメータを方策勾配法で学習させる(後述)
ニューラルネットワークのアーキテクチャ
attention(ポインタ)を付加情報として付け加えたseq2seq(Pointer network)をモデルとして使う
自然言語モデルの表(時系列は上から下)
*1: デコーダの各点において、隠れ状態ベクトルとエンコーダの各点の隠れ状態ベクトルの内積をとり、集約して一つのベクトル(コンテキストベク トル)を作り渡している
*2: 厳密には、attention(=multi-head self-attention)とfeedforwardを使っている
概要理解
attention を用いたseq2seq
- seq2seqのデコーダの各点において、「関連の強い入力単語が色濃く反映されたコンテキストベクトル」の情報も一緒に渡してあげる
- そうすることで、遠い系列の情報も組み込めるようにする
- こちらのまとめがわかりやすいです
数式理解
- seq2seq
*出力の数がO(n)として、計算量はO(n)
- attention mechanism
*出力の数がO(n)として、計算量はO(n^2) -
pointer networks
入力系列上のインデックスに対応した要素から成る出力系列の条件付き確率分布を学習する。
*出力の数がO(n)として、計算量はO(n^2)
Pointer network の利点
seq2seqやattention mechanismでは確率モデルは入力長に依存しており、入力長が大きくなるほど精度が落ちてしまったが、 pointer networkではデコーダの各点で入力参照すべき入力要素のポインタを受け取るため、入力サイズに依存せず出力精度を保つ ことができる。
実装(方策勾配法)
教師データの用意にはコストがかかるため、方策勾配法(強化学習の典型アプローチ)を使って教師なしでpointer network のパラメトリック確率 モデルp(θ)を最適化する。
方策勾配法
- b(s)は baseline function(価値関数)と呼ばれる方策勾配法に用いられる入力sの関数で、ここではLの期待値のようなもの(期待報酬)。
- b(s)の最小化も同時に行う必要がある。
コード
[1] より引用
l1: 解きたい問題のセットS、学習ステップT、バッチサイズBを宣言
l2: 確率モデルp(θ)(方策関数)のパラメータを初期化
l3: basic function b_{θ_v} (価値関数)のパラメータ初期化
l5: バッチサイズBに合わせてSからモンテカルロサンプリングによって集合{s_i}を取り出す l6: {s_i}から{π_i}を計算
l7: {s_i}から{b_i}を計算
l8: 目的関数の勾配 g_θ を計算
l9: b(s)を最適化するための第二の目的関数 L_vを計算 l10: g_θ と L_v からパラメータθ、θ_vを更新
- B=128
- 128×10000 = 1,280,000パターンのデータを学習
-
Search strategy: 各ステップにおいて、部分グラフ {s_1, s_2, …, s_B} ~ S における最適解の探索を取り入れパラメータをrefineすることで、推論の精度をあげている
計算結果
- 100地点での学習結果は、従来の解法と同じくらいの精度で解ける
- モデルができれば推論時間は高速(“We find that both greedy approaches are time-efficient and just a few percents worse than optimality.” とあるが、モデル構築にかかる時間はどう評価できるのか?)
議論
関連した取り組み
- Transformer(RNNやCNNを使わずattentionのみを用いたモデル) をベースにしたモデルを、教師ありで学習させ、ルーティング問題を 解く
- 結果:学習させた(個別でなく一つの)モデルで、VRP、OP、TSPなど様々なルーティング 問題をそこそこの精度でそこそこの時 間で解けた
- 論文:W. Kool, et al., Attention, learning so solve routing problems!, arxiv 1803.08475 (2018).
- Qiita:https://qiita.com/ohtaman/items/0c383da89516d03c3ac0
OPの機械学習アプローチの良い点と欠点
- 良い点
- 難しい定式化をせずとも自由に目的関数を設定できる
- 良い精度で問題が解ける
- 教師あり、教師なしどちらでもできる。教師ありなら問題ごとモデルを再構築しなくても様々な問題に適応できる。教師なしな ら、「質の良い学習用データセット」を用意するコストがかからない。
- 微妙な点
- 最適解である保証がない
- 細かい制約条件をどう組み込むのか?
参考文献
論文
[1] I. Bello, et al., Neural combinatorial optimization with reinforcement learning, conference paper at ICLR (2017).
[2] O. Vinyals, et al., Pointer Network, arxiv:1506.03134 (2015).
[3] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In ICLR, (2015).
[4] W. Kool, et al., Attention, learning so solve routing problems!, arxiv 1803.08475 (2018).
[5] Y. Peng, et al., Graph learning for combinatorial optimization: a survey of state of the art, Data science and engineering 6, 119-141
(2021).
記事