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. Surtout dans les problèmes d'optimisation de 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 les domaines connexes.
L'estimation statistique et l'apprentissage automatique considèrent tous deux le problème de minimisation d'une fonction objectif qui a la forme d'une somme : Q(w) = (1/n) Σ Q_i(w), où le paramètre w qui minimise Q(w) doit être estimé. Chaque fonction somme Q_i est généralement associée à la i-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 apparaissent 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, où Q_i(w) est la valeur de la fonction de perte au i-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 les itérations suivantes : w := w - η ∇Q(w) = w - (η/n) Σ ∇Q_i(w). La taille du pas est notée η, parfois appelée taux d'apprentissage en apprentissage automatique, et « := » 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 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 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 évaluer le gradient nécessite d'évaluer les gradients de toutes les fonctions somme. Pour économiser 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 - η ∇Q_i(w). Lorsque 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 pour que l'algorithme converge. En pseudocode, la descente de gradient stochastique peut être présentée comme suit :
- Choisir un vecteur de paramètres initial w et un taux d'apprentissage η.
- Répéter jusqu'à convergence :
- Mélanger les échantillons d'entraînement.
- Pour chaque échantillon d'entraînement i :
- Calculer le gradient ∇Q_i(w).
- Mettre à jour les paramètres : w := w - η ∇Q_i(w).
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 fonctionner significativement mieux que la descente de gradient stochastique « vraie » 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 un article de 1986 où cela était appelé « algorithme de rétropropagation en mode groupe ». Cela peut également entraîner une convergence plus lisse, 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. En bref, lorsque les taux d'apprentissage η diminuent à un rythme approprié, et sous des hypothèses relativement modérées, la descente de gradient stochastique converge presque sûrement vers un minimum global lorsque la fonction objectif est convexe ou pseudoconvexe, et sinon 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 = w^T x à un ensemble d'exemples d'entraînement (x_i, y_i). La fonction objectif est l'erreur quadratique moyenne : Q(w) = (1/n) Σ (y_i - w^T x_i)^2. Le gradient pour un seul exemple est ∇Q_i(w) = -2 (y_i - w^T x_i) x_i. Dans la descente de gradient stochastique, la règle de mise à jour devient w := w + 2η (y_i - w^T x_i) x_i. Cela équivaut à l'algorithme des moindres carrés moyens (LMS), également connu sous le nom de règle de Widrow-Hoff, introduit par Bernard Widrow et Ted Hoff en 1960. L'algorithme LMS est un exemple classique d'approximation stochastique et a été largement utilisé dans le traitement adaptatif du signal.
Applications en apprentissage automatique
La descente de gradient stochastique est l'algorithme d'optimisation central pour l'entraînement des réseaux de neurones, y compris les modèles de apprentissage profond. Dans l'apprentissage profond moderne, SGD et ses variantes sont utilisés pour minimiser des fonctions de perte telles que l'entropie croisée pour la classification ou l'erreur quadratique moyenne pour la régression. L'efficacité de l'algorithme pour traiter de grands ensembles de données le rend essentiel pour entraîner des modèles sur des corpus massifs, tels que ceux utilisés dans les grands modèles de langage. Par exemple, l'entraînement des modèles basés sur les transformeurs, comme introduit dans l'article de 2017 « Attention Is All You Need » par Jakob Uszkoreit, Lukasz Kaiser et d'autres, repose sur SGD ou ses variantes adaptatives comme Adam.
SGD est également utilisé dans d'autres domaines de l'intelligence artificielle, y compris la vision par ordinateur, le traitement du langage naturel et l'apprentissage par renforcement. Dans l'apprentissage par renforcement, SGD est utilisé pour mettre à jour les paramètres de politique et de fonction de valeur, comme dans les méthodes de gradient de politique. La nature stochastique de l'algorithme lui permet d'échapper aux minima locaux dans les problèmes d'optimisation non convexes, ce qui est particulièrement important pour entraîner des réseaux profonds avec des paysages de perte complexes.
Variantes et améliorations
Plusieurs variantes de la descente de gradient stochastique ont été développées pour améliorer la convergence et la stabilité. Une amélioration courante est l'utilisation de l'élan (momentum), qui accumule un vecteur de vitesse pour accélérer les gradients dans des directions cohérentes et amortir les oscillations. Une autre est le gradient accéléré de Nesterov, qui calcule le gradient à une position anticipée. Les méthodes de taux d'apprentissage adaptatif, telles que Adam, ajustent le taux d'apprentissage par paramètre en fonction des estimations des premier et deuxième moments des gradients. Ces méthodes sont largement utilisées en pratique et sont souvent considérées comme des optimiseurs par défaut pour l'entraînement des réseaux de neurones.
D'autres techniques connexes incluent les programmes de taux d'apprentissage, qui ajustent le taux d'apprentissage au fil du temps, et le écrêtage de gradient, qui empêche les gradients explosifs en réduisant les grands gradients. La normalisation par lots et la normalisation de couche sont souvent utilisées en conjonction avec SGD pour stabiliser l'entraînement et permettre des taux d'apprentissage plus élevés. De plus, les stratégies de initialisation des poids, telles que l'initialisation Xavier ou He, sont cruciales pour un entraînement SGD efficace.
Défis et considérations
L'un des principaux défis de la descente de gradient stochastique est la sélection du taux d'apprentissage. Si le taux d'apprentissage est trop élevé, l'algorithme peut diverger ; s'il est trop faible, la convergence peut être lente. En pratique, des programmes de taux d'apprentissage ou des méthodes adaptatives sont utilisés pour atténuer ce problème. Un autre défi est le bruit introduit par l'utilisation d'un sous-ensemble de données, ce qui peut faire fluctuer la perte. Cependant, ce bruit peut également être bénéfique, car il peut aider l'algorithme à échapper aux minima pointus et à trouver des minima plus plats qui généralisent mieux.
SGD est sensible à la mise à l'échelle des caractéristiques, donc la normalisation des caractéristiques est souvent recommandée. Le choix de la taille du mini-lot affecte également les performances : 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 conduire à une moins bonne généralisation. Dans l'entraînement distribué, SGD peut être parallélisé en utilisant des techniques comme les mises à jour synchrones ou asynchrones, comme implémenté dans des frameworks tels que TensorFlow et PyTorch.
Contexte historique
Les racines de la descente de gradient stochastique remontent à l'algorithme de Robbins-Monro, développé par Herbert Robbins et Sutton Monro en 1951, qui a introduit l'idée de l'approximation stochastique pour la recherche de racines. Dans les années 1960, l'algorithme LMS de Bernard Widrow et Ted Hoff a appliqué des principes similaires au filtrage adaptatif. Le lien avec l'entraînement des réseaux de neurones a été établi dans les années 1980 avec la popularisation de la rétropropagation. En 1986, David Rumelhart, Geoffrey Hinton et Ronald Williams ont publié un article qui a démontré l'efficacité de la rétropropagation avec SGD pour apprendre des représentations internes. Depuis lors, SGD est devenu une pierre angulaire de l'apprentissage automatique, permettant des percées dans des domaines tels que la reconnaissance d'images, la reconnaissance vocale et le traitement du langage naturel.
Dans les années 2010, l'essor de l'apprentissage profond et la disponibilité de grands ensembles de données et de matériel puissant, tels que les GPU de NVIDIA et AMD, ont accéléré l'adoption de SGD. Des institutions de recherche comme Stanford AI Lab, Berkeley AI Research et Université de Toronto ont contribué aux avancées théoriques et pratiques. Aujourd'hui, SGD reste un domaine de recherche actif, avec des travaux en cours sur la compréhension de ses propriétés de généralisation et le développement de nouvelles variantes.