Neural Program Synthesis with Priority Queue Training
Daniel A. Abolafia, Mohammad Norouzi, Jonathan Shen, Rui Zhao, Quoc V. Le {danabo, mnorouzi, jonathanasdf, rzhao, Google Brain
Abstract
We consider the task of program synthesis in the presence of a reward function over the output of programs, where the goal is to find programs with maximal rewards. We employ an iterative optimization scheme, where we train an RNN on a dataset of $K$ best programs from a priority queue of the generated programs so far. Then, we synthesize new programs and add them to the priority queue by sampling from the RNN. We benchmark our algorithm, called priority queue training (or PQT), against genetic algorithm and reinforcement learning baselines on a simple but expressive Turing complete programming language called BF. Our experimental results show that our simple PQT algorithm significantly outperforms the baselines. By adding a program length penalty to the reward function, we are able to synthesize short, human readable programs.
中文速览
用一种叫 BF 的图灵完备极简编程语言作为测试场，研究如何让机器仅凭奖励信号（而不依赖已知正确程序或输出）自动合成程序。研究者提出了一种叫做"优先队列训练"（Priority Queue Training，PQT）的方法：维护一个存放历史最优程序的优先队列，用队列里排名靠前的程序反复训练循环神经网络（RNN），再让 RNN 采样出新程序补充队列，如此循环迭代。实验结果表明，PQT 在成功率和稳定性上显著超越了遗传算法和策略梯度强化学习两条基线，在绝大多数任务和随机种子下都能找到正确程序；在奖励函数中加入程序长度惩罚后，还能合成简短、可读性强的程序。这项工作的意义在于，它提供了一种无需人工标注答案、只靠"对不对"的反馈就能搜索程序的通用框架，为构建更灵活的自动编程工具打开了新思路。
原文 arXiv:1801.03526;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1801.03526v2