不完全情報下の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がモデル)
http://triblive.com/local/allegheny/11865933-74/rematch-aaron-aupperlee
この論文はCFRの理論をToy Porkerでのプログラムで解説をしたものでです。
この論文の貴重な点は、下記の様なCFRの理論記述が強化学習に比べ格段に難解である所を
ここで
:累計最大Regret
:自分の最適戦略
:自分以外の戦略
:戦略の価値
:情報で行動を採った戦略
:情報で戦略での方策
プログラムで具体的に解説しています。
現在のプロPorkerではに達する場合が存在しており、この成功は
モデルの高速化と効率化がある程度旨く行っているからです。
本論文ではJavaでのソースコードを解説していますが、C言語で書き直しました。
GitHubに入れました。
https://github.com/mabonki0725/regret_cfr
(2)デモ結果の説明
・ゲームの内容
2人での対戦 カード1~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を両方で最適化しているが本当に旨くいくか半信半疑で、深層学習とは凄いものと思う。
エネルギーベースの逆強化学習の論文を再読する
ランニングできず 英語できず
(1) エネルギーベースの逆強化学習の論文を再読する
「Maximum Entropy Deep Inverse Reinforcement Learning」
https://arxiv.org/abs/1507.04888
T研のMゼミでかなり以前に解説した論文でしたが、敵対的な逆強化学習の提案で読み返してみると殆ど理解できていない事が分りかなり迷惑を掛けた自覚ともに落ち込んでいます。
この逆強化学習の手法はかなり有名でかなりのHPで散見されますが、記述が追えない箇所があるのにそのまま記載されています。
この逆強化学習では、行動選択の確率はエネルギー関数で与えられるので、熟練者の辿ったデータで逆に報酬を求め様とするものです。
この対数尤度を負の損失関数とすると
これをで微分すると
ここで
なので
またここで
とと特徴量の内積すると
よって微分は 経路での特徴量のデータ平均と真の平均との差となる
プログラムの反映で以下となる 2行目のループ内ので8,9行目でを改善している。
このプログラムでは
エネルギー関数によるGANの論文を再読する
ランニングできず 英語できず
(1) Bengioエネルギー関数によるGANの論文を再読する
「Deep Directed Generative Models with Energy-Based Probability Estimation」https://arxiv.org/abs/1606.03439
逆強化学習で最も一般的なエネルギーベースモデルが理解できなかったので再読しました。
これはエネルギーベースのGANで他のGANと異なりExactに収束状態が分るものです。実装している方も多いと思います。
深層学習でプログラムを自動生成する論文を読む
ランニング30分 英語できず
(1) 深層学習でプログラムを自動生成する論文を読む
「DeepCoder:Learning to Write Programs」
https://www.microsoft.com/en-us/research/publication/deepcoder-learning-write-programs/
この論文は下図の様なInput配列とOutput配列より、その過程のプログラムを生成するモデルで相当衝撃的な内容です。モデル名 LIPS(Learing Inductive Program Synthesis)
整数宣言→ 負値のみ採用→4倍→ソート→逆順
プログラムはDSL(Domain Specified Language)で定義された次の30個の手続きの組合わせを
推定してプログラムを構成します。(DSLの定義はAppendex F参照)
一階関数: Head Last Take Drop Access Minimum Maximum Revese Sort Sum
高階関数:Map Filter Count ZipWidth ScanL1
ラムダ関数:Mapの引数 (+1) (-1) (*2) (/2) (+(-1)) (**2) (*3) (/3) (*4) (/4)
Filterの引数 (>0) (<0) (%2 == 0) (%==1)
ZipWidht ScanL1の引数 (+) (-) (*)
深層学習では教師付学習で上記の例では以下の出力が得られています。高い確率のDSLが使われている事がわかります。
(1.1) 手法
組合わせは30個に限定されていますので、入出力から最適な組合わせを見つけるのは
深層学習で教師付学習で行います。
深層学習は確度の高い組合わせの候補を絞るだけなので、論文ではGuid法と云っています。
そこで深層学習から出た組合わせでプログラムを構成するには、以下の手法を採用しています。
・DFS(深さ優先探索)
・Enumeration(Sortと追加の試行錯誤)
・ツール採用
また矛盾が無いか確かめるため、検証ツールSMTを採用しています。
以下が深層学習を援用したプログラム生成の手続きです
1) DSLを深層学習の入出力にするためEncoder でベクトル化して
Encoder → Decoderモデルとなっています。
Encoderは上記の30個のDSLの有無を(0,1)でコード化します。
の確率が最も高い値になる様に学習します。
ここで
はプログラム
は入出力のデータ
2) DSLの分解と最大尤度での組合わせ
各DSLの尤度の合成が最大になる様に組合わせを選択します
ここで
はプログラムをN個に分解
は分解された各DSL
は各DSLで分解された入出力
3) 深層学習によるの推定
この深層学習は入出力と正解プログラムの教師学習で訓練されます。
・深層学習は以下の構成となっています。
・深層学習の最上位の推定結果は次の様になっていて候補とDSLの選択確率が求まっています。
・ 隠れ層ではRNNやLSTMを使う場合があります。
(1.2) 結果
・プログラム生成した結果
・採用モデルの成績の比較
深層学習+DFS or Enumeration法が優れている結果になっている
DFS : 深さ優先探索
L2: プログラム結合ツール採用 (Fester et al. 2015)
Enumeration : Sort and Add 法にちょる結合法採用
Beam search
Sketch: デバック検証ツール(SMT)の採用
Prior order : 出現確率の高い順
Neural network : 深層モデル
画像から原因と結果を識別する論文を読む
(1) 画像から原因と結果を識別する論文を読む
「Discovering Causal signals in Images」https://arxiv.org/abs/1605.08179
これもhttps://twitter.com/miyamotok0105さん主催の「酒を飲みながらCVPR2017の論文を読む会」で興味を持った一つです。
この論文は静止画像から原因となる物体と結果となる物体を特定するものです。
下図は人間が犬とフリスビーで遊んでいる画像で、犬がフリスビーに飛びついています。
・人間がフリスビーを掲げているのが原因 (causal)
・犬が飛びついているのが結果 (anticausal)
一般にデータから原因を特定する方法は2つあります。
1) 操作の介在があるデータから原因を推定
介入前後のデータの状態が変化するので、その変化より原因を推定します
2) データの特性から原因を推定 ICM(Inpedent Causal Mechanism)方式
データの分布状態から原因を推定します。
1)の精度は高いですが介入操作が必要です。2)はノイズがあると識別できません。
この論文は静止画像なので2)の方法に採っています。
(1.1) 静止データでの原因分析
ICMでは誤差の状態で判別しますが、2方法あります。 (a) (b)図
・ANM(Added Nose Model)で誤差の状態で原因が識別できます。
の場合は誤差が縦に並びます
の場合は誤差が横に並びます
下図だと赤の棒線線の幅が(a)では同じ、(b)では相違しているのでノイズの並びか分ります。
・Monotonic法 (c)図
真値(実践)からのノイズの分布を見ると横方向には矩形、縦方向には山形になって、この分布は で形成されたことが分ります。
・独立成分分析(ICA)
手法としては独立成分分析(ICA)で分布の方向を探ることができます。
下図はその例です。ノイズの方向が見えない場合でもICAは判断することができます。
http://www.geocities.jp/mabonakai/sub/ex_icaCausal.htm
(1.2) 論文の手法
データを高次元に写像してICMを使っています。
本論文の手法では、まず画像を部分画像個に分解します。
この分解方法については一般の矩形(BoundingBox)で行います。
(1.2.1) pixelベースの「原因」「結果」判別分析
ICMはpixelデータを高次元に写像して行っています。
一般にデータを高次元に写像するとデータは分離しやすくなります。
高次元の写像にはカーネルが一般的ですが、ここでは深層モデルで行っています。
ここで
は部分画像のpixel
は部分画像のpixel数
は原因か結果かのICM2値判別関数
・深層学習によるデータの高次元化NCC(Neural Causation Coefficent)
この論文では次式を使って「原因か結果」かを判別しています。
次式の値が1に近ければ「結果」となります。
(1.2.1) 物体レベルの判別分析
しかしながらpixelベースでは「原因か結果」では判別が難しいので、
最終的には物体とその特徴量とでNCCで判別しています。
物体とその特徴量は深層学習で20個識別しています。
上段が物体の検出精度で、下段が「結果」の識別精度となっています
交通事故が起こる危険な場面の画像生成の論文を読む
ランニング30分 英語できず
(1) 交通事故が起こる危険な場面の画像生成の論文を読む
「Expecting the Unexpected:Training Detectors for Unusual Pedestrians with Adeversarial Imposers」 https://scirate.com/arxiv/1703.06283
この論文は歩行者の危険な場面の画像を自動生成するものです。
これはhttps://twitter.com/miyamotok0105さん主催の「酒を飲みながらCVPR2017の論文を読む会」で興味を持った一つです。
一般道の自動運転を可能にするには、危険な事象のデータを大量に集めて予測回避モデルを構築する必要がありますが、この事象は非常に稀なので限界がありました。しかし、この様な場面を大量に生成できれば精度のよいモデルが出来る可能性があります。
現在はOpenposeで動作予測をしていて、歩行者の危険な行動を事前に察知できないかと問題意識を持っていた所、論文になっていたので読んでみました。
(1.1) 手法
この論文は3Dゲーム作成ツールを使ったGANモデルとなります。
・偽画像はゲーム作成ツールUnity3Dで生成
・本物の画像はGoole ImageやBaidu Imageのタイトルを[traffic violation]等の言葉で検索し
危ない歩行者の画像を集めたものです。
GANなのでUnity3D生成器はより本物らいい画像を生成し、識別器は本物と偽物を識別し互いに敵対的に訓練します。
最も一般的な3Dゲーム生成ツール[Unity]で様々な場面を生成しますが、パラメータを変動させて生成します。また経験的に人物の重なりは20%以下等の制限を入れています。
パラメータは多変量でキャラクター、背景、太陽の方向、歩行者の姿勢、天候等があります。
よってGANの使命は危険な画像になる様なを求める事になります。
一般のGANの式は以下です。
しかしUnity3Dでゲーム場面を生成するので
画像生成パラメータは多変量の正規分布を仮定して最適化はGANの深層学習で実現しています。しかし間にUnity3Dが入っていので直接微分可能ではなく収束しないかもしれません。
この論文では2段階のアルゴリズム RPN(Region Proposal Netwrk)で物体認識を実現しています。
・アルゴリズム①(偽者画像の選択)
偽者の画像で本物と誤認識率た高い複数の画像を選択
・アルゴリズム②(物体認識)
まず予備訓練として偽の画像で物体認識を訓練
本物とアルゴリズム①で得た紛らわしい画像で物体認識を訓練
次に本物だけで物体認識訓練
(1.2) 結果
危険な歩行者の状態を生成した画像で、物体を矩形で認識しています。