4
$\begingroup$

In this article on recurrent neural networks by Razvan Pascanu, $\mathbf x_t$ is the state at time $t;$ $\mathbf u_t$ the input at time $t$; and $\mathcal E$ is the cost function:

enter image description here

A proof is given of the fact that if the absolute value of the main eigenvalue of the matrix of recurrent weights is $\rho < 1$ then the vanishing gradient problem would occur:

If we consider a linear version of the model (i.e. set $\sigma$ to the identity function in eq. (2)) we can use the power iteration method to formally analyze this product of Jacobian matrices and obtain tight conditions for when the gradients explode or vanish. It is sufficient for $\rho < 1$, where $\rho$ is the spectral radius of the recurrent weight matrix $\mathbf W_{rec}$ for long term components to vanish (as $t \to\infty$) and necessary for $\rho >1$ for them to explode.

We generalize this result for nonliner functions $\sigma$ where $\lvert \sigma'(x)\rvert$ is bounded, $\lVert diag(\sigma'(\mathbf x_k )) \rVert \leq \gamma \in \mathcal R$, by relying on singular values.

We first prove that it is sufficient for $\lambda_1 <\frac{1}{\gamma}$, where $\lambda_1$ is the largest singular value of $\mathbf W_{rec}$, for the vanishing gradient problem to occur. Note that we assume the parametrization given by eq. (2). The Jacobian matrix $\frac{\partial \mathbf x_{k+1}}{\partial \mathbf x_k}$ is given by $\mathbf W_{rec}^T\, diag(\sigma'(\mathbf x_k)).$ The 2-norm of this Jacobian is bounded by the product of the norms of the the two matrices (see eq. (6)). Due to our assumption, this implies that it is smaller than $1.$

$$\forall k, \; \left\lVert \frac{\partial \mathbf x_{k+1}}{\partial \mathbf x_k} \right\rVert \leq \left \lVert \mathbf W_{rec}^T \right \rVert \, \left \lVert diag(\sigma'(\mathbf x_k)) \right \rVert < \frac{1}{\gamma}\gamma <1 \tag{6}$$

Let $\eta \in \mathrm R$ be such that $\forall k, \, \left\lVert \frac{\partial \mathbf x_{k+1}}{\partial \mathbf x_k} \right \rVert \leq \eta < 1.$ The existence of $\eta$ is given by eq. (6). By induction over $i$, we can now show that

$$\left \lVert \frac{\partial \mathcal{E}_t}{\partial \mathbf x_t} \left( \prod_{i=k}^{t-1} \frac{\partial \mathbf x_{i+1}}{\partial \mathbf x_i} \right) \right \rVert \leq \eta^{t-k}\; \left\lVert \frac{\partial \mathcal{E}_t}{\partial \mathbf x_t}\right \rVert \tag 7$$

As $\eta < 1, $ it follows that, according to eq. (7), long term contributions (for which $t-k$ is large) go to $0$ exponentially fast with $t-k.$ $\tag*{$\square$}$


Can I get some help explaining Eq.6?

In particular, I understand that if $\lambda_1 $ is the largest singular value of $\mathbf W_{\text{rec}}$, and $\lambda_1 < \frac{1}{\gamma} $, the absolute value of the largest eigenvalue $\lambda_1^2 < \frac{1}{\gamma^2}$. This latter value (spectral radius) corresponding to the norm of $\mathbf W_{\text{rec}}$, i.e. $\left\lVert \mathbf{W}_{\text{rec}} \right\rVert$.

Therefore

$$\left\lVert \frac{\partial \mathbf x_{k+1}}{\partial \mathbf x_k} \right\rVert \leq \left \lVert \mathbf W_{\text{rec}}^\top \right \rVert \, \left \lVert \text{diag}(\sigma'(\mathbf x_k)) \right \rVert < \frac{1}{\gamma^2}\gamma = \frac{1}{\gamma}$$

If $\gamma>1 \implies \lambda_1^2 < 1$ (and $\lambda_1 < 1)$, exponentiating this $\frac{1}{\gamma}$ will result in vanishing gradients. If $\gamma < 1$ the gradients will explode.

It makes sense, but it is different from eq. (6).

$\endgroup$
5
  • $\begingroup$ Also, I am not sure whether Eq.5 is right, see this question. (Though this paper was cited 1250 times, so I am probably missing something...) $\endgroup$ Sep 28, 2018 at 11:13
  • $\begingroup$ @Oren I haven't pursued the study of this topic farther. If you think the question has some value, I would ask you to answer with corrections. Otherwise, I will consider just deleting it. $\endgroup$ Sep 28, 2018 at 11:47
  • $\begingroup$ I am sorry for the previous comments. ISTM that I was wrong once again, and the paper that you quoted in the original question is indeed the most up to date version. $\endgroup$ Sep 28, 2018 at 16:56
  • $\begingroup$ @OrenMilman No sweat! I really appreciate your dedication. Let me leave your answer up for referendum - I haven't touched on the topic in forever; so if you get upvotes, I'll come back to it and happily accept it. Remind me if I forget, please. $\endgroup$ Sep 28, 2018 at 17:00
  • 1
    $\begingroup$ In equation 6, it appears that $\frac{1}{\gamma}\gamma < 1$ a typo for something else. $\endgroup$
    – Sycorax
    Sep 3, 2021 at 4:17

1 Answer 1

1
$\begingroup$

The spectral radius of a matrix is not always equal to the matrix's norm.
$A=\left(\begin{matrix}0 & 1\\ 0 & 0 \end{matrix}\right)$ is a counterexample, as $0$ is the only eigenvalue of $A$, and so the spectral radius of $A$ is $0$.

On the other hand, the largest singular value of a matrix is always equal to the matrix's norm, as shown here.

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).

$\lambda_1$ is the largest singular value of $W_{rec}$. Therefore, we get that $\lambda_1=||W_{rec}^T||$, and so $||W_{rec}^T||<\frac{1}{\gamma}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.