逆強化学習の深層学習版を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

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

確率・統計 ロボテックス

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

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

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

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

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

　

不完全情報下の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

 

　

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

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

Openposeについて

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

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

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

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

 

 

 

不完全情報下のRegret最小化(CFR)の論文を読む

ランニングできず　英語できず

(1) 不完全情報下のRegret最小化(CFR:Counterfactual Regret Minimization)の論文を読む

  「An Introduction to Counterfactual Regret Minimization」 http://modelai.gettysburg.edu/2013/cfr/cfr.pdf

　　現状の強化学習は「完全情報下のReret最小化」と看做せます。

　何故なら強化学習は、情報が完全に見え累計した罰則の最小化モデルだからです。

　しかしポーカの様な相手の情報が一部見えない強化学習は

　「不完全情報下のRegret最小化」となります。このモデルはCFR(反作用的後悔最小化）

　と呼ばれています。

　　現在モデルは下図の様に本格的Porkerゲームのプロに勝つレベルに達しており、

　モデルの正しさが実証されています。(Libratusがモデル)

f:id:mabonki0725:20171111112816p:plain

                   http://triblive.com/local/allegheny/11865933-74/rematch-aaron-aupperlee

　　この論文はCFRの理論をToy Porkerでのプログラムで解説をしたものでです。

　この論文の貴重な点は、下記の様なCFRの理論記述が強化学習に比べ格段に難解である所を　        

         R_i^T = \frac{1}{T} max_{\sigma_i^* \in \Sigma_i} \sum_{t=1}^T (u_i(\sigma_i^*,\sigma_{-i}^t) - u_i(\sigma^t))

         \hat{\sigma}_i^t (I)(a) = \frac{\sum_{t=1}^T \pi_i^{\sigma^t}(I) \sigma^t(I)(a)}{\sum_{t=1}^T \pi_i^{\sigma^t}(I)}

         ここで

             R_i^T:累計最大Regret

             \sigma_i^*:自分の最適戦略

　　　  \sigma_{-1}^t:自分以外の戦略

             u_i(\sigma^t):戦略の価値

　　　  \sigma_i^t(I)(a):情報Iで行動aを採った戦略

             \pi_i^{\sigma^t}(I):情報Iで戦略\sigma^tでの方策 

　プログラムで具体的に解説しています。

     　現在のプロPorkerでは10^{16}に達する場合が存在しており、この成功は

　モデルの高速化と効率化がある程度旨く行っているからです。

　本論文ではJavaでのソースコードを解説していますが、Ｃ言語で書き直しました。

    GitHubに入れました。

　https://github.com/mabonki0725/regret_cfr

(2)デモ結果の説明

　・ゲームの内容

　　２人での対戦　カード１～3までの内各々がランダムにカードを取る

        大きいカードを持つ方が勝つ

　　bit と poseが選択でき、bitして勝てば +2点 負ければ -2点

        双方がposeの場合、cardを見せ 勝てば +1点 負ければ -1 点

　　相手がbit時にposeを選ぶと -1 点で負ける

　　上記のルールでは下記の遷移図になる

　　

         配布 --  pose -- pose (開示)

                  |             --  bit  -- pose (降りる)

                  |                        -- bit (勝負)

                  -   bit      -- pose (降りる)

                                 - bit (勝負)

       ・デモ結果

　　　自分のcardの値と各遷移での次の選択での得点できる価値を示している。

　　　例えば下記の3poseは　自分のカードが3で相手がposeの場合で

　　　自分がposeを選ぶと価値は79%でbitを選ぶと21%となっている。

　　　何故なら、3は最強のカードなので安心してbitしても相手が降りる可能性があり

　　　その場合は1点しか獲得できないからである。ならば確実に得点できるposeの方が

　　　価値が高い

 

3
　action=Pose avrage=0.000491
　action=Bet avrage=0.999509
3pose
　action=Pose avrage=0.788462
　action=Bet avrage=0.211538
3pose - bit
　action=Pose avrage=0.153846
　action=Bet avrage=0.846154
3bit
　action=Pose avrage=0.000076
　action=Bet avrage=0.999924
1
　action=Pose avrage=0.999848
　action=Bet avrage=0.000152
1pose
　action=Pose avrage=0.999924
　action=Bet avrage=0.000076
1pose - bit
　action=Pose avrage=0.999924
　action=Bet avrage=0.000076
1bit
　action=Pose avrage=0.500000
　action=Bet avrage=0.500000
2
　action=Pose avrage=0.056895
　action=Bet avrage=0.943105
2pose
　action=Pose avrage=0.998704
　action=Bet avrage=0.001296
2pose - bit
　action=Pose avrage=0.998704
　action=Bet avrage=0.001296
2bit
　action=Pose avrage=0.000078
　action=Bet avrage=0.999922

　　　

                   

           

　・　

   

VAEによる半教師学習の論文を再読する

確率・統計 画像認識

(1) VAEによる半教師学習の論文を再読する

[1406.5298] Semi-Supervised Learning with Deep Generative Models

T研のMゼミでの発表でこの論文を再読する。

再度して判明したことは

　・変分限界の式以外は殆ど理解していなかった

　・この論文は省略が多く難しい

EncoderとDecoderを両方で最適化しているが本当に旨くいくか半信半疑で、深層学習とは凄いものと思う。

www.slideshare.net