Algorithme du gradient stochastique

À 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 :

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

où le paramètre ${\displaystyle w^{*}}$ qui minimise ${\displaystyle Q(w)}$ doit être estimé. Chacune des fonctions ${\displaystyle Q_{i}}$ est généralement associée avec la ${\displaystyle 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[1]. 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, ${\displaystyle Q_{i}(w)}$ est la valeur de la fonction objectif pour le ${\displaystyle i}$-ème exemple, et ${\displaystyle 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 :

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

où ${\displaystyle \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 ${\displaystyle 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[2].

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 ${\displaystyle Q(w)}$ est approchée par le gradient d'une seule composante de la somme (c-à-d. 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 :

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 ${\displaystyle \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[3] - [4]. Ce résultat peut aussi être obtenu comme une application du théorème de Robbins-Siegmund[5].

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

${\displaystyle 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 :

${\displaystyle {\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_{i}-y_{i})\\2x_{i}(w_{1}+w_{2}x_{i}-y_{i})\end{bmatrix}}}$

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[6]. 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, 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[7].

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

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 ${\displaystyle \eta _{t}}$ décroissante en fonction du nombre d'itérations ${\displaystyle 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[8].