Descente graduelle - Gradient descent

Descente de dégradé en 2D

La descente de gradient est un algorithme d' optimisation itératif du premier ordre pour trouver un minimum local d'une fonction dérivable . L'idée est de faire des pas répétés dans la direction opposée du gradient (ou gradient approximatif) de la fonction au point actuel, car c'est la direction de la descente la plus raide. Inversement, marcher dans la direction du gradient conduira à un maximum local de cette fonction ; la procédure est alors connue sous le nom de montée en pente .

La descente de gradient est généralement attribuée à Cauchy , qui l'a suggérée pour la première fois en 1847. Hadamard a proposé indépendamment une méthode similaire en 1907. Ses propriétés de convergence pour les problèmes d'optimisation non linéaire ont été étudiées pour la première fois par Haskell Curry en 1944, la méthode devenant de plus en plus bien étudiée. et utilisé dans les décennies suivantes, aussi souvent appelé descente la plus raide.

La description

Illustration d'une descente de pente sur une série de level sets

La descente de gradient est basée sur l'observation que si la fonction multivariable est définie et dérivable au voisinage d'un point , alors elle décroît le plus rapidement si l'on va dans le sens du gradient négatif de à . Il s'ensuit que, si

pour un assez petit, alors . En d'autres termes, le terme est soustrait de car on veut aller à contre-courant, vers le minimum local. Avec cette observation à l'esprit, on part d'une estimation pour un minimum local de , et on considère la séquence telle que

On a une suite monotone

donc, espérons-le, la séquence converge vers le minimum local souhaité. Notez que la valeur de la taille du pas peut changer à chaque itération. Avec certaines hypothèses sur la fonction (par exemple, convexe et Lipschitz ) et des choix particuliers de (par exemple, choisi soit via une recherche de ligne qui satisfait les conditions de Wolfe , ou la méthode de Barzilai-Borwein montrée comme suit),

la convergence vers un minimum local peut être garantie. Lorsque la fonction est convexe , tous les minima locaux sont également des minima globaux, donc dans ce cas, la descente de gradient peut converger vers la solution globale.

Ce processus est illustré dans l'image ci-contre. Ici, on suppose défini sur le plan, et que son graphe a une forme de bol . Les courbes bleues sont les courbes de niveau , c'est-à-dire les régions sur lesquelles la valeur de est constante. Une flèche rouge partant d'un point indique la direction du gradient négatif à ce point. Notez que le gradient (négatif) en un point est orthogonal à la ligne de contour passant par ce point. On voit que la descente de gradient nous amène au fond du bol, c'est-à-dire jusqu'au point où la valeur de la fonction est minimale.

Une analogie pour comprendre la descente de gradient

Brouillard dans les montagnes

