[DL輪読会] Learning Finite State Representations of Recurrent Policy Networks (ICLR2019)

DEEP LEARNING JP [DL Papers] “Learning Finite State Representations of Recurrent Policy Networks (ICLR2019)” Kaito Suzuki, Tohoku Univ http://deeplearning.jp/ /23 1

• http://deeplearning.jp/

目次 • • • • • • • 書誌情報 概要 背景 提案手法 実験 まとめ 感想 2 /23

書誌情報 • タイトル： Learning Finite State Representations of Recurrent Policy Networks • 著者： Anurag Koul1, Alan Fern1, Sam Greydanus2 (Oregon State University1, Google Brain2) • ICLR2019 • リンク： ・OpenReview： https://openreview.net/forum?id=S1gOpsCctm ・ArXiv： https://arxiv.org/abs/1811.12530 ・著者実装 (ポスターへのリンクあり）： https://github.com/koulanurag/mmn 3 /23

• https://openreview.net/forum?id=S1gOpsCctm
• https://arxiv.org/abs/1811.12530
• https://github.com/koulanurag/mmn

概要 • 概要 - 強化学習において, 方策はRNNで実装されることがあるが, 方策を表す学習済みRNNの入力の観測と隠れ状態を離散化すること で 状態有限機械（Moore Machine) とみなし, 解釈性の向上を狙った論 文 • 貢献 - RNNを状態有限機械に変換する新しい手法Quantum Bottleneck Network insertion (QBN) を提案 - 提案手法を6つのAtariゲームの学習済み方策に適用し, 4 /23 RNNの記憶能力の利用法を解析

