2018-01-24

ベイズによる逆強化学習をＣ言語で実装してみた

　本郷で行われた強化学習アーキテクト(2018/01/16)は千葉大学Dの石川翔太さんのベイズによる逆強化学習であった。

　　https://www.slideshare.net/ShotaIshikawa2/ss-86214928

最大エントロフィ法の逆強化学習を実装して見て納得できなかった事は、熟練者の方策変更を反映できない事であった。

その点ベイズでは熟練者のデータを分類して、その方策の移動を隠れ変数として反映できる可能性がある。

　以下の文献に従って簡単な、ベイズによる強化学習を実装してみた。

　　https://www.aaai.org/Papers/IJCAI/2007/IJCAI07-416.pdf

　プログラム(python) としては下記のGitHubを参照しました。

https://github.com/erensezener/aima-based-irl

　熟練者の選択確率を $P_{expert}(Trj(s,a)|R)$ とすると報酬 $R$ はベイズより次式の事後分布で算出する事ができる。

　　 $P_{expert}(R|Trj(s,a)) = \frac{1}{Z} P_{expert}(Trj(s,a)|R) \cdot P_{expert}(R)$

　　ここで

$s$ :局面

$a$ :行動

$Trj(s,a)$ は観測された熟練者の遷移経路

$P_{expert}(R)$ :熟練者の報酬の事前確率

　　 $Z=\sum_a \gamma \exp \{Q(s,a)|R)\}$ :分配関数

$Q(s,a)|R$ は行動価値関数 Bellman方程式で解く

　隠れ変数Ｒを変動させて事後分布を最大とするMAP(Maximum Posterior)をすればよい

ベイズモデルの有意性は上記の様に定式化が明確で理解し易いことにあるが、一般に事後分布は尤度関数が共役事前分布でないと理論的に解けず、MCMCによる繰返し計算が必要になる。

以下の手順で計算する。

①報酬の事前分布は $R$ 一様分布とする

　②MCMCを使って最適 $R$ を探査する

簡単にいうと一様分布の報酬 $R$ をランダムに変えて生成した熟練者の事後分布が高くなるなら、これを採用する

　③生成する尤度分布 $P(s,a|R)$ は仮定された $R$ よりBellaman方程式を解いて価値行動関数 $Q(s,a|R)$ に指数比例とする(ボルツマン分布の仮定)

　　 $P(R|s,a) = \frac{1}{Z} \exp \{Q(s,a^*)|R)\} \cdot P(R)$

$a^*$ は熟練者の局面 $s$ での最適行動

　　　　この実装では熟練者の経路から局面 $s$ での最頻度行動としている。

　　　　上記のpythonの例だと熟練者の事前報酬 $R^*$ を仮定して採用している。

④ 乱数で生成された報酬 $R$ での熟練者の事後分布が、前に計算された事後分布より高くなれば、この仮定された報酬 $R$ を選択する。

実験課題

　課題は最大エントロフィ逆強化学習と同じ問題とする。

　赤がゴール。熟練者データはOpen-AIで解いた100通りの経路とする。

　　 f:id:mabonki0725:20171215143025p:plain

実験結果

　ゴールに近い所が報酬が高く、遠い所が低く計算できている。

　最大エントロフィ逆強化学習よりは粗い結果となっている。これは熟練者の最適方策を単に経路データから最頻度行動を採用しているためと考えられる。

f:id:mabonki0725:20180124100306p:plain

2018-01-13

UC.Berklayの協業強化学習の論文を読む

複数の自律体での強化学習は敵対的なモデルが一般的ですが、この論文は複数の自律体が協同で問題を達成するモデルの論文で、DeepMindと双璧を成すUC.Berklayの発表です。

https://people.eecs.berkeley.edu/~russell/papers/icml17ws-cirl.

「Efficent Cooperative Inverse Reinforcement Learning」

問題設定はＣhefWorldと云い人間とロボットが協同で料理の材料を用意して、なるべく多くの料理を作るゲームです。

このモデルはAdaptive-CIRLとして以下の実験結果が報告されています。横軸は材料数、縦軸は成功した料理数です。材料数が増えた場合、論文のモデルが傑出して高い精度を出しています。　　 f:id:mabonki0725:20180113115628p:plain

