What is Time Lag in Recurrent Neural Network? Why is it a Problem? I was reading a paper on LSTM's and this term "time lag" is coming quite frequently, but there is no any definition of it mentioned anywhere in the paper. It also states that LSTM really helps to solve long time lag problems. So, what does this time lag term mean? And why is it a problem in RNNs?Thanks!
Link to the paper : LSTM paper
 A: Let us assume that we want to solve a classical problem (that is nowadays being tackled by RNNs), namely how to teach the computer to play a game. We will consider two examples: pong and chess and we will assume that we do not use LSTMs but rather only regular neural network nodes. For pong that means that we stack instances of  "linear + sigmoidal output function" into each other. The output that we need is the action (steer the bar of the player up, down or leave it where it is), i.e. it is kind of like a multiclass classification problem with 3 classes.
The input of the neural network will be raw pictures of the current playing field (in greyscale, i.e. it will mostly be 0 (black) except for where the ball and the two paddles are) and the previous hidden state and the output will be the next hidden state and an action. Let us say that the hidden state vector has dimension $d_h$ and we have an 80x80 pixel picture of the playing field then this NN can be described as an $d_h$ + 80*80 input layer, some hidden layer(s) in the middle and an output layer of size $d_h$ + 3 (in the very last 3 nodes we use a softmax instead of a sigmoid).
How do we train neural networks usually? Well in a regular, supervised learning setup we have a loss function $l$ (usually log loss for multiclass) and for a given input $x$ and model $m$ with parameters $\theta$ producing output $\hat{y} = m(x;\theta)$ and true answer $y$ we compute the gradients of the function $l(\theta) = l(y, \hat{y}) = l(y, m(x;\theta))$ and do gradient descend.
In these reinforcement learning setups we do not have a true answer (because we are training 'online' while being in the middle of the game, right) and since we have not yet finished the game we cannot decide ad hoc whether the chosen action was good or not. This is where the reward will save us: we just play a sequence, sum up the losses and multiply with the reward. Very precisely we are given the initial hidden state $h_0=0$ and an initial picture $p_0$ and we apply the neural net to obtain an action $a_0$ and a hidden state $h_1$ to proceed to a picture $p_1$ and so forth until we either win or loose the game (or a certain amount of steps has been reached in which case we will use reward 0 for a "draw"). I.e. we only do a supervised training step after a game has ended and if we won (reward +1) we pretend that the actions selected were the 'true' answers and do a regular gradient descent and if we lost (reward -1) we still pretend that the actions selected are the 'true' answers but we weight the gradient with $-1$ (making us step into --gradient = +gradient instead of -gradient as we 'should').
Let us formally write down what this means: We start with $h_0, p_0$ and apply $(h_1, (\text{prob}_{0,\text{up}}, \text{prob}_{0,\text{stay}}, \text{prob}_{0,\text{down}})) = nn(h_0, p_0)$ and the next picture $p_1$ depends on the chosen action $a_1$ that we somehow achieve from $(\text{prob}_{0,\text{up}}, \text{prob}_{0,\text{stay}}, \text{prob}_{0,\text{down}})$ (for example, by taking argmax or by sampling an action according to the probability distribution returned by the softmax). Let us assume that we play three more rounds and then the game ends. Then we compute in total
$$l(a_0, (\text{prob}_{0,\text{up}}, \text{prob}_{0,\text{stay}}, \text{prob}_{0,\text{down}})) + l(a_1, (\text{prob}_{1,\text{up}}, \text{prob}_{1,\text{stay}}, \text{prob}_{1,\text{down}})) + l(a_2, (\text{prob}_{2,\text{up}}, \text{prob}_{2,\text{stay}}, \text{prob}_{2,\text{down}})) + l(a_3, (\text{prob}_{3,\text{up}}, \text{prob}_{3,\text{stay}}, \text{prob}_{3,\text{down}}))$$
more precisely, the gradient of that w.r.t. the weights of the neural networks.
We have different ways of representing this expression but in order to remove all the references to hidden states and pictures and so on and get a function purely in $\theta$ we need to 'unroll' everything back to the initial setup.
Let us concentrate on the last summand for now. It is
$$l(a_3, \text{prob}_{3}) = l(a_3, nn(h_2, p_2)[1])$$
where "$[1]$" means "select the second part in the output of the NN".
Let us focus on hidden state for a moment. How is $h_2$ being computed? Well, it is
$$(h_2, \text{prob}_1) = nn(h_1, p_1)$$
and
$$(h_1, \text{prob}_0) = nn(h_0, p_0)$$
so essentially
$$h_2 = nn(nn(h_0, p_0)[0], p_1)[0]$$
where "$[0]$" means "select the first part".
We see that hidden states that appear at a late stage in the game can be expressed as a composition of many chained applications of the neural network w.r.t. the stuff that happened early in the game. If we want to let decision in an early stage of the game influence the decisions that we make (potentially much) later on then we need to correct the weights so that they incoperate the relation between $\text{prob}_i$ with a small index $i$ and $h_j$ with a big $j$. However, the functional relation of them is stacking many applications of $nn$ into each other, i.e. something like
$$\sigma(a\sigma(c\sigma(e...+f)+d)+b)$$
Let us forget about the weights for a second and assume $a=c=e=...=1$ and that the biases are zero $b=d=f=...=0$. Then we have a function of the form
$$\sigma(\sigma(\sigma(...(x))...)$$
If we now take the gradient of that expression then we obtain by the chain rule (since $\sigma'(x) = \sigma(x)*(1-\sigma(x))$) something like
$$\sigma(x)^a \cdot \text{something in the interval $(0,1)$}$$
where this $a$ is roughly the distance between $i$ and $j$ above (i.e. a "big" number like 100 or so). $\sigma(x)$ is a constant in the interval $(0,1)$. If you take any number $v$ in that interval and you keep on multiplying it with itself then it will converge to $0$ quite quickly (and the other factor is something bounded, so it cannot save that). 
Hence, the terms in the gradient of the loss w.r.t. $h_j$ (the object encoding the information about the current state of the game at time $j$) and $\text{prob}_i$ (the basis of the decision at time $i$) with $i$ and $j$ being far away from each other will not contribute into the gradient of the total sum of losses above.
Hence, such a network architecture can never learn the relation between actions that it has chosen in the beginning and the consequences much later. This is called the 'vanishing gradient problem' and this is what they mean by 'lag' in the LSTM paper because LSTMs where precisely developed to overcome this exact problem (by letting the information flow in a more controlled way backwards somewhat but I never really understood how that exactly works to be honest :-)).
Note: One might argue that pong is a bad example because is pong, one does not need a sophisticated long term behavioural strategy in order to win the game, a strategy of the form 'if the ball is above your paddle and moves upwards then move the paddle up and if the ball is under your paddle and is moving down then move the paddle down' is already a pretty decent one. That is the reason why it is actually possible to become quite good at Pong without an LSTM: only this actual frame right now and the last one are important (we need two because we need to encode the movement of the ball). Indeed, in this wonderful article Andrej Karpathy is doing it exactly in the way above (with just regular NN stuff without LSTM). However, he is using the hidden state in a slightly different way but nevertheless, the lag that occurs is smaller than in other games like chess. That is why it is possible to learn pong without a fancy RNN cell in the middle and it is not possible (at least not with the size of a regular NN that we can handle with our computers right now) to learn chess.
