Neural Program Meta-Induction

By Jacob Devlin, Rudy Bunel, Rishabh Singh, Matthew J. Hausknecht, Pushmeet Kohli. 2017

74 citations recorded by the source corpus.

Most recently proposed methods for Neural Program Induction work under the assumption of having a large set of input/output (I/O) examples for learning any underlying input-output mapping. This paper aims to address the problem of data and computation efficiency of program induction by leveraging information from related tasks. Specifically, we propose two approaches for cross-task knowledge transfer to improve program induction in limited-data scenarios. In our first proposal, portfolio adaptation, a set of induction models is pretrained on a set of related tasks, and the best model is adapted towards the new task using transfer learning. In our second approach, meta program induction, a $k$-shot learning approach is used to make a model generalize to new tasks without additional training. To test the efficacy of our methods, we constructed a new benchmark of programs written in the Karel programming language. Using an extensive experimental evaluation on the Karel benchmark, we demonstrate that our proposals dramatically outperform the baseline induction method that does not use knowledge transfer. We also analyze the relative performance of the two approaches and study conditions in which they perform best. In particular, meta induction outperforms all existing approaches under extreme data sparsity (when a very small number of examples are available), i.e., fewer than ten. As the number of available I/O examples increase (i.e. a thousand or more), portfolio adapted program induction becomes the best approach. For intermediate data sizes, we demonstrate that the combined method of adapted meta program induction has the strongest performance.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Natural Language Processing

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 Computer Vision and Pattern Recognition

In Natural Language Processing

Citations in the corpus

Large Language Models Are Human-Level Prompt Engineers (2022, methodology): “Using inference models is a standard practice to speed up the search by restricting the search space to a limited space of possible expressions (Menon et al., 2013; Lee et al., 2018; Devlin et al., 2017; Ellis et al., 2021).”
Conditional Neural Processes (2018, methodology): “Recently meta-learning has been applied to a wide range of tasks like RL (Wang et al., 2016; Finn et al., 2017) or program induction (Devlin et al., 2017).”
Neural Processes (2018, background): “…but there is a large literature of similar models for classiﬁcation (Koch et al., 2015; Santoro et al., 2016), reinforcement learning (Wang et al., 2016), parameter update (Finn et al., 2017; 2018), natural language processing (Bowman et al., 2015) and program induction (Devlin et al., 2017).”
Meta-Learning in Neural Networks: A Survey (2020, background): “Many more tasks have since been tackled, including text classification [135], neural program induction [263] and synthesis [264], English to SQL program synthesis [265], text-based relationship graph extractor [266], machine translation [267], and quickly adapting to new personas in dialogue”
Natural Language to Structured Query Generation via Meta-Learning (2018, background): “Program Induction / Synthesis Program induction (Reed and De Freitas, 2016; Neelakantan et al., 2015; Graves et al., 2014; Yin et al., 2015; Devlin et al., 2017) aims to infer latent programs given input/output examples, while program synthesis models (Zhong et al., 2017; Parisotto et al., 2017)…”
Learning to Synthesize Programs as Interpretable and Generalizable Policies (2021, background): “[25] Jacob Devlin, Rudy R Bunel, Rishabh Singh, Matthew Hausknecht, and Pushmeet Kohli.”
NAPS: Natural Program Synthesis Dataset (2018, background): “…on program synthesis from examples for single domain of programming: string transformations (Robust-Fill (Devlin et al., 2017b), Neuro-Symbolic Program Synthesis (Parisotto et al., 2016) and Deep API Programmer (Bhupatiraju et al., 2017)) or Karel (Devlin et al. (2017a), Bunel et al. (2018)).”
Synthetic Data for Deep Learning (2019, background): “The basic idea of teaching a machine learning model to program can be broadly divided into two subfields: program induction aims to train an end-to-end differentiable model to capture an algorithm [143], while program synthesis tries to teach a model the semantics of a domain-specific language (DSL)”
Program Synthesis and Semantic Parsing with Learned Code Idioms (2019, background): “In the last decade, it has advanced dramatically thanks to the novel neural and neuro-symbolic techniques [5, 10, 19], ﬁrst mass-market applications [28], and massive datasets [9, 39, 41].”
Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis (2018, methodology): “To mitigate some of these limitations, neural program synthesis approaches (Johnson et al., 2017; Parisotto et al., 2017; Devlin et al., 2017b) have been recently proposed that learn explicit programs in a Domain-speciﬁc language (DSL) from as few as ﬁve input-output examples.”
Learning Compositional Neural Programs with Recursive Tree Search and Planning (2019, background): “DeepCoder [Balog et al., 2016] and RobustFill [Devlin et al., 2017b] learn in a supervised manner to generate programs for list and string manipulation using domain speciﬁc languages.”
IReEn: Iterative Reverse-Engineering of Black-Box Functions via Neural Program Synthesis (2020, methodology): “One type of these approaches called neural program induction involves learning a machine learning model to mimic the behavior of the target program (Graves et al., 2014; Johnson et al., 2017; Devlin et al., 2017a).”
DreamCoder: growing generalizable, interpretable knowledge with wake–sleep Bayesian program learning (2020, background): “Yet for all these strengths, and successful applications in a number of domains ( 3–9 ), program induction has had relatively limited impact in AI.”
Execution-Guided Neural Program Synthesis (2018, methodology): “We evaluate our techniques on the Karel task (Bunel et al., 2018; Devlin et al., 2017a), the largest publicly available benchmark for input-output program synthesis, on which the most performant model in the past can achieve only an accuracy of around 77% (Bunel et al., 2018).”
Improving Molecular Design by Stochastic Iterative Target Augmentation (2020, methodology): “Program synthesis is the task of generating a program (using domain-speciﬁc language) based on given input-output speciﬁcations (Bunel et al., 2018; Gulwani, 2011; Devlin et al., 2017).”
Improving Neural Program Synthesis with Inferred Execution Traces (2018, methodology): “Several recent papers have proposed neural network-based approaches to program synthesis from input/output examples [Parisotto et al., 2017, Devlin et al., 2017b, Bunel et al., 2018].”
DreamCoder: bootstrapping inductive program synthesis with wake-sleep library learning (2021, background): “All such systems predict a distribution over programs conditioned on a specification, ranging from unigram distributions [34], to bigram-like ones [29, 30], to neural autoregressive models [12].”