L'intuition de base derrière la descente de gradient peut être illustrée par un scénario hypothétique. Une personne est coincée dans les montagnes et essaie de descendre (c'est-à-dire d'essayer de trouver le minimum global). Il y a un épais brouillard si bien que la visibilité est extrêmement faible. Par conséquent, le chemin qui descend de la montagne n'est pas visible, ils doivent donc utiliser les informations locales pour trouver le minimum. Ils peuvent utiliser la méthode de descente en pente, qui consiste à examiner la pente de la colline à leur position actuelle, puis à continuer dans la direction de la descente la plus raide (c'est-à-dire la descente). S'ils essayaient de trouver le sommet de la montagne (c'est-à-dire le maximum), alors ils procéderaient dans la direction de l'ascension la plus raide (c'est-à-dire en montée). En utilisant cette méthode, ils finiraient par trouver leur chemin vers le bas de la montagne ou éventuellement rester coincés dans un trou (c'est-à-dire un minimum local ou un point de selle ), comme un lac de montagne. Cependant, supposons également que la pente de la colline n'est pas immédiatement évidente avec une simple observation, mais qu'elle nécessite plutôt un instrument sophistiqué pour mesurer, que la personne possède actuellement. Il faut un certain temps pour mesurer la pente de la colline avec l'instrument, ils devraient donc minimiser leur utilisation de l'instrument s'ils voulaient descendre de la montagne avant le coucher du soleil. La difficulté est alors de choisir la fréquence à laquelle ils doivent mesurer la pente de la pente pour ne pas sortir de la piste.

Dans cette analogie, la personne représente l'algorithme, et le chemin emprunté en bas de la montagne représente la séquence de réglages de paramètres que l'algorithme explorera. La pente de la colline représente la pente de la surface d'erreur à ce point. L'instrument utilisé pour mesurer la pente est la différenciation (la pente de la surface d'erreur peut être calculée en prenant la dérivée de la fonction d'erreur au carré en ce point). La direction dans laquelle ils choisissent de se déplacer s'aligne sur le gradient de la surface d'erreur à ce point. Le temps qu'ils parcourent avant de prendre une autre mesure est la taille du pas.

Exemples

La descente de gradient a des problèmes avec les fonctions pathologiques telles que la fonction de Rosenbrock illustrée ici.

La fonction Rosenbrock a une vallée incurvée étroite qui contient le minimum. Le fond de la vallée est très plat. En raison de la vallée plate incurvée, l'optimisation zigzague lentement avec de petites tailles de pas vers le minimum. Le Whiplash Gradient Descent résout ce problème en particulier.

Banana-SteepDesc.gif

La nature en zigzag de la méthode est également évidente ci-dessous, où la méthode de descente de gradient est appliquée à

L'algorithme de descente de gradient en action.  (1 : contour)L'algorithme de descente de gradient en action.  (2 : superficie)

Choix de la taille du pas et de la direction de descente

Étant donné que l'utilisation d'un pas trop petit ralentirait la convergence et qu'un pas trop grand entraînerait une divergence, trouver un bon réglage de est un problème pratique important. Philip Wolfe a également préconisé l'utilisation de « choix intelligents de la direction [de descente] » dans la pratique. Bien que l'utilisation d'une direction qui s'écarte de la direction de descente la plus raide puisse sembler contre-intuitive, l'idée est que la plus petite pente peut être compensée en étant soutenue sur une distance beaucoup plus longue.

Pour raisonner mathématiquement à ce sujet, utilisons une direction et une taille de pas et considérons la mise à jour plus générale :

.

Trouver de bons réglages de et nécessite un peu de réflexion. Tout d'abord, nous aimerions que la direction de mise à jour pointe vers la descente. Mathématiquement, en dénotant l'angle entre et , cela nécessite que Pour en dire plus, nous avons besoin de plus d'informations sur la fonction objectif que nous optimisons. Sous l'hypothèse assez faible qui est continûment dérivable, on peut prouver que :

 

 

 

 

( 1 )

Cette inégalité implique que la quantité dont nous pouvons être sûrs que la fonction est diminuée dépend d'un compromis entre les deux termes entre crochets. Le premier terme entre crochets mesure l'angle entre la direction de descente et la pente négative. Le deuxième terme mesure la vitesse à laquelle le gradient change le long de la direction de descente.

En principe, l'inégalité ( 1 ) pourrait être optimisée et choisir une taille et une direction de pas optimales. Le problème est que l'évaluation du deuxième terme entre crochets nécessite d'évaluer , et les évaluations de gradient supplémentaires sont généralement coûteuses et indésirables. Voici quelques moyens de contourner ce problème :

  • Renoncez aux avantages d'une direction de descente intelligente en définissant , et utilisez la recherche de ligne pour trouver une taille de pas appropriée , telle que celle qui satisfait les conditions de Wolfe .
  • En supposant qu'il soit deux fois différentiable, utilisez son Hessian pour estimer Puis choisir et en optimisant l'inégalité ( 1 ).
  • En supposant que ce soit Lipschitz , utilisez sa constante de Lipschitz pour borner Puis choisissez et en optimisant l'inégalité ( 1 ).
  • Construisez un modèle personnalisé de pour . Choisissez ensuite et en optimisant l'inégalité ( 1 ).
  • Sous des hypothèses plus fortes sur la fonction telles que la convexité , des techniques plus avancées peuvent être possibles.

Habituellement, en suivant l'une des recettes ci-dessus, la convergence vers un minimum local peut être garantie. Lorsque la fonction est convexe , tous les minima locaux sont également des minima globaux, donc dans ce cas, la descente de gradient peut converger vers la solution globale.

Solution d'un système linéaire

L'algorithme de descente le plus raide appliqué au filtre de Wiener

La descente de gradient peut être utilisée pour résoudre un système d'équations linéaires

reformulé comme un problème de minimisation quadratique. Si la matrice du système est réelle symétrique et définie positivement , une fonction objectif est définie comme la fonction quadratique, avec la minimisation de

pour que

Pour une matrice réelle générale , les moindres carrés linéaires définissent

Dans les moindres carrés linéaires traditionnels pour le réel et la norme euclidienne est utilisée, auquel cas

La minimisation de la recherche de ligne , trouvant la taille de pas localement optimale à chaque itération, peut être effectuée analytiquement pour les fonctions quadratiques, et des formules explicites pour la valeur localement optimale sont connues.

Par exemple, pour une matrice réelle symétrique et définie positivement , un algorithme simple peut être le suivant,

Pour éviter de multiplier par deux par itération, notons qu'implique , ce qui donne l'algorithme traditionnel,

La méthode est rarement utilisée pour résoudre des équations linéaires, la méthode du gradient conjugué étant l'une des alternatives les plus populaires. Le nombre d'itérations de descente de gradient est généralement proportionnel au nombre de conditions spectrales de la matrice du système (le rapport des valeurs propres maximales et minimales de ) , tandis que la convergence de la méthode du gradient conjugué est généralement déterminée par une racine carrée du nombre de conditions, c'est-à-dire , est beaucoup plus rapide. Les deux méthodes peuvent bénéficier du préconditionnement , où la descente de gradient peut nécessiter moins d'hypothèses sur le préconditionneur.

Solution d'un système non linéaire

La descente de gradient peut également être utilisée pour résoudre un système d' équations non linéaires . Vous trouverez ci-dessous un exemple qui montre comment utiliser la descente de gradient pour résoudre trois variables inconnues, x 1 , x 2 et x 3 . Cet exemple montre une itération de la descente de gradient.

Considérons le système d'équations non linéaire

Introduisons la fonction associée

On pourrait maintenant définir la fonction objectif

que nous tenterons de minimiser. Comme première estimation, utilisons

Nous savons que

où la matrice Jacobienne est donnée par

On calcule :

Ainsi

et

Une animation montrant les 83 premières itérations de descente de gradient appliquées à cet exemple. Les surfaces sont les isosurfaces de l'estimation actuelle et les flèches indiquent la direction de la descente. En raison d'une taille de pas petite et constante, la convergence est lente.

Maintenant, il faut trouver un convenable tel que

Cela peut être fait avec n'importe lequel d'une variété d' algorithmes de recherche de ligne . On pourrait aussi simplement deviner ce qui donne

En évaluant la fonction objectif à cette valeur, on obtient

La diminution de la valeur de l'étape suivante de

est une diminution importante de la fonction objectif. D'autres étapes réduiraient encore sa valeur, jusqu'à ce qu'une solution approximative au système soit trouvée.

commentaires

La descente de gradient fonctionne dans des espaces de n'importe quel nombre de dimensions, même dans des dimensions infinies. Dans ce dernier cas, l'espace de recherche est typiquement un espace de fonction , et on calcule la dérivée de Fréchet de la fonctionnelle à minimiser pour déterminer la direction de descente.

Cette descente de gradient fonctionne dans un nombre quelconque de dimensions (au moins un nombre fini) peut être considérée comme une conséquence de l' inégalité de Cauchy-Schwarz . Cet article prouve que la grandeur du produit interne (point) de deux vecteurs de n'importe quelle dimension est maximisée lorsqu'ils sont colinéaires. Dans le cas d'une descente de gradient, ce serait lorsque le vecteur d'ajustements de variables indépendantes est proportionnel au vecteur de gradient des dérivées partielles.

La descente de gradient peut prendre de nombreuses itérations pour calculer un minimum local avec une précision requise , si la courbure dans différentes directions est très différente pour la fonction donnée. Pour de telles fonctions, le préconditionnement , qui modifie la géométrie de l'espace pour former les ensembles de niveaux de fonction comme des cercles concentriques , guérit la lente convergence. Cependant, la construction et l'application du préconditionnement peuvent être coûteuses en temps de calcul.

La descente de gradient peut être combinée avec une recherche de ligne , trouvant la taille de pas localement optimale à chaque itération. La recherche de ligne peut prendre beaucoup de temps. Inversement, l'utilisation d'un petit fixe peut donner une mauvaise convergence.

Les méthodes basées sur la méthode de Newton et l'inversion de la Hesse utilisant des techniques de gradient conjugué peuvent être de meilleures alternatives. Généralement, ces méthodes convergent en moins d'itérations, mais le coût de chaque itération est plus élevé. Un exemple est la méthode BFGS qui consiste à calculer à chaque pas une matrice par laquelle le vecteur gradient est multiplié pour aller dans une « meilleure » direction, combinée à un algorithme de recherche de ligne plus sophistiqué , pour trouver la « meilleure » valeur de For extrêmement gros problèmes, où les problèmes de mémoire informatique dominent, une méthode à mémoire limitée telle que L-BFGS doit être utilisée au lieu de BFGS ou de la descente la plus raide.

La descente de gradient peut être considérée comme l'application de la méthode d' Euler pour résoudre les équations différentielles ordinaires à un flux de gradient . À son tour, cette équation peut être dérivée comme un contrôleur optimal pour le système de contrôle avec donné sous forme de rétroaction .

Modifications

La descente de gradient peut converger vers un minimum local et ralentir au voisinage d'un point col . Même pour une minimisation quadratique sans contrainte, la descente de gradient développe un motif en zigzag d'itérations ultérieures au fur et à mesure que les itérations progressent, ce qui entraîne une convergence lente. De multiples modifications de la descente de gradient ont été proposées pour remédier à ces lacunes.

Méthodes de gradient rapide

Yurii Nesterov a proposé une modification simple qui permet une convergence plus rapide pour les problèmes convexes et a depuis été généralisée. Pour les problèmes lisses sans contraintes, la méthode est appelée méthode du gradient rapide (FGM) ou méthode du gradient accéléré (AGM). Plus précisément, si la fonction dérivable est convexe et est Lipschitz , et qu'il n'est pas supposé qu'elle est fortement convexe , alors l'erreur dans la valeur objectif générée à chaque étape par la méthode de descente de gradient sera limitée par . En utilisant la technique d'accélération Nesterov, l'erreur diminue à . On sait que le taux de décroissance de la fonction de coût est optimal pour les méthodes d'optimisation du premier ordre. Néanmoins, il est possible d'améliorer l'algorithme en réduisant le facteur constant. La méthode du gradient optimisé (OGM) réduit cette constante d'un facteur de deux et est une méthode optimale du premier ordre pour les problèmes à grande échelle.

Pour les problèmes contraints ou non lisses, la FGM de Nesterov est appelée la méthode du gradient proximal rapide (FPGM), une accélération de la méthode du gradient proximal .

Momentum ou méthode de la balle lourde

En essayant de briser le motif en zigzag de la descente de gradient, la méthode de la quantité de mouvement ou de la balle lourde utilise un terme de quantité de mouvement par analogie à une balle lourde glissant sur la surface des valeurs de la fonction minimisée, ou au mouvement de masse dans la dynamique newtonienne à travers un fluide visqueux. moyen dans un champ de force conservateur. La descente de gradient avec élan mémorise la mise à jour de la solution à chaque itération et détermine la prochaine mise à jour en tant que combinaison linéaire du gradient et de la mise à jour précédente. Pour la minimisation quadratique sans contrainte, une borne de taux de convergence théorique de la méthode de la boule lourde est asymptotiquement la même que celle de la méthode du gradient conjugué optimal .

Cette technique est utilisée dans la descente de gradient stochastique#Momentum et comme une extension des algorithmes de rétropropagation utilisés pour entraîner les réseaux de neurones artificiels .

Rallonges

La descente de gradient peut être étendue pour gérer les contraintes en incluant une projection sur l'ensemble de contraintes. Cette méthode n'est réalisable que lorsque la projection est efficacement calculable sur ordinateur. Sous des hypothèses appropriées, cette méthode converge. Cette méthode est un cas particulier de l' algorithme forward-backward pour les inclusions monotones (qui inclut la programmation convexe et les inégalités variationnelles ).

Voir également

Les références

Lectures complémentaires

Liens externes

arxiv.org/2108.1283