# Understanding a proof of conditions for vanishing/exploding gradient in RNNs

I'm looking at some of the preliminaries in understanding vanishing/exploding gradients with recurrent neural networks (RNNs), and I see this paper referenced quite a lot: https://arxiv.org/abs/1211.5063

My question pertains to equation (5), and where the matrix transpose comes from. It appears in several places, so it does not appear to be a typo.

To copy here (moving the time-step identifiers to superscripts since I do not want to misinterpret as matrix/vector indexes) they start with:

$$\mathbf{x}^{(t)} = \mathbf{W}^{(rec)}\sigma(\mathbf{x}^{(t-1)}) +\mathbf{W}^{(in)}\sigma(\mathbf{u}^{(t)}) + \mathbf{b}$$

where I'll take $\mathbf{x}^{(t)} \in \mathbb{R}^n$ and $\mathbf{W}^{(rec)} \in \mathbb{R}^{n \times n}$. In (5), considering only a single term of the product ($\partial x^{(i)}/\partial x^{(i-1)}$), they state:

$$\frac{\partial \mathbf{x}^{(i)}}{\partial \mathbf{x}^{(i-1)}} = \left(\mathbf{W}^{(rec)}\right)^T diag(\sigma^{\prime}(\mathbf{x}^{(i-1)}))$$

where the $diag$ operation takes the vector $\sigma^{\prime}(\mathbf{x}^{(i-1)})$ and creates a $n \times n$ diagonal matrix.

I've worked this out using generic indicial notation, and a simple case where $n=3$, and I don't know where the transpose is coming in. Any ideas?

