2018-02-16

Natureに掲載されたalphaGo_Zeroの記事を読む

AI論文ロボテックス

教師有り学習としての棋譜学習をしなくても強化学習だけで無敵になったNatureに掲載されたAlphaGo_Zeroの記事を読んでみる。

deepmind.com

上記のURLでpaperを押下するとNatureのサイトに行くが、大学とか特定の大企業では無料でPDFがdownloadできるメニューが現れる。現われない場合は大学か大企業の友人に頼むことになるが著作権違反になるかは分らない。

　Alpha碁につてはこれもNatureで読み、かなり衝撃を受けたので下記の資料に纏めてみたことがある。　

Alpha gor 2 from Masato Nakai

www.slideshare.net

　上記の資料の６ページにある様に従来のAlpha碁のNatureの記事では棋譜（教師）学習のＳＬと強化学習のRLのパイプラインで学習していた。

f:id:mabonki0725:20180216131827p:plain

　どの様にして棋譜学習が必要としない仕掛けになったか、Alpha碁がどの様に構造的に変化したか興味があった。

　下図はアルファ碁のRLの推論展開で「早碁モデル」をつかったものだが、

f:id:mabonki0725:20180216132307p:plain

Zeroの記事にある下図の推論過程は、上記の方法と比較して全く同じであるので、ＳＬ（棋譜学習）をすっ飛ばしてＲＬのみで済ましている様に見える。

f:id:mabonki0725:20180216083622p:plain

　しかし詳細に見ると下図で勝負の結果 $z$ から着手確率 $p$ と場面価値 $v$ を一度に深層学習で求めている所が相違している。従来のAlpha碁では勝負結果 $z$ から価値 $v$ を逆算してDQNで着手を決定していた。

　確かに着手確率 $p$ とその裏付けの価値 $v$ とを同期をとって逆伝播して学習する方が精度を高めるのは間違いない。

f:id:mabonki0725:20180216083933p:plain

　従って損失関数は着手確率 $p$ と価値 $v$ を一度に算出する次式となっている。

　　　　 $\mathcal{L}=(z - v)^2 + \pi^T \log p + c ||\theta||^2$

　　　　ここで

　　　　　 $p$ は次の着手の確率

　　　　　 $\pi$ は方策：学習過程を繰返しで形成された着手の分布

$||\theta||$ はパラメータの正則化項

またこの着手確率 $p$ と価値 $v$ の損失関数を解くのに40層のResNetを使っている。

　このResNetを使った方策と価値を統合することで、棋譜学習をせず強化学習のみで従来のAlpha碁より強いモデルを達成している様だ。

　下図の従来の棋譜を使ったモデルと比較して、この記事の最終のコメントが衝撃的である。

「我々は人類が千年かかって作りあげた碁の知識をたった数日間で達成した！」

恐ろしい革新的な事態が次々起こってきそうである。

f:id:mabonki0725:20180216090114p:plain

なお、アルファ碁のＳＬモデルの実装については下記参照

http://mabonki0725.hatenablog.com/entry/2017/03/29/090000

　AlphaGo_Zeroの実装については下記が有名

　 https://github.com/mokemokechicken/reversi-alpha-zero

2018-02-13

深層学習で将来予測して最適行動する強化学習の論文を読む

ロボテックス AI論文

深層学習で将来予測（Nステップ先）を予測して報酬を獲得する強化学習の論文を読む。

[1707.03497] Value Prediction Network

　この論文はDQNの一手先のモデルを数手先を読むモデルに拡張したもので、かつ非常に洗練された構造をもつ強化学習である。

倉庫番問題等の数手先の将来予測を必要とする課題はDQNでは解けないものとして有名である。DeepMindでは下記の様なモデルを提案していたがモデルの考え方は非常に複雑で明瞭ではなかった。

DeepMindのI2Aモデルの倉庫番ゲームの論文を読む - mabonki0725の日記

　この点本論文の将来予測モデルの構造がDQNのTree展開になっており、直感的て明瞭で発展の可能性がある。

f:id:mabonki0725:20180213062040p:plain

ここで $x$ は観測される状態で $o$ は行動オプションである

左の箱がコアとよばれこの中の近似関数は実際の報酬によってCNNやNNで学習される。

f:id:mabonki0725:20180213062410p:plain

このコアは次のアルゴリズムで再帰的にTree構造で展開される。 f:id:mabonki0725:20180213062646p:plain

