Title: EFFICIENTLY APPLYING ATTENTION TO SEQUENTIAL DATA WITH THE RECURRENT DISCOUNTED ATTENTION UNIT

Abstract: Recurrent Neural Networks architectures excel at processing sequences by modelling dependencies over different timescales. The recently introduced Recurrent Weighted Average (RWA) unit captures long term dependencies far better than an LSTM on several challenging tasks. The RWA achieves this by applying attention to each input and computing a weighted average over the full history of its computations. Unfortunately, the RWA cannot change the attention it has assigned to previous timesteps, and so struggles with carrying out consecutive tasks or tasks with changing requirements. We present the Recurrent Discounted Attention (RDA) unit that builds on the RWA by additionally allowing the discounting of the past. We empirically compare our model to RWA, LSTM and GRU units on several challenging tasks. On tasks with a single output the RWA, RDA and GRU units learn much quicker than the LSTM and with better performance. On the multiple sequence copy task our RDA unit learns the task three times as quickly as the LSTM or GRU units while the RWA fails to learn at all. On the Wikipedia character prediction task the LSTM performs best but it followed closely by our RDA unit. Overall our RDA unit performs well and is sample efficient on a large variety of sequence tasks.

1. INTRODUCTION:

Many types of information such as language, music and video can be represented as sequential data. Sequential data often contains related information separated by many timesteps, for instance a poem may start and end with the same line, a scenario which we call long term dependencies. Long term dependencies are difficult to model as we must retain information from the whole sequence and this increases the complexity of the model.

A class of model capable of capturing long term dependencies are Recurrent Neural Networks (RNNs). A specific RNN architecture, known as Long Short-Term Memory (LSTM) (Hochreiter and Schmidhuber, 1997) , is the benchmark against which other RNNs are compared. LSTMs have been shown to learn many difficult sequential tasks effectively. They store information from the past within a hidden state that is combined with the latest input at each timestep. This hidden state can carry information right from the beginning of the input sequence, which allows long term dependencies to be captured. However, the hidden state tends to focus on the more recent past and while this mostly works well, in tasks requiring equal weighting between old and new information LSTMs can fail to learn.

A technique for accessing information from anywhere in the input sequence is known as attention. The attention mechanism was introduced to RNNs by Bahdanau et al. (2014) for neural machine translation. The text to translate is first encoded by a bidirectional-RNN producing a new sequence of encoded state. Different locations within the encoded state are focused on by multiplying each of them by an attention matrix and calculating the weighted average. This attention is calculated for each translated word. Computing the attention matrix for each encoded state and translated word combination provides a great deal of flexibility in choosing where in the sequence to attend to, but the cost of computing these matrices grows as a square of the number of words to translate. This cost limits this method to short sequences, typically only single sentences are processed at a time.

The Recurrent Weighted Average (RWA) unit, recently introduced by Ostmeyer and Cowell (2017) , can apply attention to sequences of any length. It does this by only computing the attention for each input once and computing the weighted average by maintaining a running average up to the current timestep. Their experiments show that the RWA performs very well on tasks where information is needed from any point in the input sequence. Unfortunately, as it cannot change the attention it assigns to previous timesteps, it performs poorly when asked to carry out multiple tasks within the same sequence, or when asked to predict the next character in a sample of text, a task in which new information is more important than old.

We introduce the Recurrent Discounted Attention (RDA) unit, which extends the RWA by allowing it to discount the attention applied to previous timesteps. As this adjustment is applied to all previous timesteps at once, it continues to be efficient. It performs very well both at tasks requiring equal weighting over all information seen and at tasks in which new information is more important than old.

The main contributions of this paper are as follows:

1. We analyse the Recurrent Weighted Average unit and show that it cannot output certain simple sequences.

2. We propose the Recurrent Discounted Attention unit that extends the Recurrent Weighted Average by allowing it to discount the past.

3. We run extensive experiments on the RWA, RDA, LSTM and GRU units and show that the RWA, RDA and GRU units are well suited to tasks with a single output, the RDA performs best on the multiple sequence copy task while the LSTM unit performs better on the Hutter Prize Wikipedia dataset.

