Algorithme du gradient stochastique

L'algorithme du gradient stochastique est une méthode de descente de gradient (itérative) utilisée pour la minimisation d'une fonction objectif qui est écrite comme une somme de fonctions dérivables.

Préliminaires

À la fois l'estimation statistique et l'apprentissage automatique s'intéressent au problème de la minimisation d'une fonction objectif qui a la forme d'une somme :

$Q(w)={\frac {1}{n}}\sum _{i=1}^{n}Q_{i}(w)$,

où le paramètre $w^{*}$ qui minimise $Q(w)$ doit être estimé. Chacune des fonctions $Q_{i}$ est généralement associée avec la $i$-ème observation de l'ensemble des données (utilisées pour l'apprentissage).

En statistique classique, les problèmes de minimisation de sommes apparaissent notamment dans la méthode des moindres carrés et dans la méthode de maximum de vraisemblance (pour des observations indépendantes). Les estimateurs qui apparaissent alors comme minimiseurs de sommes sont appelés M-estimateur. Cependant, en statistique, il est su depuis longtemps qu'exiger ne serait-ce qu'une minimisation locale est trop restrictive pour certains problèmes d'estimation de maximum de vraisemblance, comme montré dans le célèbre exemple de Thomas Ferguson. Ainsi, les théoriciens des statistiques modernes considèrent souvent les points stationnaires de la fonction de vraisemblance (ou bien les zéros de sa dérivée, la fonction score, et d'autres équations d'estimation).

Le problème de la minimisation d'une somme se retrouve aussi dans la minimisation du risque empirique : dans ce cas, $Q_{i}(w)$ est la valeur de la fonction objectif pour le $i$-ème exemple, et $Q(w)$ est le risque empirique.

Lorsqu'elle est utilisée pour minimiser cette fonction, la méthode standard de descente de gradient correspond à cette itération :

$w:=w-\eta \nabla Q(w)=w-{\frac {\eta }{n}}\sum _{i=1}^{n}\nabla Q_{i}(w),$

où $\eta$ est le pas de l'itération (parfois appelé le taux d'apprentissage en apprentissage automatique).

Très souvent, les fonctions élémentaires constituant la somme revêtent une forme simple qui permet le calcul efficace de la fonction somme et de son gradient (qui n'est autre que la somme des gradients des fonctions élémentaires). Par exemple, en statistique, les familles exponentielle (à un paramètre) permettent une évaluation efficace de la fonction et de son gradient.

Cependant, dans d'autres cas, évaluer le gradient entier peut devenir très coûteux, lorsque le calcul des gradients de chaque morceau n'est pas simple. Et si l'ensemble d'apprentissage est très large (big data) et qu'aucune formule simple n'est disponible pour les gradients, calculer la somme des gradients peut rapidement devenir excessif. C'est dans le but d'améliorer le coût de calcul de chaque étape que la méthode de descente de gradient stochastique a été mise au point. En effet, à chaque étape, cette méthode tire un échantillon aléatoire de l'ensemble des fonctions $Q_{i}$ constituant la somme. Cette astuce devient très efficace dans le cas de problème d'apprentissage à grande ou très grande échelles.

Méthode itérative

Les fluctuations de la fonction coût objectif sont représentées en fonction des étapes de la descente de gradient, avec mini-lots.

Dans la descente de gradient stochastique (ou « en ligne »), la vraie valeur du gradient de $Q(w)$ est approchée par le gradient d'une seule composante de la somme (c'est-à-dire d'un seul exemple) :

Alors que l'algorithme parcourt l'ensemble d'apprentissage, il réalise cette étape de mise-à-jour pour chaque exemple. Plusieurs parcours de l'ensemble d'apprentissage peuvent être nécessaires avant la convergence de la méthode. Si cela est nécessaire, les données sont habituellement mélangées à chaque parcours, afin d'éviter les cycles. Une autre astuce souvent mise en place en pratique consiste à utiliser un taux d'apprentissage adaptatif afin d'améliorer ou d'assurer la convergence de l'algorithme.

En pseudo-code, la méthode de descente de gradient stochastique peut être représentée comme suit :

• Choisir des valeurs initiales pour les paramètres $w$, et un taux d'apprentissage $\eta$.
• Répéter jusqu'à ce qu'un minimum approché (assez précisément) soit obtenu :
  • Mélanger aléatoirement les échantillons de l'ensemble d'apprentissage.
  • Pour $\!i=1,2,...,n$, faire :
    • $\!w:=w-\eta \nabla Q_{i}(w).$

Un compromis entre les deux formes est appelé « mini-lots » : au lieu de calculer le gradient d'un seul exemple ou le gradient de tous les exemples, la méthode calcule à chaque étape le gradient sur plusieurs exemples (des petits lots, d'où le nom). Cette variante peut être bien plus efficace que la méthode simple de descente de gradient stochastique, parce qu'une implémentation bien écrite peut utiliser des bibliothèques de calcul vectoriel, au lieu de calculer chaque étape séparément. La variante « mini-lots » peut aussi présenter une convergence plus lisse, comme le gradient calculé à chaque étape utilise plus d'exemples d'apprentissage.

