Descente de gradient

Lorsqu’un problème d’optimisation n’est pas soluble de manière déterministe, il existe des algorithmes permettant de trouver une solution approchée à condition toutefois que la fonction à maximiser ou minimiser soit dérivable, ce qui est le cas des réseaux de neurones. Plusieurs variantes seront proposées regroupées sous le terme de descente de gradient. Quelques lectures :

• An overview of gradient descent optimization algorithms

• Implementing a Neural Network from Scratch in Python – An Introduction

Algorithme et convergence

Soit \(g : \mathbb{R} \dans \mathbb{R}\) une fonction dérivable dont il faut trouver \(\overset{*}{x} = \underset{x \in \mathbb{R}}{\arg \min} \; g\pa{x}\), le schéma suivant illustre la méthode de descente de gradient dans le cas où \(g \pa{x} = x^2\).

On note \(x_{t}\) l’abscisse à l’itération \(t\). On note \(\dfrac{\partial g\left( x_{t}\right) }{\partial x}\) le gradient de \(g\left( x\right) =x^{2}\). L’abscisse à l’itération \(t+1\) sera \(x_{t+1}=x_{t}-\varepsilon_{t}\left[ \dfrac{\partial g\left( x_{t}\right)}{\partial x}\right]\). \(\varepsilon_{t}\) est le pas de gradient à l’itération \(t\).

On suppose maintenant que \(g\) est une fonction dérivable \(g : \mathbb{R}^q \dans \mathbb{R}\) dont il faut trouver le minimum, le théorème suivant démontre la convergence de l’algorithme de descente de gradient à condition que certaines hypothèses soient vérifiées. Une généralisation de ce théorème est présentée dans [Driancourt1996].

Théorème T1 : convergence de la méthode de Newton

[Bottou1991]

Soit une fonction continue \(g : W \in \mathbb{R}^M \dans \mathbb{R}\) de classe \(C^{1}\). On suppose les hypothèses suivantes vérifiées :

• H1 : \(\underset{W\in \mathbb{R}^q}{\arg\min} \; g\left( W\right) =\left\{ W^{\ast}\right\}\) est un singleton

• H2 : \(\forall\varepsilon>0, \; \underset{\left| W-W^{\ast}\right| >\varepsilon}{\inf}\left[ \left( W-W^{\ast}\right) ^{\prime}.\nabla g\left( W\right) \right] >0\)

• H3 : \(\exists\left( A,B\right) \in \mathbb{R}^2\) tels que \(\forall W\in\mathbb{R}^p,\; \left\| \nabla g\left( W\right) \right\| ^{2}\leqslant A^{2}+B^{2}\left\| W-W^{\ast}\right\| ^{2}\)

• H4 : la suite \(\left( \varepsilon_{t}\right)_{t\geqslant0}\) vérifie, \(\forall t>0, \; \varepsilon_{t}\in \mathbb{R}_{+}^{\ast}\) et \(\sum_{t\geqslant 0}\varepsilon_{t}=+\infty\), \(\sum_{t\geqslant 0}\varepsilon_{t}^{2}<+\infty\)

Alors la suite \(\left( W_{t}\right) _{t\geqslant 0}\) construite de la manière suivante \(W_{0} \in \mathbb{R}^M\), \(\forall t\geqslant0\) : \(W_{t+1}=W_{t}-\varepsilon_{t}\,\nabla g\left( W_{t}\right)\) vérifie \(\lim_{ t \dans+\infty}W_{t}=W^{\ast}\).

L’hypothèse H1 implique que le minimum de la fonction \(g\) est unique et l’hypothèse H2 implique que le demi-espace défini par l’opposé du gradient contienne toujours le minimum de la fonction \(g\). L’hypothèse H3 est vérifiée pour une fonction sigmoïde, elle l’est donc aussi pour toute somme finie de fonctions sigmoïdes que sont les réseaux de neurones à une couche cachée.

Démonstration du théorème

Partie 1

Soit la suite \(u_{t}=\ln\left( 1+\varepsilon_{t}^{2}x^{2}\right)\) avec \(x\in\mathbb{R}\), comme \(\sum_{t\geqslant 0} \varepsilon_{t}^{2} < +\infty, \; u_{t}\thicksim\varepsilon_{t}^{2}x^{2}\), on a \(\sum_{t\geqslant 0} u_{t} < +\infty\).

Par conséquent, si \(v_{t}=e^{u_{t}}\) alors \(\prod_{t=1}^T v_{t}\overset{T \rightarrow \infty}{\longrightarrow}D \in \mathbb{R}\).

Partie 2

On pose \(h_{t}=\left\| W_{t}-W^{\ast}\right\| ^{2}\). Donc :

\begin{eqnarray} h_{t+1} -h_{t} &=&\left\| W_{t}-\varepsilon_{t}\,\nabla g\left( W_{t}\right) -W^{\ast }\right\| ^{2}-\left\|W_{t}-W^{\ast}\right\| ^{2} \end{eqnarray}

Par conséquent :

