Adaptive Computation Time (Act) in Neural Networks. (Part 1)
Adaptive Computation Time (ACT) in Neural Networks [1/3]
Part 1: ACT in RNNsThere is an interesting little-known topic of Adaptive Computation Time (ACT) in Neural Networks. It is applicable to different kinds of neural networks (RNN, ResNet, Transformer) and you can use this rather general idea somewhere else as well.The general idea is that some complex data might require more computations to produce a final result, while some simple or unimportant data might require less. And you can dynamically decide how long to process the data by training a neural network to automatically adapt to the data.The original work by Alex Graves is this one:“Adaptive Computation Time for Recurrent Neural Networks”,https://arxiv.org/abs/1603.08983BTW, I’d recommend you to keep an eye on Alex Graves’ papers, he is the author of many other interesting things, e.g. multidimensional RNNs, CTC, Grid-LSTM, he worked on NTM and DNC, and so on.So, let’s start.#1. RNN with ACTClassical RNN updates its state sₜ for each sequence element xₜ in a single step:So the RNN computation graph looks like this:Adaptive Computation Time (ACT) modifies the conventional setup by allowing the network to perform a variable number of state transitions and compute a variable number of outputs at each input step:Now each state and each output are expanded to a variable number of intermediate updates/outputs, and the resulting output will be a weighted sum of these intermediate outputs. This somehow resembles a soft attention mechanism.The modified computation graph looks like this (be aware, h is not a hidden unit state here, h is a halting unit output, more on this below):The interesting thing is how many updates to perform during each step?We introduce a halting unit (essentially a sigmoidal unit) whose role is to decide whether we should stop computations or to continue.The processing stops when the sum of halting unit outputs (h) becomes close to 1.0 (actually, 1.0 minus epsilon, where epsilon is a small value chosen to be 0.01 in the paper). Then the last h is replaced by a remainder to make sum(hᵢ) to be equal to 1.0. This procedure gives us the halting probabilities (pᵢ) of the intermediate steps. Then we determine mean-field updates for the states and outputs:So, for example, let the halting unit outputs were 0.1, 0.3, 0.4 and 0.4 at the four consecutive steps. The sum of these h’s is larger than 1-epsilon, so we produce a list of weights: [0.1, 0.3, 0.4, 0.2] (the last value was truncated) and calculate the final state and output as a weighted sum with these weights:s = 0.1*s¹ + 0.3*s² + 0.4*s³ + 0.2*s⁴y = 0.1*y¹ + 0.3*y² + 0.4*y³ + 0.2*y⁴We need to limit the computation time, otherwise, a network has an incentive to process data for as long as possible. So, we add a ponder cost to our loss function. The ponder cost resembles the total computation during the sequence. It is added to the total loss with a weight τ, a time penalty hyperparameter.The ponder cost is discontinuous in some points, but in practice, we simply ignore this, so the gradient of the ponder cost with respect to the halting activations is straightforward and the network can be differentiated as usual and trained using backpropagation.Addition training example.The idea was tested on a set of tasks specially designed to be hard without such a mechanism: determining the parity of a sequence of binary numbers (a sequence is passed as a vector all elements at once, not as a sequence of elements which is typical for RNN training, that’s important), solving logic task tests, addition of a sequence elements producing the cumulative sums, and finally sorting sequences of 2 to 15 numbers.The ACT nets produce significantly better results than baselines (the same RNNs or LSTMs but without ACT), yet require careful tuning of the time penalty hyperparameter (authors used grid search).Another interesting experiment is Wikipedia Character Prediction. It reveals an intriguing pattern of ponder allocation while processing a sequence. Character prediction networks trained with ACT consistently pause at spaces between words, and pause for longer at ‘boundary’ characters such as commas and full stops.So, looks interesting.#1b. Repeat-RNNThen an interesting paper appeared at ICLR 2018:“Comparing Fixed and Adaptive Computation Time for Recurrent Neural Networks” by Daniel Fojo, Víctor Campos, Xavier Giro-i-Nieto,https://arxiv.org/abs/1803.08165The idea is simple.What if the most important thing is not the dynamically predicted number of steps, but the ability to execute several steps for each element?The authors designed a simple baseline called Repeat-RNN that performs a fixed (>1) number of steps for each element. It is a kind of ablation of the original ACT where the number of steps is a hyperparameter now.This setting is equivalent to the expansion of the input sequence, repeating each element fixed number of times plus marking it with an additional boolean flag to distinguish a new input token from a duplicated one.The unexpected result was the Repeat-RNN was able to solve tasks using fewer SGD steps and a smaller number of repeats than ACT. Surprisingly, Repeat-RNN performed as good or better than ACT in the consideredtwo tasks (parity and addition).Both ACT and Repeat-RNN require hyperparameter tuning (time penalty for the former and number of repetitions for the latter). Both are task dependent, but the number of repetitions is much more intuitive than time penalty.It’s still an open question of why does repeatedly updating the state for each input token before moving on to the next one improve the learning capability of the network.One of the possibilities authors mention is the link between LSTM and Residual Networks, together with the recent finding that the latter perform iterative estimation, suggest that repeating inputs in RNNs may encourage iterative feature estimation and produce better performing models.Another possible reason is that the increased number of applied nonlinearities allows the network to model more complex functions with the same number of parameters.… to be continued …Part 2 is here.Part 3 is here.