不完全情報下の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でのソースコードを解説していますが、C言語で書き直しました。

    GitHubに入れました。

 https://github.com/mabonki0725/regret_cfr

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

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

[1406.5298] Semi-Supervised Learning with Deep Generative Models

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

再度して判明したことは

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

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

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

 

https://www.slideshare.net/secret/i7MUBmfO6Snbmq

エネルギーベースの逆強化学習の論文を再読する

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

(1) エネルギーベースの逆強化学習の論文を再読する

  「Maximum Entropy Deep Inverse Reinforcement Learning

https://arxiv.org/abs/1507.04888

 T研のMゼミでかなり以前に解説した論文でしたが、敵対的な逆強化学習の提案で読み返してみると殆ど理解できていない事が分りかなり迷惑を掛けた自覚ともに落ち込んでいます。

 この逆強化学習の手法はかなり有名でかなりのHPで散見されますが、記述が追えない箇所があるのにそのまま記載されています。

    この逆強化学習では、行動選択の確率はエネルギー関数で与えられるので、熟練者の辿ったデータで逆に報酬r_{s,a}を求め様とするものです。

  p(\mathcal{D},\theta|r) = \frac{1}{Z(\theta)} \exp \{ -r_{s,a}(\theta)\}

   この対数尤度を負の損失関数とすると   

       - \mathcal{L}(\theta) =\log \frac{1}{N}\sum_{s,a}^N p(\tau(s,a)|r) = \frac{1}{N}\sum_{s,a}^N \{ -r_{s,a}(\theta) - \log Z(\theta)\}

   これを\theta微分すると    

      \frac{\partial \mathcal{L}(\theta) }{\partial \theta} =[ \frac{1}{N} \sum_{s,a} \frac{\partial }{\partial \theta} r_{s,a}(\theta)] - \frac{\partial}{\partial \theta}\log Z(\theta)

   ここで   

        log Z(\theta) = log \sum_{s,a} \exp\{-r_{s,a}(\theta)\} p(\theta) = -\sum_{s,a} r_{s,a}(\theta) p(\theta)

   なので

        \frac{\partial}{\partial \theta}\log Z(\theta) = -\sum_{s,a} \frac{\partial}{\partial \theta} r_{s,a} (\theta) p(\theta)  =- \mathbb{E}_\theta \frac{\partial} {\partial \theta} r_{s,a} (\theta)

 またここで 

       -r(s,a,\theta) = \theta^T f(s,a)\thetaと特徴量f(s,a)内積すると

  -\frac{\partial}{\partial \theta} r_{s,a}(\theta_i) = f(s,a)

     \frac{\partial \mathcal{L}(\theta) }{\partial \theta} = [ \frac{1}{N} \sum_{s,a} f(s,a) ] - \mathbb{E}_\theta f(s,a) = \mathbb{E}_{s,a} f(s,a) - \mathbb{E}_\theta f(s,a)

  よって微分\frac{\partial \mathcal{L}(\theta) }{\partial \theta}は 経路\tau(s,a)での特徴量のデータ平均\mathbb{E}_{s,a} f(s,a)と真の平均 \mathbb{E}_\theta f(s,a)との差となる

 

  プログラムの反映で以下となる 2行目のループ内ので8,9行目で\thetaを改善している。

 このプログラムでは

   \mathbb{E}_{s,a} f(s,a) \to \mu_D

       \mathbb{E}_\theta f(s,a) \to \mathbb{E} [\mu]  

f:id:mabonki0725:20171025173622p:plain

 

 

エネルギー関数によるGANの論文を再読する

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

(1)  Bengioエネルギー関数によるGANの論文を再読する

   「Deep Directed Generative Models with Energy-Based Probability Estimation」https://arxiv.org/abs/1606.03439

 逆強化学習で最も一般的なエネルギーベースモデルが理解できなかったので再読しました。

 これはエネルギーベースのGANで他のGANと異なりExactに収束状態が分るものです。実装している方も多いと思います。

 

www.slideshare.net

 

 

深層学習でプログラムを自動生成する論文を読む

ランニング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)

f:id:mabonki0725:20171022130938p:plain

      整数宣言→ 負値のみ採用→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が使われている事がわかります。f:id:mabonki0725:20171022140753p:plain

 

