Descente de gradient par lots et descente de gradient stochastique

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, \dots, m$$h_{\theta}(x_{(i)}) = \theta_0+\theta_{1}x_{(i)1} + \cdots +\theta_{n}x_{(i)n}$$\mathbf{\theta}$$y_{(i)}$$h_{\theta}(x_{(i)})$

$$J(\theta) = \frac{1}{2} \sum_{i=1}^{m} (y_{(i)}-h_{\theta}(x_{(i)})^{2}$$

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

$$\theta_j := \theta_j-\alpha \frac{\partial}{\partial \theta_{j}} J(\theta)$$

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?

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.

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 . $p_{data}$$\hat{p}_{data}$

$$g = E_{p_{data}}({\partial J(\theta)\over \partial \theta})$$ 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({\hat{g}(n)}) \over SE({\hat{g}(m)})} = { \sqrt {m \over n}}$$ 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-lots$m$ $$E_{\hat{p}_{data}}(\hat{g}(m)) = E_{\hat{p}_{data}}({\partial J(\theta)\over \partial \theta})$$ $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".

2. 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.

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.$2^{10-1} = 512$