Recurrent Neural Networks and Long Short-Term Memory Networks: Tutorial
  and Survey
This is a tutorial paper on Recurrent Neural Network (RNN), Long Short-Term
Memory Network (LSTM), and their variants. We start with a dynamical system and
backpropagation through time for RNN. Then, we discuss the problems of gradient
vanishing and explosion in long-term dependencies. We explain close-to-identity
weight matrix, long delays, leaky units, and echo state networks for solving
this problem. Then, we introduce LSTM gates and cells, history and variants of
LSTM, and Gated Recurrent Units (GRU). Finally, we introduce bidirectional RNN,
bidirectional LSTM, and the Embeddings from Language Model (ELMo) network, for
processing a sequence in both directions.
Benyamin Ghojogh, Ali Ghodsi
# Recurrent Neural Networks and Long Short-Term Memory Networks: Tutorial and Survey

###### Abstract

This is a tutorial paper on Recurrent Neural Network (RNN), Long Short-Term Memory Network (LSTM), and their variants. We start with a dynamical system and backpropagation through time for RNN. Then, we discuss the problems of gradient vanishing and explosion in long-term dependencies. We explain close-to-identity weight matrix, long delays, leaky units, and echo state networks for solving this problem. Then, we introduce LSTM gates and cells, history and variants of LSTM, and Gated Recurrent Units (GRU). Finally, we introduce bidirectional RNN, bidirectional LSTM, and the Embeddings from Language Model (ELMo) network, for processing a sequence in both directions.

Machine Learning, Neural Networks, LSTM, Deep Learning, Neural Networks, Neural
were proposed to process sequences in both directions. The Embeddings from Language Model (ELMo) network (Peters et al., 2018) is a language model which makes use of the bidirectional LSTM.

This is a tutorial on RNN, LSTM, and their variants. There exist some other tutorials and surveys about this topic, some of which are (Jaeger, 2002; Jozefowicz et al., 2015; Lipton et al., 2015; Schmidhuber, 2015; Greff et al., 2016; Salehinejad et al., 2017; Staudemeyer and Morris, 2019; Yu et al., 2019; Smagulova and James, 2019). A very good survey on the variants of LSTM is (Greff et al., 2016).

## 2 Recurrent Neural Network

### Dynamical System

A dynamical system is recursive and its classical form is as follows:

\[\mathbf{h}_{t}=f_{\theta}(\mathbf{h}_{t-1}), \tag{1}\]

where \(t\) denotes the time step, \(\mathbf{h}_{t}\) is the state at time \(t\), and \(f_{\theta}(.)\) is a function fixed between the states of all time steps. Figure 1-a shows such a system. Dynamical systems are widely used in chaos theory (Broer and Takens, 2011).

We can have a dynamical system with external input signal where \(\mathbf{x}_{t}\) denotes the input signal at time \(t\). This system is modeled as:

\[\mathbf{h}_{t}=f_{\theta}(\mathbf{h}_{t-1},\mathbf{x}_{t}). \tag{2}\]

This system is depicted in Fig. 1-b.

### Parameter Sharing

The state \(\mathbf{h}_{t}\) can be considered as a summary of the past sequence of inputs and states. If a different function \(f_{\theta}\) is defined for each possible sequence length, the model will not have generalization. If the same parameters are used for any sequence length, the model will have generalization properties. Therefore, the parameters are shared for all lengths and between all states. Such a dynamical system with parameter sharing can be implemented as a neural network with weights. Such a network is called a Recurrent Neural Network (RNN), which was proposed in (Rumelhart et al., 1986).

RNN is illustrated in Fig. 1-c, where the same weight matrices are used for all time slots. RNN gets a sequence as input and outputs a sequence as a decision for a task such as regression or classification. Suppose the input, output, and state at time slot \(t\) are denoted by \(\mathbf{x}_{t}\in\mathbb{R}^{d}\), \(\mathbf{y}_{t}\in\mathbb{R}^{q}\), and \(\mathbf{h}_{t}\in\mathbb{R}^{p}\), respectively. Let \(\mathbf{W}\in\mathbb{R}^{p\times p}\) be the weight matrix between states, \(\mathbf{U}\in\mathbb{R}^{p\times d}\) be the weight matrix between the inputs and the states, and \(\mathbf{V}\in\mathbb{R}^{q\times p}\) denote the weight matrix between the states and outputs. The bias weights for the state and the output are denoted by \(\mathbf{b}_{i}\in\mathbb{R}^{p}\) and \(\mathbf{b}_{y}\in\mathbb{R}^{q}\), respectively. As shown in Fig. 1-c, we have:

\[\mathbb{R}^{p}\ni\mathbf{i}_{t}=\mathbf{W}\mathbf{h}_{t-1}+\mathbf{U}\mathbf{x}_{t}+ \mathbf{b}_{i}, \tag{3}\] \[[-1,1]^{p}\ni\mathbf{h}_{t}=\tanh(\mathbf{i}_{t})\] \[\qquad\qquad\qquad\qquad=\tanh(\mathbf{W}\mathbf{h}_{t-1}+\mathbf{U}\mathbf{x}_{t} +\mathbf{b}_{i}),\] (4) \[\mathbb{R}^{q}\ni\mathbf{y}_{t}=\mathbf{V}\mathbf{h}_{t}+\mathbf{b}_{y}, \tag{5}\]

where \(\tanh(.)\in(-1,1)\) denotes the hyperbolic tangent function, which is used as an element-wise activation function for the states.

If there is an activation function, such as softmax, at the output layer, we denote the output of activation function by:

\[\mathbb{R}^{q}\ni\widehat{\mathbf{y}}_{t}=\text{softmax}(\mathbf{y}_{t})=\frac{\exp(y _{t,1})}{\sum_{j=1}^{q}\exp(y_{t,j})}, \tag{6}\]

where \(y_{t,j}\) denotes the \(j\)-th component of \(\mathbf{y}_{t}\).

### Backpropagation Through Time (BPTT)

One of the methods for training RNN is Backpropagation Through Time (BPTT), which is very similar to the backpropagation algorithm (Rumelhart et al., 1986) because it is based on gradient descent and chain rule (Ghojogh et al., 2021), but it has also chain rule through time. BPTT was developed by several works (Robinson and Fallside, 1987; Werbos, 1988; Williams, & Zipser, 1995; Mozer, 1995). This algorithm is very solid in theory; however, it does not show the best performance in practice.

In BPTT, the loss is considered as a summation of loss functions at the previous time steps until now. As it is im

Figure 1: The folded and unfolded structures of (a) a dynamic system without input, (b) a dynamical system with input, and (c) an RNN. Every square on an edge means connection from one time slot before.
practical to consider all time steps from the start of training (especially after a long time of training), we only consider the \(T\) previous time steps. In other words, we assume that RNN has \(T\)-order Markov property (Ghojogh et al., 2019b). Therefore, the loss function is:

\[\mathbb{R}\ni\mathcal{L}=\sum_{t=1}^{T}\mathcal{L}_{t}, \tag{7}\]

where \(\mathcal{L}_{1}\) is the loss function at the current time slot and \(\mathcal{L}_{t}\) denotes the loss function at the previous \((t-1)\) time slot.

This loss functions needs to be optimized using gradient descent and chain rule. Therefore, we calculate its gradient with respect to the parameters of RNN. These parameters are \(\boldsymbol{y}_{t}\), \(\boldsymbol{h}_{t}\), \(\boldsymbol{V}\), \(\boldsymbol{W}\), \(\boldsymbol{U}\), \(\boldsymbol{b}_{i}\), and \(\boldsymbol{b}_{y}\), based on Eqs. (3), (4), and (5) and Fig. 1-c.

#### 2.3.1 Gradient With Respect to the Output

If there is no activation function at the last layer, the gradient of the loss function of RNN with respect to the output at time \(t\) is:

