This post, as the first in the series, will present the concept of a recurrent neuron and its limitations. Next posts will discuss gated neurons like LSTM and GRU, variants of dropout regularization for RNNs and some advanced stuff that I found interesting (bi-directional RNN, Multiplicative LSTM and etc).

The next section is dedicated to review the notations and basic terminology that will be used during the entire series. I will assume that the reader is familiar with the basics of neural network (fully connected architecture, back-propagation algorithm, etc). If you are not familiar with one of those concepts, I strongly recommend to review them online before going further. Those notes provides concise introduction to the field. There is also an excellent video-lecture (in Hebrew) by Prof. Shai Shalev-Shwartz from 2016. If you really want to dive deeper, you can find broad introduction in Chapter 6 in Deep Learning book (legally free electronic version here).

Neurons are organized within layers. In the very basic ANN architecture, called a fully connected (FC) neural network, a layer is just a collection of neurons that will be computed in parallel (meaning that they are not connected to each other). For any layer $i$ , each of its neurons accepts as inputs all neurons from layer $i-1$ .

A layer in FC architecture can be formulate mathematically as a function from $\mathbb{R}^{d}$ to $\mathbb{R}^{n}$ such that $$\mathbf{f}:\mathbf{x}\mapsto\left(\begin{array}{c} g_{1}\left(\mathbf{x}\right)\\ \vdots\\ g_{n}\left(\mathbf{x}\right) \end{array}\right)$$ where each $g_{i}$ is a function of a neuron as defined above, with its own weight vector and a bias scalar. The formulation can be simplified using matrix notations: $$\mathbf{f}:\mathbf{x}\mapsto\sigma\left(W\mathbf{x}+\mathbf{b}\right)$$ where $W\in\mathbb{R}^{n\times d}$ contains in the i-th row the weight vector of $g_{i}$ , and $\mathbf{b}_{i}$ is the bias of $g_{i}$ . The function $\sigma$ is the same as before but since its input is now a vector, it apply element-wise on each coordinate of the input, producing an output vector of the same length.

We denote the family of all possible FC functions based on some fixed activation function as $$\mathcal{F}_{\sigma}=\left\{ \mathbf{x}\mapsto\sigma\left(W\mathbf{x}+\mathbf{b}\right)\mid\forall W,\mathbf{b}\right\}$$ that family contains all possible layers for any input\output dimension. For abbreviation, I will not mention the dimensions of layers or the specific activation function $\sigma$ when they are not important for the discussion.

Applying several layers sequentially yield a feedforward FC neural network. That is, given $\mathbf{x}\in\mathbb{R}^{d}$ , a FC network with $t$ layers is $$\mathcal{N}\left(\mathbf{x}\right)=\mathbf{f}_{t}\left(...\mathbf{f}_{2}\left(\mathbf{f}_{1}\left(\mathbf{x}\right)\right)\right)$$ where $\forall i:\:\mathbf{f}_{i}\in\mathcal{F}_{\sigma}$ for some fixed $\sigma$ .

The number of layers in the network is its depth, and the size of the layers is its width (assuming all the layers are of the same dimension). Training the network is optimizing all the weight matrices and bias vectors such that the network will approximate some target (usually unknown) function. We can think of the optimization process as a process of iteratively updating the choice of layer functions $\mathbf{f}_{1},\mathbf{f}_{2},..$ from the family $\mathcal{F}_{\sigma}$ .

The FC architecture is simple, yet yields a very powerful model. When wide enough, even a single hidden layer network can approximate to any arbitrary precision almost any continuous function (under some mild assumptions). However, for some tasks it might not be optimal, and different architectures are being used, instead of the FC one.

How can we build a model for next-word prediction using FC neural network?

The obvious answer is to fix some window size $d$ , and build a network that gets the last $d$ words in the sentence as features, in order to predict the next word. One immediate limitation of this approach is that the window size is the same for all the examples in the training set, and it is not simple to find a suitable window size. On the one hand, choosing small window may cause the model to miss some important long term relations between words that are more than $d$ steps apart (for sentences longer than $d$ ). On the other hand, choosing very large $d$ increases the number of parameters in the model, which make the optimization harder, and increase the computation time per example, which affect both training-time and prediction-time.

Another limitation is that FC layers regards their inputs as ordered information. That is, a FC layer assigns a specific weight for each coordinate in its input vector, causing the order of the features to be meaningful. But in some tasks the order of the features may vary, for example, the subject of a sentence doesn’t limit to specific location inside an English sentence. If we want FC layer to account for that, we have to get a lot of examples (and they need to cover all different cases).

