PaperlayerView exact revision on arXiv

Source-linked AI summary

Neuro-Symbolic Program Synthesis

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

arXiv:1611.01855v1cs.AIcs.PL

TL;DR

Neural program-induction methods are costly, task-specific, and difficult to interpret or verify. NSPS combines a cross-correlation I/O encoder with R3NN to incrementally synthesize DSL programs from examples, solving unseen tasks and FlashFill benchmarks.

  • Problem

    Existing neural program-induction approaches are computationally expensive, hard to train, task-specific, and difficult to interpret or verify.

  • Method

    NSPS encodes input-output examples and uses R3NN to incrementally expand partial programs in a domain-specific language without explicit search.

  • Results

    63% of unseen tasks are solved from the model, 94% using 100 samples, and 38% of 238 real-world FlashFill benchmarks are learned.

  • Takeaways & Limitations

    NSPS constructs programs for new examples and can synthesize programs for tasks absent from training.

  • Takeaways & Limitations

    The system cannot currently learn benchmarks requiring four or more Concat operations because training does not scale well to larger programs.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper addresses limitations of neural program-induction methods by introducing NSPS, which incrementally synthesizes DSL programs from input-output examples. It evaluates the approach on regular-expression string transformations, including tasks unseen during training.

  • Existing neural program-induction methods are computationally expensive, difficult to train, task-specific, and hard to interpret or verify.
  • NSPS generates programs incrementally without explicit search and constructs programs consistent with test-time input-output examples.
  • The method combines a cross-correlation I/O network with an R3NN that expands partial programs in a DSL.
  • NSPS is evaluated on regular-expression-based string transformations using a DSL based on FlashFill.
  • 63% of previously unseen tasks are solved from the model, rising to 94% when 100 program samples are taken; 38% of 238 FlashFill benchmarks are learned.

2 PROBLEM DEFINITION

The problem is to construct a program in a given DSL that conforms to a set of input-output examples. The paper illustrates this formulation with FlashFill-style string transformations and a regular-expression DSL.

  • Given a DSL L and input-output examples, the synthesis algorithm must return a program P ∈ L that conforms to every example.
  • A DSL program transforms an input string into an output string using concatenated constants and substring expressions.
  • Substring boundaries can use constant positions or token matches based on regular-expression categories and direction.
  • The illustrated name transformation concatenates the last name, punctuation, and the first character of the input.

3 OVERVIEW OF OUR APPROACH

The approach learns a generative model over DSL programs conditioned on input-output examples, then constructs programs by expanding partial grammar derivations. Training uses sampled programs and corresponding well-formed inputs.

  • The system is trained end-to-end on DSL programs paired with input-output examples and generates programs conditioned on examples.
  • Instead of randomly searching grammar derivations, the model learns how to expand partial derivations into programs.
  • R3NN encodes partial trees so each node carries global information about the tree during program generation.
  • The input-output encoder can use LSTM representations or cross-correlation between input and output string representations.

4 TREE-STRUCTURED GENERATION MODEL

The R3NN generates DSL programs by incrementally expanding partial program trees, using recursive and reverse-recursive passes to give leaves global, position-sensitive tree representations.

  • Partial program trees: A partial program tree contains symbol leaves and production-rule inner nodes, becoming a complete program when all leaves are terminals.Expansions apply valid DSL production rules to selected non-terminal leaves.
  • R3NN representations: The R3NN maintains distributed representations for grammar symbols and production rules, with rule networks encoding right-hand-side symbols into left-hand-side representations.Reverse rule networks map left-hand-side representations back to right-hand-side child representations.
  • Pass structure: Figure 3 depicts the initial recursive pass and the reverse-recursive pass whose input is the preceding pass’s output.The two passes together provide the tree-wide information used by the generation model.
  • Recursive pass: The recursive bottom-to-top pass computes a global root representation from the representations of nodes throughout the tree.This pass applies the production-rule networks from right-hand-side nodes upward to the root.
  • Reverse-recursive pass: The reverse-recursive pass propagates root information back toward leaves, restoring tree-position information lost in the root representation.Leaves with the same symbol receive different representations when they occupy different tree positions.
  • Expansion probabilities: Expansion scores combine each leaf’s global representation with the representation of its production rule, producing probabilities over valid expansions.An additional bidirectional LSTM can process global leaf representations before score calculation.

5 CONDITIONING WITH INPUT/OUTPUT EXAMPLES

The system encodes input-output examples to condition R3NN program generation, emphasizing substring alignment while comparing several encoder designs and conditioning locations.

  • Encoding requirements: String-transformation programs must identify constant output strings and input substring indices, with the latter potentially defined by regular expressions.The DSL assumes a fixed finite universe of possible constant strings and focuses learning on substring indices.
  • Motivation: Unlike hand-designed substring extraction in earlier systems, the proposed neural encoders learn continuous representations of likely regular expressions from input-output strings.This replaces manually designed extraction procedures with learned architectures.
  • Baseline LSTM encoder: The baseline encoder processes each input-output string pair with separate deep bidirectional LSTMs and concatenates their hidden representations.It concatenates the topmost hidden representation at every time step into a feature vector for each pair.
  • Baseline LSTM encoder: The baseline concatenates pair encodings into one I/O-set vector but has little prior knowledge of string operations, making regex-based substring indices difficult to discover.This limitation motivates a cross-correlation encoder.
  • Cross-correlation encoder: The cross-correlation encoder slides output representations over input representations, computes dot products across overlapping positions, and aggregates them to expose copied-substring alignments.Its features represent possible input-output alignments across example pairs.
  • Encoder variants: The study also evaluates diffused, LSTM-sum, and augmented diffused cross-correlation variants that retain or further process alignment features.These variants respectively concatenate timestep features, apply an LSTM per alignment, or combine alignment outputs with character embeddings.
  • Conditioning locations: Example encodings can condition R3NN generation before the recursive pass, after the reverse-recursive pass, or at the root.Pre-conditioning concatenates example encodings with tree-leaf representations before bottom-up processing.
  • Conditioning locations: Pre-conditioning performed better than root- or post-conditioning, while conditioning at all three locations added no significant improvement over pre-conditioning alone.The experiments therefore report models using only pre-conditioning.

