Strong Generalization and Efficiency in Neural Programs
arXiv:2007.03629
Abstract
We study the problem of learning efficient algorithms that strongly generalize in the framework of neural program induction. By carefully designing the input / output interfaces of the neural model and through imitation, we are able to learn models that produce correct results for arbitrary input sizes, achieving strong generalization. Moreover, by using reinforcement learning, we optimize for program efficiency metrics, and discover new algorithms that surpass the teacher used in imitation. With this, our approach can learn to outperform custom-written solutions for a variety of problems, as we tested it on sorting, searching in ordered lists and the NP-complete 0/1 knapsack problem, which sets a notable milestone in the field of Neural Program Induction. As highlights, our learned model can perform sorting perfectly on any input data size we tested on, with complexity, whilst outperforming hand-coded algorithms, including quick sort, in number of operations even for list sizes far beyond those seen during training.
References in corpus (14)
- Neural Message Passing for Quantum Chemistry
- Dota 2 with Large Scale Deep Reinforcement Learning
- Gated Graph Sequence Neural Networks
- Neural Programmer-Interpreters
- Neural GPUs Learn Algorithms
- Order Matters: Sequence to sequence for sets
- Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets
- Reinforcement Learning Neural Turing Machines - Revised
- Making Neural Programming Architectures Generalize via Recursion
- TerpreT: A Probabilistic Programming Language for Program Induction
- Neural Programmer: Inducing Latent Programs with Gradient Descent
- Learning Efficient Algorithms with Hierarchical Attentive Memory
- Learning Compositional Neural Programs with Recursive Tree Search and Planning
- Learning to superoptimize programs