この学習はDQNと同じTD法を多段階に拡張したものと見做せる。

損失関数は報酬 $r_t$ と割引率 $\gamma_t$ の $L2$ ノルムとなっている。

　　 $\mathcal{L}_t=\sum^k_i (R_t-v^i_t)^2 + (r_t - r^i_t)^2+(\log_\gamma \gamma_t - log_\gamma \gamma^i_t)^2$

　この論文で重要な知見として、このモデルは課題に依存するモデルベースではなく、DQNと同じモデルフリーとして汎用性があるとしている。

実験：

　次の様な20回移動で最大の報酬（水色）を得る課題でDQNと比較している。下図ではDQNでは５個だが、本論のVPNでは６個報酬を獲得している。

　　 f:id:mabonki0725:20180213063617p:plain

　下記にこの実装プログラムがある。

https://github.com/junhyukoh/value-prediction-network

2018-02-10

回避機能をもつ逆強化学習の論文を読む

ロボテックス AI論文

NIPS2017で発表されたAbbeel達の回避機能をもつ逆強化学習の下記の論文を読む。

「Inverse Reward Design」https://arxiv.org/abs/1711.02827

この論文は予想外の事象に衝き当った場合の報酬を如何に修正するかの話なので、報酬設定→行動経路→逆強化学習→報酬関数の修正なので逆強化学習の一種として考えられる。

予想外の事象に突き当った場合のロボットが、部分観察MDPの確信度で対処する行動決定とそっくりである。POMDPは確信度が低い場合には、近づいたり、スピードを落としたりして観察がよく出来る様に行動させる場合が多い。

　この論文は、ロボットに目的の動作が出来る様に設定する報酬のデザインが誤ったり配慮が抜けてた場合でも、ロボットが当初の目的通りに動作できる様にするものである。

　論文の下図の様な例では、デザイナーは報酬を目標=1 砂漠=0.1 草原=-1として、溶岩を思いつかなかった場合が示されている。

　現実の世界（本論ではReal World)を相手にすると設計者の意図以外の事象に遭遇する場合が普通であって、この場合溶岩にはまって失敗する。

　　　 f:id:mabonki0725:20180210085859p:plain

この論文の意図はDeepMindの様な理想とする環境での知的動作ではなく、Abbeel達は現実の世界の知的ロボットに関心があるので、この様なアイデアを考えたと思われる。

　デザイナーが与えた報酬で訓練したロボットの経路を逆強化学習して、報酬関数の重み $w$ を以下で計算した場合でも、想定外の事象では重 $w$ みの信頼度を下げて、回避しょうとするのがこの論文のアイデアである。

　 $r = w^T \phi(\xi)$

ここで

　　　 $\xi$ は動作経路

　 $\phi(\xi)$ は特徴量

重み $w$ の信頼度はエネルギー関数を採用してた次式の事後分布としている。

$P(w = w^*|\hat{w},\hat{M}) \propto \frac{\exp \{\beta w^T \hat{\phi} \}}{\hat{Z}(w)} P(w)$

ここで

　　 $w^*$ は現実世界に対応した真の重み

$\hat{M}$ はMDP過程

$\xi \sim \pi(\cdot|\hat{w},\hat{M})$

　　　 $\beta$ は感応度（ハイパーパラメータ)

　 $\hat{\phi}(\xi)$ は特徴量の期待値

$\hat{\phi}(\xi) = E[\phi(\xi)]$

$\hat{Z}$ は分配関数

　　　　　 $\hat{Z}(w) = \int_{\hat{w}} \exp \{\beta w^T \hat{\phi} \}d\hat{w}$

分配関数 $Z(w)$ は算出すべき重み $w$ が不明であるので一般には計算不能であるが、経路 $\xi$ を多くサンプリングして近似する場合が多い。

ここではランダムなサンプリング法(sample-Z)と最大エントフィ法で解いた(Maxent-Z)を使って上記の重み信頼度を計算している。

　センサーが未知物体を感知した場合、一つの案として自己位置の認識に下図の様に特徴量 $\hat{\phi}$ に多次元のガウスう分布を使って重みの信頼度を計算している。

f:id:mabonki0725:20180210091949p:plain

　想定外の場合では特徴量 $\phi$ が変化するので、重み $w$ の信頼度が低下し、低い重みで報酬 $r$ を計算すると、報酬 $r$ が低くなるので、回避することができる。

