Neural GPUs Learn Algorithms

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 (4)

• Sequence to Sequence Learning with Neural Networks
• Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling
• Grammar as a Foreign Language
• Show and Tell: A Neural Image Caption Generator

Cited by in corpus (96)

• Conditional Image Generation with PixelCNN Decoders
• Evaluating Large Language Models Trained on Code
• 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
• Investigating the Limitations of Transformers with Simple Arithmetic Tasks
• Addressing Some Limitations of Transformers with Feedback Memory
• Program Synthesis with Large Language Models
• Adaptive Neural Compilation
• 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
• Neural Program Search: Solving Programming Tasks from Description and Examples
• Show Your Work: Scratchpads for Intermediate Computation with Language Models
• Siamese recurrent networks learn first-order logic reasoning and exhibit zero-shot compositional generalization
• Recent Advances in Neural Program Synthesis
• ProTo: Program-Guided Transformer for Program-Guided Tasks
• Neural Shuffle-Exchange Networks -- Sequence Processing in O(n log n) Time
• 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
• Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networks
• Can Neural Networks Understand Logical Entailment?
• Learning to Synthesize Programs as Interpretable and Generalizable Policies
• Deep API Programmer: Learning to Program with APIs
• Tree Memory Networks for Modelling Long-term Temporal Dependencies
• Measuring Arithmetic Extrapolation Performance
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
• Rationalizing Predictions by Adversarial Information Calibration
• NAPS: Natural Program Synthesis Dataset
• Compositional Generalization via Neural-Symbolic Stack Machines
• REAS: Combining Numerical Optimization with SAT Solving
• Neural Arithmetic Expression Calculator
• Neural Symbolic Machines: Learning Semantic Parsers on Freebase with Weak Supervision (Short Version)
• Latent Compositional Representations Improve Systematic Generalization in Grounded Question Answering
• Evolutionary Training and Abstraction Yields Algorithmic Generalization of Neural Computers
• Low-rank passthrough neural networks
• HyperNCA: Growing Developmental Networks with Neural Cellular Automata
• 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
• Hierarchically Compositional Tasks and Deep Convolutional Networks
• Neural Status Registers
• DTMT: A Novel Deep Transition Architecture for Neural Machine Translation
• Learning Numeracy: Binary Arithmetic with Neural Turing Machines
• Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training
• Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks
• Is Attention All What You Need? -- An Empirical Investigation on Convolution-Based Active Memory and Self-Attention
• Neural Execution of Graph Algorithms
• Neural Program Synthesis By Self-Learning
• Learning to solve arithmetic problems with a virtual abacus
• I-BERT: Inductive Generalization of Transformer to Arbitrary Context Lengths
• Towards Modular Algorithm Induction
• Improving the Universality and Learnability of Neural Programmer-Interpreters with Combinator Abstraction
• Motion Planning for Heterogeneous Unmanned Systems under Partial Observation from UAV
• Pedestrian Trajectory Prediction with Structured Memory Hierarchies
• Gradients are Not All You Need
• Multi Resolution LSTM For Long Term Prediction In Neural Activity Video
• A Primer for Neural Arithmetic Logic Modules
• Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time
• CounterExample Guided Neural Synthesis
• Dual-CLVSA: a Novel Deep Learning Approach to Predict Financial Markets with Sentiment Measurements
• Type-driven Neural Programming by Example
• SVGD: A Virtual Gradients Descent Method for Stochastic Optimization
• Self-Adaptive Network Pruning
• Grammar Filtering For Syntax-Guided Synthesis
• Progress Extrapolating Algorithmic Learning to Arbitrary Sequence Lengths
• Generalization Challenges for Neural Architectures in Audio Source Separation