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

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