(1.1) 手法

 組合わせは30個に限定されていますので、入出力から最適な組合わせを見つけるのは

 深層学習で教師付学習で行います。

 深層学習は確度の高い組合わせの候補を絞るだけなので、論文ではGuid法と云っています。

 そこで深層学習から出た組合わせでプログラムを構成するには、以下の手法を採用しています。

    ・DFS(深さ優先探索

     ・Enumeration(Sortと追加の試行錯誤)

     ・\lambda^2ツール採用

 また矛盾が無いか確かめるため、検証ツールSMTを採用しています。

 

 以下が深層学習を援用したプログラム生成の手続きです

    1)  DSLを深層学習の入出力にするためEncoder でベクトル化して 

    Encoder → Decoderモデルとなっています。 

    Encoderは上記の30個のDSLの有無を(0,1)でコード化\mathcal{A}(P)します。

    q(\mathcal{A} (P)| \varepsilon)の確率が最も高い値になる様に学習します。

   ここで

                Pはプログラム

    \varepsilonは入出力のデータ 

  2) DSLの分解と最大尤度での組合わせ

      各DSLの尤度の合成が最大になる様に組合わせを選択します

        q(\mathcal{A}(P)|\varepsilon)=\Pi_{n=1}^N  q(\mathcal{A}^n(p^n) | \varepsilon^n)

             ここで

                NはプログラムPをN個に分解

    p^nは分解された各DSL

                \varepsilon^nは各DSLp^nで分解された入出力         

     3) 深層学習によるq(\mathcal{A}(P)|\varepsilon)の推定

   この深層学習は入出力と正解プログラム\mathcal{A}(P)の教師学習で訓練されます。 

         ・深層学習は以下の構成となっています。

f:id:mabonki0725:20171022141223p:plain

  ・深層学習の最上位の推定結果は次の様になっていて候補とDSLの選択確率が求まっています。

  ・  隠れ層ではRNNやLSTMを使う場合があります。

f:id:mabonki0725:20171022142010p:plain

 

 (1.2) 結果

 ・プログラム生成した結果

f:id:mabonki0725:20171022160330p:plain

 ・採用モデルの成績の比較

  深層学習+DFS or Enumeration法が優れている結果になっている

   DFS : 深さ優先探索

         L2:\lambda^2  プログラム結合ツール採用  (Fester et al. 2015)

         Enumeration : Sort and Add 法にちょる結合法採用

         Beam search

         Sketch: デバック検証ツール(SMT)の採用 

         Prior order : 出現確率の高い順

         Neural network :  深層モデル

f:id:mabonki0725:20171022161033p:plain

      

           

 

 

 

画像から原因と結果を識別する論文を読む

(1) 画像から原因と結果を識別する論文を読む

 「Discovering Causal signals in Images」https://arxiv.org/abs/1605.08179

   これもhttps://twitter.com/miyamotok0105さん主催の「酒を飲みながらCVPR2017の論文を読む会」で興味を持った一つです。

 この論文は静止画像から原因となる物体と結果となる物体を特定するものです。

 下図は人間が犬とフリスビーで遊んでいる画像で、犬がフリスビーに飛びついています。

 ・人間がフリスビーを掲げているのが原因  (causal)

 ・犬が飛びついているのが結果                      (anticausal)

f:id:mabonki0725:20171020224752p:plain

 一般にデータから原因を特定する方法は2つあります。 

  1) 操作の介在があるデータから原因を推定   

   介入前後のデータの状態が変化するので、その変化より原因を推定します

  2) データの特性から原因を推定 ICM(Inpedent Causal Mechanism)方式

   データの分布状態から原因を推定します。

 1)の精度は高いですが介入操作が必要です。2)はノイズがあると識別できません。

 この論文は静止画像なので2)の方法に採っています。

 

  (1.1) 静止データでの原因分析 

 ICMでは誤差の状態で判別しますが、2方法あります。 (a) (b)図

 ・ANM(Added Nose Model)で誤差の状態で原因が識別できます。

           x \to y       y=f(x)+\epsilonの場合は誤差\epsilonが縦に並びます

           y \to x      x=f(y)+\epsilon の場合は誤差\epsilonが横に並びます

  下図だと赤の棒線線の幅が(a)では同じ、(b)では相違しているのでノイズの並びか分ります。

 ・Monotonic法 (c)図

  真値(実践)からのノイズの分布を見ると横方向には矩形、縦方向には山形になって、この分布は  y=f(x)+\epsilon で形成されたことが分ります。

