Source-linked AI summary
Adaptive Computation Time for Recurrent Neural Networks
Alex Graves
TL;DR
Most machine learning algorithms cannot adapt computation to task complexity, leaving experimenters to choose computation in advance. This paper introduces Adaptive Computation Time, enabling recurrent neural networks to learn per-input update counts; synthetic experiments show improved accessibility and adaptive computation, while real-data experiments reveal structure in computational demands.
Problem
Most machine learning algorithms cannot dynamically adapt computation to the complexity of the task, and recurrent-network computation must otherwise be chosen in advance.
Method
Adaptive Computation Time lets recurrent neural networks learn how many updates to perform for each input they receive.
Results
Synthetic experiments show that ACT makes otherwise inaccessible problems straightforward for RNNs and dynamically adapts computation to data demands.
Takeaways & Limitations
On real data, ACT's learned computation allocation can provide insight into data structure and the computational demands of prediction.
Takeaways & Limitations
ACT is sensitive to the time-penalty parameter controlling the trade-off between computation cost and prediction error, whose value is not obvious to choose.
Abstract
from arXiv · showhide
This paper introduces Adaptive Computation Time (ACT), an algorithm that allows recurrent neural networks to learn how many computational steps to take between receiving an input and emitting an output. ACT requires minimal changes to the network architecture, is deterministic and differentiable, and does not add any noise to the parameter gradients. Experimental results are provided for four synthetic problems: determining the parity of binary vectors, applying binary logic operations, adding integers, and sorting real numbers. Overall, performance is dramatically improved by the use of ACT, which successfully adapts the number of computational steps to the requirements of the problem. We also present character-level language modelling results on the Hutter prize Wikipedia dataset. In this case ACT does not yield large gains in performance; however it does provide intriguing insight into the structure of the data, with more computation allocated to harder-to-predict transitions, such as spaces between words and ends of sentences. This suggests that ACT or other adaptive computation methods could provide a generic method for inferring segment boundaries in sequence data.
1 Introduction
The paper addresses the inability of most machine-learning algorithms to adapt computation to input difficulty. It proposes differentiable halting for recurrent networks so computation can vary by input while trading accuracy against speed.
- Most machine-learning algorithms cannot dynamically adapt computation to the complexity of the task they perform.
- For recurrent networks, computation depends on both input-sequence length and the number of recurrent transformations, but experimenters must still choose the allocation beforehand.
- The proposed approach dynamically varies how long the network ponders each input, making effective network depth a function of inputs received so far.
- ACT uses a sigmoidal halting unit whose activation determines whether computation continues, then uses the resulting halting distribution to form mean-field outputs and states.
- Unlike Self-Delimiting Neural Networks, the approach propagates gradients with respect to halting time rather than relying on a simple activation threshold.
- A time cost encourages parsimonious computation, but its hand-chosen weight makes network behavior sensitive to the accuracy-speed trade-off.
2 Adaptive Computation Time
Adaptive Computation Time lets recurrent networks perform a variable number of state and output updates at each input step. It uses differentiable halting probabilities, mean-field updates, and a ponder penalty to balance prediction accuracy against computation.
- ACT mechanism: ACT expands each input step into a variable number N(t) of intermediate state and output updates while sharing the same transition and output parameters.The input is augmented with a binary flag so the network can distinguish repeated inputs from repeated computations for one input.
- Halting: A sigmoidal halting unit produces cumulative halting probabilities that define when computation stops and form a valid distribution over intermediate steps.The small constant ϵ is set to 0.01 in the experiments and permits halting after one update when the first activation is sufficiently high.
- Differentiable computation: Rather than sampling a discrete halt, ACT uses the halting distribution for deterministic mean-field updates of the recurrent state and output, avoiding noisy gradients.The resulting network can then be trained with ordinary backpropagation through time and gradient descent.
- Assumptions and failure mode: ACT relies on an approximate linearity assumption for interpolated states and outputs, and minimizing expected rather than total halting time can be exploited by manipulating state magnitudes.The reported failure mode assigns low ponder weight to the final update while making its vectors much larger so they dominate the mean-field result.
- Limiting computation: The ponder cost ρ_t upper-bounds total computation and is added to the sequence loss with time penalty τ, encouraging a trade-off between accuracy and speed.A hard maximum M can additionally restrict updates, primarily safeguarding against excessive computation early in training.
- Gradient approximation: The method approximates gradients by treating N(t) as constant and minimizing the remainder term, despite discontinuities when the halting threshold changes the update count.This preserves a differentiable training procedure away from the discrete update-count changes.
3 Experiments
Across four synthetic tasks and Wikipedia character prediction, ACT generally improved performance and adapted computation to task difficulty, while yielding limited gains on language-model error rates. Its ponder allocation nevertheless highlighted sequence boundaries and avoided extra computation on unpredictable inputs.
- Experimental scope: ACT was evaluated with and without recurrent networks on four synthetic tasks and one real-world language-processing task.LSTM was used for all experiments except one simple-RNN experiment, and ACT was designed to apply to any recurrent architecture.
- Parity: Parity error fell from almost 40% without ACT to below 5% for time penalties of 0.03 and below.Successful networks increased ponder time approximately linearly with the number of parity bits, whereas non-ACT and overly penalized networks maintained roughly constant ponder.
- Logic: Logic-task sequence error reached virtually zero for all τ ≤0.01, with low-τ networks clustering around 5–6 computation steps.That ponder time approximately matched the mean number of logic gates and the minimum computations needed when evaluating operations individually.
- Addition: Addition was perfectly solved for every searched τ, while efficient networks increased ponder time approximately linearly with the number of digits.The most efficient networks had a slope close to 1, and per-sequence allocation supported an approximately linear-time long-addition algorithm.
- Sorting: Sorting improved from around 12% error without ACT to around 6% for the best τ, but required roughly 9 times as much computation.Ponder spiked near sequence ends, especially for longer sequences, while average ponder per timestep was lower away from the spike.
- Wikipedia character prediction: Wikipedia error rates were fairly similar with and without ACT and across τ values, but ACT paused at spaces and longer at commas and full stops.ACT also detected XML-tag openings without increasing computation during unpredictable ID-number sequences, unlike loss and entropy, which remained high for such data.
4 Conclusion
ACT lets recurrent neural networks learn how many updates to perform for each input, adapting computation to data demands. The paper reports successful synthetic-task results, while real-data computation allocations may reveal data structure and prediction difficulty.
- ACT allows recurrent neural networks to learn how many updates to perform for each input.
- On synthetic data, ACT makes otherwise inaccessible problems straightforward for recurrent neural networks and adapts computation to the demands of the data.
- On real data, ACT’s learned allocation of computation steps can provide insight into data structure and the computational demands of prediction.
- ACT could let recurrent architectures with soft attention dynamically vary the number of glances or internal operations at each time-step.
- The algorithm is sensitive to the time penalty parameter controlling the trade-off between computation cost and prediction error.