DeepCoder 追実装まとめ

DeepCoder 実装 機械学習

概略

[(Input, Output)] => Map[関数, 出現確率]の関数をディープラーニングで学習し，それを利用してプログラム空間を探索・プログラム合成をする． 詳しくは論文．

実装

レポジトリ

chainerに慣れていないため、諸々非効率的と思うが、実装自体はそこまで難しいところはなかった。 細かい反省点としては、データセットをJSONで保存するのは馬鹿らしかったなどなどがある。ただ、とりあえずやってみることを重要視した以上、実装での汚い点、反省点があるのは当然とは思っている。

学習

最終的に学習に用いたデータセットは800万件ほど。g3.4xlargeを利用して24時間強学習した。lossは下のような感じ。環境変数で与える学習パラメータは、ALPHA=0.0001、EPOCH=1000、BATCH_SIZE=1000で行った（詳しい実装はレポジトリを参照）。今考えると学習率上げてもよかったかもしれない。

f:id:mhiroaki0000:20170802184110p:plain:w300

当初はp2.xlargeを利用していたのだが、CPU側メモリが足りなくてabortするという事態が発生したので、急遽インスタンスタイプを変更した。 データセットを生成後S3に上げるというワークフロー、メモリに展開するべきではない制約を鑑みるとSQLiteが妥当だったと考えている。

また、プロトタイピングという目的からは、学習に1日かかるというのは問題。方法は以下の3つほど考えられる。

  1. 小さいデータセット、単純な問題で実装を進め、最後に規模を大きくする
  2. 複数のGPUを積んだEC2インスタンスを利用する
  3. いくつかのp2.xlargeあたりのインスタンスでクラスタを組む

1は単純なアプローチだけど、結局規模を大きくしたときのデバッグで苦しむ気がする。2は一番素直だけど、値段が跳ね上がる（余っていないらしくスポットインスタンスによる費用抑制ができない）という問題がある。 3は、上手くスポットインスタンスを組むことができれば、一番潰しが効く気がするけど、実現難易度は高い。

評価

ランダムに100個プログラムと入出力サンプルを生成して、プログラム合成をさせた。各サンプルに対し、以下の3パターンを試している。最後のやつの詳細は論文参照。

  1. DFS (DNNなし)
  2. DFS (DNN利用)
  3. “Sort and Add” Enumeration (DNN利用)

ただし、1800秒たっても合成できない場合はタイムアウトさせて終了させている。

結果

経過時間平均と標準偏差 (秒)

DNNなし DFS with DNN “Sort and Add” Enumeration
434.55 (695.86) 1075.42 (794.41) 464.11 (718.14)

見ての通り、DNNを利用したときの方が遅くなっている。一応DNNの推論分の時間がDNN使用の時には追加されているが、それを考慮してもやはり遅くなっているはず。

経過時間平均と分散（高階関数抜き） 実行過程を眺めたところ、高階関数で時間をとっているような気がしたので、高階関数を使っていない場合飲みを抽出して再度計算した。

DNNなし DFS with DNN “Sort and Add” Enumeration
580.51 (786.43) 639.75 (781.70) 369.43 (656.61)

自分の直感どおり、早くなってはいるが、母数が少ない（18件）し、分散は大きいし、よくわからない。

まとめ・所感

DeepCoderそのものについて

実装・学習

一点（整数のembed方法）を除いて元論文の通りに実装しているはず。ただし、データセットの生成手法・学習手法については元論文に詳細な記載がないので本当に同じかはわからない。多分違う。

評価

全体的には性能向上は見られなかった。一方、高階関数を使わない場合は学習が効果があったのかもしれない（ただしよくわからない）。 総じて、上手く学習できているのかはよくわからないという結論を出さざるを得ないと思う。

なお、評価方法については、以下の2つの懸念点がある。

  • timeコマンドを時間計測に利用
    • より正確なデータが必要なら真面目な計測をしないといけないが、面倒だった
  • 各サンプル1回しかテストをしていない
    • 他に最低限のプロセスしか動いていないEC2インスタンス上でテストしたので、実行時間の分散は比較的小さいと思う

学習を続ければまだlossが下がりそうなので、もう少し学習時間を取ると予測精度が上がって速度向上につながるかもしれない。ただ、それをやっても自分として得られるものが少ない気がするのでここで追実装としては終わりの予定（暇だったりなんかのついでにできたらやるかも）

機械学習とかプログラム合成について

機械学習

  • 比較的簡単なネットワークであっても、1 GPUの学習には限界がある
    • 複数のGPUを使える環境は優先的に整えたほうが良い
  • データセットは一次記憶に展開しなくて済むよう、最初から実装するべき
    • それなりの時間を無駄にしかねない

プログラム合成について

  • 結局全探索なので、探索方法の工夫での高速化の余地は大きい
    • 今回で言えば、反復深化法のほうがDFSよりはあっていたという予感がある。
  • 実行速度にダイレクトに関わるのはプログラムの長さ
    • 長さ4, 5のプログラムが一瞬で生成できるわけではない。
    • 元論文でも、平気で合成に数千secとかかけている。

作業記録

mhiroaki.hatenablog.com mhiroaki.hatenablog.com mhiroaki.hatenablog.com mhiroaki.hatenablog.com