\[h_{t+1}-h_{t}=-2\varepsilon_{t}\underset{>0} {\underbrace{\left( W_{t}-W^{\ast}\right) ^{\prime}\,\nabla g\left( W_{t}\right) }}+\varepsilon_{t}^{2}\,\left\| \,\nabla C\left( W_{t}\right) \right\| ^{2}\leqslant\varepsilon_{t}^{2}\,\left\| \,\nabla g\left( W_{t}\right) \right\| ^{2}\leqslant\varepsilon_{t}^{2}\,\left( A^{2} +B^{2}h_{t}\right)\]

D’où :

\[h_{t+1}-h_{t}\left( 1+\varepsilon_{t}^{2}B^{2}\right) \leqslant\varepsilon_{t}^{2}\,A^{2}\]

On pose \(\pi_{t}= \prod_{k=1}^t \left( 1+\varepsilon_{k}^{2}B^{2}\right) ^{-1}\) alors en multipliant des deux côtés par \(\pi_{t+1}\), on obtient :

\[\begin{split}\begin{array}{rcl} \pi_{t+1}h_{t+1}-\pi_{t}h_{t} &\leqslant& \varepsilon_{t}^{2}\,A^{2}\pi_{t+1}\\ \text{d'où }\pi_{q+1}h_{q+1}-\pi_{p}h_{p} &\leqslant& \sum_{t=p}^q \varepsilon_{t}^{2}\,A^{2}\pi_{t+1} \leqslant \sum_{t=p}^{q} \varepsilon_{t}^{2} \, A^{2}\Pi \leqslant \sum_{t=p}^{q} \varepsilon_{t}^{2}\,A^{2}\Pi \underset{t \longrightarrow \infty}{\longrightarrow} 0 \end{array}\end{split}\]

Comme la série \(\sum_t \pa{\pi_{t+1}h_{t+1}-\pi_{t}h_{t}}\) vérifie le critère de Cauchy, elle est convergente. Par conséquent :

\[\underset{q\rightarrow\infty}{\lim}\pi_{q+1}h_{q+1}=0=\underset{q\rightarrow \infty}{\lim}\Pi h_{q+1}\]

D’où \(\underset{q\rightarrow\infty}{\lim}h_{q}=0\).

Partie 3

La série \(\sum_t\pa{h_{t+1}-h_{t}}\) est convergente car \(\Pi h_t \sim \pi_t h_t\). \(\sum_{t\geqslant0}\varepsilon_{t}^{2}\,\left\| \,\nabla g\left( W_{t}\right) \right\| ^{2}\) l’est aussi (d’après H3).

D’après (1), la série \(\sum_{t\geqslant 0}\varepsilon_{t}\left( W_{t}-W^{\ast }\right) ^{\prime} \, \nabla g\left( W_{t}\right)\) est donc convergente. Or d’après les hypothèses H2, H4, elle ne peut l’être que si :

\begin{eqnarray} \underset{t\rightarrow\infty}{\lim}W_{t}&=&W^{\ast} \end{eqnarray}

Si ce théorème prouve la convergence de la méthode de Newton, il ne précise pas à quelle vitesse cette convergence s’effectue et celle-ci peut parfois être très lente. Plusieurs variantes ont été développées regroupées sous le terme de méthodes de quasi-Newton dans le but d’améliorer la vitesse de convergence.

Ce théorème peut être étendu dans le cas où la fonction \(g\) n’a plus un seul minimum global mais plusieurs minima locaux ([Bottou1991]), dans ce cas, la suite \(\pa{W_{t}}\) converge vers un mimimum local. Dans le cas des réseaux de neurones, la fonction à optimiser est :

\begin{eqnarray} G\pa{W} &=& \sum_{i=1}^{N} e\pa {Y_{i}, \widehat{Y_{i}^W}} = \sum_{i=1}^{N} e\pa {Y_{i}, f \pa{W,X_{i}}} \nonumber \end{eqnarray}

Dès que les fonctions de transfert ne sont pas linéaires, il existe une multitude de minima locaux, ce nombre croissant avec celui des coefficients.

Calcul du gradient ou rétropropagation

Afin de minimiser la fonction \(G\) décrite en (2), l’algorithme de descente du gradient nécessite de calculer le gradient de cette fonction \(G\) qui est la somme des gradients \(\partialfrac{e}{W}\) pour chaque couple \(\pa{X_i,Y_i}\) :

\begin{eqnarray} \partialfrac{G}{W}\pa{W} &=& \sum_{i=1}^{N} \partialfrac{e\pa {Y_{i}, f \pa{W,X_{i}}}}{W} \nonumber\\ &=& \sum_{i=1}^{N} \sum_{k=1}^{C_C} \partialfrac{e\pa {Y_{i}, f \pa{W,X_{i}}}}{z_{C,k}} \partialfrac{z_{C,k}}{W} \nonumber \end{eqnarray}

Les notations utilisées sont celles de la figure du perceptron. Les résultats qui suivent sont pour \(X_i=X\) donné appartenant à la suite \(\pa{X_i}\). On remarque tout d’abord que :

\begin{eqnarray} \partialfrac{e}{w_{c,i,j}} \pa{W,X} &=& z_{c-1,j} \partialfrac{e}{y_{c,i}} \pa{W,X} \nonumber \\ \partialfrac{e}{b_{c,i}} \pa{W,X} &=& \partialfrac{e}{y_{c,i}} \pa{W,X} \nonumber \end{eqnarray}

La rétropropagation du gradient consiste donc à calculer les termes : \(\partialfrac{e}{y_{.,.}}\pa{W,X}\) puisque le gradient s’en déduit facilement. La dernière couche du réseau de neurones nous permet d’obtenir :

\begin{eqnarray} \partialfrac{e}{y_{C,i}} \pa{W,X} &=& \sum_{k=1}^{C_{C}} \partialfrac{e}{z_{C,k}} \pa{W,X} \partialfrac{z_{C,k}}{y_{C,i}} \pa{W,X} \nonumber\\ &=& \partialfrac{e}{z_{C,i}} \pa{W,X} f'_{c,i}\pa{y_{C,i}} \nonumber \end{eqnarray}

Pour les autres couches \(c\) telles que \(1 \infegal c \infegal C-1\), on a :

\begin{eqnarray} \partialfrac{e}{y_{c,i}} &=& \sum_{l=1}^{C_{c+1}} \partialfrac {e}{y_{c+1,l}} \partialfrac{y_{c+1,l}}{y_{c,i}} \nonumber \\ &=& \sum_{l=1}^{C_{c+1}} \partialfrac {e}{y_{c+1,l}} \cro { \sum_{l=1}^{C_{c}} \partialfrac {y_{c+1,l}}{z_{c,l}} \underset{=0\,si\,l\neq i}{\underbrace{\partialfrac{z_{c,l}}{y_{c,i}}}} } \nonumber \\ &=& \sum_{l=1}^{C_{c+1}} \partialfrac{e}{y_{c+1,l}} \partialfrac{y_{c+1,l}}{z_{c,i}} \partialfrac{z_{c,i}}{y_{c,i}} \nonumber \end{eqnarray}

Par conséquent :

\begin{eqnarray} \partialfrac{e}{y_{c,i}} &=& \cro{ \sum_{l=1}^{C_{c+1}} \partialfrac{e}{y_{c+1,l}}w_{c+1,l,i} } \, f_{c,i}^{\prime} \pa{y_{c,i}} \nonumber \end{eqnarray}

Cette dernière formule permet d’obtenir par récurrence les dérivées \(\partialfrac{e}{y_{.,.}}\) de la dernière couche \(C\) à la première et ce, quel que soit le nombre de couches. Cette récurrence inverse de la propagation est appelée rétropropagation. Cet algorithme se déduit des équations (3), (4), (5) et (7) :

Théorème T2 : rétropropagation

Cet algorithme s’applique à un réseau de neurones vérifiant la définition du perceptron. Il s’agit de calculer sa dérivée par rapport aux poids. Il se déduit des formules (3), (4), (5) et (7) et suppose que l’algorithme de propagation a été préalablement exécuté. On note \(y'_{c,i} = \partialfrac{e}{y_{c,i}}\), \(w'_{c,i,j} = \partialfrac{e}{w_{c,i,j}}\) et \(b'_{c,i} = \partialfrac{e}{b_{c,i}}\).

Initialisation

for i in \(1..C_C\)

\(y'_{C,i} \longleftarrow \partialfrac{e}{z_{C,i}} \pa{W,X} f'_{c,i}\pa{y_{C,i}}\)

Récurrence

for c in \(1..C-1\)

for i in \(1..C_c\)

\(y'_{c,i} \longleftarrow 0\)

for j in \(1..C_{c+1}\)

\(y'_{c,i} \longleftarrow y'_{c,i} + y'_{c+1,j} \; w_{c+1,j,i}\)

\(y'_{c,i} \longleftarrow y'_{c,i} \; f'_{c,i}\pa{y'_{c,i}}\)

Terminaison

for c in \(1..C\)

for i in \(1..C_c\)

for j in \(1..C_{c-1}\)

\(w'_{c,i,j} \longleftarrow z_{c-1,j} \; y'_{c,i}\)

\(b'_{c,i,j} \longleftarrow y'_{c,i}\)

Ces formules sont assez indigestes pour comprendre comment la rétropropagation fonctionne. La figure suivante illustre comme le gradient se propage d’un neurone au précédente de façon récursive. Je la trouve plus simple à exploiter lorsqu’on dévie du perceptron classique pour faire des choses hors des clous. Je la laisse comme ça sans trop d’explications.

L’idée de la rétropropagation : en supposant connu le gradient de l’erreur par rapport à la sortie, comment en déduir le gradient par rapport aux coefficients du réseau puis comment le propager à chaque entrée de sorte qu’il puisse être transmis aux neurones de la couche inférieure.