論文, NeurIPS2020

論文内容

Program Synthesisの性能を上げるために、一度SynthesizeしたプログラムをDNNによってrefinementする手法を提案した。

背景

DNNによるProgram Synthesis (主にProgramming by Example) には大きく2つの種類がある。

実行途中のプログラムの状態を用いてプログラムを逐次生成するもの
実行途中の状態をもちいず一気にプログラムを生成するもの

1はsequentialなプログラムの実行には適しているが、ループや分岐のようなcontrol flowを扱うことができないという問題がある。2は、それまで生成したプログラムの情報を使うことができないという問題がある。

人間がプログラミングをやる時の事を考えると、ループや分岐を用いることは多いし、一度書いたプログラムをデバッグしながら正しいプログラムとしていく方が一般的である。このような人間のプログラミング能力を現在のProgram Synthesis技術は模倣できない。

提案手法

DNNを用いプログラムのdebugをするcomponentを追加することで、Program Synthesisの性能を上げる手法を提案した。

出発点となるプログラムを生成するためのProgram Synthesis手法には特に制約はなく、任意の手法を用いることができる。ここで生成したプログラムがtestcaseをpassしない場合、提案するdebug componentによりプログラムを修正する。

プログラムの修正は (現在のプログラム, I/O example, プログラムの実行Trace)の3つを入力として受け取りtokenの追加・削除・変更を実行することで行う。token単位での編集なので同時に複数tokenの追加・削除・変更を行うことができるような設定をしている。そうでないと例えば ifや whileのような処理を追加することができないはずである。

学習では、正しいプログラムにmutationを加えて間違ったプログラムを用意し、これを用いて教師あり学習を行う。

評価

Karelというベンチマークデータセットによって評価を行った。test caseのpass率を指標として評価し、debug componentの追加によってpass率が2pt～23pt向上することを示した。

メモ・コメント

アイデアとしては自然で有望そうに思えたが、性能向上がそこまででもないなぁという印象を受けた。Table1, Table2を組み合わせると、EGNPSで探索回数を増やした方が性能が良かったりする可能性はありそうな気がする。