Our paper is setout as follows: we present the analysis of the RWA (sections 3 and 4) and propose the RDA (section 5). The experimental results (section 6), discussion (section 7) and conclusion follow (section 8).

2. RELATED WORK:

Recently many people have worked on using RNNs to predict the next character in a corpus of text. Sutskever et al. (2011) first attempted this on the Hutter Prize Wikipedia datasets using the MRNN archtecture. Since then many architectures (Graves, 2013; Chung et al., 2015; Kalchbrenner et al., 2015; Rocki, 2016; Zilly et al., 2016; Ha et al., 2016; Chung et al., 2016) and regularization techniques (Ba et al., 2016; Krueger et al., 2016) have achieved impressive performance on this task, coming close to the bit-per-character limits bespoke compression algorithms have attained.

Many of the above architectures are very complex, and so the Gated Recurrent Unit (GRU) is a much simpler design that achieves similar performance to the LSTM. Our experiments confirm previous literature (Chung et al., 2014) that reports it performing very well.

Attention mechanisms have been used in neural machine translation by Bahdanau et al. (2014) . Xu et al. (2015) experimented with hard-attention on image where a single location is selected from a multinomial distribution. Xu et al. (2015) introduced the global and local attention to refer to attention applied to the whole input and hard attention applied to a local subset of the input.

An idea related to attention is the notion of providing additional computation time for difficult inputs. Graves (2016) introduce shows that this yields insight into the distribution of information in the input data itself.

Several RNN architectures have attempted to deal with long term dependencies by storing information in an external memory (Graves et al., 2014; 2016) .

3. RECURRENT WEIGHTED AVERAGE:

At each timestep the Recurrent Weighted Average model uses its current hidden state h t-1 and the input x t to calculate two quantities:

1. The features z t of the current input:

u t = W u • x t + b u g t = W g • [x t , h t-1 ] + b g z t = u t tanh g t

where u t is an unbounded vector dependent only on the input x t , and tanh g t is a bounded vector dependent on the input x t and the hidden state h t-1 . Notation: W are weights, b are biases, (•) is matrix multiplication, and is the elementwise product.

2. The attention a t to pay to the features z t :

a t = e Wa•[xt,ht-1]+ba

The hidden state h t is then the average of of the features z t , weighted by the attention a t , and squashed through the hyperbolic tangent function:

h t = tanh t i=1 z i a i t i=1 a i

This is implemented efficiently as a running average:

n t = n t-1 + z t a t d t = d t-1 + a t h t = tanh n t d t

where n t is the numerator and d t is the denominator of the average.

4. PROPERTIES OF THE RECURRENT WEIGHTED AVERAGE:

The RWA shows superior experimental results compared to the LSTM on the following tasks:

1. Classifying whether a sequence is longer than 500 elements.

2. Memorising short random sequences of symbols and recalling them at any point in the subsequent 1000 timesteps.

3. Adding two numbers spaced randomly apart on a sequence of length 1000.

4. Classifying MNIST images pixel by pixel.

All of these tasks require combining the full sequence of inputs into a single output. It makes perfect sense that an average over all timesteps would perform well in these tasks.

On the other hand, we can imagine tasks where an average over all timesteps would not work effectively:

1. Copying many input sequences from input to output. It will need to forget sequences once they have been output.

2. Predicting the next character in a body of text. Typically, the next character depends much more on recent characters than on those from the beginning of the text.

3.. Outputting the parity of an input sequence:

h t = -1 t c for 0 < c < 1.

All of these follow from the property that d t is monotonically increasing in t, which can be seen from a t > 0 and d t = d t-1 + a t . As d t becomes larger, the magnitude of a t must increase to change the value of h t . This means that it becomes harder and harder to change the value of h t to the point where it almost becomes fixed. In the specific case of outputting the sequence h t = -1 t c we can show that a t must grow geometrically with time.

Lemma 1 Let the task be to output the sequence h t = -1 t c for 0 < c < 1. Let h t be defined by the equations of the Recurrent Weighted Average, and let z t be bounded and f h be a continuous, monotonically increasing surjection from R → (-1, 1).

Then, a t grows geometrically with increasing t.

