chapitre5.tex

\chapter{Réseaux de neurones récurrents}
\label{chap:Réseaux de neurones récurrents}
\section{Motivation}

Nous avons pu voir que les réseaux feedforward peuvent être utilisés afin d'apprendre à prédire la sortie voulue en fonction de l'entrée du réseau. 

Néanmoins, ces réseaux se limitent à des entrées et des sorties de tailles fixes. De plus, ils ne peuvent gérer des réseaux présentant des cycles. On utilise alors des réseaux récurrents qui permettent un traitement plus efficace des séquences de données. On pourra ainsi faire de la prédiction et de la génération de séquences.

Dans un premier temps, nous verrons comment modéliser ces réseaux récurrents. Puis, nous nous intéresserons à deux algorithmes d'optimisation permettant l'apprentissage des réseaux récurrents : Real Time Recurrent Learning (RTRL) et Backpropagation Through Time (BPTT).

\section{Dépliage}

Nous avons dit précédemment qu'un réseau de neurones récurrent est un réseau possédant des cycles. Néanmoins, il est difficile d'imaginer que la valeur de sortie d'un neurone au temps $t$ dépende de la sortie de ce même neurone au temps $t$. Pour résoudre ce problème, nous allons ajouter une dimension temporelle à nos réseaux et permettre aux neurones au temps $t$ de dépendre des valeurs d'autres neurones au temps $t-1$.

Afin de mettre en évidence cette dépendance temporelle sur nos graphes, les arêtes reliant la sortie d'un neurone au temps $t-1$ à un neurone au temps $t$ vont être annotées par un carré comme sur la figure \ref{arete_retard}. On les appellera arête "retard".

