Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis

Abstract

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.

arXiv commentICLR 2018

Cited by in corpus (25)

• WILDS: A Benchmark of in-the-Wild Distribution Shifts
• Programmatically Interpretable Reinforcement Learning
• Synthesize, Execute and Debug: Learning to Repair for Neural Program Synthesis
• Synthesizing explainable counterfactual policies for algorithmic recourse with program synthesis
• Lifelong Learning of Compositional Structures
• Learning to Synthesize Programs as Interpretable and Generalizable Policies
• Synthesizing Action Sequences for Modifying Model Decisions
• Interpretable Model-based Hierarchical Reinforcement Learning using Inductive Logic Programming
• BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration
• From Shallow to Deep Interactions Between Knowledge Representation, Reasoning and Machine Learning (Kay R. Amel group)
• Neural Learning of One-of-Many Solutions for Combinatorial Problems in Structured Output Spaces
• Program Synthesis with Best-First Bottom-Up Search
• Learning Fitness Functions for Machine Programming
• Program Synthesis Guided Reinforcement Learning for Partially Observed Environments
• Towards Modular Algorithm Induction
• Neural Program Synthesis By Self-Learning
• CounterExample Guided Neural Synthesis
• Hierarchical Variational Imitation Learning of Control Programs
• DeepQAMVS: Query-Aware Hierarchical Pointer Networks for Multi-Video Summarization
• Learning to Combine Per-Example Solutions for Neural Program Synthesis
• Synthesizing Tasks for Block-based Programming
• Latent Execution for Neural Program Synthesis
• Towards A Measure Of General Machine Intelligence
• On Adversarial Robustness of Synthetic Code Generation
• Dual Reinforcement-Based Specification Generation for Image De-Rendering