Proof. Provided in Appendix A.

Corollary 2 If a t is also bounded then it cannot grow geometrically for all time and so the RWA cannot output the sequence h t = -1 t c.

Corollary 2 suggests that the Recurrent Weighted Average may not actually be Turing Complete.

Overall, these properties suggest the the RWA is a good choice for tasks with a single result, but not for sequences with multiple results or tasks that require forgetting.

5. THE RECURRENT DISCOUNTED ATTENTION UNIT:

The RDA uses its current hidden state h t-1 and the input x t to calculate three quantities:

1. The features z t of the current input are calculated identically to the RWA:

u t = W u • x t + b u g t = W g • [x t , h t-1 ] + b g z t = u t tanh g t 2.

The attention a t to pay to the features:

z t a t = f a (W a • [x t , h t-1 ] + b a )

Here we generalize attention to allow any function f a which is non-negative and monotonically increasing. If we choose f a = exp, then we recover the RWA attention function.

3. The discount factor γ t to apply to the previous values in the average

γ t = σ(W γ • [x t , h t-1 ] + b γ )

where σ is the sigmoid/logistic function defined as σ(x) = 1 1+e -x .

We use these values to calculate a discounted moving average. This discounting mechanism is crucial in remediating the RWA's inability to forget the past

n t = n t-1 γ t + z t a t d t = d t-1 γ t + a t h t = f h n t d t

Here we generalize RWA further by allowing f h to be any function, and we also introduce a final transformation to the hidden state h t to produce the output

o t = f o (h t ) 5.1 CHOICES FOR THE ATTENTION FUNCTION f a , HIDDEN STATE FUNCTION f h AND OUTPUT FUNCTION f o

The attention function f a (x) is a non-negative monotonically increasing function of x. There are several possible choices: • Using a ReLU for the attention function f a almost always fails to train. Using a Softplus for f a is much more stable than a ReLU. However, it doesn't perform as well as using sigmoid or exponential attention. • Exponential attention performs well in all tasks, and works best with the tanh output function f o (h t ) = tanh(h t ). We refer to this as RDA-exp-tanh. • Sigmoid attention performs well in all tasks, and works best with the identity output function f o (h t ) = h t . We refer to this as RDA-sigmoid-id. • It is difficult to choose between RDA-exp-tanh and RDA-sigmoid-id. RDA-exp-tanh often trains faster, but it sometimes diverges with NaN errors during training. RDA-sigmoid-id trains slower but is more stable, and tends to have better loss. We include results for both of them.

6.3. SINGLE TASK SEQUENCES:

Here we investigate whether sequences with a single task can be performed as well with the RDA as with the RWA.

Each of the four tasks detailed below require the RNN to save some or all of the input sequence before outputting a single result many steps later.

1. Addition -The input consists of two sequences. The first is a sequence of numbers each uniformly sampled from [0, 1], and the second consists of all zeros except for two ones which indicate the two numbers of the first sequence to be added together. (Table 1 )

2. Classify length -A sequence of length between 1 and 1000 is input. The goal is to classify whether the sequence is longer than 500.

All RNN architectures could learn their initial hidden state for this task, which improved performance for all of them. (Table 2) 3. MNIST -The task is supervised classification of MNIST digits. We flatten the 28x28 pixel arrays into a single 784 element sequence and use RNNs to predict the digit class labels. This task challenges networks' ability to learn long-range dependencies, as crucial pixels are present at the beginning, middle and end of the sequence. We implement two variants of this task:

(a) Sequential -the pixels are fed in from the top left to the bottom right of the image. (Table 3 ) (Sutskever et al., 2011) 1.60 GF-LSTM (Chung et al., 2015) 1.58 Grid-LSTM (Kalchbrenner et al., 2015) 1.47 MI-LSTM (Wu et al., 2016) 1.44 Recurrent Memory Array Structures (Rocki, 2016a) 1.40 HyperNetworks (Ha et al., 2016) 1.35 LayerNorm HyperNetworks (Ha et al., 2016) 1.34 Recurrent Highway Networks (Zilly et al., 2016) 1 Table 7 : Bits per character on the Hutter Prize Wikipedia test set (b) Permuted -the pixels of the image are randomly permuted before the image is fed in. The same permutation is applied to all images. (Table 4 )

