Comment la descente de gradient stochastique peut-elle éviter le problème d'un minimum local?

19

Je sais que la descente de gradient stochastique a un comportement aléatoire, mais je ne sais pas pourquoi.
Y a-t-il une explication à ce sujet?

SunshineAtNoon
la source
10
Qu'est-ce que votre question a à voir avec votre titre?
Neil G

Réponses:

22

L'algorithme de gradient stochastique (SG) se comporte comme un algorithme de recuit simulé (SA), où le taux d'apprentissage du SG est lié à la température de SA. Le caractère aléatoire ou le bruit introduit par SG permet d'échapper aux minima locaux pour atteindre un meilleur minimum. Bien sûr, cela dépend de la vitesse à laquelle vous diminuez le taux d'apprentissage. Lisez la section 4.2, de Stochastic Gradient Learning in Neural Networks (pdf) , où elle est expliquée plus en détail.

Clara
la source
4
Ne regardez pas aussi bien la section 4.1, où le deuxième théorème est pour un cas limité de fonctions non convexes, en disant qu'il converge uniquement (avec des échantillons infinis) vers un certain point avec un gradient 0. Ce peut ne pas être un minimum global ou peut même être un maximum . La SGD est plus intéressante pour des raisons plus pratiques telles que l'apprentissage distribué, pas sûrement qu'elle "évitera" le minimum local.
2

En descente de gradient stochastique, les paramètres sont estimés pour chaque observation, par opposition à l'ensemble de l'échantillon en descente de gradient régulière (descente de gradient par lots). C'est ce qui lui donne beaucoup d'aléatoire. Le chemin de la descente du gradient stochastique erre sur plus d'endroits, et est donc plus susceptible de «sauter» d'un minimum local et de trouver un minimum global (Remarque *). Cependant, la descente de gradient stochastique peut toujours rester bloquée dans le minimum local.

Remarque: Il est courant de maintenir le taux d'apprentissage constant, dans ce cas, la descente de gradient stochastique ne converge pas; il erre juste autour du même point. Cependant, si le taux d'apprentissage diminue avec le temps, par exemple, il est inversement lié au nombre d'itérations, la descente du gradient stochastique convergerait.

Akavall
la source
Il n'est pas vrai que la descente de gradient stochastique ne converge pas vraiment et se demande simplement autour d'un certain point. Ce serait le cas si le taux d'apprentissage était maintenu constant. Cependant, les taux d'apprentissage ont tendance à zéro car de cette manière, lorsque l'algorithme est proche du minimum d'une fonction convexe, il cesse d'osciller et converge. La clé de la preuve de convergence du gradient stochastique sont les conditions imposées à la série des taux d'apprentissage. Voir les équations (6) et (27) de l'article original de Robbins et Monro.
clara
2

Comme cela a déjà été mentionné dans les réponses précédentes, la descente de gradient stochastique a une surface d'erreur beaucoup plus bruyante puisque vous évaluez chaque échantillon de manière itérative. Pendant que vous faites un pas vers le minimum global dans la descente de gradient par lots à chaque époque (passez sur l'ensemble d'entraînement), les étapes individuelles de votre gradient de descente de gradient stochastique ne doivent pas toujours pointer vers le minimum global selon l'échantillon évalué.

Pour visualiser cela à l'aide d'un exemple en deux dimensions, voici quelques figures et dessins de la classe d'apprentissage automatique d'Andrew Ng.

Première descente de gradient:

entrez la description de l'image ici

Deuxièmement, la descente du gradient stochastique:

entrez la description de l'image ici

Le cercle rouge dans la figure inférieure illustrera que la descente de gradient stochastique "continuera à se mettre à jour" quelque part dans la zone autour du minimum global si vous utilisez un taux d'apprentissage constant.

Voici donc quelques conseils pratiques si vous utilisez la descente de gradient stochastique:

1) mélangez l'ensemble d'entraînement avant chaque époque (ou itération dans la variante "standard")

2) utiliser un taux d'apprentissage adaptatif pour "recuire" plus près du minimum global


la source
Pourquoi voudriez-vous mélanger l'ensemble d'entraînement avant chaque époque? L'algorithme de SGD sélectionne les exemples de formation au hasard.
Vladislavs Dovgalecs
Le brassage est essentiellement une façon de le faire choisir ces échantillons d'entraînement au hasard. Dans mes implémentations, je mélange généralement l'ensemble de formation avant chaque époque, puis je forfais une boucle dans l'ensemble mélangé
2
Hm, sur wikipedia, l'algorithme SGD est décrit comme "sans remplacement", cependant, Bottou le décrit comme vous l'avez fait (Bottou, Léon. "Apprentissage automatique à grande échelle avec descente de gradient stochastique". Actes de COMPSTAT'2010. Physica-Verlag HD, 2010. 177-186.), Et je pense qu'ici j'aurais plus confiance en Bottou qu'en cette entrée Wikipedia.
4
@xeon Consultez cet article , qui soutient que l'échantillonnage sans remplacement est préférable. Ma compréhension est que sans remplacement a tendance à être empiriquement supérieure, mais les analyses théoriques n'étaient disponibles que récemment.
Dougal
1
@xeon Je viens de regarder mes diapositives PDF du cours d'Andrew Ng, et il semble qu'il les ait décrites comme sur Wikipédia (la variante "sans remplacement") pas comme Bottou. J'ai téléchargé une capture d'écran ici