背景 • RNNを方策に用いた強化学習エージェントは, VizDoomやAtariなどで 良い結果を出している (POMDP環境に有効） Playing FPS Games with Deep Reinforcement Learning [Lample+ 2017] • 一方で, RNNの記憶能力を方策がどう活用しているのかは定かでない 5 /23

背景 • RNNを状態有限機械に落とし込むことで, 学習済み方策における記憶 能力の活用法や, 対応する環境が要求する記憶能力を解析できると考 えられる （以下は潜在状態の同定タスクの例） 現在の観測のみで状態が決まり, 過去の履歴が必要ない例 過去の履歴のみで決定的に状態 が決まり, 観測が意味を持たない 6 /23 例

背景 • RNNを状態有限機械に変換する取組みは1993年頃からある - この論文と同じく, 隠れ状態の離散化を行うものが多い - 近年では質問学習を使ったものが有名 “Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples” [Weiss+, 2017] • 既存の手法はRNNとは独立の状態有限機械を抽出する形をとっている → この論文では, RNNにそのまま組み込むことができる 挿入形式の離散化手法を提案 → 離散化によって低下した性能をfine-tuningによって補える 7 /23

提案手法 • Moore Machine (MM) - 状態と出力が紐付いている状態有限機械 ℎ෠ 0 /𝑎ො 0 - 今回は方策を表現するので, 𝑜ො0 ・状態：方策のRNNの隠れ状態 𝑜ො0 𝑜ො1 ・入力：観測 𝑜ො1 ・出力：行動 ෠1 /𝑎ො1 ෠ 2 /𝑎ො 0 ℎ ℎ と対応付ける 𝑜ො1 • Moore Machine Network (MMN) ෡ → 𝐴, መ - Moore Machineにおける状態から出力への写像 𝜋: ො 𝐻 መ 𝐻 ෡ × 𝑂෠ → 𝐻 ෡ をDNNで表現したもの 遷移関数 𝛿: 観測には連続を許すので 𝑔: ො 𝑂 → 𝑂෠ もDNNで表現する ※ 離散変数, その集合, 離散変数に関わる関数には ෡ をつけて書いています 𝑜ො0 8 /23

提案手法 • RNNにおける演算を分割して整理 - 𝑂: 𝑓𝑡 = 𝑔 𝑜𝑡 : 特徴抽出器. 観測𝑜𝑡 からCNNなどで特徴量𝑓𝑡 を抽出す る - 𝑅: ℎ𝑡+1 = 𝛿(𝑓𝑡 , ℎ𝑡 ) : RNN本体. 観測を受け取って隠れ状態を更新する - 𝜋: 𝑎ො𝑡 = 𝜋(ℎ𝑡 ) : 行動への写像. 隠れ状態から行動を出力する ℎ 𝑡 𝑜𝑡 𝑂 𝑔 𝑜𝑡 𝑓𝑡 𝑅 𝛿(𝑓𝑡 , ℎ𝑡 ) ℎ𝑡 𝜋 𝑎ො𝑡 𝜋(ℎ𝑡 ) 9 /23

提案手法 • Quantized Bottleneck Network insertion (QBN) - 下の図のように, 分割したRNNの演算に2つの潜在空間を離散化した オートエンコーダ𝑏𝑓 , 𝑏ℎ を挿入する 𝑏ℎ 𝐸ℎ 𝑏𝑓 𝑜𝑡 𝑂 𝑔 𝑜𝑡 𝑓𝑡 𝐸𝑓 𝒇෠ 𝒕 ℎ𝑡 𝐷𝑓 𝑅 ෡𝒕 𝒉 𝑓ሚ𝑡 𝛿(𝑓ሚ𝑡 , ℎ෨ 𝑡 ) 𝐷ℎ ℎ෨ 𝑡 ℎ෨ 𝑡 𝜋 𝜋(ℎ෨ 𝑡 ) 𝑎ො𝑡 10 /23

提案手法 • Quantized Bottleneck Network insertion (QBN) - 𝑜ො𝑡 = 𝑓መ𝑡 としてみると, 先ほどのMMNの構成要素と መ 𝐻 ෠ 𝛿: ෡ × 𝑂෠ → 𝐻, ෡ 𝜋: ෡ → 𝐴መ のように対応付けられる 𝑔: ො 𝑂 → 𝑂, ො 𝐻 𝐸ℎ ℎ𝑡 𝑜𝑡 𝑂 𝑔 𝑜𝑡 𝑓𝑡 𝐸𝑓 𝐷𝑓 𝒇෠ 𝒕 (ෝ 𝒐𝒕 ) 𝑅 ෡𝒕 𝒉 𝑓ሚ𝑡 𝛿(𝑓ሚ𝑡 , ℎ෨ 𝑡 ) 𝐷ℎ ℎ෨ 𝑡 ℎ෨ 𝑡 𝜋 𝜋(ℎ෨ 𝑡 ) 𝑎ො𝑡 11 /23

提案手法 • オートエンコーダの潜在空間の離散化は3段階で, シンプルに[-1, 0, +1]で 近いものに丸める • 0付近での離散化をサポートするために, 潜在空間直前の活性化関数に 1.5 tanh 𝑥 + 0.5tanh(−3𝑥) を用いる • 勾配はSTL (Straight-Through Estimator) で近似 • ロスは通常の再構成誤差 12 /23

提案手法 • 全体の学習プロセスは3段階 ① RNNの学習 ② 2つのQBNの学習 ③ 2つのQBNをRNNに挿入してMMNにし, 必要があればfine-tuning - fine-tuningでは, 元のRNNの出力のsoftmaxを教師として全体 を学習 13 /23

提案手法 • 学習の終了後, MMNに対して通常の状態有限機械最小化のためのアル ゴリズム [Paull & Unger, 1959] を適用し, 隠れ状態数（ノード）の最 小化を行う • 同時に, 同じノードの間を繋いでいるだけの観測（エッジ）をまとめ, 数を少なくする • これが非常に有効で, MMNによっては隠れ状態数, 観測数を2桁減らす ことに成功している 14 /23

実験 • まずは真の状態有限機械が既知な2つの課題を用いて提案手法を検証 • Mode Counter Environment - 直接は観測されない環境の潜在状態を推定し, それと同じ行動を選択 し 続ければ正の報酬が貰える環境 - 即ち, 最適方策を表す状態有限機械と環境の状態有限機械は一致する - 適切に行動を選択するために記憶しなければならない履歴の長さを 制御できる • Tomita Grammars: - 形式言語の学習, RNNからの状態有限機械の抽出で典型的なタスク 15 /23

実験 • Mode Counter Environment: 今回用いたのは以下の3種類 (a) Amnesia: 履歴が不必要. 現在の観測のみで潜在状態が決まる (b) Blind: 観測が無意味. 過去の履歴のみで決定的に潜在状態が 決まる (c) Tracker: 観測と履歴の両方を活用する必要がある 16 /23

実験 • 離散化した潜在空間の次元𝐵ℎ , 𝐵𝑓 を変えて実験 • RNN, MMNともにテストデータでほぼAccuracy100％を達成できた • 隠れ状態数と観測数の最小化実行後, ほとんどの場合で真の状態有限 機械と一致するものが獲得できた 17 /23

実験 • 6つのAtariゲームに適用して提案手法を検証 • 方策RNNはA3C [Minh+, 2016] + GAE (Generalized Advantage Estimator) [Schulman+, 2015]で学習 • 学習データの多様性確保のため, QBNは一定確率でランダム行動を加 えた方策を環境でロールアウトして得られるℎ𝑡 , 𝑓𝑡 で学習 • 潜在空間の次元𝐵𝑓 , 𝐵ℎ を非常に大きくしており, 原理的には3𝐵𝑓 , 3𝐵ℎ 個 の離散的隠れ状態と観測が出現しうるが, 実際出てこなかったものは カウントしていないことに注意 18 /23

実験 • Pong, Freeway, Bowling, BoxingではMMNのスコ アは元のRNNのスコアを 維持 • Breakout, Space Invadersではスコアは落 ちたが, fine-tuningの効 果が大きく, ある程度はス コアを保てている • 隠れ状態/観測数最小化の 効果が非常に大きく, 隠れ 状態や観測の数が1になっ ているものまである 19 /23

実験 • 記憶能力の利用法を解析 • Pong - 3行動, 10観測のMoore Machine - 全ての観測は, 現在の隠れ状態に関わらず同じ隠れ状態に遷移する - 過去の履歴が不必要で, 現在の観測のみで行動が決まる. MCEのAmnesiaと同じ 20 /23

実験 • 記憶能力の利用法を解析 • Bowling - 24行動, 1観測のMoore Machine - 観測を無視し, 履歴に従ったopen-loop制御だけで解いている - 現在の観測が無意味で, 過去履歴のみで決定的に行動が決まる. MCEのBlindと同じ 21 /23

まとめ • RNNを状態有限機械に変換する新しい手法として, RNN内部に挿入で きfine-tuningが可能なQuantum Bottleneck Network insertion (QBN) を提案 • 真の状態有限機械が既知な2つのタスクで有効性を確認 • Atariゲームの方策に適用し, fine-tuningによって性能の低下をかなり 抑えられること, 学習後の隠れ状態/観測数最小化によって大きく隠れ 状態数/観測数を落とせることを確認 • Pong, Boxing等幾つかのAtariゲームの方策について, 過去の履歴に意 味がなく, 現在の観測のみを使っている場合や, 現在の観測に意味がな く, 過去の履歴のみを使っている場合など, RNNの記憶領域の利用法を 定性的に解析 22 /23

感想 • 解釈性というと曖昧な概念の話になりがちだが, 結構はっきりとどの ように解釈できるようになったのか述べていて良かった • 状態有限機械の最小化は一切性能に影響を与えないので, これが大き く効果があるのはとても面白いと思う • WaveRNN [Kalchbrenner+, 2018], World Models [Ha+, 2018]など, RNNの記憶能力をどう活用しているのか気になるRNNは多いので, 方 策以外にも適用のしどころがありそう (が, 自己回帰モデルとして用い られるRNNは自身の出力も入力に入れるので, 単純なMoore Machine Networkにはならないかもしれない） 23 /23