4. Copy -The input sequence starts with randomly sampled symbols. The rest of the input is blanks except for a single recall symbol. The goal is to memorize the starting symbols and output them when prompted by the recall symbol. All other output symbols must be blank. (Table 5 )

6.4. MULTIPLE SEQUENCE COPY TASK:

Here we investigate whether the different RNN units can cope with doing the same task repeatedly.

The tasks consists of multiple copying tasks all within the same sequence. Instead of having the recall symbol randomly placed over the whole sequence it always appears a couple of steps after the sequence being memorized. This gives room for 50 consecutive copying tasks in a length 1000 input sequence. (Table 6 )

6.5. WIKIPEDIA CHARACTER PREDICTION TASK:

The standard test for RNN models is character-level language modelling. We evaluate our models on the Hutter Prize Wikipedia dataset enwik8, which contains 100M characters of 205 different symbols including XML markup and special characters. We split the data into the first 90M characters for the training set, the next 5M for validation, and the final 5M for the test set. (Table 7 )

7. DISCUSSION:

We start our discussion by describing the performance of each individual unit.

Our analysis of the RWA unit showed that it should only work well on the single task sequences and we confirm this experimentally. It learns the single sequence tasks quickly but is unable to learn the multiple sequence copy task and Wikipedia character prediction task.

Our experiments show that the RDA unit is a consistent performer on all types of tasks. As expected, it learns single task sequences slower than the RWA but it actually achieves better generalization on the MNIST test sets. We speculate that the cause of this improvement is because the ability to forget effectively allows it to compress the information it has previously processed, or perhaps discounting the past should be considered as changing the attention on the past and the RDA is able to vary its attention on previous inputs based on later inputs. On the multiple sequence copy task the RDA unit was far superior to all other units learning three times as fast as the LSTM and GRU units.

On the Wikipedia character prediction task the RDA unit performed respectably, achieving a better compression rate than the GRU but worse than the LSTM.

The LSTM unit learns the single task sequences slower than all the other units and often fails to learn at all. This is surprising as it is often used on these tasks as a baseline against which other archtectures are compared. On the multiple sequence copy task it learns slowly compared to the RDA units but solves the task. The Wikipedia character prediction task is where it performs best, learning much faster and achieving better compression than the other units.

The GRU unit works very well on single task sequences often learning the fastest and achieving excellent generalization on the MNIST test sets. On the multiple sequence copy task it has equal performance to the LSTM. On the Wikipedia character prediction task it performs worse than the LSTM and RDA units but still achieves a good performance.

We now look at how our results show that different neural network architectures are suited for different tasks.

For our single output tasks the RWA, RDA and GRU units work best. Thus for similar real work applications such as encoding a molecule into a latent representation, classification of genomic sequences, answering questions or language translation, these units should be considered before LSTM units. However, our results are yet to be verified in these domains.

For sequences that contain an unknown number of independent tasks the RDA unit should be used.

For the Wikipedia character prediction task the LSTM performs best. Therefore we can't recommend RWA, RDA or GRU units on this or similar tasks.

8. CONCLUSION:

We analysed the Recurrent Weighted Average (RWA) unit and identified its weakness as the inability to forget the past. By adding this ability to forget the past we arrived at the Recurrent Discounted Attention (RDA). We implemented several varieties of the RDA and compared them to the RWA, LSTM and GRU units on several different tasks. We showed that in almost all cases the RDA should be used in preference to the RWA and is a flexible RNN unit that can perform well on all types of tasks.

We also determined which types of tasks were more suited to each different RNN unit. For tasks involving a single output the RWA, RDA and GRU units performed best, for the multiple sequence copy task the RDA performed best, while on the Wikipedia character prediction task the LSTM unit performed best. We recommend taking these results into account when choosing a unit for real world applications.

B ILLUSTRATED EMPIRICAL RESULTS:

We include figures of the loss function learning curves during training. In the case of MNIST, we report on validation accuracy instead. These experiments provide evidence that the two flavours of the RDA unit consistently perform close to the best across a broad range of tasks. Figures are best viewed in colour. 

