Neuro-Symbolic Program Synthesis

By Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, Pushmeet Kohli. 2016

348 citations recorded by the source corpus.

Recent years have seen the proposal of a number of neural architectures for the problem of Program Induction. Given a set of input-output examples, these architectures are able to learn mappings that generalize to new test inputs. While achieving impressive results, these approaches have a number of important limitations: (a) they are computationally expensive and hard to train, (b) a model has to be trained for each task (program) separately, and (c) it is hard to interpret or verify the correctness of the learnt mapping (as it is defined by a neural network). In this paper, we propose a novel technique, Neuro-Symbolic Program Synthesis, to overcome the above-mentioned problems. Once trained, our approach can automatically construct computer programs in a domain-specific language that are consistent with a set of input-output examples provided at test time. Our method is based on two novel neural modules. The first module, called the cross correlation I/O network, given a set of input-output examples, produces a continuous representation of the set of I/O examples. The second module, the Recursive-Reverse-Recursive Neural Network (R3NN), given the continuous representation of the examples, synthesizes a program by incrementally expanding partial programs. We demonstrate the effectiveness of our approach by applying it to the rich and complex domain of regular expression based string transformations. Experiments show that the R3NN model is not only able to construct programs from new input-output examples, but it is also able to construct new programs for tasks that it had never observed before during training.

Subfields: Information Systems, Ocean Engineering, Software, 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 Information Systems

In Ocean Engineering

In Software

In Natural Language Processing

Citations in the corpus

Measuring and Improving BERT’s Mathematical Abilities by Predicting the Order of Reasoning. (2021, background): “(Bobrow, 1964; Char-niak, 1969; Shi et al., 2015; Ling et al., 2017; Amini et al., 2019; Parisotto et al., 2016; Wang et al., 2018; Zou and Lu, 2019) as well as datasets (Ling et al., 2017; Amini et al., 2019; Huang et al., 2016; Saxton et al., 2019) An interesting approach is proposed in (Rabe et…”
SPoC: Search-based Pseudocode to Code (2019, background): “However, most synthesized programs are relatively short, and works that consistently synthesize longer programs are in the domains where the intermediate computation is easier to recover from input and output, such as string [11, 28, 6] and data structure transformations [10, 38].”
A Survey of Machine Learning for Big Code and Naturalness (2017, background): “[151] combine ideas from existing enumerative search techniques with learned heuristics to learn to efficiently synthesize code, usually written within a DSL.”
Neural Execution Engines: Learning to Execute Subroutines (2020, background): “Work in neural program synthesis [16, 18, 5, 1, 6]—which uses neural networks with the goal of generating and ﬁnding a “correct” program such that it will generalize beyond the training distribution—has also employed strong supervision in the form of execution traces [20, 21, 2].”
Neural Logic Machines (2019, methodology): “Neural program induction and synthesis (Neelakantan et al., 2016; Reed & De Freitas, 2016; Kaiser & Sutskever, 2016; Parisotto et al., 2017; Devlin et al., 2017; Bunel et al., 2018; Sun et al., 2018) are recently introduced to solve problems by synthesizing computer programs with neural…”
RobustFill: Neural Program Learning under Noisy I/O (2017, methodology): “In all models described here, P is generated using a sequential RNN, rather than a hierarchical RNN (Parisotto et al., 2017; Tai et al., 2015).”
Reconciling deep learning with symbolic artificial intelligence: representing objects and relations (2019, background): “So another way to impose compositionality directly is to learn programs capable of mapping the input data to the required output (e.g. [27–29]).”
Neural-Symbolic Computing: An Effective Methodology for Principled Integration of Machine Learning and Reasoning (2019, methodology): “In the ﬁeld of Program Induction, neuro-symbolic program synthesis (NSPS) has been proposed to construct computer programs on an incremental fashion using a large amount of input-output samples [33].”
Relational inductive biases, deep learning, and graph networks (2018, background): “…et al., 2016), partial tree traversals in a state-action graph (Guez et al., 2018; Farquhar et al., 2018), hierarchical action policies (Andreas et al., 2017), multi-agent communication channels (Foerster et al., 2016), “capsules” (Sabour et al., 2017), and programs (Parisotto et al., 2017).”
Junction Tree Variational Autoencoder for Molecular Graph Generation (2018, background): “For general purpose tree generation, 2016), but their model is node based whereas ours is based on message passing.”
Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding (2018, background): “Recent papers have explored using program search and neural networks to recover programs from a domain-speciﬁc language [Balog et al., 2017, Neelakantan et al., 2016, Parisotto et al., 2017].”
Learning Deep Generative Models of Graphs (2018, methodology): “To solve this problem, we may use models that sequentially sweep over edges, like (Parisotto et al., 2016), or come up with ways to do coarse-to-ﬁne generation.”
Tree-to-tree Neural Networks for Program Translation (2018, methodology): “A recent line of research study using neural networks for code generation [5, 10, 25, 19, 26, 32].”
Neural Program Synthesis with Priority Queue Training (2018, background): “…from input-output examples (Riedel et al., 2016; Bunel et al., 2016; Balog et al., 2017; Parisotto et al., 2016) and even from unstructured text (Parisotto et al., 2016), but often using restrictive programming syntax and requiring supervisory signal in the form of ground-truth programs or…”
Neural Program Repair by Jointly Learning to Localize and Repair (2019, background): “…& de Freitas, 2015; Cai et al., 2017; Wang et al., 2018), and graphs (Allamanis et al., 2018) have been proposed for a variety of tasks including repair (Devlin et al., 2017b; Allamanis et al., 2018), optimization (Bunel et al., 2017), and synthesis (Parisotto et al., 2017; Devlin et al., 2017a).”
Syntax-Directed Variational Autoencoder for Structured Data (2018, methodology): “Pick node v ( t ) ∈ Fr ( T ( t ) ) where its attributes needed are either satisﬁed, or are stochastic attributes that should be sampled ﬁrst according to Bernoulli distribution B ( ·| v ( t ) , T ( t ) ) ; , where v ( t ) . symbol = α ( t ) , and , expand the nonterminal with production rules deﬁned”
Natural Language to Structured Query Generation via Meta-Learning (2018, methodology): “eitas,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) aim to generate explicit programs and then execute them to get output. The l”