Jak stochastyczne obniżanie gradientu może zaoszczędzić czas w porównaniu ze standardowym spadkiem gradientu?

16

Standardowe zejście gradientu obliczałoby gradient dla całego zestawu danych treningowych.

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

Dla wstępnie zdefiniowanej liczby epok najpierw obliczamy wektor gradientu wagi_grad funkcji straty dla całego zestawu danych w stosunku do naszych parametrów wektora parametru.

Natomiast Stochastyczne zejście gradientu wykonuje aktualizację parametru dla każdego przykładu treningowego x (i) i etykiety 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

Mówi się, że SGD jest znacznie szybszy. Nie rozumiem jednak, jak może być znacznie szybciej, jeśli nadal mamy pętlę nad wszystkimi punktami danych. Czy obliczanie gradientu w GD jest znacznie wolniejsze niż obliczanie GD dla każdego punktu danych osobno?

Kod pochodzi stąd .

Alina
źródło
1
W drugim przypadku wziąłbyś małą partię, aby przybliżyć cały zestaw danych. Zwykle działa całkiem dobrze. Mylące jest więc to, że wygląda na to, że liczba epok jest w obu przypadkach taka sama, ale w przypadku 2. nie potrzebowałabyś tyle epok. „Hiperparametry” byłyby różne dla tych dwóch metod: GD nb_epochs! = SGD nb_epochs. Powiedzmy dla celów argumentu: GD nb_epochs = przykłady SGD * nb_epochs, więc całkowita liczba pętli jest taka sama, ale obliczanie gradientu jest znacznie szybsze w SGD.
Nima Mousavi
Ta odpowiedź na CV jest dobra i powiązana.
Zhubarb

Odpowiedzi:

24

Krótka odpowiedź:

  • W wielu ustawieniach dużych danych (powiedzmy kilka milionów punktów danych) obliczenie kosztu lub gradientu zajmuje bardzo dużo czasu, ponieważ musimy zsumować wszystkie punkty danych.
  • Mamy nie muszą mieć dokładnie gradientu w celu zmniejszenia kosztów w danej iteracji. Pewne przybliżenie gradientu działałoby OK.
  • Stochastyczny gradient przyzwoity (SGD) aproksymuje gradient przy użyciu tylko jednego punktu danych. Tak więc ocena gradientu oszczędza dużo czasu w porównaniu do sumowania wszystkich danych.
  • Przy „rozsądnej” liczbie iteracji (liczba ta może wynosić kilka tysięcy, a znacznie mniej niż liczba punktów danych, które mogą być milionami), przyzwoity gradient stochastyczny może uzyskać rozsądne dobre rozwiązanie.

Długa odpowiedź:

Moja notacja jest zgodna z kursem Coursera do uczenia maszynowego Andrew NG. Jeśli nie znasz go, możesz przejrzeć serię wykładów tutaj .

Załóżmy regresję straty kwadratowej, funkcją kosztu jest

jot(θ)=12)mja=1m(hθ(x(ja))-y(ja))2)

a gradient wynosi

rejot(θ)reθ=1mja=1m(hθ(x(ja))-y(ja))x(ja)

dla gradientu przyzwoitego (GD) aktualizujemy parametr o

θnmiw=θolre-α1mja=1m(hθ(x(ja))-y(ja))x(ja)

1/mx(ja),y(ja)

θnmiw=θolre-α(hθ(x(ja))-y(ja))x(ja)

Oto dlaczego oszczędzamy czas:

Załóżmy, że mamy 1 miliard punktów danych.

  • W GD, aby raz zaktualizować parametry, musimy mieć (dokładny) gradient. Wymaga to zsumowania tych 1 miliarda punktów danych, aby wykonać 1 aktualizację.

  • W SGD możemy myśleć o tym jako o próbie uzyskania przybliżonego gradientu zamiast gradientu dokładnego . Przybliżenie pochodzi z jednego punktu danych (lub kilku punktów danych zwanych mini wsadami). Dlatego w SGD możemy bardzo szybko zaktualizować parametry. Ponadto, jeśli „zapętlimy” wszystkie dane (zwane jedną epoką), faktycznie mamy 1 miliard aktualizacji.

Sztuka polega na tym, że w SGD nie musisz mieć 1 miliarda iteracji / aktualizacji, ale znacznie mniej iteracji / aktualizacji, powiedzmy 1 milion, i będziesz miał model „wystarczająco dobry” do użycia.


Piszę kod, aby zilustrować ten pomysł. Najpierw rozwiązujemy układ liniowy za pomocą równania normalnego, a następnie rozwiązujemy go za pomocą SGD. Następnie porównujemy wyniki pod względem wartości parametrów i wartości funkcji celu końcowego. W celu późniejszej wizualizacji będziemy musieli dostroić 2 parametry.

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)
}

Wyniki:

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

124,1343123,0355

Oto wartości funkcji kosztu nad iteracjami, widzimy, że może skutecznie zmniejszyć stratę, co ilustruje pomysł: możemy użyć podzbioru danych do przybliżenia gradientu i uzyskania „wystarczająco dobrych” wyników.

wprowadź opis zdjęcia tutaj

wprowadź opis zdjęcia tutaj

1000sq_loss_gr_approx3001000

Haitao Du
źródło
Myślałem, że argument o „szybkości” dotyczy bardziej liczby operacji / iteracji potrzebnych do uzyskania optymalnej wartości lokalnej? (A także to stochastyczne opadanie gradientu ma tendencję do zbieżności w celu uzyskania lepszych
optymów
O ile rozumiem, w kodzie Pythona podałem, że zmienna „data” jest taka sama. Mini przyzwoity gradient gradientu - kod różni się od SDG (i właśnie tam wykorzystuje tylko niewielką część danych). Ponadto w podanym wyjaśnieniu, chociaż pozbywamy się sumy w SDG, nadal obliczamy aktualizację dla każdego punktu danych. Nadal nie rozumiem, w jaki sposób aktualizacja parametru podczas zapętlania każdego punktu danych jest szybsza niż tylko zsumowanie wszystkich punktów danych jednocześnie.
Alina
@ GeoMatt22 W linku, który podałem, stwierdza: „Z drugiej strony, to ostatecznie komplikuje konwergencję do dokładnego minimum, ponieważ SGD będzie nadal przeregulowywać”. Oznacza to, że nie jest zbieżny z lepszymi optymami. A może źle to zrozumiałem?
Alina
@Tonja Nie jestem ekspertem, ale na przykład ten bardzo wpływowy artykuł w głębokim uczeniu się daje argument „szybszy i bardziej niezawodny trening” dla stochastycznego spadku. Zauważ, że nie używa on wersji „surowej”, ale używa różnych oszacowań krzywizny, aby ustawić szybkość uczenia się (zależną od współrzędnych).
GeoMatt22,
1
@Tonja, tak. zadziałałoby „słabe” przybliżenie gradientu. Możesz zaznaczyć „wzmocnienie gradientu”, co jest podobnym pomysłem. Z drugiej strony piszę trochę kodu, aby zilustrować ten pomysł. Opublikuję go, gdy będzie gotowy.
Haitao Du