Neural Program Synthesis with Priority Queue Training

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.

References in corpus (7)

• Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
• Neural Architecture Search with Reinforcement Learning
• DeepCoder: Learning to Write Programs
• TerpreT: A Probabilistic Programming Language for Program Induction
• Learning Python Code Suggestion with a Sparse Pointer Network
• A parallel corpus of Python functions and documentation strings for automated code documentation and code generation
• AI Programmer: Autonomously Creating Software Programs Using Genetic Algorithms

Cited by in corpus (17)

• Programmatically Interpretable Reinforcement Learning
• Learning to Generalize from Sparse and Underspecified Rewards
• Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients
• Generative Adversarial Self-Imitation Learning
• Guiding Deep Molecular Optimization with Genetic Exploration
• Learning Self-Imitating Diverse Policies
• A Discrete Hard EM Approach for Weakly Supervised Question Answering
• Evolutionary-Neural Hybrid Agents for Architecture Search
• Learning to Synthesize Programs as Interpretable and Generalizable Policies
• The Three Pillars of Machine Programming
• Symbolic Regression via Neural-Guided Genetic Programming Population Seeding
• Neural Architecture Search Over a Graph Search Space
• Learning to learn generative programs with Memoised Wake-Sleep
• Transfer NAS: Knowledge Transfer between Search Spaces with Transformer Agents
• Incorporating domain knowledge into neural-guided search
• Amanuensis: The Programmer's Apprentice
• CounterExample Guided Neural Synthesis