f:id:mabonki0725:20171020230544p:plain

  ・独立成分分析(ICA) 

   手法としては独立成分分析(ICA)で分布の方向を探ることができます。

   下図はその例です。ノイズの方向が見えない場合でもICAは判断することができます。

    http://www.geocities.jp/mabonakai/sub/ex_icaCausal.htm 

    f:id:mabonki0725:20171021075624p:plain

 (1.2) 論文の手法

 データを高次元に写像してICMを使っています。

 本論文の手法では、まず画像を部分画像m個に分解します。

    この分解方法については一般の矩形(BoundingBox)で行います。

 

  (1.2.1) pixelベースの「原因」「結果」判別分析

    ICMはpixelデータを高次元に写像して行っています。

 一般にデータを高次元に写像するとデータは分離しやすくなります。

f:id:mabonki0725:20171021092726p:plain

    高次元の写像にはカーネルが一般的ですが、ここでは深層モデルで行っています。

 ・カーネルによる高次元写像

     KCC( [(x_{i,j},y_{i,j} ) ]_{j=1}^{m_i}) = \psi \left( \frac{1}{m_i} \sum_{j=1}^{m_i} \phi(x_{i,j},y_{i,j}) \right)

         ここで

    x_{i,j} \ \ y_{i,j} は部分画像iのpixel

            m_iは部分画像iのpixel数

            \phi(x_{i,j},y_{i,j}) は画像をカーネルで高次元に写像

   \psiは原因か結果かのICM2値判別関数

 ・深層学習によるデータの高次元化NCC(Neural Causation Coefficent)

  f:id:mabonki0725:20171021082605p:plain

       この論文では次式を使って「原因か結果」かを判別しています。

       次式の値が1に近ければ「結果」となります。

     \frac{1}{2} \{1- NCC ( [(x_{i,j},y_{i,j} ) ]_{j=1}^{m_i})) +  NCC( [(x_{i,j},y_{i,j} ) ]_{j=1}^{m_i})  \}

 

(1.2.1) 物体レベルの判別分析  

  しかしながらpixelベースでは「原因か結果」では判別が難しいので、

    最終的には物体c_kとその特徴量f_kとでNCCで判別しています。

 物体c_kとその特徴量f_kは深層学習で20個識別しています。

          NCC( [(c_k,f_k ) ]) = \psi \left( \frac{1}{m_k} \sum_{j=1}^{m_k} \phi(c_{k,j},f_{k,j}) \right)   

 上段が物体の検出精度で、下段が「結果」の識別精度となっています

f:id:mabonki0725:20171021084534p:plain

 

 

交通事故が起こる危険な場面の画像生成の論文を読む

ランニング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生成器はより本物らいい画像を生成し、識別器は本物と偽物を識別し互いに敵対的に訓練します。

f:id:mabonki0725:20171020104118p:plain

 最も一般的な3Dゲーム生成ツール[Unity]で様々な場面を生成しますが、パラメータzを変動させて生成します。また経験的に人物の重なりは20%以下等の制限を入れています。

 パラメータzは多変量でキャラクター、背景、太陽の方向、歩行者の姿勢、天候等があります。 

f:id:mabonki0725:20171019215319p:plain

 よってGANの使命は危険な画像になる様なp_\theta^{Unity}(z)を求める事になります。

 一般のGANの式は以下です。

  min_G \  max_D V(D,G) = \mathbb{E}_{x \sim p_t(x)} [\log D(x) ] + \mathbb{E}_{z \sim p_z(z)} [\log(1 - D(G(z))) ]

 しかしUnity3Dでゲーム場面を生成するので

  min_I \  max_D V(D,I) = \mathbb{E}_{x \sim p_t(x)} [\log D(x) ] + \mathbb{E}_{z \sim \color{red}{Unity(Z_I)}} [\log(1 - D(G(z))) ]

    画像生成パラメータZ_Iは多変量の正規分布を仮定して最適化はGANの深層学習で実現しています。しかし間にUnity3Dが入っていので直接微分可能ではなく収束しないかもしれません。

 

    この論文では2段階のアルゴリズム RPN(Region Proposal Netwrk)で物体認識を実現しています。 

 ・アルゴリズム①(偽者画像の選択)

  偽者の画像で本物と誤認識率た高い複数の画像Iを選択

 ・アルゴリズム②(物体認識)

  まず予備訓練として偽の画像で物体認識を訓練

  本物とアルゴリズム①で得た紛らわしい画像で物体認識を訓練

  次に本物だけで物体認識訓練

 

(1.2) 結果

 危険な歩行者の状態を生成した画像で、物体を矩形で認識しています。 

f:id:mabonki0725:20171019221040p:plain