　実験では分配関数 $Z(w)$ をMaxEnt-ZやSample-Zを用いて重みの信頼度を計算した方が、この手当てをしない場合 Proxyより、遥かに溶岩を回避できている。　

　　右図は未知物体では重みの信頼度の事後分布で計算した実験

　　左図は未知物体に統計モデルを使用した実験

f:id:mabonki0725:20180210092529p:plain

Negative Side Effects センサーの想定外検知

Reward Hacking センサー情報の相互矛盾検知

　　　　 Raw Ovservation ガウス分布を使って判定する

　　　　 Classifyer Feature 識別器を使って判定する

2018-02-07

FIRLの論文を読むが難しい

AI論文ロボテックス

ベイズによる逆強化学習が、杉山先生の密度比による逆強化学習と同じ手法になったので、残る有名な手法はFIRL(Feature Construction IRL)のみになった。

この手法は下記のAbbeel率いるBarkleyチームのLevineによる論文がある。

https://homes.cs.washington.edu/~zoran/firl.pdf

この手法はこれまでの報酬を固定の特徴量の近似関数で表す手法と全く異なっていて、特徴量を回帰木で分解して有意な特徴量を選択しながら、２次計画法で最適な報酬関数を求める方法となっている。

f:id:mabonki0725:20180207104749p:plain

　　　ここで

　　 $\mathcal{D}$ は熟練者の行動データ

　　　　 $T_{R \to \Phi}$ は回帰木で選択した特徴量

　　　　 $R_{\Phi}$ は改善対象の報酬関数

$||NR_{\Phi}||$ は同じ状態をもつグループを繋ぐ正則化項

　拘束条件では熟練者の行動範囲 $s \in \mathcal{D}$ であれば、正しい価値関数 $V(s)$ が計算され、それを逸脱すると、劣化した価値関数 $V(s)$ が計算される。逸脱した行動 $a$ は観測できないので $\varepsilon$ の罰則を与えている。

　回帰木は、次式で定義され、枝に含まれる状態 $s$ を報酬の寄与で分割して、最適な回帰木は上記の２次計画法で算出している。

　　 $t_j = \{\delta_j,\phi_j,t_{j-},t_{j+}\}$

ここで

　　　 $t_{j-}$ は木の枝でこのノードに含まれる状態 $s$ で報酬に寄与しない側

$t_{j+}$ は木の枝でこのノードに含まれる状態 $s$ で報酬に寄与する側

$\delta(s)$ は状態 $s$ が報酬に寄与するか判断する関数

　　　 $\phi(s)$ は状態 $s$ がこのノードに含まれるかの指標

　 $t_{j-}$ と $t_{j+}$ はさらに回帰木を生成していくが、経験的に浅い分岐でよいとしている。

　この論文は式記号も難しく、本当に妥当な回帰木が得られるか判断が付かない。詳しいロジックを追求するには下記のMatlabのサイトがある。　

github.com

　逆強化学習に詳しい千葉大の荒井研究室ではこのFIRLを昨年稼動して発表している。しかしFIRLの優位性を示せてなく記述も簡単すぎて詳しい事がわからない。　

https://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=162700&item_no=1&attribute_id=1&file_no=1

2018-02-03

ガウス過程による逆強化学習を実装(python)してみる

ロボテックス Python

先日下記の論文について自分の理解を述べたが、文献に沿ったプログラムがあったので、これを自分なりに修正して稼動してみると、完全に自分の理解が誤っていたことが判明した。もし以前の記述を読んだ方がいれば大変申し訳なく、下記にて修正させて頂きます。

Nonlinear Inverse Reinforcement Learning with Gaussian Processes

(1)ロジックの説明

　プログラムによって理解したロジックです。

この手法のプログラムを読むと、ガウス過程の逆強化学習は以下の手順で行っています。

　① 局面を表す特徴量を選定します。

　②熟練者の操作過程の特徴量を記録します。

　⑥の尤度(IRL term)が最大になるまで③から⑥を繰返します。

　　③特徴量の記録から、ガウスカーネル $K_{u,u}$ のパラメータ $\theta$ を最大尤度(GP probability) で計算します

　　 $P(\theta|X_u) = - \frac{1}{2} tr(K^{-2}_{u,u}) - \sum_i \log(\lambda+1)$

　　④次式に従って特徴量 $X_u$ と観測された報酬 $u$ でカーネル過程回帰します

