Neural GPUs Learn Algorithms
arXiv:1511.08228
Abstract
Learning an algorithm from examples is a fundamental problem that has been widely studied. Recently it has been addressed using neural networks, in particular by Neural Turing Machines (NTMs). These are fully differentiable computers that use backpropagation to learn their own programming. Despite their appeal NTMs have a weakness that is caused by their sequential nature: they are not parallel and are are hard to train due to their large depth when unfolded. We present a neural network architecture to address this problem: the Neural GPU. It is based on a type of convolutional gated recurrent unit and, like the NTM, is computationally universal. Unlike the NTM, the Neural GPU is highly parallel which makes it easier to train and efficient to run. An essential property of algorithms is their ability to handle inputs of arbitrary size. We show that the Neural GPU can be trained on short instances of an algorithmic task and successfully generalize to long instances. We verified it on a number of tasks including long addition and long multiplication of numbers represented in binary. We train the Neural GPU on numbers with upto 20 bits and observe no errors whatsoever while testing it, even on much longer numbers. To achieve these results we introduce a technique for training deep recurrent networks: parameter sharing relaxation. We also found a small amount of dropout and gradient noise to have a large positive effect on learning and generalization.
References in corpus (12)
- Adam: A Method for Stochastic Optimization
- Neural Machine Translation by Jointly Learning to Align and Translate
- Sequence to Sequence Learning with Neural Networks
- Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling
- Convolutional LSTM Network: A Machine Learning Approach for Precipitation Nowcasting
- LSTM: A Search Space Odyssey
- Highway Networks
- Grammar as a Foreign Language
- Learning to Execute
- Grid Long Short-Term Memory
- Show and Tell: A Neural Image Caption Generator
- Fast Algorithms for Convolutional Neural Networks
Cited by in corpus (97)
- Conditional Image Generation with PixelCNN Decoders
- Evaluating Large Language Models Trained on Code
- Ask Me Anything: Dynamic Memory Networks for Natural Language Processing
- Universal Transformers
- Learning Multiagent Communication with Backpropagation
- Adding Gradient Noise Improves Learning for Very Deep Networks
- Neural Programmer-Interpreters
- Fast Decoding in Sequence Models using Discrete Latent Variables
- Learning to Optimize
- Recent Advances in Deep Learning: An Overview
- DeepMath - Deep Sequence Models for Premise Selection
- RobustFill: Neural Program Learning under Noisy I/O
- A Survey of Deep Learning Techniques for Neural Machine Translation
- Programming with a Differentiable Forth Interpreter
- Analysing Mathematical Reasoning Abilities of Neural Models
- Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architectures
- One-Shot Generalization in Deep Generative Models
- Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples
- CLVSA: A Convolutional LSTM Based Variational Sequence-to-Sequence Model with Attention for Predicting Trends of Financial Markets
- A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
- Neural Networks for Text Correction and Completion in Keyboard Decoding
- Deep Learning for Symbolic Mathematics
- Memory Augmented Neural Networks with Wormhole Connections
- Learning Continuous Semantic Representations of Symbolic Expressions
- Neural Symbolic Machines: Learning Semantic Parsers on Freebase with Weak Supervision
- Addressing Some Limitations of Transformers with Feedback Memory
- Investigating the Limitations of Transformers with Simple Arithmetic Tasks
- Adaptive Neural Compilation
- Program Synthesis with Large Language Models
- Learning Efficient Algorithms with Hierarchical Attentive Memory
- Neural Program Synthesis with Priority Queue Training
- Supervising strong learners by amplifying weak experts
- Improving the Neural GPU Architecture for Algorithm Learning
- Convolution by Evolution: Differentiable Pattern Producing Networks
- Arkade: k-Nearest Neighbor Search With Non-Euclidean Distances using GPU Ray Tracing
- LabelSens: Enabling Real-time Sensor Data Labelling at the point of Collection on Edge Computing
- Attending to Mathematical Language with Transformers
- Learning Compositional Neural Programs with Recursive Tree Search and Planning
- Strong Generalization and Efficiency in Neural Programs
- Pointer Graph Networks
- Show Your Work: Scratchpads for Intermediate Computation with Language Models
- Recent Advances in Neural Program Synthesis
- Neural Program Search: Solving Programming Tasks from Description and Examples
- Siamese recurrent networks learn first-order logic reasoning and exhibit zero-shot compositional generalization
- Neural Shuffle-Exchange Networks -- Sequence Processing in O(n log n) Time
- ProTo: Program-Guided Transformer for Program-Guided Tasks
- Learning Algorithms via Neural Logic Networks
- A Framework for Searching for General Artificial Intelligence
- Lie Access Neural Turing Machine
- Extensions and Limitations of the Neural GPU
- Deep API Programmer: Learning to Program with APIs
- Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networks
- Learning to Synthesize Programs as Interpretable and Generalizable Policies
- Can Neural Networks Understand Logical Entailment?
- On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
- Measuring Arithmetic Extrapolation Performance
- Tree Memory Networks for Modelling Long-term Temporal Dependencies
- Rationalizing Predictions by Adversarial Information Calibration
- Compositional Generalization via Neural-Symbolic Stack Machines
- NAPS: Natural Program Synthesis Dataset
- Neural Arithmetic Expression Calculator
- Neural Symbolic Machines: Learning Semantic Parsers on Freebase with Weak Supervision (Short Version)
- REAS: Combining Numerical Optimization with SAT Solving
- Low-rank passthrough neural networks
- Latent Compositional Representations Improve Systematic Generalization in Grounded Question Answering
- HyperNCA: Growing Developmental Networks with Neural Cellular Automata
- Evolutionary Training and Abstraction Yields Algorithmic Generalization of Neural Computers
- The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers
- You Look Twice: GaterNet for Dynamic Filter Selection in CNNs
- Genetic algorithms with DNN-based trainable crossover as an example of partial specialization of general search
- Neural Status Registers
- Hierarchically Compositional Tasks and Deep Convolutional Networks
- DTMT: A Novel Deep Transition Architecture for Neural Machine Translation
- Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training
- Neural Execution of Graph Algorithms
- Is Attention All What You Need? -- An Empirical Investigation on Convolution-Based Active Memory and Self-Attention
- Learning Numeracy: Binary Arithmetic with Neural Turing Machines
- Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks
- Learning to solve arithmetic problems with a virtual abacus
- Towards Modular Algorithm Induction
- Improving the Universality and Learnability of Neural Programmer-Interpreters with Combinator Abstraction
- I-BERT: Inductive Generalization of Transformer to Arbitrary Context Lengths
- Motion Planning for Heterogeneous Unmanned Systems under Partial Observation from UAV
- Neural Program Synthesis By Self-Learning
- Gradients are Not All You Need
- Multi Resolution LSTM For Long Term Prediction In Neural Activity Video
- CounterExample Guided Neural Synthesis
- Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time
- Pedestrian Trajectory Prediction with Structured Memory Hierarchies
- A Primer for Neural Arithmetic Logic Modules
- Progress Extrapolating Algorithmic Learning to Arbitrary Sequence Lengths
- Dual-CLVSA: a Novel Deep Learning Approach to Predict Financial Markets with Sentiment Measurements
- Self-Adaptive Network Pruning
- Type-driven Neural Programming by Example
- Generalization Challenges for Neural Architectures in Audio Source Separation
- SVGD: A Virtual Gradients Descent Method for Stochastic Optimization
- Grammar Filtering For Syntax-Guided Synthesis