Under review as a conference paper at ICLR 2017
NEURO-SYMBOLIC PROGRAM SYNTHESIS
Emilio Parisotto
1,2
, Abdel-rahman Mohamed
1
, Rishabh Singh
1
,
Lihong Li
1
, Dengyong Zhou
1
, Pushmeet Kohli
1
1
Microsoft Research, USA
2
Carnegie Mellon University, USA
eparisot@andrew.cmu.edu , {asamir,risin,lihongli,denzho,pkohli}@microsoft.com
ABSTRACT
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 ar-
chitectures are able to learn mappings that generalize to new test inputs. While
achieving impressive results, these approaches have a number of important limi-
tations: (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 au-
tomatically 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 corre-
lation 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 pro-
grams. We demonstrate the effectiveness of our approach by applying it to the
rich and complex domain of regular expression based string transformations. Ex-
periments 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.
1 INTRODUCTION
The act of programming, i.e., developing a procedure to accomplish a task, is a remarkable demon-
stration of the reasoning abilities of the human mind. Expectedly, Program Induction is considered
as one of the fundamental problems in Machine Learning and Artificial Intelligence. Recent progress
on deep learning has led to the proposal of a number of promising neural architectures for this prob-
lem. Many of these models are inspired from computation modules (CPU, RAM, GPU) (Graves
et al., 2014; Kurach et al., 2015; Reed & de Freitas, 2015; Neelakantan et al., 2015) or common
data structures used in many algorithms (stack) (Joulin & Mikolov, 2015). A common thread in this
line of work is to specify the atomic operations of the network in some differentiable form, allowing
efficient end-to-end training of a neural controller, or to use reinforcement learning to make hard
choices about which operation to perform. While these results are impressive, 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). While some recently
proposed methods (Kurach et al., 2015; Gaunt et al., 2016; Riedel et al., 2016; Bunel et al., 2016)
do learn interpretable programs, they still need to learn a separate neural network model for each
individual task.
Motivated by the need for model interpretability and scalability to multiple tasks, we address the
problem of Program Synthesis. Program Synthesis, the problem of automatically constructing pro-
grams that are consistent with a given specification, has long been a subject of research in Computer
Science (Biermann, 1978; Summers, 1977). This interest has been reinvigorated in recent years on
1
arXiv:1611.01855v1 [cs.AI] 6 Nov 2016
剩余13页未读，继续阅读
资源评论
