Why does the transformer do better than RNN and LSTM in long-range context dependencies?

Question

I am reading the article How Transformers Work where the author writes

Another problem with RNNs, and LSTMs, is that it’s hard to parallelize the work for processing sentences, since you have to process word by word. Not only that but there is no model of long and short-range dependencies.

Why exactly does the transformer do better than RNN and LSTM in long-range context dependencies?

Answer 1

I'll list some bullet points of the main innovations introduced by transformers , followed by bullet points of the main characteristics of the other architectures you mentioned, so we can then compared them.

Transformers

Transformes (Attention is all you need) were introduced in the context of machine translation with the purpose to avoid recursion in order to allow parallel computation (to reduce training time) and also to reduce drop in performances due to long dependencies. The main characteristics are:

• Non sequential: sentences are processed as a whole rather than word by word.
• Self Attention: this is the newly introduced 'unit' used to compute similarity scores between words in a sentence.
• Positional embeddings: another innovation introduced to replace recurrence. The idea is to use fixed or learned weights which encode information related to a specific position of a token in a sentence.

The first point is the main reason why transformer do not suffer from long dependency issues. Original transformers do not relies on past hidden states to capture dependencies with previous words, they process a sentence as a whole, reason why there is no risk to loose (or 'forget') past information. Moreover, also multi-head attention and positional embeddings both provide information about the relationship between different words.

RNN / LSTM

Recurrent neural networks and Long-short term memory models for what concern this question are almost identical in their core properties:

• Sequential processing: sentences must be processed words by words.
• Past information retained through past hidden states: sequence to sequence models follow the Markov property, each state is assumed to be dependent only on the previously seen state.

The first property is the reason why RNN and LSTM can't be trained in parallel. In order to encode the second word in a sentence I need the previously computed hidden states of the first word, therefore I need to compute that first. The second property is a bit more subdole, but not hard to grasp conceptually. Information in RNN and LSTM are retained thank's to previously computed hidden states. The point is that the encoding of a specific word is retained only for the next time step, which means that the encoding of a word strongly affect only the representation of the next word, its influence is quickly lost after few time steps. LSTM (and also GruRNN) can boost a bit the dependency range they can learn thanks to a deeper processing of the hidden states through specific units (which comes with an increased number of parameters to train) but nevertheless the problem is inherently related to recursion. Another way in which people mitigated this problem is to use Bi-directional models, which encode the same sentence from two direction, from the start to end and from the end to the start, allowing this way words at the end of a sentence to have stronger influence in the creation of the hidden representation, but this is just a workaround rather than a real solution for very long dependencies.

CNN

Also convolutional neural network are widely used in nlp since they are quite fast to train and effective with short texts. The way they tackle dependencies is by applying different kernels to the same sentence, and indeed since they're first application to text (Convolutional Neural Networks for Sentence Classification) they were implement as multichannel CNN. Why do different kernels allow to learn dependencies? Because a kernel of size 2 for example would learn relationships between pairs of words, a kernel of size 3 would capture relationships between triplets of words and so on. The evident problem here is that the number of different kernels required to capture dependencies among all possible combination of words in a sentences would be enormous and unpractical because of the exponential growing number of combinations when increasing the maximum length size of input sentences.

To summarise, Transformers are better than all the other architectures because they totally avoid recursion, by processing sentences as a whole and by learning relationships between words thank's to multi-head attention mechanisms and positional embeddings. Nevertheless, it must be pointed out that also transformers can capture only dependencies within the fixed input size used to train them, i.e. if I use as a maximum sentence size 50, the model will not be able to capture dependencies between the first word of a sentence and words that occur more than 50 words later, like in another paragraph. New transformers like Transformer-XL tries to overcome exactly this issue, by kinda re-introducing recursion by storing hidden states of already encoded sentences to leverage them in the subsequent encoding of the next sentences.

Answer 2

Let's start with RNN. A well known problem is vanishin/exploding gradients, which means that the model is biased by most recent inputs in the sequence, or in other words, older inputs have practically no effect in the output at the current step.

LSTMs/GRUs mainly try to solve this problem, by including a separate memory (cell) and/or extra gates to learn when to let go of past/current information. Check these series of lectures for more in-depth discussion. Also check the interactive parts of this article for some intuitive understanding of dependency on past elements.

Now, given all this, information from past steps still goes through a sequence of computations and we're relying on these new gate/memory mechanisms to pass information from old steps to the current one.

One major advantage of the transformer architecture, is that at each step we have direct access to all the other steps (self-attention), which practically leaves no room for information loss, as far as message passing is concerned. On top of that, we can look at both future and past elements at the same time, which also brings the benefit of bidirectional RNNs, without the 2x computation needed. And of course, all this happens in parallel (non-recurrent), which makes both training/inference much faster.

The self-attention with every other token in the input means that the processing will be in the order of $\mathcal{O}(N^2)$ (glossing over details), which means that it's going to be costly to apply transformers on long sequences, compared to RNNs. That's probably one area that RNNs still have an advantage over transformers.

Answer 3

First: RNN is one part of the Neural Network family for processing sequential data. The way in which RNN is able to store information from the past is to loop in its architecture, which automatically keeps information from the past stored. Second: sltm / gru is a component of regulating the flow of information referred to as the gate and GRU has 2 gates, namely reset gate and gate update. If we want to make a decision to eat like the analogy above, resetting the gate on the GRU will determine how to combine new inputs with past information, and update the gate, will determine how much past information should be kept. source : https://link.springer.com/article/10.1007/s00500-019-04281-z