\[\mathbb{R}^{q}\ni\frac{\partial\mathcal{L}}{\partial\boldsymbol{y}_{t}} \stackrel{{(a)}}{{=}}\frac{\partial\mathcal{L}}{\partial \mathcal{L}_{t}}\times\frac{\partial\mathcal{L}_{t}}{\partial\boldsymbol{y}_{t }}\stackrel{{(\gamma)}}{{=}}\frac{\partial\mathcal{L}_{t}}{ \partial\boldsymbol{y}_{t}}, \tag{8}\]

where \((a)\) is because of the chain rule.

The gradient of the loss function at time \(t\) with respect to the output at time \(t\), i.e., \(\partial\mathcal{L}_{t}/\partial\boldsymbol{y}_{t}\), is calculated based on the formula of the loss function. The loss function can be any loss function for classification, regression, or other tasks.

If there is an activation function at the last layer (see Eq. (6)), the gradient is:

\[\mathbb{R}^{q}\ni\frac{\partial\mathcal{L}}{\partial\boldsymbol{y}_{t}} \stackrel{{(a)}}{{=}}\frac{\partial\mathcal{L}}{\partial \mathcal{L}_{t}}\times\frac{\partial\mathcal{L}_{t}}{\partial\widehat{ \boldsymbol{y}}_{t}}\times\frac{\partial\widehat{\boldsymbol{y}}_{t}}{ \partial\boldsymbol{y}_{t}}\stackrel{{(\gamma)}}{{=}}\frac{ \partial\mathcal{L}_{t}}{\partial\widehat{\boldsymbol{y}}_{t}}\times\frac{ \partial\widehat{\boldsymbol{y}}_{t}}{\partial\boldsymbol{y}_{t}}, \tag{9}\]

where \((a)\) is because of the chain rule. The derivative \(\partial\widehat{\boldsymbol{y}}_{t}/\partial\boldsymbol{y}_{t}\) is calculated based on the formula of the activation function. The other derivative, \(\partial\mathcal{L}_{t}/\partial\widehat{\boldsymbol{y}}_{t}\), is calculated based on the formula of the loss as a function of the output of the activation function.

#### 2.3.2 Gradient With Respect to the State

The gradient of the loss function of RNN with respect to the state at time \(t\) is:

