NEURAL-GUIDED DEDUCTIVE SEARCH FOR REAL- TIME PROGRAM SYNTHESIS FROM EXAMPLES
Synthesizing user-intended programs from a small number of input-output examples is a challenging problem with several important applications like spreadsheet manipulation, data wrangling and code refactoring. Existing synthesis systems either completely rely on deductive logic techniques that are extensively handengineered or on purely statistical models that need massive amounts of data, and in general fail to provide real-time synthesis on challenging benchmarks. In this work, we propose Neural Guided Deductive Search (NGDS), a hybrid synthesis technique that combines the best of both symbolic logic techniques and statistical models. Thus, it produces programs that satisfy the provided specifications by construction and generalize well on unseen examples, similar to data-driven systems. Our technique effectively utilizes the deductive search framework to reduce the learning problem of the neural component to a simple supervised learning setup. Further, this allows us to both train on sparingly available real-world data and still leverage powerful recurrent neural network encoders. We demonstrate the effectiveness of our method by evaluating on real-world customer scenarios by synthesizing accurate programs with up to 12× speed-up compared to state-of-the-art systems.
The paper presents a branch-and-bound approach to learn good programs
(consistent with data, expected to generalise well), where an LSTM is
used to predict which branches in the search tree should lead to good
programs (at the leaves of the search tree). The LSTM learns from
inputs of program spec + candidate branch (given by a grammar
production rule) and ouputs of quality scores for programms. The issue
of how greedy to be in this search is addressed.
In the authors' set up we simply assume we are given a 'ranking
function' h as an input (which we treat as black-box). In practice
this will simply be a guess (perhaps a good educated one) on which
programs will perform correctly on future data. As the authors
indicate, a more ambitious paper would consider learning h, rather
than assuming it as a given.
The paper has a number of positive features. It is clearly written
(without typo or grammatical problems). The empirical evaluation
against PROSE is properly done and shows the presented method working
as hoped. This was a competent approach to an interesting (real)
problem. However, the 'deep learning' aspect of the paper is not
prominent: an LSTM is used as a plug-in and that is about it. Also,
although the search method chosen was reasonable, the only real
innovation here is to use the LSTM to learn a search heuristic.
The authors do not explain what "without attention" means.
I think the authors should mention the existence of (logic) program
synthesis using inductive logic programming. There are also (closely
related) methods developed by the LOPSTR (logic-based program
synthesis and transformation) community. Many of the ideas here are
reminiscent of methods existing in those communities (e.g. top-down search
with heuristics). The use of a grammar to define the space of programs
is similar to the "DLAB" formalism developed by researchers at KU
Leuven.
ADDED AFTER REVISIONS/DISCUSSIONS
The revised paper has a number of improvements which had led me to give it slightly higher rating.