Neuro-Symbolic Program Synthesis

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 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.

Cited by in corpus (41)

• Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding
• A Syntactic Neural Model for General-Purpose Code Generation
• RobustFill: Neural Program Learning under Noisy I/O
• Neural-Symbolic Computing: An Effective Methodology for Principled Integration of Machine Learning and Reasoning
• Tree-to-tree Neural Networks for Program Translation
• Learning to Infer and Execute 3D Shape Programs
• Generative Code Modeling with Graphs
• Tree-Transformer: A Transformer-Based Method for Correction of Tree-Structured Data
• Neural Termination Analysis
• Recent Advances in Neural Program Synthesis
• Neural-Guided Symbolic Regression with Asymptotic Constraints
• Synthesize, Execute and Debug: Learning to Repair for Neural Program Synthesis
• SPoC: Search-based Pseudocode to Code
• Learning to Synthesize Programs as Interpretable and Generalizable Policies
• Robot Program Parameter Inference via Differentiable Shadow Program Inversion
• Imitation-Projected Programmatic Reinforcement Learning
• Neutaint: Efficient Dynamic Taint Analysis with Neural Networks
• Neuro-Symbolic Artificial Intelligence: Current Trends
• NAPS: Natural Program Synthesis Dataset
• Synthesizing Action Sequences for Modifying Model Decisions
• BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration
• From Shallow to Deep Interactions Between Knowledge Representation, Reasoning and Machine Learning (Kay R. Amel group)
• Latent Programmer: Discrete Latent Codes for Program Synthesis
• Towards Neural-Guided Program Synthesis for Linear Temporal Logic Specifications
• Data Generation for Neural Programming by Example
• Intelligence, physics and information -- the tradeoff between accuracy and simplicity in machine learning
• Learning Fitness Functions for Machine Programming
• Neural Program Synthesis with a Differentiable Fixer
• Text2App: A Framework for Creating Android Apps from Text Descriptions
• Neural Program Synthesis By Self-Learning
• Architecture for a multilingual Wikipedia
• CounterExample Guided Neural Synthesis
• Learning Execution through Neural Code Fusion
• PLANS: Robust Program Learning from Neurally Inferred Specifications
• Latent Execution for Neural Program Synthesis
• Enhancing Reinforcement Learning with discrete interfaces to learn the Dyck Language
• Type-driven Neural Programming by Example
• Neural Program Generation Modulo Static Analysis
• Towards A Measure Of General Machine Intelligence
• Unsupervised Program Synthesis for Images By Sampling Without Replacement
• Using Meta-Knowledge Mined from Identifiers to Improve Intent Recognition in Neuro-Symbolic Algorithms