Descente de gradient stochastique

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 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 en apprentissage automatique, notamment pour l'entraînement des réseaux de neurones et d'autres modèles de apprentissage profond.

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) Σᵢ Qᵢ(w), où le paramètre w qui minimise Q(w) doit être estimé. Chaque fonction de somme Qᵢ est généralement associée à la i-ème observation dans l'ensemble de données d'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 résultent de minimiseurs de sommes est appelée M-estimateurs. Cependant, il est reconnu depuis longtemps qu'exiger même une minimisation locale est trop restrictif pour certains problèmes de maximum de vraisemblance, c'est pourquoi 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.

Le problème de minimisation de somme se pose également pour la minimisation du risque empirique. Là, Qᵢ(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 standard (ou « par lots ») de descente de gradient effectuerait des itérations de la forme : w := w - η ∇Q(w) = w - (η/n) Σᵢ ∇Qᵢ(w). La taille du pas η est parfois appelée taux d'apprentissage en apprentissage automatique. Dans de nombreux cas, les fonctions de somme ont une forme simple qui permet des évaluations peu coûteuses de la fonction somme et du gradient de la somme, comme dans les familles exponentielles à un paramètre. Cependant, 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 elle nécessite d'évaluer les gradients de toutes les fonctions de somme. Pour économiser sur le coût de calcul, la descente de gradient stochastique échantillonne un sous-ensemble de fonctions de somme à chaque étape, ce qui est très efficace dans les 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ᵢ(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.

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

1. Initialiser les paramètres w et le taux d'apprentissage η.
2. Répéter jusqu'à convergence :
   • Mélanger les données d'entraînement.
   • Pour chaque exemple d'entraînement i :
   • Calculer le gradient ∇Qᵢ(w).
   • Mettre à jour w := w - η ∇Qᵢ(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 nettement mieux que la véritable descente de gradient stochastique 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 la rétropropagation. 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. En bref, lorsque les taux d'apprentissage 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 sinon converge presque sûrement vers un minimum local. Ceci est une conséquence du théorème de Robbins–Siegmund.

Régression linéaire

Supposons que nous voulions ajuster une ligne droite ŷ = w·x à un ensemble d'exemples d'entraînement (xᵢ, yᵢ). Un objectif courant est de minimiser l'erreur quadratique moyenne : Q(w) = (1/n) Σᵢ (ŷᵢ - yᵢ)². Le gradient pour un seul exemple est ∇Qᵢ(w) = 2(ŷᵢ - yᵢ)xᵢ. Dans la descente de gradient stochastique, la mise à jour devient w := w - η(ŷᵢ - yᵢ)xᵢ. Cet exemple simple illustre comment SGD utilise un échantillon à la fois, ce qui le rend efficace en calcul pour les grands ensembles de données.

Applications en apprentissage automatique

La descente de gradient stochastique est l'algorithme d'optimisation de base pour l'entraînement de nombreux modèles d'apprentissage automatique, y compris les modèles de apprentissage profond tels que les transformeurs et les grands modèles de langage. Elle est utilisée pour entraîner les réseaux de neurones pour des tâches comme la reconnaissance d'images, le traitement du langage naturel et l'IA générative. Des variantes comme Adam et d'autres variantes de SGD ont été développées pour améliorer la convergence et la stabilité. Le choix du programme de taux d'apprentissage est crucial pour un entraînement efficace.

Défis et extensions

SGD est confronté à des défis tels que le choix d'un taux d'apprentissage approprié, la gestion des gradients bruités et l'évitement des minima locaux médiocres. Les extensions incluent l'élan, les taux d'apprentissage adaptatifs (par exemple, Adam), et des techniques comme le clipping de gradient pour empêcher les gradients explosifs. Dans l'apprentissage profond, des méthodes comme la normalisation par lots et le décrochage sont souvent utilisées en conjonction avec SGD pour améliorer l'entraînement.

Contexte historique

L'algorithme de Robbins–Monro des années 1950 a posé les fondations de l'approximation stochastique. Dans les années 1980 et 1990, SGD est devenu populaire dans l'entraînement des réseaux de neurones, en particulier avec la rétropropagation. Aujourd'hui, il reste un outil fondamental dans la recherche et l'industrie de l'intelligence artificielle, utilisé par les principaux laboratoires et entreprises d'IA.

Voir aussi

• descente de gradient (non listé, mais lié)
• fonctions de perte
• augmentation de données
• élagage de modèle