Étant donné une fonction de coût convexe, en utilisant SGD pour l'optimisation, nous aurons un gradient (vecteur) à un certain point au cours du processus d'optimisation.
Ma question est, étant donné le point sur le convexe, le gradient ne pointe-t-il que vers la direction dans laquelle la fonction augmente / diminue le plus rapidement, ou le gradient pointe toujours vers le point optimal / extrême de la fonction de coût ?
Le premier est un concept local, le second est un concept global.
SGD peut finalement converger vers la valeur extrême de la fonction de coût. Je m'interroge sur la différence entre la direction du gradient étant donné un point arbitraire sur le convexe et la direction pointant vers la valeur extrême globale.
La direction du gradient doit être la direction à laquelle la fonction augmente / diminue le plus rapidement sur ce point, non?
la source
Réponses:
Ils disent qu'une image vaut plus que mille mots. Dans l'exemple suivant (gracieuseté de MS Paint, un outil pratique pour les statisticiens amateurs et professionnels), vous pouvez voir une surface de fonction convexe et un point où la direction de la descente la plus raide diffère clairement de la direction vers l'optimum.
Sur une note sérieuse: il y a des réponses bien supérieures dans ce fil qui méritent également un vote positif.
la source
Une vue intuitive consiste à imaginer un chemin de descente qui est un chemin courbe. Voir par exemple les exemples ci-dessous.
Par analogie: Imaginez que je vous bandes les yeux et que je vous mette quelque part sur une montagne avec la tâche de revenir au point extrême (bas). Sur la colline, si vous ne disposez que d' informations locales , vous ne savez pas dans quelle direction se trouvera le fond du lac.
Si vous pouvez assumer la convexité
Sans convexité
Dans le problème convexe, cela n'est pas possible. Vous pouvez relier cela aux isolignes pour la fonction de coût ayant une courbure dans la même direction lorsque le problème est convexe.
En descente de gradient stochastique
Voici une autre vue pour quatre points de données . Chacune des quatre images montre la surface d'un point unique différent. À chaque étape, un point différent est choisi le long duquel le gradient est calculé. Cela fait qu'il n'y a que quatre directions le long desquelles une étape est effectuée, mais les tailles de pas diminuent lorsque nous nous rapprochons de la solution.
Les images ci-dessus concernent 4 points de données générés par la fonction:
ce qui se traduit par:
Écrit par StackExchangeStrike
la source
La descente la plus abrupte peut être inefficace même si la fonction objectif est fortement convexe.
Descente en pente ordinaire
Je veux dire "inefficace" dans le sens où la descente la plus raide peut prendre des mesures qui oscillent énormément loin de l'optimum, même si la fonction est fortement convexe ou même quadratique.
qui présente cette progression follement oscillante vers le minimum.
Le chemin direct vers le minimum serait de se déplacer "en diagonale" plutôt que de cette façon qui est fortement dominée par les oscillations verticales. Cependant, la descente de gradient ne possède que des informations sur la pente locale, donc elle "ne sait pas" que la stratégie serait plus efficace, et elle est soumise aux caprices de la Hesse ayant des valeurs propres à différentes échelles.
Descente de gradient stochastique
SGD a les mêmes propriétés, à l'exception du fait que les mises à jour sont bruyantes, ce qui implique que la surface du contour est différente d'une itération à l'autre, et donc les gradients sont également différents. Cela implique que l'angle entre la direction du pas de gradient et l'optimum aura également du bruit - imaginez les mêmes tracés avec un peu de gigue.
Plus d'information:
Peut-on appliquer l'analyticité d'un réseau neuronal pour améliorer la descente de gradient?
Pourquoi les dérivés du second ordre sont-ils utiles dans l'optimisation convexe?
Comment un changement dans la fonction de coût peut-il être positif?
Cette réponse emprunte cet exemple et cette figure au Neural Networks Design (2nd Ed.) Chapter 9 de Martin T. Hagan, Howard B. Demuth, Mark Hudson Beale, Orlando De Jesús.
la source
La direction locale la plus raide n'est pas la même que la direction optimale globale. Si c'était le cas, alors la direction de votre gradient ne changerait pas; car si vous allez toujours vers votre optimum, votre vecteur de direction pointera toujours vers l'optimum. Mais ce n'est pas le cas. Si c'était le cas, pourquoi se donner la peine de calculer votre gradient à chaque itération?
la source
Les autres réponses mettent en évidence des problèmes de taux de convergence gênants pour GD / SGD, mais votre commentaire "SGD peut éventuellement converger ..." n'est pas toujours correct (en ignorant les remarques pédantes sur le mot "peut" car il semble que vous vouliez dire "volonté").
Je ne sais pas si la convexité est suffisante pour briser un comportement pire qui existe pour SGD général, mais si vous autorisez des fonctions aussi complexes que cubiques pour votre fonction de coût, alors SGD peut rebondir sur un sous-ensemble dense du domaine et ne jamais converger nulle part ou approcher n'importe quel cycle.
Une chose intéressante à propos de l'ensemble de la situation est qu'il existe un nombre incalculable de fonctions (comme SGD) qui prennent des fonctions convexes arbitraires en entrée puis émettent une règle de mise à jour qui converge toujours rapidement vers le minimum global (s'il en existe une). Même s'il existe conceptuellement beaucoup d'entre eux, nos meilleures tentatives d'optimisation convexe ont toutes des contre-exemples pathologiques. D'une certaine manière, l'idée d'une règle de mise à jour simple / intuitive / performante va à l'encontre de l'idée d'une règle de mise à jour prouvée correcte.
la source
Peut-être que les réponses à cette question nécessitent une mise à jour rapide. Il semble que SGD donne un minimum global également dans le cas non convexe (convexe est juste un cas spécial de cela):
Les auteurs établissent la convergence de SGD à un minimum global pour les problèmes d'optimisation non convexes qui sont couramment rencontrés dans la formation des réseaux de neurones. L'argument exploite les deux propriétés importantes suivantes: 1) la perte d'entraînement peut atteindre une valeur nulle (approximativement); 2) SGD suit un chemin convexe en étoile. Dans un tel contexte, bien que SGD ait longtemps été considéré comme un algorithme randomisé, l'article révèle qu'il converge de manière intrinsèquement déterministe vers un minimum global.
Cela devrait être pris avec un grain de sel. Le document est toujours en cours d'examen.
La notion de trajectoire convexe en étoile donne une indication sur l'endroit où le gradient pointe à chaque itération.
la source