6 EXPERIMENTS

Experiments evaluate generalization, input/output encoders, sequential versus tree-structured generation, sampling, and FlashFill benchmark performance. NSPS generalizes to unseen program structures but is constrained by program size and sampling requirements.

  • Experimental setup: Training programs are limited to 13 instructions because longer programs can be composed from subprograms of at most 13 instructions.
  • Experimental setup: The evaluation distinguishes input/output generalization from program generalization, with test cases using unseen program trees and unseen input/output pairs.
  • 6.2 EXAMPLE ENCODING: The LSTM and augmented diffused cross-correlation encoders perform best, while summed cross-correlation loses positional information and performs poorly.The LSTM encoder finds nearly 88% of programs without explicitly built-in prior knowledge.
  • 6.3 IO2SEQ: At 100 samples, io2seq reaches around 42% accuracy versus 91% for R3NN on latent test functions.io2seq predicts linearized trees symbol-by-symbol, including parentheses, requiring about 100 samples for length-13 programs; R3NN requires no more than 13.
  • 6.4 EFFECT OF BACKTRACKING SEARCH: By 300 samples, R3NN approaches perfect test-set accuracy, while sampling performance increases until roughly 2000 samples before leveling off.The pattern suggests the model identifies suitable program types but may remain uncertain about details such as the regular expression.
  • 6.5 FLASHFILL BENCHMARKS: The model solves 91 FlashFill tasks, or 38.2%, and solves 82.7% of the 110 benchmarks requiring programs of at most 13 instructions.The smallest programs needed for the benchmarks range from 4 to 63 instructions, and only 13% are solved with 10 samples.
  • 6.5 FLASHFILL BENCHMARKS: Additional input-output examples reduce FlashFill performance to about 29%, possibly because they constrain the consistent-program space or confuse the encoder.
  • 6.5 FLASHFILL BENCHMARKS: The system solves many benchmarks requiring up to three Concat operations but cannot learn benchmarks requiring four or more.Examples include a six-argument name-combination task and a five-argument phone-number transformation task.

7 RELATED WORK

Related work spans neural program-induction architectures, DSL-based program search, probabilistic code models, and tree-structured neural networks. NSPS differs by learning an end-to-end, semantics-oriented generator for DSL programs.

  • Neural program induction: Neural program-induction methods use differentiable operations inspired by computation modules such as Turing machines, RAM, and stacks.
  • DSL-based synthesis: DSL-based synthesis has been applied to bitvectors, Excel macros, superoptimization, protocol synthesis, and loop-free programs.
  • DSL-based synthesis: Prior DSL synthesis methods search large hypothesis spaces using enumerative, stochastic, constraint-based, or version-space algebra techniques.
  • Neuro-symbolic synthesis: NSPS is trained end-to-end, whereas previous techniques require substantial manual effort to design efficient-search heuristics.
  • Probabilistic code models: Probabilistic code models typically capture syntactic properties, while NSPS also attempts to capture semantics for learning the desired program.
  • Tree-structured neural networks: R3NN is related to tree and graph neural networks, especially Inside-Outside Recursive Neural Networks that incrementally generate parse trees using global leaf representations.

8 CONCLUSION

NSPS incrementally constructs programs from input-output examples, including programs not seen during training. Its supervised-learning setup assumes target programs are available during training, motivating reinforcement-learning alternatives when only an oracle is available.

  • 8 CONCLUSION: NSPS incrementally constructs full program trees from input-output examples using the Recursive-Reverse-Recursive Neural Network.The R3NN encodes and expands a partial program tree into a full program tree.
  • 8 CONCLUSION: The method remains effective when the target program was not seen during training.
  • 8 CONCLUSION: The supervised-learning formulation assumes target programs during training, whereas oracle-only settings may require reinforcement learning.In oracle-only scenarios, an oracle returns the desired output for an input without providing target programs.

A DOMAIN-SPECIFIC LANGUAGE FOR STRING TRANSFORMATIONS

The DSL evaluates string-transformation programs by recursively combining constants and substrings selected through position logics. Position logics locate regular-expression matches relative to the beginning or end of the input string.

  • A DOMAIN-SPECIFIC LANGUAGE FOR STRING TRANSFORMATIONS: A Concat expression concatenates the recursively evaluated constituent substring expressions.
  • A DOMAIN-SPECIFIC LANGUAGE FOR STRING TRANSFORMATIONS: A substring expression evaluates left and right position logics, then returns the corresponding slice v[p1..p2].The slice starts at the left index inclusively and ends at the right index exclusively.
  • A DOMAIN-SPECIFIC LANGUAGE FOR STRING TRANSFORMATIONS: Position logic (r, k, Start) returns the Start of the kth regular-expression match from the beginning or end of v.Positive k counts matches from the beginning, while negative k counts from the end.
Loading 1611.01855v1…