Program synthesis is the task of automatically generating a program consistent with
 a specification. Recent years have seen proposal of a number of neural approaches
 for program synthesis, many of which adopt a sequence generation paradigm similar
 to neural machine translation, in which sequence-to-sequence models are trained to
 maximize the likelihood of known reference programs. While achieving impressive
 results, this strategy has two key limitations. First, it ignores Program Aliasing: the
 fact that many different programs may satisfy a given specification (especially with
 incomplete specifications such as a few input-output examples). By maximizing
 the likelihood of only a single reference program, it penalizes many semantically
 correct programs, which can adversely affect the synthesizer performance. Second,
 this strategy overlooks the fact that programs have a strict syntax that can be
 efficiently checked. To address the first limitation, we perform reinforcement
 learning on top of a supervised model with an objective that explicitly maximizes
 the likelihood of generating semantically correct programs. For addressing the
 second limitation, we introduce a training procedure that directly maximizes the
 probability of generating syntactically correct programs that fulfill the specification.
 We show that our contributions lead to improved accuracy of the models, especially
 in cases where the training data is limited. The task of program synthesis is to automatically generate a program that is consistent with a specification such as a set of input-output examples, and has been studied since the early days of Artificial Intelligence BID34 . There has been a lot of recent progress made on neural program induction, where novel neural architectures inspired from computation modules such as RAM, stack, CPU, turing machines, and GPU BID10 BID17 BID20 BID11 BID31 BID18 have been proposed to train these architectures in an end-to-end fashion to mimic the behavior of the desired program. While these approaches have achieved impressive results, they do not return explicit interpretable programs, tend not to generalize well on inputs of arbitrary length, and require a lot of examples and computation for learning each program. To mitigate some of these limitations, neural program synthesis approaches BID16 BID28 BID7 have been recently proposed that learn explicit programs in a Domain-specific language (DSL) from as few as five input-output examples. These approaches, instead of using a large number of input-output examples to learn a single program, learn a large number of different programs, each from just a few input-output examples. During training, the correct program is provided as reference, but at test time, the learnt model generates the program from only the input-output examples.While neural program synthesis techniques improve over program induction techniques in certain domains, they suffer from two key limitations. First, these approaches use supervised learning with reference programs and suffer from the problem of Program Aliasing: For a small number of input-output examples, there can be many programs that correctly transform inputs to outputs. The problem is the discrepancy between the single supervised reference program and the multitude of correct programs. FIG0 shows an example of this: if maximizing the probability of ground truth program, predicting Program B would be assigned a high loss even though the two programs are semantically equivalent for the input-output example. Maximum likelihood training forces the model to learn to predict ground truth programs, which is different from the true objective of program synthesis: predicting any consistent program. To address this problem, we alter the optimization objective: instead of maximum likelihood, we use policy gradient reinforcement learning to directly encourage generation of any program that is consistent with the given examples.The second limitation of neural program synthesis techniques based on sequence generation paradigm BID7 ) is that they often overlook the fact that programs have a strict syntax, which can be checked efficiently. Similarly to the work of BID28 , we explore a method for leveraging the syntax of the programming language in order to aggressively prune the exponentially large search space of possible programs. In particular, not all sequences of tokens are valid programs and syntactically incorrect programs can be efficiently ignored both during training and at test time. A syntax checker is an additional form of supervision that may not always be present.To address this limitation, we introduce a neural architecture that retains the benefits of aggressive syntax pruning, even without assuming access to the definition of the grammar made in previous work BID28 . This model is jointly conditioned on syntactic and program correctness, and can implicitly learn the syntax of the language while training.We demonstrate the efficacy of our approach by developing a neural program synthesis system for the Karel programming language BID29 , an educational programming language, consiting of control flow constructs such as loops and conditionals, making it more complex than the domains tackled by previous neural program synthesis works.This paper makes the following key contributions:• We show that Reinforcement Learning can directly optimize for generating any consistent program and improves performance compared to pure supervised learning.• We introduce a method for pruning the space of possible programs using a syntax checker and show that explicit syntax checking helps generate better programs.• In the absence of a syntax checker, we introduce a model that jointly learns syntax and the production of correct programs. We demonstrate this model improves performance in instances with limited training data.
Using the DSL grammar and reinforcement learning to improve synthesis of programs with complex control flow.
{"src": "scitldr-AIC_train", "paper_id": "H1Xw62kRZ"}