What we would like to have here is called parameter sharing. We will come back to that term later in this post.

We will use an upper-script to denote the time step, so $h^{\left(t\right)}$ is the state of a neuron at time $t$ . Since the neurons need to pass information to themselves (i.e. their state from previous invocation) they become recurrent neurons, a.k.a recurrent cells.

Recurrent neuron uses internally two functions. The first function updates the inner state based on current input and previous state, which is the transition from time $t-1$ to time $t$ , $$s:\mathbf{x},h^{\left(t-1\right)}\mapsto tanh\left(\left\langle \mathbf{x},\mathbf{w}\right\rangle +b+h^{\left(t-1\right)}\cdot u\right)$$ $u\in\mathbb{R}$ is a new parameter denoting the weight for the previous state.

And the second function is for computing the output of the neuron at current time $t$ , based on its new state $$g^{\left(t\right)}:h^{\left(t\right)}\mapsto\sigma\left(h^{\left(t\right)}\cdot v+c\right)$$ with $v,c\in\mathbb{R}$ as the weight and bias of the computation respectively.

We can move again to matrix notations to denote several parallel recurrent cells that forms a recurrent layer. The first function updates the vector of states for the entire layer $$\mathbf{s}:\mathbf{x},\mathbf{h}^{\left(t-1\right)}\mapsto tanh\left(W\mathbf{x}+\mathbf{b}+U\mathbf{h}^{\left(t-1\right)}\right)$$ and the second function for computing the output of the layer based on the current state $$\mathbf{f}:\mathbf{h}^{\left(t\right)}\mapsto\sigma\left(V\mathbf{h}^{\left(t\right)}+\mathbf{c}\right)$$ When we come to compare that to the FC formulation, we see that actually the function $\mathbf{f}$ itself hasn’t changed, but now it accepts as input the state of the layer $\mathbf{h}$ , rather than the input to the layer $\mathbf{x}$ . Another change is that before the layer computes its output, it first update its hidden state.

Note that we can extend the definition of the family $\mathcal{F}_{tanh}$ to contains functions like the state-transforming function $\mathbf{s}$ , by making each $\mathbf{f}\in\mathcal{F}_{tanh}$ accepts two vectors as input instead of one (and we also need another weight matrix for the second input). So denote the family of all hidden-state transition functions as $$\mathcal{S}_{\sigma}=\left\{ \mathbf{x},\mathbf{h}^{\left(t-1\right)}\mapsto\sigma\left(W\mathbf{x}+\mathbf{b}+U\mathbf{h}^{\left(t-1\right)}\right)\mid\forall W,U,\mathbf{b}\right\}$$ usually the activation function is $\sigma=tanh$ . We will use that family later on, when discuss gated units as LSTM and GRU.

FC network for next-word prediction: Let the window size be $d=3$ . The input to the network can be represent as a vector $\mathbf{x}\in\mathbb{N}^{3}$ and the output as $y\in\mathbb{N}$ . The FC network amounts to $$\mathcal{N}_{FC}\left(\mathbf{x}\right)=f\left(x\right)$$ for some $f\in\mathcal{F}_{\sigma}$ that maps from $\mathbb{R}^{3}$ to $\mathbb{R}$ .

Recurrent neural network (RNN), however, leads to different representation: the input and the output both integers $x,y\in\mathbb{N},$ so the state transition function $s\in\mathcal{S}$ and the output function $f\in\mathcal{F}_{\sigma}$ are both from $\mathbb{R}$ to $\mathbb{R}$ . The idea of the recurrent architecture is to apply the same recurrent layer several times on different inputs (each input from different time-step) in order to get a prediction.

Here is a detailed description of how to do that: we take a series of three consecutive words from the beginning of a sentence: $x^{\left(1\right)},x^{\left(2\right)},x^{\left(3\right)}$ and a target next word: $y$ . First, feed the network with $x^{\left(1\right)}$ , it updates the inner state from $h^{\left(0\right)}=0$ to some hidden state $h^{\left(1\right)}$ and outputs $\hat{y}^{\left(1\right)}$ . We ignore that output and feed the next word $x^{\left(2\right)}$ , the network updates its state to $h^{\left(2\right)}$ and produces $\hat{y}^{\left(2\right)}$ that is also ignored. Lastly, we feed $x^{\left(3\right)}$ to the network, the inner state is being updated to $h^{\left(3\right)}$ and another output is produced $\hat{y}^{\left(3\right)}$ which is now considered as the prediction of the network. Note that in each invocation of the network, the output depends on both the current input and the previous state, therefore $\hat{y}^{\left(3\right)}$ is the result of the entire history $x^{\left(1\right)},x^{\left(2\right)},x^{\left(3\right)}$ and $h^{\left(0\right)}$ (which was initialized to zero).

