Descente de gradient par lots et descente de gradient stochastique

101

Supposons que nous ayons un ensemble d’entraînement pour . Supposons également que nous exécutions un type d'algorithme d'apprentissage supervisé sur l'ensemble d'apprentissage. Les hypothèses sont représentées par . Nous devons trouver les paramètres qui minimisent la "distance" entre et . Soit(x(i),y(i))i=1,,mhθ(x(i))=θ0+θ1x(i)1++θnx(i)nθy(i)hθ(x(i))

J(θ)=12i=1m(y(i)hθ(x(i))2

Ensuite, nous voulons trouver qui minimise . En descente en gradient, nous initialisons chaque paramètre et effectuons la mise à jour suivante:θJ(θ)

θj:=θjαθjJ(θ)

Quelle est la principale différence entre la descente en gradient par lots et la descente en gradient stochastique?

Les deux utilisent la règle de mise à jour ci-dessus. Mais l'un est-il meilleur que l'autre?

utilisateur20616
la source

Réponses:

121

L’applicabilité de la descente de gradient ou de gradient stochastique dépend vraiment de la variété d’erreurs attendue.

La descente en dégradé par lots calcule le dégradé en utilisant l'ensemble de données. C'est excellent pour les variétés d'erreur convexes ou relativement lisses. Dans ce cas, nous nous dirigeons directement vers une solution optimale, locale ou globale. De plus, la descente en gradient de lots, avec un taux d’apprentissage recuit, finira par trouver le minimum situé dans son bassin d’attraction.

La descente de gradient stochastique (SGD) calcule le gradient en utilisant un seul échantillon. La plupart des applications de SGD utilisent en réalité un minibatch de plusieurs échantillons, pour des raisons qui seront expliquées un peu plus tard. SGD fonctionne bien (pas bien, je suppose, mais mieux que la descente en gradient par lots) pour les variétés d'erreur qui ont beaucoup de maxima / minima locaux. Dans ce cas, le gradient un peu plus bruyant calculé en utilisant le nombre réduit d’échantillons tend à faire sortir le modèle des minima locaux dans une région qui, espérons-le, est plus optimale. Les échantillons simples sont vraiment bruyants, alors que les minibatchs ont tendance à minimiser un peu le bruit. Ainsi, la quantité de jerk est réduite lors de l’utilisation de miniatures. Un bon équilibre est atteint lorsque la taille du mini-lot est suffisamment petite pour éviter certains des minima locaux médiocres, mais suffisamment grande pour ne pas t éviter les minima globaux ou les minima locaux les plus performants. (Incidemment, cela suppose que les meilleurs minima ont un bassin d’attraction plus grand et plus profond et qu’il est donc plus facile d’y entrer.)

L'un des avantages de SGD est qu'il est beaucoup plus rapide sur le plan informatique. Les grands ensembles de données ne peuvent souvent pas être conservés dans la RAM, ce qui rend la vectorisation beaucoup moins efficace. Au lieu de cela, chaque échantillon ou lot d’échantillons doit être chargé, traité, les résultats stockés, etc. Le minibatch SGD, en revanche, est généralement intentionnellement suffisamment petit pour pouvoir être traité par ordinateur.

Habituellement, cet avantage de calcul est exploité en effectuant beaucoup plus d'itérations de SGD, ce qui fait beaucoup plus d'étapes que la descente en gradient par lots conventionnelle. Il en résulte généralement un modèle très proche de celui qui serait trouvé via une descente en gradient par lots ou mieux.

J'aime penser au fonctionnement de SGD, c'est imaginer que j'ai un point qui représente la distribution de mes entrées. Mon modèle tente d'apprendre cette distribution d'entrée. La zone d'entrée est entourée d'une zone ombrée qui représente les distributions d'entrée de tous les mini-lots possibles que j'ai pu échantillonner. On suppose généralement que les distributions d’entrée de minibatch sont proches de la distribution d’entrée réelle. La descente de gradient par lots, à toutes les étapes, emprunte la route la plus raide pour atteindre la vraie distribution d’entrée. SGD, en revanche, choisit un point au hasard dans la zone ombrée et emprunte la route la plus raide vers ce point. À chaque itération, cependant, il choisit un nouveau point. La moyenne de toutes ces étapes correspondra approximativement à la vraie distribution des entrées, généralement très bien.

Jason_L_Bens
la source
13
En pratique, personne n’utilise Batch Gradient Descent. C'est tout simplement trop coûteux en calcul pour ne pas gagner autant. (Le gain étant que vous réduisez réellement le "vrai" gradient.) Lorsque vous utilisez une fonction de perte hautement non convexe, il vous suffit de marcher dans la bonne direction et vous finirez par converger vers un minimum local. Ainsi, minibatch SGD.
Sabalaba
@Jason_L_Bens avez-vous des références (articles ou textes en ligne) où je peux en savoir plus sur ces algorithmes?
user110320
1
@ user110320 Pas par hasard, non, bien qu'il s'agisse d'algorithmes très courants. Il devrait donc y avoir une tonne de ressources disponibles sur le sujet avec un peu de recherche. Si vous recherchez une approche générale, je vous conseillerais de lire quelques-unes des architectures d'apprentissage approfondies de Yoshua Bengio pour l'IA. C'est là que j'ai commencé.
Jason_L_Bens
6

Comme l’indique une autre réponse, la raison principale d’utiliser SGD est de réduire le coût de calcul du gradient tout en maintenant en grande partie la direction du gradient lorsqu’une moyenne est calculée sur plusieurs mini-lots ou échantillons, ce qui contribue certainement à vous ramener aux minima locaux.

  1. Pourquoi le minibatch fonctionne-t-il ?

La mathématique derrière cela est que le "vrai" gradient de la fonction de coût (le gradient pour l'erreur de généralisation ou pour un ensemble d'échantillons infiniment grand) est l'attente du gradient sur la distribution générant les données vraies ; le gradient réel calculé sur un lot d'échantillons est toujours une approximation du gradient réel avec la distribution de données empiriques . pdatap^data

g=Epdata(J(θ)θ)
La descente de gradient par lots peut vous apporter le possible gradient "optimal" étant donné tous vos échantillons de données. Ce n'est toutefois pas le "vrai" gradient. Un lot plus petit (minibatch) n'est probablement pas aussi optimal que le lot complet, mais il s'agit d'approximations; il en va de même pour le minibatch à échantillon unique (SGD). La différence entre leurs erreurs-types est inversement proportionnelle à la taille du minibatch. Autrement dit,
SE(g^(n))SE(g^(m))=mn
En d'autres termes, la réduction de l'erreur type est la racine carrée de l'augmentation de la taille de l'échantillon. L'équation ci-dessus concerne les gradients calculés en une étape de la descente du gradient du minibatch. Lorsque vous parcourez les étapes des mises à jour de gradients de minibatch et utilisez tous les échantillons d'apprentissage à la fin d'une même époque, vous calculez virtuellement la moyenne des gradients en fonction de tous les échantillons donnés. C'est-à-dire que, pour la taille du mini-lot , À partir des équations ci-dessus, nous pouvons conclure que, avec une époque, vos gradients moyennés avec différentes tailles de mini-lotsm
Ep^data(g^(m))=Ep^data(J(θ)θ)
m (de l’un au lot complet) ont la même erreur type et, ce qui est plus important encore, ce sont toutes des approximations fidèles du gradient "vrai", c’est-à-dire qu’ils se déplacent dans la bonne direction du gradient "vrai".
  1. Pourquoi un minibatch peut-il mieux fonctionner ?

Tout d’abord, le minibatch permet de résoudre certains problèmes d’apprentissage techniquement impossibles à attaquer en raison de la réduction de la demande de calcul avec une taille de lot inférieure.

Deuxièmement, une taille de lot réduite ne signifie pas nécessairement une précision de gradient réduite. Les échantillons d'apprentissage ont souvent beaucoup de bruits, de valeurs aberrantes ou de préjugés. Un mini-lot échantillonné de manière aléatoire peut refléter la distribution générant les données réelles mieux (ou pas pire) que le lot complet original. Si certaines itérations des mises à jour du gradient du mini-lot vous donnent une meilleure estimation, globalement, le résultat moyen d'une époque peut être supérieur au gradient calculé à partir d'un lot complet.

Troisièmement, le minibatch ne permet pas seulement de traiter des échantillons de données déplaisants, mais également de gérer une fonction de coût déplaisante comportant de nombreux minima locaux. Comme le mentionne Jason_L_Bens, il est parfois plus facile pour les variétés d'erreur de piéger un dégradé régulier dans des minima locaux, alors qu'il est plus difficile de piéger le dégradé temporairement aléatoire calculé avec minibatch.

Enfin, avec la descente de gradient, vous n'atteignez pas les minima globaux en une étape, mais vous effectuez une itération sur la variété erro. Gradient ne vous donne en grande partie que la direction à parcourir. Avec un minibatch, vous pouvez itérer beaucoup plus rapidement. Dans de nombreux cas, plus il y a d'itérations, meilleur est le point que vous pouvez atteindre. Vous ne vous souciez pas vraiment du tout, le point est optimal globalement ou même localement. Vous voulez juste atteindre un modèle raisonnable qui vous apporte une erreur de généralisation acceptable. Minibatch facilite les choses.

Vous pouvez trouver que le livre "Deep learning" de Ian Goodfellow, et autres, a de très bonnes discussions sur ce sujet si vous le lisez attentivement.

Xiao-Feng Li
la source
Pour les problèmes d'optimisation convexes, ce que vous avez dit est correct. Toutefois, pour utiliser des méthodes de gradient sur des fonctions non convexes, vous avez oublié une raison très critique pour laquelle SGD est meilleur que le traitement par lots. Voir ma réponse datascience.stackexchange.com/questions/16807/…
horaceT
@horaceT Merci pour votre commentaire. Étant donné que Jason_L_Bens a décrit le point que vous avez mentionné ci-dessus avec des détails, je n'ai pas pris la peine de le répéter, mais en renvoyant sa réponse au dernier troisième paragraphe, avec tout le respect que je vous dois. En ce qui concerne l’optimisation de la descente en pente, le non-convexe est reflété par les minima locaux, y compris le point de selle (voir le dernier troisième paragraphe); et dans un souci de description, ma réponse décrit SGD comme un minibatch mais avec une taille de lot de 1 (voir le troisième paragraphe).
Xiao-Feng Li
3

Pour moi, le dégradé de lot ressemble au dégradé maigre. Dans un dégradé pauvre, la taille du lot est choisie de sorte que chaque paramètre devant être mis à jour varie également de manière indépendante, mais pas nécessairement orthogonalement, dans le lot. Par exemple, si le lot contient 10 expériences, 10 lignes, il est possible de former colonnes indépendantes. 10 lignes permettent la mise à jour indépendante, mais non orthogonale, de 512 paramètres.2101=512

Sven Ahlinder
la source