Neural Program Synthesis with Priority Queue Training

By Daniel A. Abolafia, Mohammad Norouzi, Quoc V. Le. 2018

69 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Information Systems, Prompting & Reasoning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Prompting & Reasoning

Citations in the corpus

A Discrete Hard EM Approach for Weakly Supervised Question Answering (2019, background): “…weak supervision, including beam-based MML (MML which keeps a beam during training), conventional hard EM 8 , REINFORCE (Williams, 1992), iterative ML (Liang et al., 2017; Abolaﬁa et al., 2018) and a family of MAPO (Memory-augmented policy optimization) (Liang et al., 2018; Agarwal et al., 2019).”
Evolutionary-Neural Hybrid Agents for Architecture Search (2018, neutral): “Priority Queue Training (PQT) [1].”
Programmatically Interpretable Reinforcement Learning (2018, methodology): “There have also been some recent approaches to use RL for learning to search programs in DSLs (Bunel et al., 2018; Abolafia et al., 2018).”
Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing (2018, background): “rams may correspond to the correct functional form. Unfortunately, relying on policy samples to explore the space often leads to forgetting a high reward trajectory unless it is re-sampled frequently [26, 3]. 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, Canada. ”
Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients (2019, methodology): “within AutoML that use an autoregressive RNN to define a distribution over discrete objects and use reinforcement learning to optimize this distribution under a black-box performance metric (Zoph & Le, 2017; Ramachandran et al., 2017; Bello et al., 2017; Abolafia et al., 2018).”
Leveraging Language to Learn Program Abstractions and Search Heuristics (2021, methodology): “Our work draws on recent program synthesis approaches that learn to synthesize programs from examples using neural models to guide search (Gulwani et al., 2015; Balog et al., 2016; Parisotto et al., 2016; Devlin et al., 2017; Polosukhin & Skidanov, 2018; Abolafia et al., 2018; Nye et al., 2019; Elli”
Learning to Synthesize Programs as Interpretable and Generalizable Policies (2021, background): “[47] Daniel A Abolafia, Mohammad Norouzi, Jonathan Shen, Rui Zhao, and Quoc V Le.”
Learning to Generalize from Sparse and Underspecified Rewards (2019, background): “…> 1 , the curve corresponding to IML is above the curve corresponding to MAPO, especially on W IKI SQL. Examining the details of the experiments in Abolaﬁa et al. (2018), we realize that their program synthesis tasks are primarily about discovering an individual program that is consistent with a…”