2017-11-11

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

　・　

2017-10-30

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

確率・統計画像認識

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

[1406.5298] Semi-Supervised Learning with Deep Generative Models

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

再度して判明したことは

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

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

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

Semi vae memo (2) from Masato Nakai

www.slideshare.net

2017-10-24

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

ロボテックス AI論文

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

(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)$ との差となる

プログラムの反映で以下となる　２行目のループ内ので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

2017-10-23

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

確率・統計画像認識

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

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

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

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

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

Deep genenergyprobdoc from Masato Nakai

www.slideshare.net

2017-10-21

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

AI論文確率・統計

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

　　整数宣言→ 負値のみ採用→４倍→ソート→逆順

　プログラムは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) ＤＳＬを深層学習の入出力にするため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$ をＮ個に分解

　　　　 $p^n$ は分解された各DSL

$\varepsilon^n$ は各DSL $p^n$ で分解された入出力

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

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

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

f:id:mabonki0725:20171022141223p:plain

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

　　・隠れ層ではＲＮＮや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

2017-10-19

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

AI論文画像認識確率・統計

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

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

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

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

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

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

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

f:id:mabonki0725:20171020224752p:plain

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

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

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

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

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

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

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

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

　ICMでは誤差の状態で判別しますが、２方法あります。　(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$ は原因か結果かのICM２値判別関数

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

　　 f:id:mabonki0725:20171021082605p:plain

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

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

　　 $\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

2017-10-18

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

AI論文画像認識

ランニング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ゲーム作成ツールを使ったＧＡＮモデルとなります。

　　・偽画像はゲーム作成ツールUnity3Dで生成

　　・本物の画像はGoole ImageやBaidu Imageのタイトルを[traffic violation]等の言葉で検索し

　　　危ない歩行者の画像を集めたものです。　

GANなのでUnity3D生成器はより本物らいい画像を生成し、識別器は本物と偽物を識別し互いに敵対的に訓練します。

f:id:mabonki0725:20171020104118p:plain

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

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

f:id:mabonki0725:20171019215319p:plain

　よってＧＡＮの使命は危険な画像になる様な $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$ は多変量の正規分布を仮定して最適化はＧＡＮの深層学習で実現しています。しかし間にＵnity3Dが入っていので直接微分可能ではなく収束しないかもしれません。

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

　・アルゴリズム①（偽者画像の選択）

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

　・アルゴリズム②（物体認識）

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

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

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

(1.2) 結果

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

f:id:mabonki0725:20171019221040p:plain