PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural GPUs Learn Algorithms

Łukasz Kaiser, Ilya Sutskever

arXiv:1511.08228v3cs.LGcs.NE

TL;DR

Learning algorithms from examples with neural networks remains challenging. The Neural GPU addresses this with a parallel, shallow, Turing-complete architecture and learns non-trivial superlinear-time algorithms that generalize to much longer inputs without errors.

  • Problem

    Learning algorithms from examples with neural networks remains an open research question.

  • Method

    The Neural GPU uses parallel convolutional gated recurrent units in a shallow, Turing-complete architecture for learning algorithms.

  • Results

    Trained on up-to 20-bit numbers, the Neural GPU learned binary multiplication with no errors on tested inputs up-to 2000 bits and also learned addition and other algorithmic tasks.

  • Takeaways & Limitations

    These results support using neural networks for symbolic algorithms and potentially program synthesis without discrete state.

  • Takeaways & Limitations

    Only a few models in the 729-model grid search generalized without error to 2000-bit numbers, although dropout and gradient noise improved reliability.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The Neural GPU is presented as a parallel, shallow, Turing-complete architecture for learning algorithms, overcoming efficiency and optimization challenges of Neural Turing Machines. It learns long binary multiplication, addition, and other algorithmic tasks from examples while generalizing far beyond training lengths.

  • Sequence-to-sequence models are limited by fixed-size encoding, while attention removes that bottleneck but does not resolve all remaining problems.Neural Turing Machines address arbitrary algorithms theoretically, but soft attention, considerable depth, difficult optimization, and poor parallelization hinder computational efficiency and learning.
  • The Neural GPU is Turing-complete in principle and designed to use highly parallel, shallow computation rather than Neural Turing Machines’ deep sequential processing.This design aims to make learning complex algorithms easier to optimize and execution more efficient.
  • Trained on numbers up to 20 bits, the Neural GPU made no errors on tested binary multiplications up to 2000 bits.The paper describes this as the first neural network to learn an algorithm with superlinear runtime in input size.
  • The same architecture learns long binary addition, counting, copying, sequence reversal, and sequence duplication.
  • Stack-augmented RNNs generalize addition trained on up to 20-bit numbers only to about 100-bit numbers, never 200-bit numbers and never without error.The paper calls this the strongest generalization obtained without the Neural GPU.

2 THE NEURAL GPU

The Neural GPU stores embedded inputs in a two-dimensional mental image and evolves that state with stacked convolutional gated recurrent units. It produces outputs from the final state through a learned output matrix and is trained end-to-end with differentiable optimization.

  • 2 THE NEURAL GPU: A CGRU updates each mental-image position using update and reset gates whose linear transforms are implemented by convolutional kernel banks.The convolution preserves the mental image shape and uses kernels of shape [k_w, k_h, m, m].
  • 2 THE NEURAL GPU: The convolution uses zero padding and stride 1, allowing standard optimized convolution implementations to support Neural GPU computation.The authors note that faster convolution methods can be directly used.
  • 2 THE NEURAL GPU: The Neural GPU embeds the input sequence into the first column of a tensor-shaped starting state, then applies l stacked CGRU layers for n recurrent steps.The state has shape [w, h, m], and the final state is s_fin = s_n.
  • 2 THE NEURAL GPU: The model predicts each output by applying a learned matrix O to the corresponding first-column vector in the final state and selecting the maximal logit.Training uses softmax cross-entropy over the logits.
  • 2 THE NEURAL GPU: All Neural GPU components are differentiable, enabling stochastic-gradient training; the reported configuration uses Adam, gradient clipping, l = 2, w = 4, m = 24, and 3 × 3 kernels.Adam uses ε = 10^-4, and gradients are clipped to norm 1.

3 EXPERIMENTS

