Making Neural Programming Architectures Generalize via Recursion

Abstract

Empirically, neural networks that attempt to learn programs from data have exhibited poor generalizability. Moreover, it has traditionally been difficult to reason about the behavior of these models beyond a certain level of input complexity. In order to address these issues, we propose augmenting neural architectures with a key abstraction: recursion. As an application, we implement recursion in the Neural Programmer-Interpreter framework on four tasks: grade-school addition, bubble sort, topological sort, and quicksort. We demonstrate superior generalizability and interpretability with small amounts of training data. Recursion divides the problem into smaller pieces and drastically reduces the domain of each neural network component, making it tractable to prove guarantees about the overall system's behavior. Our experience suggests that in order for neural architectures to robustly learn program semantics, it is necessary to incorporate a concept like recursion.

Published in ICLR 2017

Cited by in corpus (39)

• Deep Reinforcement Learning: An Overview
• Measuring Coding Challenge Competence With APPS
• Relational Neural Expectation Maximization: Unsupervised Discovery of Objects and their Interactions
• Learning to Infer and Execute 3D Shape Programs
• Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples
• Dynamic Neural Program Embedding for Program Repair
• ReviewRobot: Explainable Paper Review Generation based on Knowledge Synthesis
• Neural Program Synthesis with Priority Queue Training
• Supervising strong learners by amplifying weak experts
• Learning compositionally through attentive guidance
• Strong Generalization and Efficiency in Neural Programs
• Learning Compositional Neural Programs with Recursive Tree Search and Planning
• Estimate and Replace: A Novel Approach to Integrating Deep Neural Networks with Existing Applications
• Recent Advances in Neural Program Synthesis
• CmnRec: Sequential Recommendations with Chunk-accelerated Memory Network
• Learning Scalable and Precise Representation of Program Semantics
• Lifelong Learning of Compositional Structures
• Building a Neural Semantic Parser from a Domain Ontology
• Neural network gradient-based learning of black-box function interfaces
• Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networks
• Learning to Synthesize Programs as Interpretable and Generalizable Policies
• Learning to Recombine and Resample Data for Compositional Generalization
• AutoCorrect: Deep Inductive Alignment of Noisy Geometric Annotations
• Compositional Generalization via Neural-Symbolic Stack Machines
• Evolutionary Training and Abstraction Yields Algorithmic Generalization of Neural Computers
• Compositional Generalization with Tree Stack Memory Units
• The Three Pillars of Machine Programming
• Neural Status Registers
• Learning Fitness Functions for Machine Programming
• Pointer Value Retrieval: A new benchmark for understanding the limits of neural network generalization
• Explaining Transition Systems through Program Induction
• Learning an Executable Neural Semantic Parser
• Improving the Universality and Learnability of Neural Programmer-Interpreters with Combinator Abstraction
• Using Program Induction to Interpret Transition System Dynamics
• Inductive Visual Localisation: Factorised Training for Superior Generalisation
• Amanuensis: The Programmer's Apprentice
• Progress Extrapolating Algorithmic Learning to Arbitrary Sequence Lengths
• Type-driven Neural Programming by Example
• Neural Program Meta-Induction