La convergence de l'algorithme de descente de gradient stochastique a été analysée via les théories de l'optimisation convexe et de l'approximation stochastique. En bref, lorsque l'on peut assurer que le taux d'apprentissage $\eta$ est décroissant (avec une vitesse suffisante), et vérifie certaines hypothèses de régularité, alors l'algorithme converge presque sûrement vers un minimum global, si la fonction coût est convexe ou quasi-convexe, ou sinon converge presque sûrement vers un minimum local. Ce résultat peut aussi être obtenu comme une application du théorème de Robbins-Siegmund.

Exemple

Supposons que nous voulions utiliser une ligne droite ($y=\!w_{1}+w_{2}x$) pour représenter un ensemble de points d'apprentissages (en deux dimensions) $\!(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$, en utilisant les moindres carrés. La fonction coût à minimiser est alors :

$Q(w)=\sum _{i=1}^{n}Q_{i}(w)=\sum _{i=1}^{n}\left(w_{1}+w_{2}x_{i}-y_{i}\right)^{2}.$

La dernière ligne de l'algorithme en pseudo-code (voir ci-dessus) pour ce problème précis devient :

${\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}:={\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}-\eta {\begin{bmatrix}2(w_{1}+w_{2}x_{1}-y_{1})\\2x_{2}(w_{1}+w_{2}x_{2}-y_{2})\end{bmatrix}}$

Applications

La descente de gradient stochastique est un algorithme très utilisé pour l'entraînement de nombreuses familles de modèles en apprentissage automatique, notamment les machines à vecteurs support (linéaires), la régression logistique (voir par exemple Vowpal Wabbit) et les modèles graphiques. Lorsqu'elle est combinée à l'algorithme de propagation inverse, la méthode obtenue est l'algorithme standard de facto, le plus utilisé pour l'entraînement des réseaux neuronaux artificiels.

La méthode DGS (SGD en anglais) est en compétition directe avec l'algorithme L-BFGS, ^{[citation nécessaire]} qui lui aussi est très utilisé. DGS est utilisé depuis les années 1960 au moins, pour entraîner des modèles de régression linéaire, initialement sous le nom ADALINE.

Un autre algorithme assez utilisé de descente de gradient stochastique est le filtre moyen des moindres carrés (LMS) adaptatif.

Extensions et variantes

