Comment peut-il être piégé dans une pointe de selle?

14

Je suis actuellement un peu perplexe sur la façon dont la descente en gradient en mini-lot peut être piégée dans un point de selle.

La solution est peut-être trop insignifiante pour ne pas l’obtenir.

Vous obtenez un nouvel échantillon à chaque époque, et il calcule une nouvelle erreur en fonction d'un nouveau lot, de sorte que la fonction de coût est uniquement statique pour chaque lot, ce qui signifie que le gradient doit également changer pour chaque mini-lot .. mais en fonction de cela, cela devrait une implémentation vanilla a des problèmes avec les points de selle?

Un autre défi clé de la minimisation des fonctions d'erreur hautement non convexes communes aux réseaux de neurones est d'éviter d'être piégé dans leurs nombreux minima locaux sous-optimaux. Dauphin et al. [19] soutiennent que la difficulté ne vient en fait pas des minima locaux mais des points de selle, c'est-à-dire des points où une dimension s'incline vers le haut et une autre vers le bas. Ces points de selle sont généralement entourés d'un plateau de la même erreur, ce qui rend notoirement difficile pour SGD de s'échapper, car le gradient est proche de zéro dans toutes les dimensions.

Je voudrais dire que SGD en particulier aurait un avantage clair contre les points de selle, car il fluctue vers sa convergence ... Les fluctuations et l'échantillonnage aléatoire, et la fonction de coût étant différente pour chaque époque devraient être des raisons suffisantes pour ne pas être piégés dans une seule.

Pour un gradient de lot complet décent, il est logique qu'il puisse être piégé au point de selle, car la fonction d'erreur est constante.

Je suis un peu confus sur les deux autres parties.

Fixining_ranges
la source
1
Moti comprend. Le point de selle aux pentes très hautes et entouré de pentes nulles lance une descente en pente à grands pas vers "les badlands" dont il ne peut se remettre. Pensez à chercher un puits sur une plaine essentiellement plate. Pensez maintenant au puits comme au sec et avec une fourmilière au centre. Une descente en pente qui atterrit sur la fourmilière, mais pas au sommet exact, va lancer la recherche radialement. Imaginez maintenant que le pas de la recherche est mille fois plus grand que le diamètre du puits. Si jamais la recherche trouve le puits, la fourmilière le pousse vers la montana
EngrStudent - Reinstate Monica
Je ne comprends pas ce que vous demandez. Êtes-vous confus pourquoi SGD ne peut pas être piégé dans la selle à cause du bruit hérité que SGD a, donc selon vous, il devrait pouvoir s'échapper? (contrairement à s'il s'agissait d'un batch complet GD, alors si le gradient est nul et sans bruit, il ne peut pas s'échapper, c'est ce que vous demandez?)
Pinocchio

Réponses:

16

Jetez un œil à l'image ci-dessous de Off Convex . Dans une fonction convexe (image la plus à gauche), il n'y a qu'un minimum local, qui est aussi le minimum global. Mais dans une fonction non convexe (image la plus à droite), il peut y avoir plusieurs minima locaux et joindre souvent deux minima locaux est un point de selle. Si vous vous approchez d'un point plus élevé, le gradient est relativement plus plat et vous risquez de vous y coincer, surtout si vous vous déplacez uniquement dans une direction.

Représentation schématique d'un point de selle

Maintenant, la chose est de savoir si vous optimisez à l'aide de mini-batchou descente de gradient stochastique, la fonction non convexe sous-jacente est la même et le gradient est une propriété de cette fonction. Lorsque vous effectuez un mini-batch, vous considérez de nombreux échantillons à la fois et effectuez la moyenne du pas de gradient sur chacun d'eux. Cela réduit la variance. Mais si la direction moyenne du gradient pointe toujours dans la même direction que le point de selle, vous risquez toujours de vous y coincer. L'analogie est que si vous faites 2 pas en avant et 1 pas en arrière, en moyenne par rapport à ceux-ci, vous finissez par faire un pas en avant. Si vous effectuez SGD à la place, vous effectuez toutes les étapes l'une après l'autre, mais si vous vous déplacez toujours dans une seule direction, vous pouvez atteindre le point de selle et constater que le dégradé de tous les côtés est assez plat et la taille de l'étape est trop petit pour passer sur cette partie plate. Ça ne marche pas

Jetez un œil à la visualisation ici . Même avec SGD, si les fluctuations ne se produisent que le long d'une seule dimension, les étapes devenant de plus en plus petites, elles convergeraient au point de selle. Dans ce cas, la méthode du mini-lot réduirait simplement la quantité de fluctuation mais ne serait pas en mesure de changer la direction du gradient.

