Wie kann der stochastische Gradientenabstieg im Vergleich zum normalen Gradientenabstieg Zeit sparen?

Standardgradientenabstieg berechnet den Gradienten für den gesamten Trainingsdatensatz.

for i in range(nb_epochs):
  params_grad = evaluate_gradient(loss_function, data, params)
  params = params - learning_rate * params_grad

Für eine vordefinierte Anzahl von Epochen berechnen wir zunächst den Gradientenvektor Weight_Grad der Verlustfunktion für den gesamten Datensatz mit unseren Parametervektorparametern.

Im Gegensatz dazu führt der stochastische Gradientenabstieg eine Parameteraktualisierung für jedes Trainingsbeispiel x (i) und Etikett y (i) durch.

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 soll viel schneller sein. Ich verstehe jedoch nicht, wie viel schneller es sein kann, wenn wir immer noch eine Schleife über alle Datenpunkte haben. Ist die Berechnung des Gradienten in GD viel langsamer als die Berechnung von GD für jeden Datenpunkt einzeln?

Code kommt von hier .

Kurze Antwort:

• Bei vielen Big Data-Einstellungen (z. B. mehreren Millionen Datenpunkten) dauert die Berechnung der Kosten oder des Gefälles sehr lange, da alle Datenpunkte summiert werden müssen.
• Wir brauchen KEINEN genauen Gradienten, um die Kosten in einer bestimmten Iteration zu reduzieren . Eine Annäherung des Gradienten würde in Ordnung sein.
• Stochastic Gradient Decent (SGD) approximiert den Gradienten mit nur einem Datenpunkt. Das Auswerten des Verlaufs spart also viel Zeit im Vergleich zum Summieren aller Daten.
• Mit einer "vernünftigen" Anzahl von Iterationen (diese Anzahl könnte einige Tausend sein und viel weniger als die Anzahl von Datenpunkten, die Millionen sein können), kann ein anständiger stochastischer Gradient eine vernünftig gute Lösung erhalten.

Lange Antwort:

Meine Notation folgt Andrew NGs Coursera-Kurs zum maschinellen Lernen. Wenn Sie damit nicht vertraut sind, können Sie die Vorlesungsreihe hier nachlesen .

Nehmen wir an, die Regression auf den Quadratverlust ist die Kostenfunktion

und der gradient ist

Für Gradient Decent (GD) aktualisieren wir den Parameter um

Für den stochastischen Gradienten anständig werden die Summe und die Konstante entfernt, aber der Gradient für den aktuellen Datenpunkt , wo Zeit gespart wird.$1/m$$x^{(i)},y^{(i)}$

Deshalb sparen wir Zeit:

Angenommen, wir haben 1 Milliarde Datenpunkte.

• Um in GD die Parameter einmal zu aktualisieren, müssen wir den (genauen) Gradienten haben. Dies erfordert die Summe dieser 1 Milliarde Datenpunkte, um 1 Aktualisierung durchzuführen.

• In SGD können wir uns vorstellen, dass wir versuchen, einen approximierten Gradienten anstelle eines exakten Gradienten zu erhalten . Die Annäherung kommt von einem Datenpunkt (oder mehreren Datenpunkten, die als Minibatch bezeichnet werden). Daher können wir in SGD die Parameter sehr schnell aktualisieren. Wenn wir alle Daten "durchlaufen" (eine Epoche genannt), haben wir tatsächlich 1 Milliarde Aktualisierungen.

Der Trick ist, dass Sie in SGD nicht 1 Milliarde Iterationen / Aktualisierungen benötigen, sondern viel weniger Iterationen / Aktualisierungen, z.

Ich schreibe einen Code, um die Idee zu demonstrieren. Wir lösen das lineare System zuerst durch eine normale Gleichung und lösen es dann mit SGD. Dann vergleichen wir die Ergebnisse in Bezug auf Parameterwerte und endgültige Zielfunktionswerte. Um es später zu visualisieren, müssen wir 2 Parameter einstellen.

set.seed(0);n_data=1e3;n_feature=2;
A=matrix(runif(n_data*n_feature),ncol=n_feature)
b=runif(n_data)
res1=solve(t(A) %*% A, t(A) %*% b)

sq_loss<-function(A,b,x){
  e=A %*% x -b
  v=crossprod(e)
  return(v[1])
}

sq_loss_gr_approx<-function(A,b,x){
  # note, in GD, we need to sum over all data
  # here i is just one random index sample
  i=sample(1:n_data, 1)
  gr=2*(crossprod(A[i,],x)-b[i])*A[i,]
  return(gr)
}

x=runif(n_feature)
alpha=0.01
N_iter=300
loss=rep(0,N_iter)

for (i in 1:N_iter){
  x=x-alpha*sq_loss_gr_approx(A,b,x)
  loss[i]=sq_loss(A,b,x)
}

Die Ergebnisse:

as.vector(res1)
[1] 0.4368427 0.3991028
x
[1] 0.3580121 0.4782659

Beachten Sie, dass die Verlustwerte und sehr nahe liegen , obwohl die Parameter nicht zu nahe liegen.$124.1343$$123.0355$

Hier sind die Kostenfunktionswerte über Iterationen. Wir können sehen, dass sie den Verlust effektiv verringern können, was die Idee veranschaulicht: Wir können eine Teilmenge von Daten verwenden, um den Gradienten zu approximieren und "gut genug" -Ergebnisse zu erhalten.

Lassen Sie uns nun den Rechenaufwand zwischen zwei Ansätzen überprüfen. In dem Experiment haben wir Datenpunkte, die mit Hilfe von SD den Gradienten auswerten, sobald die Daten über diesen summiert werden müssen. ABER in SGD summiert die Funktion nur 1 Datenpunkt, und insgesamt sehen wir, dass der Algorithmus weniger als Iterationen konvergiert (Anmerkung, nicht Iterationen). Dies ist die Rechenersparnis.300 $1000$sq_loss_gr_approx$300$$1000$