ここ最近のDNNを用いたProgram Synthesisについて自分から見えていること、思っていることを雑にまとめてみる。

Neural Program Synthesisのカテゴリ

Neural Program Synthesisにはいくつか種類がある。大きく、

  1. 探索の効率化手段としてDNNを用いる
  2. 自然言語生成と同じ枠組みでDNNを用いる
  3. DNNでinterpreterを近似し、backpropagationでプログラムを最適化する

の3つに分けられる。 ただし、1と2の違いは曖昧としたものではある。 イメージとしては1はASTを生成していて、2は文字列 (ソースコード) を生成しているイメージを持っている。

1については、2017年DeepCoderの登場後、Programming by Exampleの目的では結構つかわれている印象がある。一番最近だとTFCoderやBUSTLEが当てはまると思っている。

一方、text to code translation (自然言語を入力とするProgra Synthesis)では2が一般的な印象がある。機械翻訳と同じSeq2Seqタスクとして扱えるので実装が簡単だったとかの理由がありそう。例えば、SIGPX 5で自分が紹介・その後再実装したNL2Codeが当てはまる。2020年には (Program Synthesis用ではないが) GPT-3も登場した。

3は偶に出てくるが、適用できる問題設定が狭いからかあまり大きくはとりあげられていない印象がある。この論文のような3D形状を扱うプログラミングタスクで使われている例を見る (他のタスクで見たことがない)

「1: 探索の効率化手段としてDNNを用いる」について

DNNを用いたProgram Synthesisとして一番分かりやすい実装かなと思う。また、探索アルゴリズムではプログラミング言語の文法を用いてsyntaxのおかしいプログラムを排除できるので、生成したプログラムはsyntax上はvalidであることを比較的簡単に保証できる。

問題規模を絞って探索範囲を狭めた場合、徐々にツール化の目途が立ちつつあるように見える。TFCoderはその一例。

一方、この方針で単純に問題規模を大きくし複雑なプログラムを合成する、という研究はあまりうまくいっていないように見える。 最近はProgramming by Exampleタスクであることを使って、プログラム合成 → 実行 → プログラム修正 → 実行 ….というループを回しiterativeに解法を洗練させていくアプローチをよく見る。この論文は強化学習によってプログラムを修正している。

想像でしかないが、やはり一発で正しいプログラムを合成するというのは難易度が高く、(人間がやるように) テストしながらプログラムをデバッグしていく過程が必須なんじゃないかと思う。

また、

  • 探索問題である以上探索回数を多くするのが性能に直結しがち
  • プログラミング言語の文法を使った探索は複雑であまりGPU向きでない
  • 後処理でinvalidなsyntaxなものを排除するのは簡単

といった点で問題規模が大きくなると、この1の方針をとるメリットが薄れがちというのもあるのでは? と思っている。

「2: 自然言語生成と同じ枠組みでDNNを用いる」について

GPT-3から話題に大きく上がっている。機械翻訳と同じ枠組みで英語 → 日本語を翻訳するように英語 → Java/Python/…. を翻訳するタスクとしてProgram Synthesisを行う。

プログラムをsequence (文字列) として生成するため、普通にやるとsyntaxがおかしいプログラムが出力される。 2017年～2019年ごろまではこの問題への対処がホットなテーマだったように思う。NL2Codeは生成 (decode) の工夫で対処している。

ただ、最近はこの問題意識は重視されていなさそう。Microsoftが出したNeural Program Synthesisのベンチマークデータセットの提案論文では後処理でsyntaxがおかしいプログラムを外しているらしい。実際一度parseすればsyntax errorがあるかどうかはすぐわかるので大量に生成して後でフィルタリングすれば良というのは合理的な気がする。

どの程度論理的にプログラムを生成できるかについては、調査した論文は見たことがない。ただ、個人的に実験した感覚では学習データの丸暗記 + ちょっとした変更、の域を超えるものではない印象がある。

GPT-3がどうなのかは出遅れてOpenAI APIにまだアクセスできないので実際のところは分からない。ただ、「GPT-3も学習済みタスクから近いものをとってきているらしい」という論文があり、個人的にはこの話が納得がいっている。 (雑に言えば)「GPT-3はStack Overflowを暗記したのでStack Overflowにある質問なら答えることができる」みたい状況にあるのではないだろうか。

「3: DNNでinterpreterを近似し、backpropagationでプログラムを最適化する」について

DNNでinterpreterを近似するという手法の制約上、画像や3Dモデルに対して適用している例しかしらない。自分で試したことがないので正直勘所が分からないというのもあるので、試してみたいなぁという気持ちがある。

今後

1のような探索+枝刈りDNNという手法はツール化・実用化のフェーズに入りつつある気がする。IDE上のツールみたいな感じで実用化がゴールなのかな。例えばdoctestを書くとその場で関数の中身が合成される、というように。

2はホットな分野だけど、着地点がまだ見えていない気がする。Web上にあるsample programを暗記できているとすると、「ググる代わりにchatbotに聞く」みたいなアプリケーションとしての実用化が一番最初なのかもしれないと思う。

3は実例が少ないけど、個人的には期待している。Neural Architecture Searchがドメイン知識を利用せず微分可能にして素直にSGDで最適化、という方針が結構うまくいったのと同じように、案外多くのドメインがこの方針で高速化できたりしないのかなと思っている。 当てずっぽうでも丸暗記でもないNeural Program Synthesisを実現できそうな技術が今のところこれしか見当たらないから期待をかけている、という側面も多分にありはするけど……