\begin{figure}
\begin{center}
\input{images/chapter5/recurrent_edge.tex}
\caption{Réseau de neurones récurrent où l'arête avec un carré signifie que le n\oe{}ud $h$ prend sa valeur au temps $t-1$ comme entrée au temps $t$.}
\label{arete_retard}
\end{center}
\end{figure}

On peut maintenant remarquer que pour une séquence $x_1, ..., x_n$ le réseau récurrent de la figure \ref{arete_retard} est équivalent au réseau feedforward de la figure \ref{reseau_deplie}.

\begin{figure}
\begin{center}
\input{images/chapter5/unfolded_graph.tex}
\caption{Réseau de neurones feedforward équivalent au réseau récurrent de la figure \ref{arete_retard} pour la séquence d'entrée $x_1, ..., x_n$.}
\label{reseau_deplie}
\end{center}
\end{figure}

Le passage d'un réseau récurrent à un réseau feedforward s'appelle dépliage.

Une fois le réseau déplié, on peut utiliser l'algorithme de propagation classique pour les graphes de calculs afin de calculer la sortie du réseau récurrent.

Nous avons utilisé trois méthodes pour générer des réseaux dépliés. La première prend en entrée un réseau récurrent avec des arêtes retard et obtient le dépliage à partir de celui-ci.

La seconde prend en entrée un \textit{layer}, représenté figure \ref{layer}, c'est-à-dire le sous-graphe qui va être copié à chaque pas de temps et le clone autant de fois qu'il le faut.

\begin{figure}
\begin{center}
\input{images/chapter5/layer.tex}
\caption{Représentation d'un layer. Il contient les n\oe{}uds du graphe à un temps $t$. Il prend en entrée la sortie de l'état caché du temps $t-1$ appelée $h_{in}$ et l'entrée $x_t$. Il a comme sortie l'état caché $h_{out}$ ainsi que $\hat{y}_t$ qui sera comparé avec $y_t$ la sortie attendue au temps $t$. Le $layer$ sert aussi lors de la phase de rétropropagation.}
\label{layer}
\end{center}
\end{figure}

Enfin la dernière méthode est de ne pas utiliser d'algorithme "général" permettant de passer d'un graphe récurrent à un graphe acyclique mais plutôt d'écrire pour chaque architecture de réseau une fonction dépliant ce réseau. Une telle fonction contiendra principalement une boucle créant les n\oe{}uds nécessaires pour chaque temps.

Devant la diversité des architectures des réseaux récurrents, la dernière méthode est la plus sensée et la plus pratique. Elle offre une liberté totale quant à l'architecture du graphe tout en étant relativement simple.

\section{BPTT}

Contrairement à ce que nous avons fait lors du projet, nous allons d'abord présenter l'algorithme \textit{backpropagation through time} (BPTT) car il s'agit d'une simple généralisation de la rétropropagation déjà présentée pour les réseaux feedforward.

L'algorithme comprend deux étapes :
\begin{enumerate}
\item Déplier le réseau récurrent pour avoir un réseau feedforward.
\item Appliquer l'algorithme de rétropropagation à ce réseau feedforward.
\end{enumerate}

La seule difficulté conceptuelle réside donc dans le dépliage.

En pratique, le dépliage est un processus coûteux en temps. Lors de l'apprentissage, on évite donc de déplier un graphe pour chaque exemple d'apprentissage. Pour cela, on fixe, si possible, la taille des séquences d'entrée lors de l'apprentissage. Nous pourrons ainsi utiliser le même réseau pour tous les exemples. En outre, comme tous les exemples auront la même taille, nous pourrons les placer dans une matrice comme pour les réseaux feedforward et passer un batch d'exemples en même temps ce qui permet d'accélérer encore les calculs en utilisant pleinement la puissance de \texttt{numpy}.

\section{RTRL}

\label{RTRL_section}

Détaillons maintenant l'algorithme RTRL qui a une philosophie complètement différente. Au lieu de rétropropager le gradient, nous allons le propager.

Nous nous plaçons dans le cas particulier où le réseau est fully-connected comme sur la figure \ref{fully_connected_recurrent_network}. 

\begin{figure}
\begin{center}
\input{images/chapter5/fully_connected_recurrent_network.tex}
\caption{Réseau de neurones récurrent fully-connected avec 2 entrées et 3 autres neurones.}
\label{fully_connected_recurrent_network}
\end{center}
\end{figure}

Nous notons $I$ l'ensemble des neurones d'entrée et $U$ l'ensemble des autres neurones. Posons alors une notation unifiant ces deux ensembles : 
\begin{equation}
z_k(t) = \left\{
    \begin{array}{ll}
        x_k(t) \text{ si } k \in I \\
        y_k(t-1) \text{ si } k \in U
    \end{array}
\right.
\label{z_k}
\end{equation}
avec $y_k(0) = 0$ pour tout $k \in U$.

Posons aussi, $s_k(t)$ la somme pondérée des entrées du neurone $k$ au temps $t$ :
\begin{equation}
s_k(t) = \sum_{l \in U \cup I}{w_{k,l}z_l(t)}
\label{s_k}
\end{equation}

On a alors :
$$
\forall k \in U, y_k(t) = f_k(s_k(t))
$$

La fonction de coût total est la somme des coûts partiels que l'on calcule à chaque temps $t$ :
$$
E = \sum_{t=1}^{n}{E(t)}
$$

Nous pouvons alors calculer la dérivée du coût partiel au temps $t$, $E(t)$, par rapport à un poids $w_{i,j}$ :
\begin{equation}
\frac{\partial E(t)}{\partial w_{i,j}} = \sum_{k \in U}{\frac{\partial E(t)}{\partial y_k(t)}\frac{\partial y_k(t)}{\partial w_{i,j}}}
\label{E_t}
\end{equation}
Le terme $\frac{\partial E(t)}{\partial y_k(t)}$ est connu, il dépend de la fonction de coût utilisée. Pour une fonction de coût quadratique $E(t) = \sum_{k \in U}{(y_k(t) - d_k(t))^2}$ avec $d_k(t)$ la valeur attendue pour $y_k(t)$, on a $\frac{\partial E(t)}{\partial y_k(t)} = 2(y_k(t) - d_k(t))$. 

Il nous reste donc le terme $\frac{\partial y_k(t)}{\partial w_{i,j}}$ à calculer. Déterminons une relation de récurrence entre $\frac{\partial y_k(t+1)}{\partial w_{i,j}}$ et les $(\frac{\partial y_l(t)}{\partial w_{i,j}})_{l\in U}$ :
$$
\frac{\partial y_k(t+1)}{\partial w_{i,j}} 
= \frac{\partial y_k(t+1)}{\partial s_k(t+1)}\frac{\partial s_k(t+1)}{\partial w_{i,j}}
= f_k'(s_k(t+1))\frac{\partial s_k(t+1)}{\partial w_{i,j}}
$$
En utilisant la formule \ref{s_k}, on a alors :
$$
\begin{array}{rcl}
\frac{\partial y_k(t+1)}{\partial w_{i,j}} & 
= & f_k'(s_k(t+1))\sum_{l \in I \cup U}{\frac{\partial s_k(t+1)}{\partial z_l(t+1)}\frac{\partial z_l(t+1)}{\partial w_{i,j}}+\frac{\partial s_k(t+1)}{\partial w_{k,l}}\frac{\partial w_{k,l}}{\partial w_{i,j}}} \\
& = & f_k'(s_k(t+1))\left(\sum_{l \in I \cup U}{w_{k,l}\frac{\partial z_l(t+1)}{\partial w_{i,j}}}+\delta_{i,k}z_j(t+1)\right)
\end{array}
$$
Puis en utilisant la formule \ref{z_k}, on a finalement :
\begin{equation}
\frac{\partial y_k(t+1)}{\partial w_{i,j}} = f_k'(s_k(t+1))\left(\sum_{l \in U}{w_{k,l}\frac{\partial y_l(t)}{\partial w_{i,j}}}+\delta_{i,k}z_j(t+1)\right)
\label{y_k_recurrence}
\end{equation}

Utilisons les formules \ref{E_t} et \ref{y_k_recurrence} pour écrire l'algorithme de propagation du gradient. Dans l'algorithme \ref{RTRL}, $p$ représente les $(\frac{\partial y_k(t)}{\partial w_{i,j}})_{k,i,j}$ et $\epsilon$ les $(\frac{\partial E}{\partial w_{i,j}})_{i,j}$. On effectue la propagation des entrées en même temps que la propagation du gradient.

\begin{algorithm} 
\begin{algorithmic}
\Procedure{$propager\_gradient$}{$I, U, w, f, x, d$}
\State Initialiser un tableau $z$ à 2 dimensions de taille $(n+1, |I \cup U|)$ à $0$.
\State Initialiser un tableau $s$ de taille $|U|$ à $0$.
\State Initialiser un tableau $p$ à 3 dimensions de taille $(|U|, |U|, |I \cup U|)$ à $0$.
\State Initialiser un tableau $\epsilon$ à 2 dimensions de taille $(|U|, |I \cup U|)$ à $0$.
\For{$t \in \{1, ..., n\}$}
	\State // Propagation
	\For{$k \in I$}
		\State $z[t-1][k] \leftarrow x[t][k]$
	\EndFor
	\For{$k \in U$}
		\State $s[k] \leftarrow \sum_{l \in U \cup I}{w_{k,l}z[t-1][l]}$
		\State $z[t][k] \leftarrow f_k(s[k])$
	\EndFor
	\State // Propagation de l'erreur
	\For{$k \in U$}
		\For{$i \in U$}
			\For{$j \in I \cup U$}
				\State $p[k][i][j] \leftarrow f_k'(s[k])\left(\sum_{l \in U}{w_{k,l}p[l-1][i][j]+\delta_{i,k}z[t][j]}\right)$
			\EndFor
		\EndFor
	\EndFor
	\For{$i \in U$}
		\For{$j \in I \cup U$}
			\State $\epsilon[i][j] \leftarrow \epsilon[i][j] + \sum_{k \in U}{2(z[t][k]-d[t][k])p[k][i][l]}$
		\EndFor
	\EndFor
\EndFor
\EndProcedure
\end{algorithmic} 
\caption{Algorithme RTRL.}
\label{RTRL}
\end{algorithm}

On parle d'apprentissage en temps réel car il est possible d'apprendre après chaque élément de la séquence $x_1, ..., x_n$. On peut également accumuler le gradient sur toute la séquence $x_1, ..., x_n$ comme présenté dans l'algorithme \ref{RTRL}. Nos expériences ont montré qu'il était mieux d'accumuler le gradient sur une séquence entière voire sur des batches de plusieurs séquences.

\section{Comparaison des deux algorithmes}

La première remarque à faire est que, si on prend le réseau décrit dans la section précédente et que l'on accumule le gradient sur une séquence, alors les algorithmes RTRL et BPTT calculent la même quantité : $\frac{\partial E}{\partial w}$.

On pourra vérifier en pratique que les deux algorithmes calculent bien la même quantité dans la section suivante où les résultats sont identiques.

Intéressons-nous maintenant aux complexités de ces deux algorithmes. Le tableau ci-dessous résume leurs complexités en espace et en temps où l'on considère un réseau à $n$ neurones et une séquence de taille $L$.

\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& Complexité en temps & Complexité en espace \\
\hline 
RTRL & $O(n^4)$ & $O(n^{3})$ \\
\hline
BPTT & $O(Ln^2)$ & $O(Ln)$ \\
\hline
\end{tabular}
\end{center}

Justifions rapidement ces résultats. Pour RTRL :
\begin{itemize}
\item Complexité en espace : besoin de stocker un tableau $p$ de dimension $3$ d'où un coût en $O(n^3)$.
\item Complexité en temps : la mise à jour de chaque élément du tableau nécessite le calcul d'une somme de $n$ termes d'où un coût en $O(n^4)$.
\end{itemize}

Et pour BPTT :
\begin{itemize}
\item Complexité en espace : valeurs de sortie des $Ln$ neurones (après dépliage).
\item Complexité en temps : chacun des $Ln$ neurones met à jour ses poids en $O(n)$ ($O(1)$ pour chacun de ses $n$ poids) d'où un coût en $O(Ln^2)$.
\end{itemize}

L'algorithme BPTT est donc bien plus intéressant du point de vue temporel et même spatial si la taille de la séquence n'est pas trop élévée.

L'algorithme BPTT a donc de nombreux avantages par rapport à RTRL :
\begin{itemize}
\item conceptuellement, il s'agit de la continuité naturelle de la rétropropagation des réseaux feedforward pour les réseaux récurrents ;
\item il possède une meilleure complexité temporelle et spatiale que RTRL ;
\item il peut s'appliquer à n'importe quelle architecture de réseaux récurrents, et donc en particulier à l'architecture LSTM que nous verrons plus tard. RTRL n'a quant à lui été développé que pour les réseaux fully-connected, même s'il doit être possible de déterminer les formules de propagation pour d'autres architectures.
\end{itemize}

\section{Évaluation}

Nous avons implémenté les algorithmes BPTT et RTRL avec comme objectif d'apprendre à des réseaux récurrents la grammaire de Reber.

Dans la première sous-section est décrit avec plus de détails le problème à résoudre. Dans la deuxième sous-section, sont exposés les résultats obtenus par les deux algorithmes.

\subsection{Grammaire de Reber}

Dans un premier temps, nous avons comparé ces algorithmes sur l'apprentissage de la grammaire de Reber, qui est régulière. Nous utiliserons la grammaire simple présentée sur la figure \ref{Grammaire de Reber simple}.

\begin{figure}[h!]
\begin{center}
\input{images/chapter5/reber_simple.tex}
\caption{Automate reconnaissant la grammaire de Reber simple}
\label{Grammaire de Reber simple}
\end{center}
\end{figure}

À l'aide de cette automate, nous avons généré deux ensembles de mots distincts afin d'entraîner d'une part et de tester d'autre part notre futur réseau. L'objectif du réseau sera alors d'apprendre cette grammaire afin de prédire les caractères possibles après un caractère donné.

Plus précisément, si $w_1w_2...w_n$ est un mot reconnu par la grammaire de Reber, nous associons à chaque lettre de l'ensemble $\{B, T, P, S, X, V, E\}$ un nombre dans $\{1, ..., 7\}$. Puis nous créons une séquence $(x_1, ..., x_n)$ où pour tout $i$, $x_i \in \mathbb{R}^7$ est la lettre $w_i$ \textit{one hot encoded}. Par exemple si $w_1$ est $B$ et que $B$ est associé au nombre $1$ alors $x_1 = (1, 0, ..., 0)$. À chaque temps $t \in \{1, ..., n-1\}$, nous voulons que le réseau prédise les transitions possibles de l'automate après qu'il ait vu $w_1...w_t$.

Les réseaux que nous utiliserons, émettront à chaque temps $t$ un vecteur de $\mathbb{R}^7$ où chaque coordonnée sera comprise entre $0$ et $1$. Nous dirons que le réseau a prédit une transition utilisant la lettre $w$ au temps $t$ si la coordonnée correspondante du vecteur a une valeur supérieure à un seuil défini. Nous avons utilisé $0.3$ comme valeur seuil.

Lors des phases de test, nous calculons un score pour évaluer le réseau. Ce score est la proportion des mots pour lesquels celui-ci a correctement prédit toutes les transitions.

Ce premier problème permet d'évaluer la capacité des réseaux récurrents à traiter des séquences de taille variable.

L'étape suivante consistera à tester les algorithmes sur l'apprentissage de la grammaire de Reber symétrique présentée sur la figure \ref{Grammaire de Reber symétrique}.  
\begin{figure}[h!]
\begin{center}
\input{images/chapter5/reber_double.tex}
\caption{Automate reconnaissant la grammaire de Reber symétrique}
\label{Grammaire de Reber symétrique}
\end{center}
\end{figure}

Cette fois le problème qui nous intéresse est de savoir si le réseau est capable de retenir une information sur le long terme. Ainsi nous évaluons le réseau sur sa capacité à bien se souvenir que la deuxième lettre est la même que l'avant-dernière lettre d'un mot de la grammaire de Reber symétrique.

Nous utilisons ici un score différent. Le score sera la proportion des mots pour lesquels le réseau a correctement prédit que la deuxième lettre était la même que l'avant-dernière.

\subsection{Résultats}

Le tableau ci-dessous montre les sorties d'un réseau récurrent entraîné avec RTRL. À chaque temps, il renvoie un vecteur de $\mathbb{R}^7$ indiquant pour lui les transitions possibles. Les transitions sélectionnées sont celles dont la sortie associée est supérieure à $0.3$. Elle sont en gras dans le tableau.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
Caractère présenté & B & T & P & S & X & V & E \\
\hline
B & 0.01 & \textbf{0.48} & \textbf{0.51} & 0.01 & 0.01 & 0.01 & 0.01 \\
\hline
T & 0.00 & 0.02 & 0.00 & \textbf{0.56} &  \textbf{0.43} & 0.02 & 0.01 \\
\hline
X & 0.00 & 0.01 & 0.00 & \textbf{0.53} & \textbf{0.47} & 0.02 & 0.00 \\
\hline
X & 0.01 & \textbf{0.47} & 0.01 & 0.03 & 0.02 & \textbf{0.50} & 0.02 \\
\hline
V & 0.01 & 0.01 & \textbf{0.51} & 0.00 & 0.00 & \textbf{0.47} & 0.03 \\
\hline
V & 0.00 & 0.00 & 0.01 & 0.02 & 0.02 & 0.00 & \textbf{0.97} \\
\hline
\end{tabular}
\end{center}

On remarque que sur cet exemple, toutes les prédictions sont valides.

De manière plus générale, ce réseau récurrent est capable d'apprendre parfaitement la grammaire de Reber simple. En effet dans la figure \ref{curves_reber_simple} où sont présentes les courbes d'apprentissage d'un réseau entrainé avec RTRL et BPTT, on remarque qu'assez rapidement, après environ 5000 chaînes de caractères, le réseau atteint un score de $1.0$. C'est-à-dire que sur les $10000$ chaînes que nous lui soumettons, il prédit à chaque fois toutes les transitions justes.

\begin{figure}[h!]
\begin{center}
\begin{tabular}{cc}
\includegraphics[scale=0.3]{images/chapter5/learning_curve_rtrl_reber_sequence.png} & 
\includegraphics[scale=0.3]{images/chapter5/learning_curve_bptt_reber_sequence.png}
\end{tabular}
\caption{Évolution de la précision lors de l'apprentissage d'un réseau récurrent à 7 neurones d'entrée, 2 neurones cachés et 7 neurones de sorties avec RTRL (à gauche) et avec BPTT (à droite).}
\label{curves_reber_simple}
\end{center}
\end{figure}

L'apprentissage de la grammaire de Reber simple par un réseau récurrent est donc un succès. On obtient bien des résultats équivalents avec les deux algorithmes de calcul du gradient, ce qui était attendu.

\medbreak

Intéressons-nous maintenant à la grammaire de Reber symétrique. L'objectif est maintenant de tester si cette architecture de réseaux récurrents est capable d'apprendre des dépendances à long terme ou autrement dit d'apprendre des motifs sur une longue période de temps.

On retrouvera les résultats moyennés pour les deux algorithmes sur la figure \ref{curves_reber_double}. Le score utilisé sur ces courbes est le même que pour la grammaire de Reber simple. Si l'on considère seulement la bonne prédiction de l'avant-dernière lettre alors on obtient un score de $0.75$.

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.4]{images/chapter5/rtrl_bptt.png}
\caption{Résultats des algorithmes BPTT (rouge) et RTRL (bleu) sur l'apprentissage d'une grammaire de Reber symétrique, moyenné sur 100 essais. Le réseau utilisé contient 7 neurones d'entrée, 12 neurones cachés et 7 neurones de sortie.}
\label{curves_reber_double}
\end{center}
\end{figure}

On remarque donc que le réseau n'est pas capable d'apprendre parfaitement la grammaire de Reber symétrique. Sa principale cause d'échec est l'incapacité à prédire correctement l'avant-dernière lettre comme étant la seconde. Néanmoins, on remarque encore que les algorithmes RTRL et BPTT offrent exactement la même dynamique ce qui confirme que ces deux algorithmes calculent bien la même quantité dans ce cas-ci.

On en conclut que l'architecture de réseaux récurrents que nous avons utilisée, bien que permettant de traiter des séquences de taille variable, est limitée quant à son apprentissage des longues dépendances temporelles.

Dans la section suivante, nous allons donner des pistes théoriques pour comprendre l'incapacité de ces réseaux à apprendre des motifs sur des grandes périodes de temps. Cette vision théorique nous permettra ensuite d'introduire la cellule LSTM.

\section{Problème des dépendances temporelles}

\label{dependances_temporelles}

Pour conclure cette partie, nous allons effectuer une analyse théorique montrant les limitations des réseaux récurrents fully-connected. Il en ressortira la nécessité d'une architecture plus complexe permettant la conservation des dépendances temporelles à long terme.

Nous allons prendre un réseau et des notations similaires à celui utilisé dans la partie \ref{RTRL_section} sur l'algorithme RTRL. On retrouvera une visualisation de l'architecture considérée dans la figure \ref{archi_dep_tempo}. On prend un réseau avec $n$ neurones cachés numérotés de $1$ à $n$, $m - n$ neurones de sortie numérotés de $n+1$ à $m$ et $p - m$ neurones d'entrée numérotés de $m+1$ à $p$.

Les neurones cachés prennent comme entrées au temps $t$ les entrées du réseau au temps $t$ ainsi que les sorties des neurones cachés au temps $t-1$. Tandis que les neurones de sortie prennent comme entrées les sorties des neurones cachés au temps $t$.

On note alors pour $i \in \{1, ..., m\}$ :
\begin{itemize}
	\item $s_i(t) = \left\{
    \begin{array}{ll}
        \sum_{j = 1}^{n}{w_{ij}y_j(t-1)} + \sum_{j = m+1}^{p}{w_{ij}y_j(t)} & \textsf{si } i \in \{1, ..., n\} \\
        \sum_{j = 1}^{n}{w_{ij}y_j(t)} & \textsf{si } i \in \{n+1, ..., m\}
    \end{array}
\right.$
	\item $y_i(t) = f_i(s_i(t))$
	\item $E = \sum{E(t)}$
	\item $\epsilon_i(t) = \frac{\partial E}{\partial s_i(t)}$
\end{itemize}

\begin{figure}
\begin{center}
\input{images/chapter5/network_demo_propag.tex}
\caption{Architecture considérée dans la sous-section \ref{dependances_temporelles}}
\label{archi_dep_tempo}
\end{center}
\end{figure}

Notre objectif est de montrer que la dépendance temporelle entre un neurone caché du temps $t$ et d'un neurone du temps $t + q$ diminue rapidement avec $q$. Ce qui montrera que cette architecture n'est pas adaptée pour apprendre des dépendances à long terme.

$\epsilon_i(t)$ représente le gradient de l'erreur par rapport à l'activation d'un neurone $i$ du temps $t$ et $\epsilon_j(t+q)$ le gradient de l'erreur par rapport à l'activation d'un neurone $j$ du temps $t+q$. On voudrait montrer que ces deux quantités s'influencent de moins en moins lorsque $q$ augmente. En effet, cela montrerait qu'il est difficile d'apprendre des dépendances à long terme. Pour cela, nous allons donc étudier la quantité $\frac{\partial \epsilon_i(t)}{\partial \epsilon_j(t+q)}$ et montrer que celle-ci décroit rapidement avec $q$.

Pour un neurone de sortie, on a :
$$
\epsilon_i(t) = \frac{\partial E}{\partial y_i(t)}\frac{\partial y_i(t)}{s_i(t)} = \frac{\partial E}{\partial y_i(t)}f'_i(s_i(t))
$$

De même pour un neurone caché, d'après la règle de la chaine :
$$
\epsilon_i(t) = \sum_{j = 0}^{n}{\frac{\partial E}{\partial s_j(t+1)}\frac{\partial s_j(t+1)}{\partial s_i(t)}} + \sum_{j = n+1}^{m}{\frac{\partial E}{\partial s_j(t)}\frac{\partial s_j(t)}{\partial s_i(t)}}
$$

D'où :
$$
\epsilon_i(t) = \sum_{j = 0}^{n}{\epsilon_j(t+1)f'_i(s_i(t))w_{ji}} + \sum_{j = n+1}^{m}{\epsilon_j(t)f'_i(s_i(t))w_{ji}}
$$

On en déduit :
$$
\frac{\partial \epsilon_i(t)}{\partial \epsilon_j(t+1)} = f'_i(s_i(t))w_{ji}
$$

D'où par récurrence :
$$
\frac{\partial \epsilon_i(t)}{\partial \epsilon_j(t+q)} = \sum_{l_1 = 0}^{n}{\sum_{l_2 = 0}^{n}{...\sum_{l_{q-1} = 0}^{n}{\prod_{i=1}^{q}{f'_{l_i}(t+i-1)w_{l_{i+1}l_i}}}}}
$$
Cette quantité représente un flux local.

Réécrivons cette quantité en utilisant une notation matricielle :
$$
\frac{\partial \epsilon_i(t)}{\partial \epsilon_j(t+q)} = W_j^TF'(t + q - 1)(\prod_{k = 2}^{q-1}{WF'(t + q - k)})W_if'_i(s_i(t))
$$
avec : 
\begin{itemize}
\item $W = (w_{ij})_{i,j}$
\item $F'(t) = diag(f'_1(s_1(t)), ..., f'_n(s_n(t)))$
\end{itemize}

Soit une norme matricielle $||.||_A$ compatible avec une norme vectorielle $||.||_x$ telle que $max_{1, ..., n}(|x_i|) \leq ||x||_x$.

L'hypothèse sur la norme $||.||_x$ donne :
$$
|x^Ty| = |\sum_{i=1}^{n}{x_iy_i}| \leq n max(|x_i|) max(|y_i|) \leq n||x||_x ||y||_x
$$

On a alors :
$$
|\frac{\partial \epsilon_i(t)}{\partial \epsilon_j(t+q)}| \leq n ||W_j||_x ||F'(t + q - 1)(\prod_{k = 2}^{q-1}{WF'(t + q - k)})W_if'_i(s_i(t))||_x
$$

Par compatibilité :
$$
|\frac{\partial \epsilon_i(t)}{\partial \epsilon_j(t+q)}| \leq n ||W_j||_x ||W||_A^{q-2} ||W_i||_x (f'_{max})^{q}
$$
avec $f'_{max} = max_{1, ..., n}(||F'(i)||_A)$

On remarque que :
$$
\forall i, ||W_i||_x = ||We_i||_x \leq ||W||_A ||e_i||_x \leq \lambda ||W||_A
$$
avec $e_i=(1_{i=j})_j$ et $\lambda = max_{1, ..., n}(||e_i||_x)$

Finalement :
$$
|\frac{\partial \epsilon_i(t)}{\partial \epsilon_j(t+q)}| \leq \lambda n ||W||_A^{q}(f'_{max})^{q}
$$

On prend $||A||_A = max_i(\sum_{j}{|a_{ij}|})$, $||x||_x = max_i(|x_i|)$ et $f_i(t) = \sigma(t) = \frac{1}{1+exp(-t)}$. On a alors $f'_{max} = \frac{1}{4}$, $\lambda = 1$ et $||W||_A \leq n w_{max}$ avec $w_{max} = max_{i,j}(|w_{ij}|)$, d'où :
$$
|\frac{\partial \epsilon_i(t)}{\partial \epsilon_j(t+q)}| \leq n (\frac{nw_{max}}{4})^{q}
$$

On en conclut que si $w_{max} < \frac{4}{n}$ alors on a une décroissance exponentielle.

Ce résultat dit donc que si les poids sont inférieurs à une certaine valeur, alors on peut être sûr que le réseau ne pourra pas modéliser convenablement les dépendances à long terme.

Afin de contourner ce problème, nous introduisons dans la partie suivante une architecture de réseaux de neurones récurrents, le LSTM, qui a été développée pour résoudre ce problème spécifiquement.