:



Figures and Tables:

MNIST permuted classification.

Addition: steps until loss < 0.001.

Table content: <table><tr><td/><td>Addition</td><td colspan="2">Classify Length</td></tr><tr><td>Model</td><td>Steps until loss &lt; 0.001</td><td>Model</td><td>Steps until accuracy = 1.0.</td></tr><tr><td>GRU</td><td>2036</td><td>GRU</td><td>71</td></tr><tr><td>LSTM</td><td>&gt; 10000</td><td>LSTM</td><td>776</td></tr><tr><td>RDA-exp-tanh</td><td>1781</td><td>RDA-exp-tanh</td><td>164</td></tr><tr><td>RDA-sigmoid-id</td><td>2016</td><td>RDA-sigmoid-id</td><td>414</td></tr><tr><td>RWA</td><td>1735</td><td>RWA</td><td>133</td></tr></table>

Classify: steps until accuracy = 1.0.

Table content: <table><tr><td colspan="2">MNIST</td></tr><tr><td>Model</td><td>Test Set Accuracy</td></tr><tr><td>GRU</td><td>0.985</td></tr><tr><td>LSTM</td><td>0.114</td></tr><tr><td>RDA-exp-tanh</td><td>0.985</td></tr><tr><td>RDA-sigmoid-id</td><td>0.987</td></tr><tr><td>RWA</td><td>0.979</td></tr></table>

MNIST test set accuracy.

Table content: <table><tr><td colspan="2">MNIST permuted</td></tr><tr><td>Model</td><td>Permuted Test Set Accuracy</td></tr><tr><td>GRU</td><td>0.944</td></tr><tr><td>LSTM</td><td>0.915</td></tr><tr><td>RDA-exp-tanh</td><td>0.905</td></tr><tr><td>RDA-sigmoid-id</td><td>0.913</td></tr><tr><td>RWA</td><td>0.899</td></tr></table>

MNIST permuted test set accuracy.

Table content: <table/>

Copy: steps until accuracy > 0.999

Table content: <table><tr><td/><td>Copy</td><td/><td>Multicopy</td></tr><tr><td>Model</td><td>Steps until accuracy &gt; 0.999</td><td>Model</td><td>Steps until accuracy &gt; 0.99</td></tr><tr><td>GRU</td><td>5329</td><td>GRU</td><td>3984</td></tr><tr><td>LSTM</td><td>&gt; 20000</td><td>LSTM</td><td>4048</td></tr><tr><td>RDA-exp-tanh</td><td>11831</td><td>RDA-exp-tanh</td><td>1114</td></tr><tr><td>RDA-sigmoid-id</td><td>9840</td><td>RDA-sigmoid-id</td><td>1316</td></tr><tr><td>RWA</td><td>5660</td><td>RWA</td><td>&gt; 10000</td></tr></table>

Multicopy: steps until accuracy > 0.99

Table content: <table><tr><td>Hutter Prize Wikipedia</td><td/></tr><tr><td>Model</td><td>BPC</td></tr><tr><td>Stacked LSTM (Graves, 2013)</td><td>1.67</td></tr><tr><td>MRNN</td><td/></tr></table>

Peer review (iclr2018):
 Summary: This paper proposes an extension to the RWA model by introducing the discount gates to computed discounted averages instead of the undiscounted attention. The problem with the RWA is that the averaging mechanism can be numerically unstable due to the accumulation operations when computing d_t. Pros: - Addresses an issue of RWAs. Cons: -The paper addresses a problem with an issue with RWAs. But it is not clear to me why would that be an important contribution. -The writing needs more work. -The experiments are lacking and the results are not good enough. General Comments: This paper addresses an issue regarding to RWA which is not really widely adopted and well-known architecture, because it seems to have some have some issues that this paper is trying to address. I would still like to have a better justification on why should we care about RWA and fixing that model. The writing of this paper seriously needs more work. The Lemma 1 doesn*t make sense to me, I think it has a typo in it, it should have been (-1)^t c instead of -1^t c. The experiments are only on toyish and small scale tasks. According to the results the model doesn*t really do better than a simple LSTM or GRU.