\[\mathbb{R}^{p}\ni\frac{\partial\mathcal{L}}{\partial\boldsymbol{h }_{t}}\stackrel{{(a)}}{{=}}\Big{(}\frac{\partial\mathcal{L}}{ \partial\boldsymbol{y}_{t}}\times\frac{\partial\boldsymbol{y}_{t}}{\partial \boldsymbol{h}_{t}}\Big{)}+\Big{(}\frac{\partial\mathcal{L}}{\partial \boldsymbol{h}_{t+1}}\times\frac{\partial\boldsymbol{h}_{t+1}}{\partial \boldsymbol{h}_{t}}\Big{)}\] \[\stackrel{{(\ref{eq:eq
slots. The derivative \(\partial\mathcal{L}/\partial\mathbf{h}_{t}\in\mathbb{R}^{p}\) in Eq. (18) was computed in Section 2.3.2. The derivative \(\partial\mathbf{h}_{t}/\partial\mathbf{W}\) in Eq. (18) is:

\[\mathbb{R}^{p\times p^{2}}\ni\frac{\partial\mathbf{h}_{t}}{\partial\mathbf{W}}=\frac{ \partial\mathbf{h}_{t}}{\partial\dot{\mathbf{i}}_{t}}\times\frac{\partial\dot{\mathbf{i}} _{t}}{\partial\mathbf{W}},\]

because of the chain rule. The first term is:

\[\mathbb{R}^{p\times p}\ni\frac{\partial\mathbf{h}_{t}}{\partial\dot{\mathbf{i}}_{t}}= (1-\mathbf{h}_{t}^{\top}\mathbf{h}_{t})\mathbf{I}_{p\times p}, \tag{19}\]

according to Eq. (15). Based on the Magnus-Neudecker convention (Ghojogh et al., 2021), the second term is calculated as:

\[\mathbb{R}^{p\times p^{2}}\ni\frac{\partial\dot{\mathbf{i}}_{t}}{\partial\mathbf{W}}= \mathbf{h}_{t-1}^{\top}\otimes\mathbf{I}_{p\times p},\]

where \(\otimes\) denotes the Kronecker product.

#### 2.3.5 Gradient With Respect to \(\mathbf{U}\)

The gradient of the loss function of RNN with respect to the weight matrix \(\mathbf{U}\) is:

\[\mathbb{R}^{p\times d}\ni\frac{\partial\mathcal{L}}{\partial\mathbf{U}}\overset{ (a)}{=}\sum_{t=1}^{T}\textbf{vec}_{p\times d}^{-1}\Big{(}\big{(}\frac{ \partial\mathbf{h}_{t}}{\partial\mathbf{U}}\big{)}^{\top}\times\frac{\partial\mathcal{ L}}{\partial\mathbf{h}_{t}}\Big{)}, \tag{20}\]

where \((a)\) is because \(\mathbf{U}\) exists in all time slots and changing \(\mathbf{U}\) affects the loss \(\mathcal{L}\) in all time slots. The derivative \(\partial\mathcal{L}/\partial\mathbf{h}_{t}\in\mathbb{R}^{p}\) in Eq. (18) was computed in Section 2.3.2. The derivative \(\partial\mathbf{h}_{t}/\partial\mathbf{U}\) in Eq. (18) is:

\[\mathbb{R}^{p\times(pd)}\ni\frac{\partial\mathbf{h}_{t}}{\partial\mathbf{U}}=\frac{ \partial\mathbf{h}_{t}}{\partial\dot{\mathbf{i}}_{t}}\times\frac{\partial\dot{\mathbf{i}} _{t}}{\partial\mathbf{U}},\]

because of the chain rule. The first term is already calculated in Eq. (19). Based on the Magnus-Neudecker convention (Ghojogh et al., 2021), the second term is calculated as:

\[\mathbb{R}^{p\times(pd)}\ni\frac{\partial\dot{\mathbf{i}}_{t}}{\partial\mathbf{U}}= \mathbf{x}_{t}^{\top}\otimes\mathbf{I}_{p\times p}.\]

#### 2.3.6 Gradient With Respect to \(\mathbf{b}_{i}\)

The gradient of the loss function of RNN with respect to the bias \(\mathbf{b}_{i}\) is:

\[\mathbb{R}^{p}\ni\frac{\partial\mathcal{L}}{\partial\mathbf{b}_{i}}\overset{(a)}{ =}\sum_{t=1}^{T}\Big{(}\big{(}\frac{\partial\mathbf{h}_{t}}{\partial\mathbf{b}_{i}} \big{)}^{\top}\times\frac{\partial\mathcal{L}}{\partial\mathbf{h}_{t}}\Big{)}, \tag{21}\]

where \((a)\) is because \(\mathbf{b}_{i}\) exists in all time slots and changing \(\mathbf{b}\) affects the loss \(\mathcal{L}\) in all time slots. The derivative \(\partial\mathcal{L}/\partial\mathbf{h}_{t}\) was already calculated in Section 2.3.2. The derivative \(\partial\mathcal{h}_{t}/\partial\mathbf{b}_{i}\) is calculated as:

\[\mathbb{R}^{p\times p}\ni\frac{\partial\mathbf{h}_{t}}{\partial\mathbf{b}_{i}}\overset{ (a)}{=}\frac{\partial\mathbf{h}_{t}}{\partial\dot{\mathbf{i}}_{t}}\times\frac{ \partial\dot{\mathbf{i}}_{t}}{\partial\mathbf{b}_{i}}\overset{(3)}{=}\frac{\partial \mathbf{h}_{t}}{\partial\dot{\mathbf{i}}_{t}},\]

where \((a)\) is because of the chain rule and the derivative \(\partial\mathbf{h}_{t}/\partial\dot{\mathbf{i}}_{t}\) was already calculated in Eq. (19).

#### 2.3.7 Gradient With Respect to \(\mathbf{b}_{y}\)

The gradient of the loss function of RNN with respect to the bias \(\mathbf{b}_{y}\) is:

\[\mathbb{R}^{q}\ni\frac{\partial\mathcal{L}}{\partial\mathbf{b}_{y}}\overset{(a)}{ =}\sum_{t=1}^{T}\Big{(}\frac{\partial\mathcal{L}}{\partial\mathbf{y}_{t}}\times \frac{\partial\mathbf{y}_{t}}{\partial\mathbf{b}_{y}}\Big{)}\overset{(b)}{=}\sum_{t=1} ^{T}\frac{\partial\mathcal{L}_{t}}{\partial\mathbf{y}_{t}}, \tag{22}\]

where \((a)\) is because \(\mathbf{b}_{y}\) exists in all time slots and changing \(\mathbf{b}_{y}\) affects the loss \(\mathcal{L}\) in all time slots. The equation \((b)\) is because of Eqs. (8) and (5). The derivative \(\partial\mathcal{L}_{t}/\partial\mathbf{y}_{t}\in\mathbb{R}^{q}\) is calculated based on the formula of the loss function.

#### 2.3.8 Updates by Gradient Descent

BPPT updates the parameters of RNN by gradient descent (Ghojogh et al., 2021) using the calculated gradients:

\[\mathbf{h}_{t} :=\mathbf{h}_{t}-\eta\frac{\partial\mathcal{L}}{\partial\mathbf{h}_{t}}, \quad\forall t\in\{1,\dots,T\},\] \[\mathbf{V} :=\mathbf{V}-\eta\frac{\partial\mathcal{L}}{\partial\mathbf{V}},\] \[\mathbf{W} :=\mathbf{W}-\eta\frac{\partial\mathcal{L}}{\partial\mathbf{W}},\] \[\mathbf{U} :=\mathbf{U}-\eta\frac{\partial\mathcal{L}}{\partial\mathbf{U}},\] \[\mathbf{b}_{i} :=\mathbf{b}_{i}-\eta\frac{\partial\mathcal{L}}{\partial\mathbf{b}_{i}},\] \[\mathbf{b}_{y} :=\mathbf{b}_{y}-\eta\frac{\partial\mathcal{L}}{\partial\mathbf{b}_{y}},\]

where \(\eta>0\) is the learning rate and the gradients are calculated by Eqs. (10), (17), (18), (20), (21), and (22).

## 3 Gradient Vanishing or Explosion in Long-term Dependencies

In recurrent neural networks, so as in deep neural networks, the final output is the composition of a large number of non-linear transformations. This results in the problem of either vanishing or exploding gradients in recurrent neural networks, especially for capturing long-term dependencies in sequence processing (Bengio et al., 1993; Bengio et al., 1994). This problem is explained in the following. Recall Eq. (2) for a dynamical system:

\[\mathbf{h}_{t}=f_{\theta}(\mathbf{h}_{t-1},\mathbf{x}_{t}).\]

By induction, the hidden state at time \(t\), i.e., \(\mathbf{h}_{t}\), can be written as the previous \(T\) time steps. If the subscript \(t\) denotes the previous \(t\) time steps, we have by induction (Hochreiter, 1998; Hochreiter et al., 2001):

\[\mathbf{h}_{1}=f_{\theta}\Big{(}f_{\theta}\big{(}\dots f_{\theta}(\mathbf{h}_{T},\mathbf{x}_{ T+1})\dots,\mathbf{x}_{2}\big{)},\mathbf{x}_{1}\Big{)}.\]
Then, by the chain rule in derivatives, the derivative loss at time \(T\), i.e., \(\mathcal{L}_{T}\), is:

\[\frac{\partial\mathcal{L}_{T}}{\partial\theta} =\sum_{t\leq T}\frac{\partial\mathcal{L}_{t}}{\partial\mathbf{h}_{t}} \frac{\partial\mathbf{h}_{t}}{\partial\theta}\overset{(a)}{=}\sum_{t\leq T}\frac{ \partial\mathcal{L}_{t}}{\partial\mathbf{h}_{T}}\frac{\partial\mathbf{h}_{T}}{ \partial\mathbf{h}_{t}}\frac{\partial\mathbf{h}_{t}}{\partial\theta}\] \[\overset{(2)}{=}\sum_{t\leq T}\frac{\partial\mathcal{L}_{t}}{ \partial\mathbf{h}_{T}}\frac{\partial\mathbf{h}_{T}}{\partial\mathbf{h}_{t}}\frac{ \partial f_{\theta}(\mathbf{h}_{t-1},\mathbf{x}_{t})}{\partial\theta}, \tag{23}\]

where \((a)\) is because of the chain rule. In this expression, there is the derivative of \(\mathbf{h}_{T}\) with respect to \(\mathbf{h}_{t}\) which itself can be calculated by the chain rule:

\[\frac{\partial\mathbf{h}_{T}}{\partial\mathbf{h}_{t}}=\frac{\partial\mathbf{h}_{T}}{ \partial\mathbf{h}_{T-1}}\times\frac{\partial\mathbf{h}_{T-1}}{\partial\mathbf{h}_{T-2} }\times\cdots\times\frac{\partial\mathbf{h}_{t+1}}{\partial\mathbf{h}_{t}}. \tag{24}\]

for capturing long-term dependencies in the sequence, \(T\) should be large. This means that in Eq. (24), and hence in Eq. (23), the number of multiplicand terms becomes huge. On the one hand, if each derivative is slightly smaller than one, the entire derivative in the chain rule becomes very small for multiplication of many terms smaller than one. This problem is referred to as gradient vanishing. On the other hand, if every derivative is slightly larger than one, the entire derivative in the chain rule explodes, resulting in the problem of exploding gradients. Note that gradient vanishing is more common than gradient explosion in recurrent networks.

There exist various attempts for resolving the problem of gradient vanishing or explosion (Hochreiter, 1998; Bengio et al., 2013). In the following, some of these attempts are introduced.

### Close-to-identity Weight Matrix

As Eq. (4) shows, the state is multiplied by a weight matrix \(\mathbf{W}\) at every time step and if there is long-term dependency, many of these \(\mathbf{W}\) matrices are multiplied. Suppose the eigenvalue decomposition (Ghojogh et al., 2019) of the matrix \(\mathbf{W}\) is \(\mathbf{W}=\mathbf{A}\mathbf{\Lambda}\mathbf{A}^{\top}\) where \(\mathbf{A}\in\mathbb{R}^{p\times p}\) and \(\mathbf{\Lambda}:=\text{\bf diag}([\lambda_{1},\dots,\lambda_{p}]^{\top})\) contain the eigenvectors and eigenvalues of \(\mathbf{W}\), respectively. Eq. (4) is restated as:

\[\mathbf{h}_{t}=\tanh(\mathbf{A}\mathbf{\Lambda}\mathbf{A}^{\top}\mathbf{h}_{t-1}+\mathbf{U}\mathbf{x}_{t} +\mathbf{b}_{i}). \tag{25}\]

If a change \(\varepsilon\) in some element of the state \(\mathbf{h}_{t-1}\) is aligned with an eigenvector of the weight matrix \(\mathbf{W}\), then the effect of this change in \(\mathbf{h}_{t}\) will be \((\lambda^{t}\,\varepsilon)\) after \(t\) time steps, according to Eq. (25). Two cases may happen:

* If the largest eigenvalue is less than one, i.e., \(\lambda<1\), then the change \((\lambda^{t}\,\varepsilon)\) is contrastive because \(\lambda^{t}\ll 1\) for long-term dependencies. In this case, gradient vanishing occurs in long-term dependency and the network forgets very long time ago.
* If the largest eigenvalue is less than one, i.e., \(\lambda>1\), then the change \((\lambda^{t}\,\varepsilon)\) is diverging because \(\lambda^{t}\gg 1\) for long-term dependencies. In this case, the gradient network forgets very long time ago. In this case, gradient explosion occurs in long-term dependency and remembering very long time ago dominates the short-term memories.

As remembering short-term memories is usually more important than remembering very past time in different tasks, it is recommended to use the weight matrix \(\mathbf{W}\) whose largest eigenvalue is less than one; this makes the RNN have the Markovian property because it forgets very past after some point. However, if the largest eigenvalue of \(\mathbf{W}\) is much less than one, i.e., \(\lambda\ll 1\), gradient vanishing happens very sooner than expected. Therefore, it is recommended to use the weight matrix \(\mathbf{W}\) whose largest eigenvalue is _slightly_ less than one, i.e., \(\lambda\lesssim 1\). This makes the RNN slightly contrastive. One way to have the weight matrix \(\mathbf{W}\) whose largest eigenvalue is slightly less than one is to make this matrix close to the identity matrix (Mikolov et al., 2015).

There exist some other ways to determine the weight matrix \(\mathbf{W}\). For example, the wight matrix can be set to be an orthogonal matrix (Arjovsky et al., 2016). Another approach is to copy the previous state exactly to the current state. In this approach, the Eq. (4) is modified to (Hu et al., 2018):

\[\begin{split}\mathbf{h}_{t}&=\tanh(\mathbf{W}\mathbf{h}_{t-1}+ \mathbf{h}_{t-1}+\mathbf{U}\mathbf{x}_{t}+\mathbf{b}_{i})\\ &=\tanh\big{(}(\mathbf{W}+\mathbf{I})\mathbf{h}_{t-1}+\mathbf{U}\mathbf{x}_{t}+\mathbf{b}_ {i}\big{)},\end{split} \tag{26}\]

where \(\mathbf{I}\) is the identity matrix. This prevents gradient vanishing because it brings a copy of the previous step to the current state. This can also be interpreted as strengthening the diagonal of the weight matrix \(\mathbf{W}\); hence, increasing the largest eigenvalue of \(\mathbf{W}\) for preventing gradient vanishing.

### Long Delays

As Eq. (4) and Fig. 1-c show, in the regular RNN, every state \(\mathbf{h}_{t}\) is fed by its previous state \(\mathbf{h}_{t-1}\) through the weight matrix \(\mathbf{W}\). As discussed in Section 3.1, in the regular RNN, the effect of the change \(\varepsilon\) in a state results in \((\lambda^{t}\,\varepsilon)\) after \(t\) time steps, where \(\lambda\) is the largest eigenvalue of \(\mathbf{W}\).

As shown in Fig. 1-c, the regular RNN has one-step connections or delays between the states. It is possible to have longer delays between the states in addition to the one-step delays (Lin et al., 1995). In other words, it is possible to have higher levels of Markov property in the network. Let \(\mathbf{W}_{k}\) denote the weight matrix for \(k\)-step delays between the states. Then, Eq. (4) can be modified to:

\[\mathbf{h}_{t}=\tanh\Big{(}\sum_{k}\mathbf{W}_{k}\mathbf{h}_{t-k}+\mathbf{U}\mathbf{x}_{t}+\mathbf{b}_ {i}\Big{)}, \tag{27}\]

where the summation is over the \(k\) values for the existing
delays in the RNN structure. An example for an RNN network with one-step and three-step delays is:

\[\mathbf{h}_{t}=\tanh\Big{(}\mathbf{W}_{1}\mathbf{h}_{t-1}+\mathbf{W}_{3}\mathbf{h}_{t-3}+\mathbf{U}\mathbf{x} _{t}+\mathbf{b}_{i}\Big{)},\]

which is illustrated in Fig. 2.

Having long delays in RNN is one of the attempts for preventing gradient vanishing (Lin et al., 1995). This is justified because every state is having impact not only from the previous state but also from the more previous states. Therefore, in backpropagation through time, there is some skip in gradient flow from a state to more previous states without the need to go through the middle states in the chain rule.

### Leaky Units

Another way to resolve the problem of gradient vanishing is leaky units (Jaeger et al., 2007; Sutskever and Hinton, 2010). Let \(h_{t,j}\) denote the \(j\)-th element of the state \(\mathbf{h}_{t}\in[-1,1]^{p}\). In leaky units, Eq. (4) is modified to the following element-wise equation:

\[\begin{split} h_{t,j}=&\,(1-\frac{1}{\tau_{j}})\,h_ {t-1,j}\\ &+\frac{1}{\tau_{j}}\tanh(\mathbf{W}_{j};\mathbf{h}_{t-1}+\mathbf{U}_{j};\mathbf{ x}_{t}+b_{i,j}),\end{split} \tag{28}\]

where \(1\leq\tau_{j}<\infty\) and \(\mathbf{W}_{j:}\) is the \(j\)-th row of \(\mathbf{W}\) and \(\mathbf{U}_{j:}\) is the \(j\)-th row of \(\mathbf{U}\) and \(b_{i,j}\) is the \(j\)-th element of \(\mathbf{b}_{i}\). When \(\tau_{i}=1\), then Eq. (28) becomes:

\[h_{t,j}=\frac{1}{\tau_{j}}\tanh(\mathbf{W}_{j};\mathbf{h}_{t-1}+\mathbf{U}_{j};\mathbf{x}_{t}+b _{i,j}),\]

which gives back Eq. (4) in the regular RNN. However, when \(\tau_{i}\gg 1\), then Eq. (28) becomes:

\[h_{t,j}=h_{t-1,j},\]

which means that the previous state is copied to the current state. The larger the \(\tau_{i}\), the easier the gradient propagates for \(h_{t,i}\). Therefore, by tuning \(\tau_{i}\), it is possible to control how much of the past should be directly copied and how much should be passed through the weight matrix. This can control the amount of gradient vanishing. Note that leaky units use different \(\tau_{i}\)'s because there may be a need to keep some of the directions of states (with \(\tau_{i}=1\)) or forget some of the directions (with \(\tau_{i}\gg 1\)). In other words, it decides about the \(p\) directions of states separately.

### Echo State Networks

One of the approaches to handle the problem of gradient vanishing in RNN is to use echo state networks (Jaeger and Haas, 2004; Jaeger, 2007). These networks consider the recurrent neural network as a black box having hidden units with nonlinear activation functions and connections between them. This black box of recurrent connections is called the _reservoir dynamical system_ which models the internal structure of a computer or brain. The connections in the reservoir system are usually sparse and the weights of these connections are considered to be fixed. The output of the reservoir system is connected to an additional linear output layer whose weights are learnable. The echo state network minimizes the mean squared error in the output layer; hence, it performs linear regression in the last layer (Jaeger and Haas, 2004). This network is shown in Fig. 3. Because of not learning the recurrent weights in the reservoir system and sufficing to learn the weights of the output layer, the echo state network does not face the gradient vanishing problem. A tutorial on this topic is (Jaeger, 2002).

### Other methods

There exist some other methods for not having gradient vanishing in recurrent networks. For example, hierarchical RNN (Hihi and Bengio, 1995) and deep RNN (Graves, 2013) have been proposed which stack several recurrent networks. Another related category of networks is the time-delay neural networks (Lang et al., 1990; Peddinti et al., 2015) which are used for shift-invariant sequence processing, especially used in speech recognition (Sugiyama et al., 1991). In these networks, every neuron in a layer receives a contextual window of the neurons in the previous layer as well as their delayed outputs in several time slots ago. Moreover, these networks apply backpropagation on several copies of the network shifted across the sequence

Figure 3: The echo state network.

Figure 2: The (a) folded and (b) unfolded structures of an RNN with long delays. Every square on an edge means connection from one time slot before.
(time) so that the network becomes time-invariant.

## 4 Long Short-Term Memory Network

As the examples in Section 1 showed, we need short-term relations in some cases and long-term relations in some other cases. RNN learns the sequence based on one or several previous states, depending on its structure and the level of its Markov property (see Fig. 2). Therefore, we need to decide on the structure of RNN to be able to handle short-term or long-term dependencies in the sequence. Instead of manual design of the RNN structure or deciding manually when to clear the state, we can let the neural network learn by itself when to clear the state based on its input sequence. Long Short-Term Memory (LSTM), initially proposed in (Hochreiter & Schmidhuber, 1995; 1997), is able to do this; it learns from its input sequence when to use short-term dependency (i.e., when to clear the state) and when to use the long-term memory (i.e., when not to clear the state).

### LSTM Gates and Cells

LSTM consists of several cells, each of which corresponds to a time slot (see Fig. 4). Every LSTM cell contains several gates for learning different aspects of the input time series (see Fig. 5). These gates are introduced in the following.

#### 4.1.1 The Input Gate

One of the gates in the LSTM cell is the _input gate_, first proposed in (Hochreiter & Schmidhuber, 1995; 1997). This gate takes the input at the current time slot, \(\mathbf{x}_{t}\in\mathbb{R}^{d}\), and the hidden state of the last time slot, \(\mathbf{h}_{t-1}\in[-1,1]^{p}\), and outputs the signal \(\mathbf{i}_{t}\in[0,1]^{p}\):

\[\mathbf{i}_{t}=\text{sig}\big{(}\mathbf{W}_{i}\,\mathbf{h}_{t-1}+\mathbf{U}_{i}\,\mathbf{x}_{t}+( \mathbf{p}_{i}\odot\mathbf{c}_{t-1})+\mathbf{b}_{i}\big{)}, \tag{29}\]

where \(\mathbf{W}_{i}\in\mathbb{R}^{p\times p}\), \(\mathbf{U}_{i}\in\mathbb{R}^{p\times d}\), and the bias \(\mathbf{b}_{i}\in\mathbb{R}^{p}\) are the learnable weights for the input gate, \(\odot\) denotes the Hadamard (element-wise) product, \(\mathbf{c}_{t-1}\in\mathbb{R}^{p}\) is the final memory of the last time slot (which will be explained in Section 4.1.5), and \(\mathbf{p}_{i}\in\mathbb{R}^{p}\) is the learnable _peephole weight_(Gers & Schmidhuber, 2000) letting a possible leak of information from the previous final memory. The function \(\text{sig}(.)\in(0,1)\) is the sigmoid function which is applied element-wise:

\[\text{sig}(x)=\frac{1}{1+\exp(-x)}. \tag{30}\]

As Eq. (29) demonstrates, the input gate considers the effect of the input and the previous hidden state. It may also use a leak of information from the previous memory through the peephole. This gate carries the importance of the information of the input at the current time slot. The input gate is depicted in Fig. 5.

#### 4.1.2 The Forget Gate

Another gate in the LSTM cell is the _forget gate_, first proposed in (Gers et al., 2000). This gate also takes the input at the current time slot, \(\mathbf{x}_{t}\in\mathbb{R}^{d}\), and the hidden state of the last time slot, \(\mathbf{h}_{t-1}\in[-1,1]^{p}\), and outputs the signal \(\mathbf{f}_{t}\in[0,1]^{p}\):

\[\mathbf{f}_{t}=\text{sig}\big{(}\mathbf{W}_{f}\,\mathbf{h}_{t-1}+\mathbf{U}_{f}\,\mathbf{x}_{t}+( \mathbf{p}_{f}\odot\mathbf{c}_{t-1})+\mathbf{b}_{f}\big{)}, \tag{31}\]

where \(\mathbf{W}_{f}\in\mathbb{R}^{p\times p}\), \(\mathbf{U}_{f}\in\mathbb{R}^{p\times d}\), and the bias \(\mathbf{b}_{f}\in\mathbb{R}^{p}\) are the learnable weights for the forget gate, and \(\mathbf{p}_{f}\in\mathbb{R}^{p}\) is the learnable _peephole weight_(Gers & Schmidhuber, 2000) letting a possible leak of information from the previous final memory.

As Eq. (31) shows, the forget gate considers the effect of the input and the previous hidden state, and perhaps a leak of information from the previous memory. This gate controls the amount of forgetting the previous information with respect to the new-coming information. the forget gate is illustrated in Fig. 5.

#### 4.1.3 The Output Gate

The next gate in the LSTM cell is the _output gate_ first proposed in (Hochreiter & Schmidhuber, 1995; 1997). This gate also takes the input at the current time slot, \(\mathbf{x}_{t}\in\mathbb{R}^{d}\), and the hidden state of the last time slot, \(\mathbf{h}_{t-1}\in[-1,1]^{p}\), and outputs the signal \(\mathbf{o}_{t}\in[0,1]^{p}\):

\[\mathbf{o}_{t}=\text{sig}\big{(}\mathbf{W}_{o}\,\mathbf{h}_{t-1}+\mathbf{U}_{o}\,\mathbf{x}_{t}+( \mathbf{p}_{o}\odot\mathbf{c}_{t})+\mathbf{b}_{o}\big{)}, \tag{32}\]

where \(\mathbf{W}_{o}\in\mathbb{R}^{p\times p}\), \(\mathbf{U}_{o}\in\mathbb{R}^{p\times d}\), and the bias \(\mathbf{b}_{o}\in\mathbb{R}^{p}\) are the learnable weights for the output gate, and \(\mathbf{p}_{o}\in\mathbb{R}^{p}\) is the learnable _peephole weight_(Gers & Schmidhuber, 2000) letting a possible leak of information from the current final memory.

As shown in Eq. (32), the output gate considers the effect of the input and the previous hidden state, and a possible information leak from the current memory. The output gate is shown in Fig. 5.

#### 4.1.4 The New Memory Cell (Block Input)

The LSTM cell includes a gate named the _new memory cell_. This gate takes the input at the current time slot, \(\mathbf{x}_{t}\in\mathbb{R}^{d}\), and the hidden state of the last time slot, \(\mathbf{h}_{t-1}\in[-1,1]^{p}\), and outputs the signal \(\widetilde{\mathbf{c}}_{t}\in[-1,1]^{p}\). This gate considers the effect of the input and the previous hidden state to represent the new information of current input. It is formulated as:

\[\widetilde{\mathbf{c}}_{t}=\tanh(\mathbf{W}_{c}\,\mathbf{h}_{t-1}+\mathbf{U}_{c}\,\mathbf{x}_{t}+ \mathbf{b}_{c}), \tag{33}\]

where \(\mathbf{W}_{c}\in\mathbb{R}^{p\times p}\), \(\mathbf{U}_{c}\in\mathbb{R}^{p\times d}\), and the bias \(\mathbf{b}_{c}\) are the learnable weights for the new memory cell. The new memory cell is also referred to as the _block input_ in the literature (Greff et al., 2016). The signal \(\widetilde{\mathbf{c}}_{t}\) is sometimes denoted by
\(\mathbf{z}_{t}\) in the literature. The new memory cell is illustrated in Fig. 5.

#### 4.1.5 The Final Memory Calculation

After computation of the outputs of the input gate \(\mathbf{i}_{t}\), the forget gate \(\mathbf{f}_{t}\), and the new memory cell \(\widetilde{\mathbf{c}}_{t}\), we calculate the _final memory_\(\mathbf{c}_{t}\in\mathbb{R}^{p}\):

\[\mathbf{c}_{t}=(\mathbf{f}_{t}\odot\mathbf{c}_{t-1})+(\mathbf{i}_{t}\odot\widetilde{\mathbf{c}}_{t }), \tag{34}\]

where \(\mathbf{c}_{t-1}\in\mathbb{R}^{p}\) is the final memory of the previous time slot.

As Eq. (34) demonstrates, the final memory considers the effect of the forget gate, the previous memory, the input, and the new memory. In the first term, i.e., \(\mathbf{f}_{t}\odot\mathbf{c}_{t-1}\), the forget gate \(\mathbf{f}_{t}\in[0,1]^{p}\) controls how much of the previous memory \(\mathbf{c}_{t-1}\) should be forgotten. The closer the \(\mathbf{f}_{t}\) is to zero, the more the network forgets the previous memory \(\mathbf{c}_{t-1}\). In the second term, i.e., \(\mathbf{i}_{t}\odot\widetilde{\mathbf{c}}_{t}\), the input gate \(\mathbf{i}_{t}\in[0,1]^{p}\) and the new memory cell \(\widetilde{\mathbf{c}}_{t}\in[-1,1]^{p}\) both control how much of the new input information should be used. The closer the input gate \(\mathbf{i}_{t}\) is to one and the closer the new memory cell \(\widetilde{\mathbf{c}}_{t}\) is to \(\pm 1\), the more the input information is used.

In other words, the first and second terms in Eq. (34) determine the trade-off of usage of old versus new information in the sequence. The weights of these gates are trained in a way that they pass or block the input/previous information based on the input sequence and the time step in the sequence. The final memory calculation is depicted in Fig. 5.

#### 4.1.6 The Hidden State (Block Output)

After computation of the output of the output gate \(\mathbf{o}_{t}\) and the final memory \(\mathbf{c}_{t}\), we calculate the _hidden state_\(\mathbf{h}_{t}\in\mathbf{c}_{t-1}\). The hidden state \(\mathbf{h}_{t}\) is the hidden state \(\mathbf{h}_{t}\). The hidden state \(\mathbf{h}_{t}\) is the hidden state \(\mathbf{h}_{t}\).
\([-1,1]^{p}\):

\[\mathbf{h}_{t}=\mathbf{o}_{t}\odot\tanh(\mathbf{c}_{t}). \tag{35}\]

This hidden state is also considered as the _block output_ of the LSTM cell, depicted in Fig. 5.

#### 4.1.7 The Output

The output \(\mathbf{y}_{t}\in\mathbb{R}^{q}\) of the LSTM cell is as follows:

\[\mathbf{y}_{t}=\mathbf{V}\mathbf{h}_{t}+\mathbf{b}_{y}, \tag{36}\]

where \(\mathbf{V}\in\mathbb{R}^{q\times p}\) and the bias \(\mathbf{b}_{y}\in\mathbb{R}^{q}\) are the learnable weights for the output. It is possible to use an activation function, such as Eq. (6), after this output signal. Figure 5 shows the output signal in the LSTM cell.

Note that in the literature, the output is sometimes considered to be equal to the hidden state, i.e., \(\mathbf{y}_{t}=\mathbf{h}_{t}\), by setting \(\mathbf{V}=\mathbf{I}\) (the identity matrix) and \(\mathbf{b}_{y}=\mathbf{0}\) (the zero vector).

### History and Variants of LSTM

LSTM has gone through various developments and improvements gradually (Greff et al., 2016). Some of the variants of LSTM do not have the peepholes. In this case, the Eqs. (29), (31), and (32) are simplified to:

\[\mathbf{i}_{t}=\text{sig}\big{(}\mathbf{W}_{i}\,\mathbf{h}_{t-1}+\mathbf{U}_{i}\, \mathbf{x}_{t}+\mathbf{b}_{i}\big{)}, \tag{37}\] \[\mathbf{f}_{t}=\text{sig}\big{(}\mathbf{W}_{f}\,\mathbf{h}_{t-1}+\mathbf{U}_{f}\, \mathbf{x}_{t}+\mathbf{b}_{f}\big{)},\] (38) \[\mathbf{o}_{t}=\text{sig}\big{(}\mathbf{W}_{o}\,\mathbf{h}_{t-1}+\mathbf{U}_{o}\, \mathbf{x}_{t}+\mathbf{b}_{o}\big{)}, \tag{39}\]

respectively. In the following, we review a history of variants of the LSTM networks.

#### 4.2.1 Original LSTM

LSTM was originally proposed by Hochreiter and Schmidhuber in years 1995 to 1997 (Hochreiter & Schmidhuber, 1995; 1997). We call it the _original LSTM_(Hochreiter & Schmidhuber, 1997). The original LSTM had only the input and output gates, introduced in Sections 4.1.1 and 4.1.3, and it did not have a forget gate. It also did not contain the peepholes; therefore, its gates were Eqs. (37) and (39). The original LSTM trained the network using BPTT (introduced in Section 2.3) and a mixture of real-time recurrent learning (Robinson & Fallside, 1987; Williams, 1989).

#### 4.2.2 Vanilla LSTM

Later, Gers _et. al._(Gers et al., 2000; Gers & Schmidhuber, 2000) applied some changes to the original LSTM. The forget gate, introduced in Section 4.1.2, was proposed for the first time in (Gers et al., 2000) to let the network forget its previous states either completely or partially. The peephole connections, introduced in Sections 4.1.1, 4.1.2, and 4.1.3, were first proposed in (Gers & Schmidhuber, 2000). The peepholes let a possible leak of information from the previous or current final memory. This lets the memory control the gates.

These two papers (Gers et al., 2000; Gers & Schmidhuber, 2000) also incorporated the _full gate recurrence_, in which all gates receive additional recurrent inputs from all gates at the previous time step. In full gate recurrence, the Eqs. (29), (31), and (32) become:

\[\begin{split}\dot{\mathbf{i}}_{t}=\text{sig}\big{(}& \mathbf{W}_{i}\,\mathbf{h}_{t-1}+\mathbf{U}_{i}\,\mathbf{x}_{t}+(\mathbf{p}_{i}\odot\mathbf{c}_{t-1})+ \mathbf{b}_{i}\\ &+\mathbf{R}_{ii}\,\dot{\mathbf{i}}_{t-1}+\mathbf{R}_{if}\,\mathbf{f}_{t-1}+\mathbf{R }_{io}\,\mathbf{o}_{t-1}\big{)}.\end{split} \tag{40}\]

\[\begin{split}\mathbf{f}_{t}=\text{sig}\big{(}& \mathbf{W}_{f}\,\mathbf{h}_{t-1}+\mathbf{U}_{f}\,\mathbf{x}_{t}+(\mathbf{p}_{f}\odot\mathbf{c}_{t-1})+ \mathbf{b}_{f}\\ &+\mathbf{R}_{fi}\,\dot{\mathbf{i}}_{t-1}+\mathbf{R}_{ff}\,\mathbf{f}_{t-1}+\mathbf{R }_{fo}\,\mathbf{o}_{t-1}\big{)}.\end{split} \tag{41}\]

\[\begin{split}\mathbf{o}_{t}=\text{sig}\big{(}& \mathbf{W}_{o}\,\mathbf{h}_{t-1}+\mathbf{U}_{o}\,\mathbf{x}_{t}+(\mathbf{p}_{o}\odot\mathbf{c}_{t})+ \mathbf{b}_{o}\\ &+\mathbf{R}_{oi}\,\dot{\mathbf{i}}_{t-1}+\mathbf{R}_{of}\,\mathbf{f}_{t-1}+\mathbf{R }_{oo}\,\mathbf{o}_{t-1}\big{)},\end{split} \tag{42}\]

where \(\mathbf{R}_{ii},\mathbf{R}_{if},\mathbf{R}_{io},\mathbf{R}_{fi},\mathbf{R}_{ff},\mathbf{R}_{fo},\mathbf{R }_{oi},\mathbf{R}_{of},\mathbf{R}_{oo}\in\mathbb{R}^{p\times p}\) are the learnable recurrent weights. Note that the full gate recurrence often disappeared in later papers on LSTM. Later, Graves and Schmidhuber adapted the original LSTM and proposed the _vanilla LSTM_ in 2005 (Graves & Schmidhuber, 2005a), which is one of the most common LSTMs in the literature. The vanilla LSTM incorporated the structures of the original LSTM (Hochreiter & Schmidhuber, 1997) and the papers (Gers et al., 2000; Gers & Schmidhuber, 2000). The full BPTT, introduced in Section 2.3, was used for LSTM in the vanilla LSTM (Graves & Schmidhuber, 2005a).

#### 4.2.3 Other LSTM Variants

There are other variants of LSTM (Greff et al., 2016; Jozefowicz et al., 2015); although, the most common used LSTM is the vanilla LSTM (Graves & Schmidhuber, 2005a). BPTT was used for LSTM training in (Graves & Schmidhuber, 2005a); however, Kalman filtering was used for its training (Gers et al., 2002) before that. Another training method for LSTM was evolutionary learning (Schmidhuber et al., 2007). Context-sensitive evolutionary learning was also used for LSTM training (Bayer et al., 2009).

Later works tried to improve the performance of LSTM. For example, Sak _et. al._ added a linear layer which projects the output of the LSTM to smaller number of parameters before the recurrent connections (Sak et al., 2014). Doetsch _et. al._ converted the slope of activation functions of the LSTM gates to learnable parameters for performance improvement (Doetsch et al., 2014). _Dynamic cortex memory_ was another LSTM variant which added connections between the gates within every LSTM cell (Otte et al., 2014). Finally in 2014, one the biggest improvements of LSTM was proposed, which was named the Gated Recurrent Units (GRU) (Cho et al., 2014). The philosophy of GRU was to simplify the LSTM cell because we may no need to have a very complicated cell to learn the sequence information. In
other words, GRU raised the question of whether we need to be that flexible like LSTM to learn the sequence. GRU is less flexible than LSTM but it is good enough for sequence learning.

GRU redesigned the LSTM cell by introducing reset gate, update gate, and new memory cell; therefore, the number of gates were reduced from four to three. It was empirically shown in (Chung et al., 2014) that the performance of LSTM improves by using GRU cells. Later in 2017, the GRU was further simplified by merging the reset and update gates into a forget gate (Heck and Salem, 2017). Nowadays, GRU is the most commonly used LSTM structure. Section 4.3 introduces the details of the GRU cell.

### Gated Recurrent Units (GRU)

GRU was first proposed in (Cho et al., 2014). As was mentioned in Section 4.2.3, GRU simplified the LSTM cell in order to make the flexibility of LSTM.

#### 4.3.1 Fully Gated Unit

The main GRU was the _fully gated unit_(Cho et al., 2014), whose gates are introduced in the following. Its gates are illustrated in Fig. 6.

**- The Reset Gate:** One of the gates in the GRU cell is the _reset gate_. This gate takes the input at the current time slot, \(\mathbf{x}_{t}\in\mathbb{R}^{d}\), and the hidden state of the last time slot, \(\mathbf{h}_{t-1}\in[-1,1]^{p}\), and outputs the signal \(\mathbf{r}_{t}\in[0,1]^{p}\):

\[\mathbf{r}_{t}=\text{sig}(\mathbf{W}_{r}\,\mathbf{h}_{t-1}+\mathbf{U}_{r}\,\mathbf{x}_{t}+\mathbf{b}_{ r}), \tag{43}\]

where \(\mathbf{W}_{r}\in\mathbb{R}^{p\times p}\), \(\mathbf{U}_{r}\in\mathbb{R}^{p\times d}\), and the bias \(\mathbf{b}_{r}\in\mathbb{R}^{p}\) are the learnable weights for the reset gate. The reset gate considers the effect of the input and the previous hidden state, and it controls the amount of forgetting/resetting the previous information with respect to the new-coming information. Comparing Eqs. (38) and (43) shows that the reset gate in the GRU cell is similar to the forget gate in the LSTM cell. The reset gate is depicted in Fig. 6.

**- The Update Gate:** Another gate in the GRU cell is the _update gate_. This gate also takes the input at the current time slot, \(\mathbf{x}_{t}\in\mathbb{R}^{d}\), and the hidden state of the last time slot, \(\mathbf{h}_{t-1}\in[-1,1]^{p}\), and outputs the signal \(\mathbf{z}_{t}\in[0,1]^{p}\):

\[\mathbf{z}_{t}=\text{sig}(\mathbf{W}_{z}\,\mathbf{h}_{t-1}+\mathbf{U}_{z}\,\mathbf{x}_{t}+\mathbf{b}_{ z}), \tag{44}\]

where \(\mathbf{W}_{z}\in\mathbb{R}^{p\times p}\), \(\mathbf{U}_{z}\in\mathbb{R}^{p\times d}\), and the bias \(\mathbf{b}_{z}\in\mathbb{R}^{p}\) are the learnable weights for the update gate. The update gate considers the effect of the input and the previous hidden state, and it controls the amount of using the new input data for updating the cell by the coming information of sequence. Comparing Eqs. (37) and (44) shows that the update gate in the GRU cell is similar to the input gate in the LSTM cell. Figure 6 shows the update gate in the GRU cell.

**- The New Memory Cell:** The GRU cell includes a gate named the _new memory cell_. This gate takes the input at the current time slot, \(\mathbf{x}_{t}\in\mathbb{R}^{d}\), and the hidden state of the last time slot, \(\mathbf{h}_{t-1}\in[-1,1]^{p}\), and outputs the signal

Figure 6: The conveyor belt in the GRU cell (the fully gated unit).
\(\widetilde{\mathbf{h}}_{t}\in[-1,1]^{p}\):

\[\widetilde{\mathbf{h}}_{t}=\tanh\Bigl{(}\mathbf{W}_{c}\left(\mathbf{r}_{t}\odot\mathbf{h}_{t-1} \right)\Bigr{)}+\mathbf{U}_{c}\,\mathbf{x}_{t}+\mathbf{b}_{c}\Bigr{)}, \tag{45}\]

where \(\mathbf{W}_{c}\in\mathbb{R}^{p\times p}\), \(\mathbf{U}_{c}\in\mathbb{R}^{p\times d}\), and the bias \(\mathbf{b}_{c}\) are the learnable weights for the new memory cell. This gate considers the effect of the input and the previous hidden state to represent the new information of current input. Comparing Eqs. (33) and (45) shows that the new memory cell in the GRU cell is similar to the new memory cell in the LSTM cell. Note that, in the LSTM cell, the hidden state (see Eq. (35)) and the new memory cell (see Eq. (33)) were different; however, the hidden state of the GRU cell (see Eq. (45)) replaces the new memory signal in the LSTM cell. The new memory cell is shown in Fig. 6.

**- The Final Memory (Hidden State):** After computation of the outputs of the update gate \(\mathbf{z}_{t}\) and the new memory cell \(\widetilde{\mathbf{h}}_{t}\), we calculate the _final memory_ or the _hidden state_\(\mathbf{h}_{t}\in\mathbb{R}^{p}\):

\[\mathbf{h}_{t}=\bigl{(}(\mathbf{1}-\mathbf{z}_{t})\odot\mathbf{h}_{t-1}\bigr{)}+(\mathbf{z}_{t} \odot\widetilde{\mathbf{h}}_{t}), \tag{46}\]

where \(\mathbf{h}_{t-1}\in\mathbb{R}^{p}\) is the hidden state of the previous time slot. The final memory block is illustrated in Fig. 6.

As Eq. (46) demonstrates, the final memory considers the effect of the update gate, the previous memory, and the new memory. In the first term, i.e., \((\mathbf{1}-\mathbf{z}_{t})\odot\mathbf{h}_{t-1}\), the update gate \(\mathbf{z}_{t}\in[0,1]^{p}\) controls how much of the previous state \(\mathbf{h}_{t-1}\) should be used based on the input data. The closer the \(\mathbf{z}_{t}\) is to one (resp. zero), the more the network forgets (resp. considers) the previous state \(\mathbf{h}_{t-1}\). In the second term, i.e., \(\mathbf{z}_{t}\odot\widetilde{\mathbf{h}}_{t}\), the update gate \(\mathbf{z}_{t}\in[0,1]^{p}\) and the new memory cell \(\widetilde{\mathbf{h}}_{t}\in[-1,1]^{p}\) both control how much of the new input information should be used. In other words, it controls how much the information should be updated by the new information. The closer the update gate \(\mathbf{z}_{t}\) is to one and the closer the new memory cell \(\widetilde{\mathbf{h}}_{t}\) is to \(\pm 1\), the more the input information is used.

Overall, the first and second terms in Eq. (46) determine the trade-off of usage of old versus new information in the sequence. The weights of these gates are trained in a way that they pass or block the input/previous information based on the input sequence and the time step in the sequence. Comparing Eqs. (34) and (46) shows that the final memory in the GRU cell is in the form of the final memory in the LSTM cell; however, they have somewhat different functionality.

#### 4.3.2 Minimal Gated Unit

_Minimal gated unit_(Heck & Salem, 2017) is another variant of GRU which has simplified the gate by merging the reset and update gates into a forget gate. This merging is possible because the forget gate can control both the previous and new information of the sequence.

**- The Forget Gate:** The _forget gate_ takes the input at the current time slot, \(\mathbf{x}_{t}\in\mathbb{R}^{d}\), and the hidden state of the last time slot, \(\mathbf{h}_{t-1}\in[-1,1]^{p}\), and outputs the signal \(\mathbf{r}_{t}\in[0,1]^{p}\):

\[\mathbf{f}_{t}=\text{sig}(\mathbf{W}_{f}\,\mathbf{h}_{t-1}+\mathbf{U}_{f}\,\mathbf{x}_{t}+\mathbf{b}_{ f}), \tag{47}\]

where \(\mathbf{W}_{f}\in\mathbb{R}^{p\times p}\), \(\mathbf{U}_{f}\in\mathbb{R}^{p\times d}\), and the bias \(\mathbf{b}_{f}\in\mathbb{R}^{p}\) are the learnable weights for the forget gate. The forget gate considers the effect of the input and the previous hidden state, and it controls the amount of forgetting the previous information with respect to the new-coming information. Therefore, it controls both forgetting or using the previous memory and using the new coming information.

**- The New Memory Cell and the Final Memory:** Because the forget gate replaces the reset and the update gate in the minimal gate unit, Eqs. (45) and (46) are changed to:

\[\widetilde{\mathbf{h}}_{t} =\tanh\Bigl{(}\mathbf{W}_{c}\left(\mathbf{f}_{t}\odot\mathbf{h}_{t-1}) \right)+\mathbf{U}_{c}\,\mathbf{x}_{t}+\mathbf{b}_{c}\Bigr{)}, \tag{48}\] \[\mathbf{h}_{t} =\bigl{(}(\mathbf{1}-\mathbf{f}_{t})\odot\mathbf{h}_{t-1}\bigr{)}+(\mathbf{f}_{t} \odot\widetilde{\mathbf{h}}_{t}), \tag{49}\]

respectively, to be the new memory cell and the final memory in the minimal gate unit.

## 5 Bidirectional RNN and LSTM

### Justification of Bidirectional Processing

A bidirectional RNN or LSTM network processes the sequence in both directions; left to right and right to left. In the first glance, online causal tasks such as reading a text or listening to a speech do not have access to the future. Therefore, bidirectional networks seem to violate causality in them. However, in many of these tasks, it is possible to wait for the completion of a part of the sequence such as a sentence and then decide about it. For example, it is normal to wait for the completion of sentence in speech recognition and then recognize it (Graves & Schmidhuber, 2005a;b). In text processing, the text is usually available except in a streaming text. Even in streaming text, it is possible to wait for a sentence to complete. Therefore, it makes sense to use bidirectional networks for processing sequences because, sometimes, the important related word comes after a word and not necessarily before it. An example for such a case is the sentence "The police is chasing the thief" where the word "thief" is a strongly related (opposite) word for the word "police". In this sentence, both the words "thief" and "police" are related and it is worth to process the sentence in both directions.

### Bidirectional RNN

The bidirectional RNN was first proposed in (Schuster & Paliwal, 1997) and further exploited in (Baldi et al., 1999). It uses two sets of states each for one of the directions in
the sequence. Let the states for left-to-right and right-to-left processing be denoted by \(\overrightarrow{\boldsymbol{h}}_{t}\) and \(\overleftarrow{\boldsymbol{h}}_{t}\), respectively. In the bidirectional RNN, Eq. (4) is replaced by two equations (Graves et al., 2013):

\[\overrightarrow{\boldsymbol{h}}_{t}=\tanh(\overrightarrow{ \boldsymbol{W}}\overrightarrow{\boldsymbol{h}}_{t-1}+\overrightarrow{ \boldsymbol{U}}\boldsymbol{x}_{t}+\overrightarrow{\boldsymbol{b}}_{i}), \tag{50}\] \[\overleftarrow{\boldsymbol{h}}_{t}=\tanh(\overleftarrow{ \boldsymbol{W}}\overleftarrow{\boldsymbol{h}}_{t+1}+\overleftarrow{ \boldsymbol{U}}\boldsymbol{x}_{t}+\overleftarrow{\boldsymbol{b}}_{i}), \tag{51}\]

and Eq. (5) is replaced by:

\[\boldsymbol{y}_{t}=\overrightarrow{\boldsymbol{V}}\overrightarrow{ \boldsymbol{h}}_{t}+\overleftarrow{\boldsymbol{V}}\overleftarrow{ \boldsymbol{h}}_{t}+\boldsymbol{b}_{y}, \tag{52}\]

where the arrows show the parameters for each direction of processing. The unfolding schematic of the bidirectional RNN is illustrated in Fig. 7. As this figure shows, the outputs of both directions are connected to an output layer. In some cases, this output layer may be replaced by a third multi-layer neural network. All weights of the bidirectional RNN are trained using backpropagation through time similarly to what was explained in Section 2.3. It is noteworthy that the deep variant of bidirectional RNN has been proposed in (Graves et al., 2013).

### Bidirectional LSTM

Bidirectional LSTM was first proposed in (Graves and Schmidhuber, 2005; 20). As obvious from its name, the bidirectional LSTM includes two LSTM networks each of which processes the sequence from one direction. In other words, there are two LSTM networks which are fed with the sequence in opposite orders. This structure is depicted in Fig. 8. Experiments have shown that the bidirectional LSTM outperforms the unidirectional LSTM (Graves and Schmidhuber, 2005; Graves et al., 2005). This is expected according to the justification in Section 5.1. Because of its advantages, various methods have combined the bidirectional LSTM with other methods. For example, a hybrid of the bidirectional LSTM and HMM (Ghojogh et al., 2019) has shown its merit (Graves et al., 2005). Another example is the hybrid of bidirectional LSTM and Conditional Random Fields (CRF) (Lafferty et al., 2001) for the sequence tagging task (Huang et al., 2015). Other extensions of bidirectional LSTM networks exist such as (Peters et al., 2017).

### Embeddings from Language Model (ELMo)

The Embeddings from Language Model (ELMo) network, first proposed in (Peters et al., 2018), is a language model which makes use of bidirectional LSTM networks. It is one of the successful context-aware language modeling networks. It has been widely used in various applications such as in medical interview processing (Sarzynska-Wawer et al., 2021).

The structure of ELMo is illustrated in Fig. 9. As shown in this figure, ELMo contains \(L\) layers of bidirectional LSTM networks where the output of each bidirectional LSTM is fed to the next bidirectional LSTM. in The bidirectional LSTM networks of ELMo, \(\boldsymbol{V}=\boldsymbol{I}\) is set so that the outputs \(\boldsymbol{y}\) becomes equal to the hidden states \(\boldsymbol{h}\). At time slot \(t\) and layer \(l\), the outputs (or hidden states) of the two directions of LSTM are concatenated together to make \(\boldsymbol{h}_{t}^{(l)}\):

\[\boldsymbol{h}_{t}^{(l)}:=[\overrightarrow{\boldsymbol{h}}_{t}^{(l)\top}, \overleftarrow{\boldsymbol{h}}_{t}^{(l)\top}]^{\top}.\]

Then, a linear combination of these hidden states of layers is considered to be the embedding vector of ELMo network at time \(t\)(Peters et al., 2018):

\[\boldsymbol{y}_{t}^{\text{ELMo}}:=\gamma\sum_{l=1}^{L}s_{l}\, \boldsymbol{h}_{t}^{(l)}, \tag{53}\]

where \(\gamma\) and \(\{s_{l}\}_{l=1}^{L}\) are the hyperparameter scalar weights which are determined according to the specific task (e.g.,

Figure 8: The bidirectional LSTM.

Figure 7: The bidirectional RNN.
question answering, translation, etc) in natural language processing.

## 6 Conclusion

This was a tutorial paper on RNN, LSTM, and its variants. We covered dynamical system, backpropagation through time, LSTM gates and cells, history and variants of LSTM, the GRU cell, bidirectional RNN, bidirectional LSTM, and ELMo network.