　　 $\log P(u,\theta|X_u) = -\frac{1}{2} u^T K^{-1}_{u,u} u -\frac{1}{2} \log |K_{u,u}| - \frac{n}{2} \log 2\pi + \log P(\theta)$

　⑤擬似報酬 $u$ の事後分布で真の報酬 $r$ を逆算します

　　　この事後分布(GP posterior)は尤度分布と事前分布ともガウス分布なので

　　　理論解で計算できます

　　　 $r = K^T_{r,u} \cdot k^{-1}_{u,u} \cdot u$

　⑥真の報酬 $r$ よりBellman方程式を解いてこの尤度(IRL term)を計算します。

　根拠のロジックは次式の式になります。

f:id:mabonki0725:20180129073901p:plain

　ここで

　　 $D$ は熟練者のデータ

$Xu$ は特徴量

$u$ は観測された報酬

$r$ は真の報酬

　　 $\theta$ はガウス・カーネルのパラメータ

　　IRL termはBellman方程式の解

GP posterior はガウス分布の事後分布

GP probabilityはガウス過程回帰

(2) 実験課題

　５×５のセルにマーク１と２がある。各セルにエージェントは上下左右に移動する

　マーク１からの距離が３以内でかつマーク２からの距離が２以内のセルに居るなら報酬を得る

　マーク１から3超かマーク1に居るなら罰則がある。

　この規則に従うと以下の報酬になる。　

f:id:mabonki0725:20180203095534p:plain

(3) 実装した結果

　　熟練者のデータは上記(2)のルールに従って移動して、その100経路のログを記録している。

　　この行動記録から上記(1)のロジックで報酬を算出している。

　　但し、ARD（Auto Relevant Decision 自動関連決定)のガウスカーネルを使用した。

　　ガウス過程による逆強化学習の結果(右)は真の報酬に近い値となっている。

f:id:mabonki0725:20180203095721p:plain

github.com

参照したプログラムが探しだせなくなったので、自分が修正したプログラムを示します。

2018-01-31

逆強化学習の課題にPlen2を使う

学校の研究でPlen2を使った逆強化学習を企画しているが、初めてPlen2を使ってみた。

このToyロボットはサーボモータでの稼動点が20点あり、ここに信号を送って逆強化学習の実証実験をする。

このPlen2はArdinoが20個のモータを制御する仕掛けで現在8万円弱とまだ高価である。

Plen2はPC上のWebを使ったコントロール画面で動作を定義する。

PC上のWebサーバがを通じてPlen2と通信する仕組み。

まずは、下のURLに従ってFirmWareをインストールする。

　http://plen.jp/playground/wiki/tutorials/plen2/firmware

動作に関しては、下図のモーション・編集はExcelのマクロ記憶の様に保存して、これを呼び出す仕掛けだがこの動作にエラーが出ている。

「Plen2 motion」の画像検索結果

2018-01-29

ガウス過程による逆強化学習の論文を読む

最大エントロフィの逆強化学習の性能はベイズより優れていることは実装してみて判明したが、下記の論文によるとガウス過程(Gaussian Process)を使った逆強化学習が傑出してよい性能を出している。　

papers.nips.cc

この論文の高速道路の実験例をみるとパトカーやパトバイクに近い所は人間がスピード抑制をしている事が観測されている。

f:id:mabonki0725:20180129072437p:plain

