Towards Synthesizing Complex Programs from Input-Output Examples

  • 2018-02-11 04:33:30
  • Xinyun Chen, Chang Liu, Dawn Song
  • 0

Abstract

In recent years, deep learning techniques have been developed to improve theperformance of program synthesis from input-output examples. Albeit itssignificant progress, the programs that can be synthesized by state-of-the-artapproaches are still simple in terms of their complexity. In this work, we movea significant step forward along this direction by proposing a new class ofchallenging tasks in the domain of program synthesis from input-outputexamples: learning a context-free parser from pairs of input programs and theirparse trees. We show that this class of tasks are much more challenging thanpreviously studied tasks, and the test accuracy of existing approaches isalmost 0%. We tackle the challenges by developing three novel techniques inspired bythree novel observations, which reveal the key ingredients of using deeplearning to synthesize a complex program. First, the use of anon-differentiable machine is the key to effectively restrict the search space.Thus our proposed approach learns a neural program operating a domain-specificnon-differentiable machine. Second, recursion is the key to achievegeneralizability. Thus, we bake-in the notion of recursion in the design of ournon-differentiable machine. Third, reinforcement learning is the key to learnhow to operate the non-differentiable machine, but it is also hard to train themodel effectively with existing reinforcement learning algorithms from a coldboot. We develop a novel two-phase reinforcement learning-based searchalgorithm to overcome this issue. In our evaluation, we show that using ournovel approach, neural parsing programs can be learned to achieve 100% testaccuracy on test inputs that are 500x longer than the training samples.

 

Quick Read (beta)

loading the full paper ...