• Just in case the link ever dies, the paper is called "On the difficulty of training Recurrent Neural Networks", authored by Razvan Pascanu, Tomas Mikolov, Yoshua Bengio. – Oren Milman Sep 28 '18 at 9:08
• I also did the math and got $\frac{\partial\text{x}^{\left(i\right)}}{\partial\text{x}^{\left(i-1\right)}}=\text{W}^{\left(rec\right)}\text{diag}\left(\sigma^{'}\left(\text{x}^{\left(i-1\right)}\right)\right)$ – Oren Milman Sep 28 '18 at 11:09
• Note that the version of the paper that you linked to is not the most up to date one. This is the most up to date (and this is actually the only version that appears when you search for the paper's name in google scholar). – Oren Milman Sep 28 '18 at 17:00
• And by the way, even if you are right, it doesn't really matter for the rest of the proof, as the paper assumes that $W^{(rec)}$ is a square matrix, and thus $||W^{(rec)}||=||(W^{(rec)})^T||$, as shown here (which uses what is shown here). – Oren Milman Sep 28 '18 at 17:05

(Note that I only used the latest version (as far as I can tell) of the paper: On the difficulty of training recurrent neural networks, though the equation that you asked about is the same in both versions.
Also, I followed your lead and moved the subscripts to superscripts, even in quotes.)

# tl;dr

I think you are right, and the paper is wrong.
(Though it still feels off that such a mistake endured, as the paper was cited over 1250 times.)

# Making sure we got the paper's notation right

Equation (2) is $$\mathbf{x}^{(t)}=\mathbf{W}^{(rec)}\sigma(\mathbf{x}^{(t-1)})+\mathbf{W}^{(in)}\sigma(\mathbf{u}^{(t)})+\mathbf{b}$$.

We denote by $$\mathbf{x}^{(t)}$$ the hidden state of the network at time $$t$$

I.e. $$\mathbf{x}^{(t)}$$ is a vector of the states of each of the hidden neurons, before applying the activation function.
So $$\mathbf{x}^{(t)}_j$$ is the state of the $$j$$-th hidden neuron before applying the activation function, and is given by: $$\mathbf{x}_{j}^{(t)}=\left(\mathbf{W}^{(rec)}\sigma(\mathbf{x}^{(t-1)})\right)_{j}+\left(\mathbf{W}^{(in)}\sigma(\mathbf{u}^{(t)})\right)_{j}+\mathbf{b}_{j}\\\downarrow\\\left(*\right)\\\mathbf{x}_{j}^{(t)}=\mathbf{W}_{j}^{(rec)}\sigma(\mathbf{x}^{(t-1)})+\mathbf{W}_{j}^{(in)}\sigma(\mathbf{u}^{(t)})+\mathbf{b}_{j}$$ while $$\mathbf{W}_{j}^{(rec)}$$ is the $$j$$-th row (i.e. it is a row vector) of $$\mathbf{W}^{(rec)}$$.

From $$(*)$$ we deduce that $$\mathbf{W}_{j}^{(rec)}$$ is a vector of the weights for the connections from hidden neurons in time $$t-1$$ to the $$j$$-th hidden neuron in time $$t$$.

To keep it simple, let's say $$n=2$$, i.e. there are $$2$$ hidden neurons.
Then the connections between the hidden neurons in time $$1$$ and time $$2$$ look like this: (while $$\mathbf{W}_{j,k}^{(rec)}$$ is the element of $$\mathbf{W}^{(rec)}$$ in row $$j$$ and column $$k$$)

Lastly, the Jacobian matrix is usually defined such that: $$\frac{\partial\mathbf{x}^{(i)}}{\partial\mathbf{x}^{(i-1)}}=\left(\begin{matrix}\frac{\partial\mathbf{x}_{1}^{(i)}}{\partial\mathbf{x}_{1}^{(i-1)}} & \cdots & \frac{\partial\mathbf{x}_{1}^{(i)}}{\partial\mathbf{x}_{n}^{(i-1)}}\\ \vdots & \ddots & \vdots\\ \frac{\partial\mathbf{x}_{n}^{(i)}}{\partial\mathbf{x}_{1}^{(i-1)}} & \cdots & \frac{\partial\mathbf{x}_{n}^{(i)}}{\partial\mathbf{x}_{n}^{(i-1)}} \end{matrix}\right)$$ But sometimes it is defined as the transpose of the matrix given above.

I guess that the paper uses the usual definition, but I am not sure, so later (at the end of the answer) we would have to also check whether the paper makes sense in case it uses the alternative definition.

# Why I think you are right

Let $$\mathbf{a}_{k}^{(t)}\equiv\sigma(\mathbf{x}_{k}^{(t)})$$. Then: $$\frac{\partial\mathbf{a}_{k}^{(i-1)}}{\partial\mathbf{x}_{k}^{(i-1)}}=\sigma'(\mathbf{x}_{k}^{(i-1)})$$

Moreover, from $$(*)$$ we get: $$\mathbf{x}_{j}^{(t)}=\underset{k=1}{\overset{n}{\sum}}\mathbf{W}_{j,k}^{(rec)}\sigma(\mathbf{x}_{k}^{(t-1)})+\mathbf{W}_{j}^{(in)}\sigma(\mathbf{u}^{(t)})+\mathbf{b}_{j}\\\downarrow\\\mathbf{x}_{j}^{(t)}=\underset{k=1}{\overset{n}{\sum}}\mathbf{W}_{j,k}^{(rec)}\mathbf{a}_{k}^{(t-1)}+\mathbf{W}_{j}^{(in)}\sigma(\mathbf{u}^{(t)})+\mathbf{b}_{j}$$ Thus: $$\frac{\partial\mathbf{x}_{j}^{(i)}}{\partial\mathbf{a}_{k}^{(i-1)}}=\mathbf{W}_{j,k}^{(rec)}$$

Applying the chain rule gives: $$\frac{\partial\mathbf{x}_{j}^{(i)}}{\partial\mathbf{x}_{k}^{(i-1)}}=\frac{\partial\mathbf{x}_{j}^{(i)}}{\partial\mathbf{a}_{k}^{(i-1)}}\cdot\frac{\partial\mathbf{a}_{k}^{(i-1)}}{\partial\mathbf{x}_{k}^{(i-1)}}=\mathbf{W}_{j,k}^{(rec)}\cdot\sigma'(\mathbf{x}_{k}^{(i-1)})$$

Let's go back to our image of the simple network and check whether we got a sensible result.
E.g. $$\frac{\partial\mathbf{x}_{1}^{(2)}}{\partial\mathbf{x}_{2}^{(1)}}=\mathbf{W}_{1,2}^{(rec)}\cdot\sigma'(\mathbf{x}_{2}^{(1)})$$ means that the rate of change of the state of hidden neuron $$1$$ in time $$2$$, with respect to the state of hidden neuron $$2$$ in time $$1$$ is determined by $$\mathbf{W}_{1,2}^{(rec)}$$ and $$\sigma'(\mathbf{x}_{2}^{(1)})$$: Looks good.

Moving on, we can now find the Jacobian matrix: $$\frac{\partial\mathbf{x}^{(i)}}{\partial\mathbf{x}^{(i-1)}}=\left(\begin{matrix}\mathbf{W}_{1,1}^{(rec)}\cdot\sigma'(\mathbf{x}_{1}^{(i-1)}) & \cdots & \mathbf{W}_{1,n}^{(rec)}\cdot\sigma'(\mathbf{x}_{n}^{(i-1)})\\ \vdots & \ddots & \vdots\\ \mathbf{W}_{n,1}^{(rec)}\cdot\sigma'(\mathbf{x}_{1}^{(i-1)}) & \cdots & \mathbf{W}_{n,n}^{(rec)}\cdot\sigma'(\mathbf{x}_{n}^{(i-1)}) \end{matrix}\right)\\\downarrow\\\frac{\partial\mathbf{x}^{(i)}}{\partial\mathbf{x}^{(i-1)}}=\mathbf{W}^{(rec)}\cdot\text{diag}\left(\sigma'(\mathbf{x}^{(i-1)})\right)$$

# Why I think the paper is wrong

According to the paper: $$\frac{\partial\mathbf{x}^{(i)}}{\partial\mathbf{x}^{(i-1)}}=\left(\mathbf{W}^{(rec)}\right)^{T}\cdot\text{diag}\left(\sigma'(\mathbf{x}^{(i-1)})\right)$$

Assuming this is right, we get: $$\frac{\partial\mathbf{x}^{(i)}}{\partial\mathbf{x}^{(i-1)}}=\left(\begin{matrix}\mathbf{W}_{1,1}^{(rec)} & \cdots & \mathbf{W}_{n,1}^{(rec)}\\ \vdots & \ddots & \vdots\\ \mathbf{W}_{1,n}^{(rec)} & \cdots & \mathbf{W}_{n,n}^{(rec)} \end{matrix}\right)\cdot\left(\begin{matrix}\sigma'(\mathbf{x}_{1}^{(i-1)})\\ & \ddots\\ & & \sigma'(\mathbf{x}_{n}^{(i-1)}) \end{matrix}\right)\\\downarrow\\\frac{\partial\mathbf{x}^{(i)}}{\partial\mathbf{x}^{(i-1)}}=\left(\begin{matrix}\mathbf{W}_{1,1}^{(rec)}\cdot\sigma'(\mathbf{x}_{1}^{(i-1)}) & \cdots & \mathbf{W}_{n,1}^{(rec)}\cdot\sigma'(\mathbf{x}_{n}^{(i-1)})\\ \vdots & \ddots & \vdots\\ \mathbf{W}_{1,n}^{(rec)}\cdot\sigma'(\mathbf{x}_{1}^{(i-1)}) & \cdots & \mathbf{W}_{n,n}^{(rec)}\cdot\sigma'(\mathbf{x}_{n}^{(i-1)}) \end{matrix}\right)$$ And therefore (this step isn't necessary, but it helps me to not confuse indices): $$\frac{\partial\mathbf{x}_{n}^{(i)}}{\partial\mathbf{x}_{1}^{(i-1)}}=\mathbf{W}_{1,n}^{(rec)}\cdot\sigma'(\mathbf{x}_{1}^{(i-1)})$$ And generally: $$\frac{\partial\mathbf{x}_{j}^{(i)}}{\partial\mathbf{x}_{k}^{(i-1)}}=\mathbf{W}_{k,j}^{(rec)}\cdot\sigma'(\mathbf{x}_{k}^{(i-1)})$$

Let's go back to our image of the simple network and check whether the paper's claim lead to a sensible result.
E.g. $$\frac{\partial\mathbf{x}_{1}^{(2)}}{\partial\mathbf{x}_{2}^{(1)}}=\mathbf{W}_{2,1}^{(rec)}\cdot\sigma'(\mathbf{x}_{2}^{(1)})$$ means that the rate of change of the state of hidden neuron $$1$$ in time $$2$$, with respect to the state of hidden neuron $$2$$ in time $$1$$ is determined by $$\mathbf{W}_{2,1}^{(rec)}$$ and $$\sigma'(\mathbf{x}_{2}^{(1)})$$: This doesn't look sensible to me.

But we did note earlier that we are not sure about the paper's definition of the Jacobian matrix. Maybe things make sense in case it uses the alternative definition, such that: $$\frac{\partial\mathbf{x}^{(i)}}{\partial\mathbf{x}^{(i-1)}}=\left(\begin{matrix}\frac{\partial\mathbf{x}_{1}^{(i)}}{\partial\mathbf{x}_{1}^{(i-1)}} & \cdots & \frac{\partial\mathbf{x}_{n}^{(i)}}{\partial\mathbf{x}_{1}^{(i-1)}}\\ \vdots & \ddots & \vdots\\ \frac{\partial\mathbf{x}_{1}^{(i)}}{\partial\mathbf{x}_{n}^{(i-1)}} & \cdots & \frac{\partial\mathbf{x}_{n}^{(i)}}{\partial\mathbf{x}_{n}^{(i-1)}} \end{matrix}\right)$$ In this case, we get that: $$\frac{\partial\mathbf{x}_{n}^{(i)}}{\partial\mathbf{x}_{1}^{(i-1)}}=\mathbf{W}_{n,1}^{(rec)}\cdot\sigma'(\mathbf{x}_{n}^{(i-1)})$$ And generally: $$\frac{\partial\mathbf{x}_{j}^{(i)}}{\partial\mathbf{x}_{k}^{(i-1)}}=\mathbf{W}_{j,k}^{(rec)}\cdot\sigma'(\mathbf{x}_{j}^{(i-1)})$$

E.g. $$\frac{\partial\mathbf{x}_{1}^{(2)}}{\partial\mathbf{x}_{2}^{(1)}}=\mathbf{W}_{1,2}^{(rec)}\cdot\sigma'(\mathbf{x}_{1}^{(1)})$$ means that the rate of change of the state of hidden neuron $$1$$ in time $$2$$, with respect to the state of hidden neuron $$2$$ in time $$1$$ is determined by $$\mathbf{W}_{1,2}^{(rec)}$$ and $$\sigma'(\mathbf{x}_{1}^{(1)})$$: This also doesn't look sensible to me.