La descente de gradient stochastique (souvent abrégée SGD) est une méthode itérative pour optimiser une fonction objectif possédant des propriétés de régularité appropriées, telles que la différentiabilité ou la sous-différentiabilité. Elle peut être considérée comme une approximation stochastique de l'optimisation par descente de gradient, car elle remplace le gradient réel, calculé à partir de l'ensemble des données, par une estimation de celui-ci, calculée à partir d'un sous-ensemble de données sélectionné aléatoirement. En particulier dans les problèmes d'optimisation en haute dimension, cela réduit la charge de calcul très élevée, permettant des itérations plus rapides en échange d'un taux de convergence plus faible. L'idée de base derrière l'approximation stochastique remonte à l'algorithme de Robbins-Monro des années 1950. Aujourd'hui, la descente de gradient stochastique est devenue une méthode d'optimisation importante dans apprentissage automatique et plus largement dans intelligence artificielle.
Contexte
L'estimation statistique et l'apprentissage automatique considèrent tous deux le problème de la minimisation d'une fonction objectif qui a la forme d'une somme : Q(w) = (1/n) * somme_{i=1}^{n} Q_i(w), où le paramètre w qui minimise Q(w) doit être estimé. Chaque fonction somme Q_i est typiquement associée à la i-ème observation dans l'ensemble de données utilisé pour l'entraînement. En statistique classique, les problèmes de minimisation de somme apparaissent dans les moindres carrés et dans l'estimation du maximum de vraisemblance pour des observations indépendantes. La classe générale d'estimateurs qui émergent comme minimiseurs de sommes est appelée M-estimateurs. Cependant, en statistique, il est reconnu depuis longtemps qu'exiger même une minimisation locale est trop restrictif pour certains problèmes d'estimation du maximum de vraisemblance. Par conséquent, les théoriciens statistiques contemporains considèrent souvent les points stationnaires de la fonction de vraisemblance, ou les zéros de sa dérivée, la fonction de score, et d'autres équations d'estimation.
Le problème de minimisation de somme apparaît également pour la minimisation du risque empirique. Là, Q_i(w) est la valeur de la fonction de perte au i-ème exemple, et Q(w) est le risque empirique. Lorsqu'elle est utilisée pour minimiser la fonction ci-dessus, une méthode de descente de gradient standard (ou « par lots ») effectuerait des itérations de la forme w := w - eta nabla Q(w) = w - (eta/n) somme_{i=1}^{n} nabla Q_i(w). La taille du pas est notée eta, parfois appelée taux d'apprentissage en apprentissage automatique, et le symbole « := » désigne la mise à jour d'une variable dans l'algorithme.
Dans de nombreux cas, les fonctions somme ont une forme simple qui permet des évaluations peu coûteuses de la fonction somme et du gradient de la somme. Par exemple, en statistique, les familles exponentielles à un paramètre permettent des évaluations économiques de fonctions et de gradients. Cependant, dans d'autres cas, l'évaluation du gradient de la somme peut nécessiter des évaluations coûteuses des gradients de toutes les fonctions somme. Lorsque l'ensemble d'entraînement est énorme et qu'aucune formule simple n'existe, l'évaluation des sommes de gradients devient très coûteuse, car l'évaluation du gradient nécessite d'évaluer les gradients de toutes les fonctions somme. Pour économiser sur le coût de calcul à chaque itération, la descente de gradient stochastique échantillonne un sous-ensemble de fonctions somme à chaque étape. Cela est très efficace dans le cas de problèmes d'apprentissage automatique à grande échelle.
Méthode itérative
Dans la descente de gradient stochastique (ou « en ligne »), le vrai gradient de Q(w) est approximé par un gradient à un seul échantillon : w := w - eta * nabla Q_i(w). Alors que l'algorithme parcourt l'ensemble d'entraînement, il effectue la mise à jour ci-dessus pour chaque échantillon d'entraînement. Plusieurs passages peuvent être effectués sur l'ensemble d'entraînement jusqu'à ce que l'algorithme converge. Si cela est fait, les données peuvent être mélangées à chaque passage pour éviter les cycles. Les implémentations typiques peuvent utiliser un taux d'apprentissage adaptatif afin que l'algorithme converge.
Un compromis entre le calcul du vrai gradient et le gradient à un seul échantillon consiste à calculer le gradient sur plus d'un échantillon d'entraînement, appelé « mini-lot », à chaque étape. Cela peut être significativement plus performant que la descente de gradient stochastique « pure » décrite, car le code peut utiliser des bibliothèques de vectorisation plutôt que de calculer chaque étape séparément, comme cela a été montré pour la première fois dans le contexte de l'« algorithme de rétropropagation en mode groupé ». Cela peut également entraîner une convergence plus régulière, car le gradient calculé à chaque étape est moyenné sur plus d'échantillons d'entraînement.
La convergence de la descente de gradient stochastique a été analysée en utilisant les théories de la minimisation convexe et de l'approximation stochastique. Brièvement, lorsque les taux d'apprentissage eta diminuent à un rythme approprié, et sous des hypothèses relativement faibles, la descente de gradient stochastique converge presque sûrement vers un minimum global lorsque la fonction objectif est convexe ou pseudoconvexe, et autrement converge presque sûrement vers un minimum local. C'est en fait une conséquence du théorème de Robbins-Siegmund.
Régression linéaire
Supposons que nous voulions ajuster une ligne droite y = a + bx à un ensemble d'exemples d'entraînement (x_i, y_i) en utilisant les moindres carrés. La fonction objectif est Q(a, b) = (1/n) somme_{i=1}^{n} (y_i - (a + bx_i))^2. La descente de gradient par lots calculerait le gradient de Q par rapport à a et b en utilisant tous les n exemples. La descente de gradient stochastique, en revanche, choisit un exemple aléatoire i et met à jour a et b en utilisant uniquement le gradient de l'erreur quadratique pour cet exemple : a := a - eta (-2)(y_i - (a + bx_i)), et b := b - eta (-2x_i)(y_i - (a + bx_i)). C'est beaucoup moins coûteux par itération, surtout lorsque n est grand.
Applications en apprentissage automatique
La descente de gradient stochastique est la pierre angulaire de l'entraînement des réseaux de neurones et des modèles de apprentissage profond. Dans ces contextes, la fonction objectif est typiquement le risque empirique, et la fonction de perte mesure l'écart entre les sorties prédites et réelles. Par exemple, lors de l'entraînement d'un modèle transformeur pour le traitement du langage naturel, SGD ou ses variantes sont utilisées pour mettre à jour les poids du réseau en fonction de mini-lots de données textuelles. La méthode est particulièrement efficace pour les problèmes à grande échelle, tels que ceux rencontrés dans les grands modèles de langage, où les données d'entraînement peuvent consister en des milliards de jetons.
SGD a également été appliqué dans d'autres domaines, notamment la vision par ordinateur, l'apprentissage par renforcement, et l'IA générative. Dans l'IA générative, des modèles comme la série GPT d'OpenAI et Claude d'Anthropic sont entraînés en utilisant des techniques d'optimisation stochastique. Le choix de l'optimiseur, souvent SGD avec momentum ou Adam, affecte significativement la vitesse et la qualité de la convergence.
Variantes et améliorations
Plusieurs variantes de la descente de gradient stochastique ont été développées pour remédier à ses limitations, telles que la convergence lente et la sensibilité au taux d'apprentissage. Celles-ci incluent les variantes de SGD comme le momentum, le gradient accéléré de Nesterov, AdaGrad, RMSProp, et Adam. Chaque variante modifie la règle de mise à jour pour améliorer les propriétés de convergence. Par exemple, le momentum ajoute une fraction de la mise à jour précédente à la mise à jour actuelle, aidant à accélérer les gradients dans la bonne direction et à amortir les oscillations. Adam, qui signifie Estimation Adaptative des Moments, maintient des taux d'apprentissage par paramètre qui sont adaptés en fonction des estimations des premier et deuxième moments des gradients.
Une autre amélioration importante est l'utilisation de programmes de taux d'apprentissage, qui ajustent le taux d'apprentissage pendant l'entraînement. Les programmes courants incluent la décroissance par paliers, la décroissance exponentielle et le recuit cosinusoïdal. Ces programmes aident l'algorithme à converger plus fiablement en réduisant la taille du pas à mesure que l'optimisation progresse.
D'autres techniques qui interagissent avec SGD incluent le clipping de gradient, qui empêche les gradients explosifs en réduisant les gradients qui dépassent un seuil, et la normalisation par lots et la normalisation de couche, qui stabilisent la distribution des entrées de chaque couche, permettant souvent des taux d'apprentissage plus élevés.
Convergence et défis
Bien que SGD soit efficace en termes de calcul, il introduit une variance dans les estimations du gradient, ce qui peut provoquer des fluctuations de la perte. Le taux de convergence de SGD est généralement plus lent que celui de la descente de gradient par lots en termes de nombre d'itérations, mais le coût par itération est beaucoup plus faible, ce qui conduit à un entraînement global plus rapide dans les contextes à grande échelle. Le choix de la taille du mini-lot est un hyperparamètre critique : des lots plus petits introduisent plus de bruit mais nécessitent moins de mémoire, tandis que des lots plus grands fournissent des gradients plus lisses mais peuvent converger vers des minima plus nets, qui peuvent se généraliser moins bien.
SGD peut également rester bloqué dans des points de selle ou des minima locaux, en particulier dans des problèmes non convexes comme l'apprentissage profond. Diverses stratégies, telles que le redémarrage, l'utilisation du momentum ou l'emploi de taux d'apprentissage adaptatifs, aident à atténuer ces problèmes. En pratique, SGD et ses variantes ont été remarquablement efficaces pour entraîner des réseaux profonds, atteignant des résultats de pointe sur de nombreuses tâches.
Contexte historique
Les racines de la descente de gradient stochastique résident dans l'algorithme de Robbins-Monro, introduit par Herbert Robbins et Sutton Monro en 1951 pour l'approximation stochastique. La méthode a ensuite été adaptée à l'apprentissage automatique dans les années 1980, en particulier dans le contexte de la rétropropagation pour les réseaux de neurones. Le terme « descente de gradient stochastique » est devenu largement utilisé à mesure que le domaine de l'apprentissage automatique grandissait. Aujourd'hui, c'est un outil fondamental dans la boîte à outils de tout praticien de l'apprentissage automatique, et il est implémenté dans tous les principaux frameworks d'apprentissage profond, y compris ceux utilisés par des entreprises comme Google DeepMind, Amazon Web Services et Microsoft Azure.