左上が人間のスピード抑制データ(濃い色）で、GPIRL（ガウス過程逆強化学習）が殆ど等しいことが示されている。ここでの比較先は

　MaxEntIRL(最大エントリフィIRL）

FIRL(Feature Construction IRL)

この手法のプログラムを読むと、ガウス過程の逆強化学習は以下の手順で行っています。

　① 局面を表す特徴量 $X_u$ を選定します。

　②熟練者の操作過程 $\mathcal{D}$ の特徴量を記録します。

　⑥の尤度(IRL term)が最大になるまで③から⑥を繰返します。

　　③特徴量の記録から、ガウスカーネル $K_{u,u}$ のパラメータ $\theta$ を最大尤度(GP probability) で計算します

　　 $P(\theta|X_u) = - \frac{1}{2} tr(K^{-2}_{u,u}) - \sum_i \log(\lambda+1)$

この $\theta$ は特徴量 $X_u$ の正則化項のパラメータです $\theta$ は乱数を振って上式が最大(最尤度)となる値を採用しています。

　　④式(3)に従って特徴量 $X_u$ と観測された報酬 $u$ でカーネル過程回帰します

f:id:mabonki0725:20180129073958p:plain

　　これはカーネル $K_{u,u}$ を分散とする対数分布ですが、最後に $\log P(\theta)$ が追加されています。

　　⑤擬似報酬 $u$ の事後分布で真の報酬 $r$ を逆算します

　　　この事後分布(GP posterior)は尤度分布と事前分布ともガウス分布なので

　　　理論解で計算できます

　　　 $r = K^T_{r,u} \cdot k^{-1}_{u,u} \cdot u$

　　　報酬 $r$ と特徴量 $X_u$ のカーネル $K_{r,u}$ を使っています。問題は報酬 $r$ の算出にこれが未定なのに使っています。よってこの式は仮置きの報酬 $r$ を使って、SGDの繰返しで精緻化する方針としています。

　⑥式(2)の $P(\mathcal{D}|r$ は仮置きの報酬 $r$ よりBellman方程式を解いてこの式(2)尤度(IRL term)を計算します。

f:id:mabonki0725:20180129073901p:plain

　　　ここで

　　　　 $D$ は熟練者のデータ

　　 $Xu$ は特徴量

　　 $u$ はガウス過程

$r$ は報酬

　　　　 $\theta$ は $X_u$ の正則化項

　　　　IRL termはBellman方程式の解

　　GP posterior はガウス分布の事後分布

　　GP probabilityはガウス過程回帰

⑦仮置きの報酬 $r$ をSGDで精緻化するため、本論文ではL-BFGSを使ったと記述があります。この微分式については下記のSupprementに詳細に記述され、Python版ではこの通り実装されています。　　　

Nonlinear Inverse Reinforcement Learning with Gaussian Processes f:id:mabonki0725:20180311155547p:plain

　　SGDの為に以下の微分項を計算する

$\frac{\partial}{\partial \theta} \log P(\mathcal{D},u,\theta|Xu) = \frac{\partial \mathcal{L}_D}{\partial r} \frac{\partial r}{\partial \theta} + \frac{\mathcal{L}_G}{\partial \theta} + \frac{\partial \mathcal{L}_H}{\partial \theta}$

$\frac{\partial}{\partial u} \log P(\mathcal{D},u,\theta|Xu) = \frac{\partial \mathcal{L}_D}{\partial r} \frac{\partial r}{\partial u} + \frac{\partial \mathcal{L}_G}{\partial u}$

ここで諸値は以下で与えられる

　　　 $\frac{\partial\mathcal{L}_D}{\partial r} = \hat{u} - \mathbb{E}(u)$ エネルギーベースの逆強化学習

$\frac{\partial\mathcal{L}_G}{\partial \theta_i} = \frac{1}{2} \mathrm{tr} [\alpha \alpha^T - K_{u,u}^{-1} \frac{\partial K_{u,u}}{\partial \theta_i} ]$ ここで $\alpha = K_{u,u}^{-1} u$

$\frac{\partial\mathcal{L}_G}{\partial \theta_i} = - K_{u,u}^{-1} u$

　　 $\frac{\partial r}{\partial u} = K_{r,u}^T K_{u,u}^{-1}$

$\frac{\partial r}{\partial \theta} = \frac{\partial[r=K_{r,u}^T K_{u,u}^{-1} u]}{\partial \theta_i}$

ここで $\theta = \{\beta,\lambda\}$ なので $\frac{\partial \mathcal{L}_H}{\partial \theta}$ は

　　　 $\frac{\partial \mathcal{L}_H}{\partial \beta} = \mathrm{tr} [K_{u,u}^{-3} \frac{\partial K_{u,u}}{\partial \beta}]$

$\frac{\partial \mathcal{L}_H}{\partial \lambda} = \mathrm{tr} [K_{u,u}^{-3} \frac{\partial K_{u,u}}{\partial \beta} ] - \frac{1}{\sum_i \Lambda_{ii} +1}$

実験課題

黄色の位置から３距離までと赤の位置から２距離の場合に居続けると報酬が加算される（左下の赤い範囲）。コマを上下左右に移動して報酬の多寡で強化学習を行った軌跡をデータとして保存する。

f:id:mabonki0725:20180203095534p:plain

強化学習で学習した軌跡でPythonによるガウス過程を使った逆強化学習の結果が右図。一応左図の真の結果に近く細かい報酬が得られている。

f:id:mabonki0725:20180203095721p:plain