At first glance it looks like there is no meaningful differences between the architectures. We have an implicit sliding window over the words in the sentence for the recurrent neuron rather than explicit sliding window as with the FC neuron. Moreover, the output $y$ of FC neuron also depends on all previous time steps because the input $\mathbf{x}$ is just the values of $\left(x^{\left(1\right)},x^{\left(2\right)},x^{\left(3\right)}\right)$ .

However, note that in the FC architecture, each word in the input vector has its own weight and bias whereas in recurrent architecture we use the same weights over and over again (by applying the same function). In other words, in recurrent layers we share the parameters across time. The formula below demonstrate how we applied the same function $s\in\mathcal{S}$ to updates the hidden-state across different time steps $$h^{\left(t\right)}=s\left(x^{\left(t\right)},h^{\left(t-1\right)}\right)\Longrightarrow h^{\left(3\right)}=s\left(x^{\left(3\right)},s\left(x^{\left(2\right)},s\left(x^{\left(1\right)},0\right)\right)\right)$$ then making a prediction using some $f\in\mathcal{F}_{\sigma}$ on the current state $$\hat{y}^{\left(3\right)}=f\left(h^{\left(3\right)}\right)$$ Parameter sharing has a very powerful effect on the learnability of the network both because it reduces the number of parameters that needed to be optimized and it make the network robust to small changes in the context (recall the example about the order of features in the input). In addition, the recurrent layer practically has a dynamic window size. Going back to our next-word prediction network, we can continue to apply the network on consecutive inputs, teaching it dependencies between words that are further than 3 time steps.

Note that in our example, we ignored the “intermediate” predictions of the network: $\hat{y}^{\left(1\right)}$ and $\hat{y}^{\left(2\right)}$ , but we could keep them and feed them as inputs to another recurrent layer making our RNN network deeper. We will discuss it in a later post.

Furthermore, parameter sharing has a serious drawback. Recall that applying the network for multiple time steps leads to a composition of the same $\mathbf{s}\in\mathcal{S}$ upon itself $t$ times, something like this $$\mathbf{h}^{\left(t\right)}=\mathbf{s}\left(\mathbf{x}^{\left(t\right)},\mathbf{s}\left(\mathbf{x}^{\left(t-1\right)},\mathbf{s}\left(\mathbf{x}^{\left(t-2\right)},...\right)\right)\right)$$ which may cause the gradient during back-propagation to either explode or vanish. This problem is known as the vanishing and exploding gradients. In order to get an intuition about that, we make the following simplifications: assume that the activation function inside $\mathbf{s}$ is the identity instead of $tanh$ , and $\mathbf{x}^{\left(t\right)}=\mathbf{0}$ for all $t$ . Suppose that $\mathbf{h}^{\left(0\right)}$ is given to us and it is not all zeros (that is, it encodes some information about the past).

We have that $\mathbf{h}^{\left(t\right)}=U\mathbf{h}^{\left(t-1\right)}$ so applying the recurrent neuron for $t$ time steps amounts to $\mathbf{h}^{\left(t\right)}=U^{t}\mathbf{h}^{\left(0\right)}$ . What happen to $U^{t}$ as $t$ increases? it easier to see the answer when considering the scalar case. If $U$ was a real positive number, then either $U^{t}\to0$ when $U<1$ , or $U^{t}\to\infty$ when $U>1$ . The same goes with matrices, suppose $U$ has an eigenvalue decomposition such that $U=V^{\top}\Sigma V$ for orthogonal $V$ , so $U^{t}=V^{\top}\Sigma^{t}V$ causing the small entries on the diagonal of $\Sigma$ to vanish, and the large entries to explode. Since the gradients in our network are being scaled according to $\Sigma^{t}$ , they are either explode or vanished. The problem with very large gradients is that they cause the network to diverge (large updates to the parameters), on the other hand, very small gradients cause infinitesimally small updates to the parameters which prevent the network from learning. That is describe much more formally and rigorously here.

Next post I will discuss two popular improvements to the recurrent neurons that helps avoid the limitations above: the LSTM and GRU cells.

Acknowledgments: I want to thank Ron Shiff for his useful comments and corrections to this post.