Neural GPUs Learn Algorithms

By Lukasz Kaiser, Ilya Sutskever. 2015

399 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

In Model Architectures

Citations in the corpus

Attention is All you Need (2017, methodology): “In the following sections, we will describe the Transformer, motivate self-attention and discuss its advantages over models such as [14, 15] and [8].”
Can Active Memory Replace Attention? (2016, methodology): “As a baseline for our investigation of active memory models, we will use the Neural GPU model from [12], depicted in Figure 3, and defined as follows.”
Universal Transformers (2018, methodology): “…practical sequence models competitive on large-scale tasks such as machine translation, and computationally universal models such as the Neural Turing Machine or the Neural GPU (Graves et al., 2014; Kaiser & Sutskever, 2016), which can be trained using gradient descent to perform algorithmic tasks.”
Show Your Work: Scratchpads for Intermediate Computation with Language Models (2021, neutral): “The related problem of neural algorithm induction has attracted considerable interest (Graves et al., 2014; Kurach et al., 2016; Kaiser & Sutskever, 2016; Graves et al., 2016; Reed & de Freitas, 2016; Veliˇckovi´c et al., 2020a;b).”
Program Synthesis with Large Language Models (2021, neutral): “…are deep network architectures that aim to learn algorithms from input-output examples, by structuring the network in a way that corresponds to mathematical models of computation like Turing machines [Graves et al., 2014, Kaiser and Sutskever, 2016, Kurach et al., 2016, Graves et al., 2016].”
Evaluating Large Language Models Trained on Code (2021, methodology): “…incorporated inductive biases based on modern computing devices, such as the Neural Turing Machine (Graves et al., 2014), memory networks (Weston et al., 2015; Sukhbaatar et al., 2015), the Neural GPU (Kaiser & Sutskever, 2015), and the differentiable neural computer (Graves et al., 2016).”
Conditional Image Generation with PixelCNN Decoders (2016, background): “We used 200 K synchronous updates over 32 GPUs in TensorFlow [1]”
Programmable Agents (2017, background): “Different approaches to this problem focus on networks that infer programs [3, 10, 22], on networks that execute programs [39, 30, 5] and on networks that jointly do both [14, 17, 38, 29, 13]; although there is much overlap between many of these approaches.”
Supervising strong learners by amplifying weak experts (2018, background): “Algorithm learning: our problem differs from traditional work on learning algorithms (Graves et al., 2016; Kaiser and Sutskever, 2015; Neelakantan et al., 2015) because we don’t assume that we have access to ground truth labels.”
Neural Execution Engines: Learning to Execute Subroutines (2020, background): “Prior work has found that scalar numbers have difﬁculty representing large ranges [25] and that binary is a useful representation that generalizes well [12, 21].”
Neural Logic Machines (2019, methodology): “Neural program induction and synthesis (Neelakantan et al., 2016; Reed & De Freitas, 2016; Kaiser & Sutskever, 2016; Parisotto et al., 2017; Devlin et al., 2017; Bunel et al., 2018; Sun et al., 2018) are recently introduced to solve problems by synthesizing computer programs with neural…”
Making Neural Programming Architectures Generalize via Recursion (2017, methodology): “…to name a few, this includes the Differentiable Neural Computer (Graves et al., 2016), Neural Turing Machine (Graves et al., 2014), Neural GPU (Kaiser & Sutskever, 2015), Neural Programmer (Neelakantan et al., 2015), Pointer Network (Vinyals et al., 2015), Hierarchical Attentive Memory…”
Analysing Mathematical Reasoning Abilities of Neural Models (2019, methodology): “…to validate new architectures which aim capture algorithmic/systematic reasoning have often been drawn from this domain (Graves et al., 2016; Kaiser & Sutskever, 2015; Joulin & Mikolov, 2015), and thus in providing a large scale training and evaluation framework for such models, we hope to…”
Sparse is Enough in Scaling Transformers (2021, neutral): “As can be seen in the table below, the baseline Transformer does not generalize well, while Terraformer manages to get a large portion correctly, even if it is not perfect like the Neural GPU [16].”
Neural Module Networks (2015, background): “Other policy- and algorithm-learning approaches with modular substructure include [16, 4].”
Ask Me Anything: Dynamic Memory Networks for Natural Language Processing (2015, background): “Various other neural memory or attention architectures have recently been proposed for algorithmic problems (Joulin & Mikolov, 2015; Kaiser & Sutskever, 2015), caption generation for images (Malinowski & Fritz, 2014; Chen & Zitnick, 2014), visual question answering (Yang et al., 2015) or other NLP…”
Neural Programmer-Interpreters (2015, neutral): “(Zaremba & Sutskever, 2015; Zaremba et al., 2015; Kaiser & Sutskever, 2015; Kurach et al., 2015; Neelakantan et al., 2015).”