De nombreuses améliorations sur l'algorithme SGD initial ont été proposées et utilisées. En particulier, en apprentissage automatique, la nécessité de fixer un taux d'apprentissage (le pas de l'algorithme) est souvent problématique : un paramètre trop grand peut faire diverger l'algorithme tandis qu'un paramètre trop petit ralentit la convergence.

Une extension de SGD relativement simple consiste à choisir comme taux d'apprentissage une fonction $\eta _{t}$ décroissante en fonction du nombre d'itérations $t$, donnant une progression du taux d'apprentissage, de sorte que les premières itérations permettent de forts changements dans les paramètres, tandis que les itérations tardives ne feront que les peaufiner légèrement. De telles progressions décroissantes sont connues depuis les travaux de MacQueen sur les K-moyennes.

SGD Moment

Parmi les autres propositions, on notera notamment la méthode du moment, qui apparaît dans un article de Rumelhart, Hinton et Williams sur l'apprentissage par rétro-propagation. La méthode SGD avec moment conserve en mémoire la mise-à-jour à chaque étape ($\Delta w$), et calcule la suivante comme une combinaison linéaire du gradient actuel et de la modification précédente : si on note $w_{n}$ les coefficients obtenus après n itérations, ainsi que $\Delta w_{n}$ la n-ième mise à jour des paramètres :

$\Delta w_{n+1}:=\eta \nabla Q_{i}(w)+\alpha \Delta w_{n}$

$w_{n+1}:=w_{n}-\Delta w_{n+1}$

Le nom moment vient d'une analogie avec le moment en physique : le vecteur de paramètres $w$, considéré comme une particule qui voyage au travers de l'espace des paramètres (souvent en grande dimension), subit une accélération via le gradient (qui agit comme une « force »). Contrairement à la méthode SGD classique, cette variante a tendance à continuer de voyager dans la même direction, en empêchant les oscillations. La méthode SGD moment a été utilisée avec succès depuis plusieurs dizaines d'années .

Moyennage

L'algorithme de SGD moyenné, inventé indépendamment par David Ruppert et Boris Polyak à la fin des années 1980, est une méthode SGD qui conserve en mémoire la valeur moyenne (cumulée) de son vecteur de paramètre au cours du temps. C'est-à-dire que l'étape de mise-à-jour est la même que pour l'algorithme SGD ordinaire, mais en gardant aussi la trace de la valeur moyenne (étape après étape) :

${\bar {w}}={\frac {1}{t}}\sum _{i=0}^{t-1}w$.

Lorsque l'optimisation est terminée, ce vecteur moyenné de paramètres sera utilisé à la place de $w$.

AdaGrad

AdaGrad (diminutif de adaptive gradient, anglais pour « gradient adaptatif ») est une amélioration de la méthode SGD qui détermine automatiquement un taux d'apprentissage pour chaque paramètre. On choisit toujours un taux d'apprentissage commun ($\eta$), mais celui-ci est multiplié par les éléments du vecteur $G_{j,j}$, qui est obtenu comme diagonale de la matrice $G$ suivante :

$G=\sum _{\tau =1}^{t}g_{\tau }g_{\tau }^{\mathsf {T}}$

où $g_{\tau }=\nabla Q_{i}(w)$ est le gradient à l'étape $\tau$. La diagonale est donnée par : $G_{j,j}=\sum _{\tau =1}^{t}g_{\tau ,j}^{2}$.

Ce vecteur est mis-à-jour à chaque itération. Ainsi, $G$ accumule les amplitudes (carrées) des gradients au cours de la descente, par composante. La formule pour chaque mise-à-jour est désormais :

$w:=w-\eta \,\mathrm {diag} (G)^{-{\frac {1}{2}}}\odot g$

ou, si on écrit la mise-à-jour pour chaque paramètre :

$w_{j}:=w_{j}-{\frac {\eta }{\sqrt {G_{j,j}}}}g_{j}.$

Chaque $G_{j,j}$ donne un facteur multiplicatif appliqué au taux d'apprentissage correspondant à l'unique paramètre $w_{i}$. Et comme le dénominateur de ce facteur (${\sqrt {G_{i}}}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2}}}$) est la norme ℓ₂ des dérivées précédentes, les mises-à-jour trop importantes des paramètres sont atténuées tandis que les petites modifications sont faites avec un taux d'apprentissage plus grand (et donc sont amplifiées) .

Alors qu'elle fut initialement pensée pour des problèmes convexes, AdaGrad a été appliquée avec succès à l'optimisation non-convexe.

Notes et références

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Stochastic gradient descent » (voir la liste des auteurs).

Voir aussi

Articles connexes

• Classifieur linéaire
• Algorithme d'apprentissage incrémentiel

Lectures supplémentaires

• (fr) Algorithme du gradient stochastique avec exemples [PDF]
• (en) Dimitri Bertsekas, Convex Analysis and Optimization, Athena Scientific, 2003
• (en) Dimitri P. Bertsekas, Nonlinear Programming, Cambridge, MA., Athena Scientific, 1999 (ISBN 1-886529-00-0)
• (en) Léon Bottou, Advanced Lectures on Machine Learning, LNAI 3176, Springer Verlag, 2004, 146–168 p. (ISBN 978-3-540-23122-6, lire en ligne)
• W. C. Davidon, « New least-square algorithms », Journal of Optimization Theory and Applications, vol. 18, n^o 2,‎ 1976, p. 187–197 (DOI 10.1007/BF00935703, MR 418461)
• Krzysztof C. Kiwiel, « Convergence of approximate and incremental subgradient methods for convex optimization », SIAM Journal of Optimization, vol. 14, n^o 3,‎ 2003, p. 807–840 (DOI 10.1137/S1052623400376366, MR 2085944) (Contient une liste de références très fournie).
• Pattern Classification, Richard O. Duda, Peter E. Hart, David G. Stork, (ISBN 0-471-05669-3), 2000
• Introduction to Stochastic Search and Optimization, James C. Spall, (ISBN 0-471-33052-3), 2003

Logiciels

• sgd : une bibliothèque C++ (sous licence LGPL) qui utilise la descente de gradient stochastique pour entraîner des MVS et des modèles ''conditional random field''.
• CRF-ADF : une bibliothèque C# implémentant la méthode de descente de gradient stochastique et sa variation AdaGrad pour entraîner des modèles conditional random field.
• Vowpal Wabbit : une solution d'apprentissage rapide et scalable (sous licence BSD) par John Langford et d'autres contributeurs. Contient notamment quelques variantes de l'algorithme de descente de gradient stochastique. Le dépôt source est sur GitHub.

Liens externes

• Utilisation de la descente de gradient stochastique en C++ avec Boost et Ublas pour la régression linéaire