Leveraging Grammar and Reinforcement Learning for Neural Program\n Synthesis

Abstract

Program synthesis is the task of automatically generating a program\nconsistent with a specification. Recent years have seen proposal of a number of\nneural approaches for program synthesis, many of which adopt a sequence\ngeneration paradigm similar to neural machine translation, in which\nsequence-to-sequence models are trained to maximize the likelihood of known\nreference programs. While achieving impressive results, this strategy has two\nkey limitations. First, it ignores Program Aliasing: the fact that many\ndifferent programs may satisfy a given specification (especially with\nincomplete specifications such as a few input-output examples). By maximizing\nthe likelihood of only a single reference program, it penalizes many\nsemantically correct programs, which can adversely affect the synthesizer\nperformance. Second, this strategy overlooks the fact that programs have a\nstrict syntax that can be efficiently checked. To address the first limitation,\nwe perform reinforcement learning on top of a supervised model with an\nobjective that explicitly maximizes the likelihood of generating semantically\ncorrect programs. For addressing the second limitation, we introduce a training\nprocedure that directly maximizes the probability of generating syntactically\ncorrect programs that fulfill the specification. We show that our contributions\nlead to improved accuracy of the models, especially in cases where the training\ndata is limited.\n