La descente de gradient standard calculerait le gradient pour l'ensemble des données d'apprentissage.
for i in range(nb_epochs):
params_grad = evaluate_gradient(loss_function, data, params)
params = params - learning_rate * params_grad
Pour un nombre prédéfini d'époques, nous calculons d'abord le vecteur de gradient weights_grad de la fonction de perte pour l'ensemble de données par rapport à nos paramètres de vecteur de paramètres.
La descente de gradient stochastique, en revanche, effectue une mise à jour des paramètres pour chaque exemple d'apprentissage x (i) et étiquette y (i).
for i in range(nb_epochs):
np.random.shuffle(data)
for example in data:
params_grad = evaluate_gradient(loss_function, example, params)
params = params - learning_rate * params_grad
SGD serait beaucoup plus rapide. Cependant, je ne comprends pas comment cela peut être beaucoup plus rapide si nous avons encore une boucle sur tous les points de données. Le calcul du gradient dans GD est-il beaucoup plus lent que le calcul de GD pour chaque point de données séparément?
Le code vient d' ici .
Réponses:
Réponse courte:
Longue réponse:
Ma notation suit le cours Coursera d'apprentissage automatique d'Andrew NG. Si vous ne le connaissez pas, vous pouvez consulter la série de conférences ici .
Supposons une régression sur la perte au carré, la fonction de coût est
et le gradient est
pour un gradient décent (GD), nous mettons à jour le paramètre en
Voici pourquoi nous gagnons du temps:
Supposons que nous ayons 1 milliard de points de données.
Dans GD, afin de mettre à jour les paramètres une fois, nous devons avoir le gradient (exact). Cela nécessite de résumer ces 1 milliard de points de données pour effectuer 1 mise à jour.
Dans SGD, nous pouvons penser qu'il essaie d'obtenir un gradient approximatif au lieu d'un gradient exact . L'approximation provient d'un point de données (ou de plusieurs points de données appelés mini-lots). Par conséquent, dans SGD, nous pouvons mettre à jour les paramètres très rapidement. De plus, si nous "bouclons" sur toutes les données (appelées une époque), nous avons en fait 1 milliard de mises à jour.
L'astuce est que, dans SGD, vous n'avez pas besoin d'avoir 1 milliard d'itérations / mises à jour, mais beaucoup moins d'itérations / mises à jour, disons 1 million, et vous aurez un modèle "assez bon" à utiliser.
J'écris un code pour démo l'idée. Nous résolvons d'abord le système linéaire par une équation normale, puis le résolvons avec SGD. Ensuite, nous comparons les résultats en termes de valeurs de paramètres et de valeurs de fonctions objectives finales. Afin de le visualiser plus tard, nous aurons 2 paramètres à régler.
Les resultats:
Voici les valeurs de la fonction de coût sur les itérations, nous pouvons voir qu'elle peut effectivement réduire la perte, ce qui illustre l'idée: nous pouvons utiliser un sous-ensemble de données pour approximer le gradient et obtenir des résultats "assez bons".
sq_loss_gr_approx
la source