Source-linked AI summary
Reinforcement Learning Neural Turing Machines - Revised
Wojciech Zaremba, Ilya Sutskever
TL;DR
The paper asks whether neural models can learn to interact with discrete Interfaces, which are not directly trainable by standard backpropagation. It proposes the RL–NTM, using Reinforce for discrete access and backpropagation for continuous outputs, and shows success on simple algorithmic tasks while exposing substantial training limitations.
Problem
The paper examines how to train models to interact with discrete Interfaces, which cannot be trained directly with standard backpropagation because they are not differentiable.
Method
The RL–NTM uses Reinforce to learn access decisions over discrete input and memory tapes, while backpropagation learns memory and output contents.
Results
The RL–NTM succeeds on repeat copy, sequence reversal, and other simple algorithmic tasks, although success depends highly on the controller architecture.
Takeaways & Limitations
Reinforce can train an NTM-style model to solve very simple algorithmic problems, but learning memory access patterns with Reinforce appears difficult.
Takeaways & Limitations
Although Turing complete in principle, the RL–NTM is difficult to train and solves only relatively simple problems; sorting and long integer addition were too difficult.
Abstract
from arXiv · showhide
The Neural Turing Machine (NTM) is more expressive than all previously considered models because of its external memory. It can be viewed as a broader effort to use abstract external Interfaces and to learn a parametric model that interacts with them. The capabilities of a model can be extended by providing it with proper Interfaces that interact with the world. These external Interfaces include memory, a database, a search engine, or a piece of software such as a theorem verifier. Some of these Interfaces are provided by the developers of the model. However, many important existing Interfaces, such as databases and search engines, are discrete. We examine feasibility of learning models to interact with discrete Interfaces. We investigate the following discrete Interfaces: a memory Tape, an input Tape, and an output Tape. We use a Reinforcement Learning algorithm to train a neural network that interacts with such Interfaces to solve simple algorithmic tasks. Our Interfaces are expressive enough to make our model Turing complete.
1 INTRODUCTION
The paper extends Neural Turing Machines to discrete Interfaces, using reinforcement learning for discrete access and backpropagation for continuous writing. The RL–NTM solves several simple algorithmic tasks, but success depends strongly on the controller architecture.
- External Interfaces can extend machine-learning models’ capabilities, including through memory, databases, search engines, or software tools.
- The RL–NTM uses Reinforce to learn access to discrete Input and Memory Tapes, while backpropagation determines what to write to memory and output.
- Discrete Interface access can have size-independent cost, and an unbounded memory plus deferred output can make the model Turing complete in principle.
- The RL–NTM succeeds on repeat copy, sequence reversal, and other simple algorithmic tasks, but success depends highly on the controller architecture.
- Implementing the RL–NTM was non-trivial because many components interact, motivating a numerical procedure for checking Reinforce gradients.
2 THE MODEL
The RL–NTM is an Interface–Controller system with discrete input, memory, and output tapes. It combines reinforcement learning for discrete actions with backpropagation for predictions and memory writes.
- The Controller is the only learning component and learns to interact with its Interfaces to solve a task.
- The model exposes input, memory, and output tapes as Interfaces, with movable read heads for input and memory and a write-only output head.
- The objective is expected log probability over action sequences and desired outputs, optimized jointly by Reinforce and backpropagation.
- At each timestep, the controller reads tape values and prior actions, then writes memory, predicts a target symbol, and selects head movements.
- The model receives a direct learning signal only when it chooses to make a prediction, allowing arbitrarily delayed prediction in principle.
3 RELATED WORK
Prior Interface–Controller models mainly use continuous, differentiable Interfaces, whereas this work studies discrete Interfaces trained with Reinforce. The resulting RL–NTM is Turing complete in principle but remains difficult to train and limited to relatively simple tasks.
- The model combines a controller with sequential input, delayed output, and differentiable memory in related work, while this paper changes the Interface type.
- Earlier memory-based models use differentiable Interfaces, while the RL–NTM uses discrete Interfaces trained with Reinforce.
- The RL–NTM uses Reinforce to train how its attention mechanism accesses the various tapes.
- The RL–NTM is Turing complete in principle because it can postpone prediction arbitrarily and access unbounded memory.
- Despite that theoretical property, the model is difficult to train and solves only relatively simple problems.
4 THE REINFORCE ALGORITHM
Reinforce trains a stochastic policy by sampling action sequences and weighting rewards, providing an unbiased but high-variance gradient estimator. The RL–NTM uses this approach for learning discrete actions and applies variance-reduction techniques.
- The policy pθ(at|a1:(t−1)) assigns probabilities to actions conditioned on previous actions.
- The RL–NTM uses Reinforce to learn discrete interface access while training other outputs with backpropagation.
- Reinforce maximizes expected cumulative reward over action sequences that terminate an episode.The action space may be exponentially large or infinite, so direct summation is generally impractical.
- Reinforce estimates the objective and its gradient by sequentially sampling actions and accumulating their rewards.The resulting estimator is unbiased, but sampling approximates the sum over possible action sequences.
- Future-reward backpropagation and online and offline baselines reduce the gradient estimator’s high variance.The paper states that all three techniques are crucial for solving the evaluated tasks.
5 GRADIENT CHECKING
The paper introduces an exhaustive gradient-checking procedure for Reinforce implementations. It replaces stochastic sampling with deterministic enumeration of terminating action sequences, enabling exact objective and derivative checks on small problems.
- The gradient checker was developed to verify the complex RL–NTM implementation and is presented as an independent contribution.
- Gradient verification compares the expected Reinforce gradient with the numerical derivative of the expected objective.
- The method reduces small tasks to manageable action spaces and enumerates every terminating action sequence.This restriction is analogous to the size limitations of conventional gradient checkers.
- A deterministic sampler outputs each action sequence exactly once while accumulating its probability.
- Weighting each sequence’s Reinforce gradient by its probability permits exact computation of the objective and derivative.The procedure can perform gradient verification within seconds on a laptop instead of requiring billions of samples.
6 TASKS
The experiments evaluate RL–NTM on algorithmic sequence-transformation tasks using available tape Interfaces. The task designs vary the required reordering, repetition, compression, and memory use.
- The task suite includes Copy, DuplicatedInput, Reverse, RepeatCopy, and ForwardReverse problems.
- Copy requires reproducing a variable-length input sequence terminated by an end-of-sequence symbol.
- DuplicatedInput requires emitting every third symbol from an input in which each symbol is repeated three times.
- Reverse outputs the input sequence in reverse order, while RepeatCopy outputs two or three copies of the sequence.
- ForwardReverse restricts the input-tape pointer to forward movement, making external memory necessary for a perfect solution.
7 CURRICULUM LEARNING
RL–NTM training uses curriculum learning because difficult instances could not be solved directly. Training shifts toward harder complexities as performance improves, while retaining probability mass on the hardest levels.
- Direct training on difficult, typically long instances failed, whereas a curriculum of increasing complexity enabled learning.Without a curriculum, all but the shortest sequences were experimentally unsolvable in an all-or-nothing sense.
- Problem complexity is measured by the maximal desired-output length for typical inputs.
- The training distribution shifts toward harder instances as model performance improves.
- Maintaining non-negligible probability mass on the hardest difficulty levels is critical for curriculum effectiveness.Removing that mass makes the curriculum much less effective.
- The curriculum increases complexity when normalized average zero-one loss falls below 0.2, with at least 100 updates between increases.
8 CONTROLLERS
The paper compares generic and task-specialized controllers for RL-NTM training. The direct access controller is better suited to symbol-rearrangement tasks, but its architectural modification is not domain independent.
- Controller choices: The RL-NTM’s controller strongly affects reinforcement-learning success, and some tasks require task-specific architectures.The paper notes that controller complexity and trainability are central constraints.
- Controller choices: The paper compares an LSTM controller with a direct access controller.The LSTM is intended as a generic controller, whereas direct access is specialized for symbol rearrangement.
- Direct access mechanism: The direct access design adds gated paths from input to memory and output, and from memory to output and adjacent memory locations.A sigmoid computed from the controller state modulates these additive contributions.
- Direct access mechanism: This mechanism reduces the need for the LSTM to retain input symbols in controller registers and shortens backpropagation paths.These changes are intended to make learning symbol-rearrangement tasks easier.
- Direct access mechanism: The direct access modification is a drawback because it is domain dependent and may not improve performance on many other tasks.Its task-specific fit trades off against generality.
9 EXPERIMENTS
The experiments evaluate RL-NTM on copying, reversal, and other algorithmic tasks, while highlighting interface-dependent comparisons and strong controller and curriculum requirements. Performance is mixed on harder tasks such as sorting and long integer addition.
- Evaluation scope: The experiments lack comparison with other models, and task difficulty depends on how inputs are delivered through the available interfaces.The authors therefore caution that claims such as solving addition are difficult to assess across interface configurations.
- Copying and task design: The RL-NTM generalizes copying to arbitrary sequence lengths, although its interfaces make the shared copying task relatively simple.Copying is the task shared with the Neural Turing Machine.
- Task behavior: In ForwardReverse, the model moves to the sequence end without predicting, stores the input in memory, and uses that memory to reverse the sequence.This task requires delayed output together with memory-based sequence transformation.
- Failure cases: Sorting, long integer addition, and RepeatCopy with a forward-only input tape produced less empirical success.Sorting achieved reasonable performance but relied on an ad-hoc algorithm and excessive controller-memory use.
- Training requirements: All components were empirically essential: the LSTM controller failed on several tasks, direct access succeeded, and curriculum was required except for short sequences.The authors report that successful tasks either solved within 20,000 parameter updates or failed regardless of further updates.
10 CONCLUSIONS
The paper shows that Reinforce can train NTM-style models on simple algorithmic problems, but learning discrete memory-access patterns remains difficult. It also develops variance-reduction and gradient-checking techniques to make this training practical.
- Reinforce can train an NTM-style model to solve very simple algorithmic problems, although learning memory-access patterns remains difficult.
- The Reinforce gradient-checking procedure avoids sampling and verifies gradients within seconds on a laptop, making debugging and tuning substantially easier.
- A separate baseline LSTM first processes the entire input tape, then predicts a baseline at each timestep alongside the controller.
- The offline baseline technique introduces a biased estimator, although the authors report that it works well in practice.
APPENDIX B: EXECUTION TRACES
The execution traces illustrate successful RL–NTM behavior across several algorithmic tasks, with predictions matching the desired outputs in the successful examples. They also expose a failure mode when RepeatCopy restricts the input tape to forward movement.
- Successful execution traces show output predictions perfectly matching the desired outputs for the illustrated tasks.
- The traces include successful Reverse and ForwardReverse instances, respectively showing executions without and with external-memory use.
- When RepeatCopy permits only forward input movement, the memory pointer moves randomly instead of copying the input into memory for later use.