Neural GPUs learn long binary addition and multiplication and generalize beyond their training lengths. They also solve simpler algorithmic tasks at substantially longer sequence lengths, with parameter-sharing relaxation and small dropout improving training and generalization.

  • Experiment scope: The experiments were designed to test whether Neural GPUs learn algorithmic tasks and generalize well beyond the sequence lengths used for training.The study begins with long binary addition and multiplication and then evaluates several additional algorithmic tasks.
  • Core tasks: The core experiments study long binary addition and multiplication, encoding inputs and outputs as sequences of discrete symbols with task-specific arithmetic and padding symbols.Addition uses {0, 1, +, PAD}, while multiplication uses {0, 1, ·, PAD}; addition operates on equal-length, lower-endian binary numbers.
  • Other algorithmic tasks: After training on sequences up to length 41, Neural GPUs made no errors on the tested simpler tasks at lengths up to 4001.The tested tasks included copying, reversing, duplicating, and sorting bit sequences.
  • Training methods: Small dropout improved generalization, producing more models that generalized to higher lengths and enabling multiplication models to generalize to 2000 bits.Dropout rates were searched at 6%, 9%, and 13.5%, and dropout was applied to the whole mental image rather than recurrent connections.
  • Training methods: Parameter-sharing relaxation was crucial for multiplication: without it, models struggled to fit training data and failed to generalize, whereas almost all 729 relaxed runs fit the training set.The method temporarily uses r non-shared parameter sets and gradually pulls them toward their average; r = 6 was often used.

4 DISCUSSION

The discussion highlights Neural GPU’s computational efficiency and data efficiency, while identifying weaker performance with decimal inputs and inconsistent long-range generalization. It also explains how width increases hidden-state capacity without increasing parameter count.

  • Visualization: The learned computation can be visualized through state evolution; for duplication, the model moves part of the embedding downward at each step.The visualization encodes −1 as white, 1 as black, and other values as gray.
  • Limitations: Decimal inputs degraded performance: long decimal multiplication was not learned, although increasing m to 128 enabled the other tasks.The binary representation performed better than the decimal representation.
  • Limitations: Only a few models in a 729-model grid search generalized without error to 2000-bit numbers, while dropout and gradient noise improved training and generalization reliability.Many models generalized to 40 or 200 bits, but substantially fewer worked without error at 2000 bits.
  • Why use width?: A width-1 Neural GPU with m = 64 generalized to 2000-bit binary multiplication, while width increases hidden-state information without increasing parameter count.A one-dimensional Neural GPU with four times larger m can represent every function representable by the original architecture; width can therefore act as a factorization.
  • Speed and data efficiency: A 2-layer Neural GPU for n = 32 and m = 64 required about 0.6s per joint forward-backward step on an NVIDIA GTX 970 GPU.After unfolding, the network contained 128 CGRU layers operating on 32 mental images, each 4 × 64 × 64.
  • Speed and data efficiency: Using only about 2000 total training instances, some models still generalized well from binary addition to 200-bit numbers.The standard experiments used about 200k examples, whereas the reduced-data experiment used 100 examples per training length.

5 CONCLUSIONS AND FUTURE WORK

The Neural GPU achieves a qualitative advance by learning a non-trivial superlinear-time algorithm that generalizes to much greater lengths without errors. The authors propose applications to program synthesis and language processing, while highlighting parameter sharing relaxation as broadly useful for recurrent-network training.

  • Conclusions: Table 1 shows that the Neural GPU learns a non-trivial superlinear-time algorithm that generalizes to much higher lengths without errors, unlike previous architectures.The authors describe this as the first such neural-network result.
  • Future work: Neural GPUs may extend neural networks to program synthesis, potentially replicating prior results such as Kaiser (2012) more scalably, while learning symbolic algorithms without discrete state.Their data efficiency is described as surprising, and dropout and noise further improve performance.
  • Future work: Future work includes applying Neural GPUs to language processing and using parameter sharing relaxation to improve training across deep recurrent networks.Gating and recursion may enable deeper translation models without overfitting, building on convolutional word-based translation results.
Loading 1511.08228v3…