La SGD peut parfois se détacher de simples points de selle, si les fluctuations sont dans d'autres directions et si la taille du pas est suffisamment grande pour qu'elle dépasse la planéité. Mais parfois, les régions de selle peuvent être assez complexes, comme dans l'image ci-dessous.

Régions de selle complexes

La façon dont les méthodes comme l'élan, ADAGRAD, Adam, etc. sont capables de sortir de cela, est de considérer les gradients passés. Considérez l'élan,

vt=γvt1+ηthetaJ(θ)

vt1

Antimoine
la source
Enfin, pas exactement! Pour une réponse dans la pratique, voir: stats.stackexchange.com/a/284399/117305
alifornia
@AliAbbasinasab Je pense que Antimony explique bien. Bien sûr, rester coincé dans une pointe de selle ordinaire n'est guère comme vous le mentionnez dans votre réponse, mais il a juste montré la possibilité que le SGD puisse être attrapé. Et pour moi, il vient de montrer des points de selle inhabituels auxquels SGD ne peut pas échapper.
Kazuya Tomita
2

Ça ne devrait pas.

[ 1 ] a montré que la descente de gradient avec une initialisation aléatoire et une taille de pas constante appropriée ne converge pas vers un point de selle. C'est une longue discussion mais pour vous donner une idée de pourquoi voir l'exemple suivant:

f(x,y)=12x2+14y412y2

entrez la description de l'image ici

z1=[00],z2=[01],z3=[01]

z2z3z1

z0=[x0]z1z1xR2

2f(x,y)=[1003y21]

2f(z1)xxz1

Californie
la source
Vous pourriez tout aussi facilement choisir une fonction de contre-exemple où vous serez coincé dans une pointe de selle à chaque fois ...
Jan Kukacka
1
Je n'ai pas pu accéder à votre lien [1] - pourriez-vous fournir une citation complète? En attendant, il est possible de construire des contre-exemples à votre réclamation, indiquant qu'elle doit être basée sur des hypothèses supplémentaires non déclarées.
whuber
@whuber, vous pouvez facilement préparer des contre-exemples. Par exemple, si vous n'avez qu'une ligne comme espace. J'ai juste essayé d'ajouter un point qui peut ne pas être évident pour beaucoup (ce n'était pas trop évident au départ pourquoi). À propos de la référence, je n'ai aucune idée pourquoi vous ne pouvez pas l'atteindre. J'ai revérifié, le lien est valide et je suis également mis à jour. Vous pouvez rechercher "Gradient Descent Converges to Minimizers, Jason D. Lee, Max Simchowitz, Michael I. Jordan † et Benjamin Recht † ♯Department of Electrical Engineering and Computer Sciences † Department of Statistcs University of California, Berkeley, 19 avril 2019 "
alifornia
Merci pour la référence. Un rapide coup d'œil (le lien fonctionne maintenant) montre que l'analyse est limitée aux "selles strictes" (où il y a des valeurs propres positives et négatives de la Hesse), ce qui exclut de nombreuses possibilités. Les déclarations finales de l'article comprennent "nous notons qu'il existe des problèmes d'optimisation sans contrainte très difficiles où la condition de selle stricte échoue" et ils offrent une minimisation quartique à titre d'exemple.
whuber
0

Si vous consultez le document référencé (ils montrent également avec emphase comment leur approche sans selle améliore effectivement le SGD en mini-lot), ils déclarent:

Un pas de la méthode de descente en gradient pointe toujours dans la bonne direction près d'un point de selle ... et donc de petits pas sont faits dans des directions correspondant à des valeurs propres de petite valeur absolue.

Ils notent également la présence de "plateaux" à proximité des points de selle (en d'autres termes, la selle n'est pas raide) - dans ces cas, des pas trop petits entraîneraient en effet une convergence prématurée avant d'avoir échappé à la zone de selle. Puisqu'il s'agit d'une optimisation non convexe, la convergence du taux d'apprentissage aggraverait la situation.

Il semble possible que l'on puisse essayer une approche itérative, où l'on redémarre le mini-SGD une fois qu'il est terminé (c'est-à-dire, réinitialiser le taux d'apprentissage) pour voir si l'on peut échapper à la région problématique.

MotiN
la source
0

Je pense que le problème est que lorsque vous approchez d'un point de selle, vous entrez dans un plateau, c'est-à-dire une zone avec de faibles gradients (en valeur absolue). Surtout lorsque vous approchez de la crête. Votre algorithme diminue donc la taille du pas. Avec une taille de pas réduite, tous les gradients (dans toutes les directions) sont désormais de petite valeur absolue. Donc l'algorithme s'arrête, pensant qu'il est au minimum.

Si vous ne diminuez pas les étapes, vous dépasserez le minimum et les manquerez beaucoup. Vous devez en quelque sorte diminuer la taille du pas.

Aksakal presque sûrement binaire
la source