この問題はロボットは人間の意図や好みを推測して材料を提供する必要があるので、ロボット側から見ると人間の好みを観察して合わせる必要があります。それでCIRL(Cooperative Inverse Reinforcement)として人間の行動をデータとする逆強化学習としてモデル化できますが、人間の好みが見えないPOMDP(部分観察マルコフ決定過程）として捉える事ができます。

POMDPでは一般に観察データ $O$ から状況 $s$ を推察する確信度 $b$ を導入します。一般には観察データから正解の状況 $s$ で回帰で求めらることが多いです。

　 $s_k = \theta_{k,1}O_1 + \dots + \theta_{k,n} O_n$

この論文では価値関数 $\alpha_\sigma(s)$ はBellman方程式に類推確率 $P(s,z | s,a)$ を考慮して以下に改変して計算しています。

　 $\alpha_\sigma(s) = R(s) + \gamma \sum_{s' \in S} \sum_{z \in Z} P(s',z | s,a) \alpha_{v(z)} (s')$

　ここで

　　 $z$ ：観察データ

　　 $\alpha_{v(z)}(s')$ は観察zでの状況s'の価値

大きな問題は協業なので、人間の意図に沿わない材料をロボットが用意した場合でも料理にする必要があります。

この論文では、人間の類推確率 $P(s,a^H|s,a^R)$ を以下で更新しています。

　 $P(s',a^H | s,a^R) = P((x',\theta'),a^H | (x,\theta),a^R)))$

$=T(x,a^H,a^R,x')\cdot\mathcal{1}(\theta' = \theta) \cdot P(a^H|x,a^R,\theta)$

ここで

T:推移確率

　　状態 $s$ は(観察 $x$ ,パラメータ $\theta$ )で定義

　　 $a^H$ は人間の行動

　　 $a^R$ はロボットの行動

複数の自律体の強化学習は、逆強化学習よりも互いの意図を確信度で代替するPOMDPでも実現できること示した意義があると考えられます。

2018-01-08

UC.Berkeleyの敵対的逆強化学習の論文を読む

Abbeel率いるUC.Berkeleyのロボット学者達が昨年初「GANとIRL」は同義だとする画期的な論文を示しましたが、この一派がまたこの論文に述べられたGAN-GCLを発展させたGANによるIRLの論文（Adversarial Inverse Reinforcement Learning:AIRL)を発表しました。

[1710.11248] Learning Robust Rewards with Adversarial Inverse Reinforcement Learning

GAN-GCL(Genarative Adversarial Network-Guided Cost Learning)では経路を使った識別関数でしたが、この手法は安定しないため、局面( $s,a$ )での識別関数に変更して性能を向上させました。

この識別関数はGANの定義通りで以下となります。

　 $D_\theta(s,a) = \frac{\exp(f_\theta(s,a))}{\exp(f_\theta(s,a)) + \pi(a|s)}$

　ここで

　　 $\exp(f_\theta(s,a))$ は熟練者の局面 $s$ 行動 $a$ での選択率を与える擬似関数（ $\theta$ が特徴量）

　　 $\pi(a|s)$ はIRLで生成された擬似方策

このモデルは熟練者の選択とIRLで生成された擬似方策を識別関数 $D_\theta(s,a)$ で識別し、これを改善することによって熟練者の選択・擬似関数を改善します。

論文では以下の①~③を繰返す敵対的アルゴリズムとなっていて、繰返し毎に熟練者と擬似IRLの生成結果を近似していきます。

　①局面 $s$ 行動 $a$ でのデータが熟練者によるものか、IRLで生成されたデータか判断し識別関数 $D_\theta(s,a)$ を改善します。

$D_{\theta,\phi}(s,a) = \frac{\exp(f_{\theta,\phi}(s,a))}{\exp(f_{\theta,\phi}(s,a)) + \pi(a|s)}$

　②報酬 $r_{\theta,\phi}$ は上記の識別関数を次式に投入すると、IRLの公式となるので計算できます。

　　 $r_{\theta,\phi} \gets \log D_{\theta,\phi}(s,a,s') - \log(1-D_{\theta,\phi}(s,a,s'))$

$f_{\theta,\phi}(s,a,s') = g_\theta(s,a) + \gamma h_\phi(s') - h_\phi(s)$

ここでは報酬擬似関数 $g_{\theta}(s,a)$ と価値擬似関数 $h_\phi(s)$ に分離して近似解を解いています。

③得られた報酬 $r_{\theta,\phi}$ より擬似方策 $\pi$ を計算します。

　実験では以下の２つの訓練時と試験時では異なる強化学習の精度を比較しています。

f:id:mabonki0725:20180108174238p:plain

　　Pointmass-Maze Ant-Disabled

左図は訓練時は緑→青へ、試験時は青→緑へ移動する実験

右図は訓練時は４本同じ足で前進、試験時は前足が短くしています。

比較先としてTRPOによる経路を真値としています。

f:id:mabonki0725:20180108174812p:plain

ここで　State-OnlyのYesは識別関数が(s,a)で判定しており、Noは経路( $\tau$ )での識別判定です。特にAnt-DisabledではAIRLでないと全く試験時には前に動作しないと述べています。

流石にGANとIRLが同等である事を示したチームのモデルであるだけに敵対的なIRLモデルとなっています。

なお、GANとIRLが同等である説明資料を以下に添付します。

Irs gan doc from Masato Nakai

www.slideshare.net

2018-01-03

逆強化学習の深層学習版をC言語で実装してみた

確率・統計 AI論文ロボテックス

年末にC言語でSGD（確率勾配法）で逆強化学習を実装したが、深層学習版でも実装してみました。

SGDと結果は殆ど変わりませんが、PRMLの５章にあるチューニング無しのロジックの深層学習なので相当時間がかかりました（約３分　SGD版の100倍）。

示せたことはChainerやTensorflowなしでも解けることですが、1990年ぐらいに既にSutton等が強化学習はニューロで解ける事を示していました。

この課題は簡単なので、複雑な報酬に対応する深層学習の効果が発揮できず、時間だけがかかる結果となっています。

ようやく3年越しで、Max Entropy Deep IRL method(2014)を理解することができました。

https://arxiv.org/abs/1507.04888

f:id:mabonki0725:20180103153241p:plain

2017-12-15

逆強化学習をC言語で実装してみた

確率・統計ロボテックス

(1) 逆強化学習をC言語で実装してみた

　計算機どうしが互いに強化するモデル（敵対モデル）を構成するには、単独での初期学習が充実していないと実現しないのは、アルファー碁やbonanzaの示す所と考えています。

　そこで敵対モデルを一般的に拡張した場合での初期学習としては、熟練者の行動ログより仮想報酬を計算する逆強化学習が考えられます。

　逆強化学習法で最も実績がある最大Entrophy法をC言語で実装しました。

Deep IRL by C language from Masato Nakai

www.slideshare.net

実験対象は下記のゲームの強化学習の結果を熟練者として読込み、逆強化学習で報酬を計算しました。

　・対象はopen-aiの4*4セル（左上と右下がゴール）のグリッドワードゲームの

　　強化学習したゴールまでの経路データ(99経路）をログに落とし、これを熟練者の行動履歴としました。

　　　　　　 f:id:mabonki0725:20171215143025p:plain

　・この99経路のログを読み最大Entophy法で仮想報酬を計算する。

　・逆強化学習は特徴ベクトルの設定が成否を握りますが、

　　この問題は簡単なので16*16の対角ベクトルを使用しています。

(2) 結果

　ゴールに近いセルほど仮想報酬が高く計算されていることが分ります。

　全く対称とならないのは、Open-AIの経路データのサンプリングの歪みが反映されています。

f:id:mabonki0725:20171215140454p:plain

2017-12-12

不完全情報下のRegret最小化の拡張

(1)　不完全情報下のRegret最小化の拡張

　これはボーカゲームの様に相手の手札が見えない場合の最適選択するモデルです。

　このモデルはビジネスや部分的観察時の自動運転に応用でれば相当な威力を持つはずですが、この分野に詳しいDeNAのゲーム部門の人に聞いても、応用の文献は少ないとの返答でした。

　本格的なポーカモデルは人に勝つ様なレベルまで達しています。このロジックは勝負を繰り返す毎に相手の癖で負けた時をRegret（後悔)として、相手の癖を見抜いて勝つことでRegretを最小化するモデルです。

　このモデル全部の理論式は難解すぎて私には敷居が高すぎるのですが、この理論をJavaで実装した論文があったので、これをＣ言語で実装し拡張してみました。

http://modelai.gettysburg.edu/2013/cfr/cfr.pdf

　論文では２者で1,2,3の手札だけで大きい値が勝ちとした場合で、賭け(bet)と降り(pose)の各々の推奨確率を出すものになっています。但しbetで負けると-２点、poseだと-1点で済みます。

　今回ではモデルを以下に拡張してみました。

　　①手札が3→5

　　②参加者が2→3

　　③相手の賭けや降りの局面での自分の次の一手についての推奨確率を算出

結果では、自分の手札と相手の出方について、自分の次の一手について妥当な推奨確率が得られています。

結果の見方

　Xcardは自分の手札となります。

　action=Pose average=x.xxxx は自分が降りる推奨確率

　action=Bet average=x.xxxx は自分が賭けに出る推奨確率

　#Ｎpose はN番目の人がposeした局面

　#Nbit はN番目の人が賭けに出た局面

　#Npose bitはN番目の人が降りたが別の人が賭けに出た局面

結果

4card
　　action=Pose avrage=0.004410
　　action=Bet avrage=0.995590
4card #2pose
　　action=Pose avrage=0.019243
　　action=Bet avrage=0.980757
4card #3pose bit
　　action=Pose avrage=0.001131
　　action=Bet avrage=0.998869
4card #1b
　　action=Pose avrage=0.000747
　　action=Bet avrage=0.999253
3card
　　action=Pose avrage=0.994308
　　action=Bet avrage=0.005692
3card #1pose
　　action=Pose avrage=0.715343
　　action=Bet avrage=0.284657
3card #3pose bit
　　action=Pose avrage=0.001012
　　action=Bet avrage=0.998988
3card #1b
　　action=Pose avrage=0.001157
　　action=Bet avrage=0.998843
3card #2pose
　　action=Pose avrage=0.711650
　　action=Bet avrage=0.288350
3card #2pose bit
　　action=Pose avrage=0.001001
　　action=Bet avrage=0.998999
3card #3b
　　action=Pose avrage=0.007379
　　action=Bet avrage=0.992621
1card
　　action=Pose avrage=0.999751
　　action=Bet avrage=0.000249
1card #1pose
　　action=Pose avrage=0.999611
　　action=Bet avrage=0.000389
1card #1pose bit
　　action=Pose avrage=0.999708
　　action=Bet avrage=0.000292
1card #3b
　　action=Pose avrage=0.999448
　　action=Bet avrage=0.000552
4card #3pose
　　action=Pose avrage=0.008656
　　action=Bet avrage=0.991344
4card #2pose bit
　　action=Pose avrage=0.003741
　　action=Bet avrage=0.996259
4card #2b
　　action=Pose avrage=0.001005
　　action=Bet avrage=0.998995
1card #2pose
　　action=Pose avrage=0.999247
　　action=Bet avrage=0.000753
1card #2pose bit
　　action=Pose avrage=0.998960
　　action=Bet avrage=0.001040
1card #2b
　　action=Pose avrage=0.998918
　　action=Bet avrage=0.001082
5card
　　action=Pose avrage=0.002274
　　action=Bet avrage=0.997726
5card #2pose
　　action=Pose avrage=0.004293
　　action=Bet avrage=0.995707
5card #3pose bit
　　action=Pose avrage=0.001128
　　action=Bet avrage=0.998872
5card #3b
　　action=Pose avrage=0.000783
　　action=Bet avrage=0.999217
2card
　　action=Pose avrage=0.999751
　　action=Bet avrage=0.000249
2card #3pose
　　action=Pose avrage=0.999301
　　action=Bet avrage=0.000699
2card #3pose bit
　　action=Pose avrage=0.252349
　　action=Bet avrage=0.747651
2card #1b
　　action=Pose avrage=0.821005
　　action=Bet avrage=0.178995
1card #3pose bit
　　action=Pose avrage=1.000000
　　action=Bet avrage=0.000000
2card #1pose
　　action=Pose avrage=0.998437
　　action=Bet avrage=0.001563
2card #2b
　　action=Pose avrage=0.111200
　　action=Bet avrage=0.888800
4card #1pose bit
　　action=Pose avrage=0.001151
　　action=Bet avrage=0.998849
2card #2pose bit
　　action=Pose avrage=0.502903
　　action=Bet avrage=0.497097
2card #3b
　　action=Pose avrage=0.646351
　　action=Bet avrage=0.353649
4card #1pose
　　action=Pose avrage=0.001156
　　action=Bet avrage=0.998844
4card #3b
　　action=Pose avrage=0.000761
　　action=Bet avrage=0.999239
5card #1pose
　　action=Pose avrage=0.001399
　　action=Bet avrage=0.998601
5card #1pose bit
　　action=Pose avrage=0.000542
　　action=Bet avrage=0.999458
1card #1b
　　action=Pose avrage=1.000000
　　action=Bet avrage=0.000000
3card #3pose
　　action=Pose avrage=0.989238
　　action=Bet avrage=0.010762
2card #2pose
　　action=Pose avrage=0.999237
　　action=Bet avrage=0.000763
2card #1pose bit
　　action=Pose avrage=0.936695
　　action=Bet avrage=0.063305
1card #3pose
　　action=Pose avrage=0.500000
　　action=Bet avrage=0.500000
3card #2b
　　action=Pose avrage=0.007183
　　action=Bet avrage=0.992817
5card #1b
　　action=Pose avrage=0.000721
　　action=Bet avrage=0.999279
5card #3pose
　　action=Pose avrage=0.001124
　　action=Bet avrage=0.998876
3card #1pose bit
　　action=Pose avrage=0.013992
　　action=Bet avrage=0.986008
5card #2b
　　action=Pose avrage=0.000731
　　action=Bet avrage=0.999269
5card #2pose bit
　　action=Pose avrage=0.001044
　　action=Bet avrage=0.998956

2017-11-25

Openpose によるバスケット・フリースローの解析

Openposeを使ってバスケット・フリースローの解析をしてみました。

Openposeについて

・動的認識率はかなり高い

・骨格座標は結果は１フレーム毎にファイルに出力され加工しやす。

・20フレーム毎/秒で（変更可能）で出力される

・但し２次元しか認識されない

Open pose時系列解析7 from Masato