論文内容

Program Synthesisに機械学習を適用する際、specificationとground truthプログラムが揃ったデータセットの用意が課題となる。強化学習を用いることでそれ以外のデータセットに対してもProgram Synthesisの学習を可能とした。RLの性能をあげるための学習アルゴリズムを提案した。

背景

Program Synthesisに機械学習/DNNを適用する際、入力となるspecificationと出力となるground truthプログラムが揃ったデータセットが必要となる。また、既存研究ではsynthesize対象の言語を制約の強いDSLに絞っている。

強化学習を用いてProgram Synthesisをすることを考えると、必要なのはreward functionだけとなる。reward functionを計算するためにはground truthプログラムは必須ではない。

このため、RLの活用によってより広い範囲のProgram Synthesisに機械学習/DNNを適用することが可能となると考えられる。この論文では、RLを利用したProgram Synthesisの方法を提案した。

提案手法

基礎となるのは通常のpolicy gradientなRL (REINFORCE) である。

提案手法 (Priority Queue Training) では、REINFORCEのlossに加えtopk lossを最適化の目的関数に追加 (加算) している。topk lossは今までの学習中でrewardが高かったtop k個のプログラムに対するlog liklihoodである。

評価

BFに対するProgram Synthesisで提案手法を評価した。遺伝的アルゴリズムやPriority Queue Traininigを用いないRLに比べ、提案手法はより多くのケースでtest caseをpassするプログラムを生成できた。また、topk lossだけで学習しREINFORCEのlossをなくしても性能が劣化しないことを明らかにした。

メモ・コメント

“3. Approach”にあるDNNモデルの図を見ると、encoderはなくdecoderだけからなるDNNを用いているらしい。したがって、test caseの入出力は本当に一切見ずにrewardだけから正しいプログラムを探す、という問題設定で手法の設計・評価をしている。

合成ごとに学習を回すというのはかなり時間がかかるはず。また、人間の行うプログラミングを考えても仕様の情報を陽に使わないというのは無理があるように思う。

一方で、「推論時に強化学習のような枠組みで正しいプログラムを探索する」というのはProgram Synthesisの性能を上げる上で効果的かもしれないと思う。むやみにbeam searchのbeam sizeを上げるよりは効率よく探索できる可能性がありそう。