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

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

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

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

\begin{aligned} jot (θ) = \frac{1}{2) m} \sum_{ja = 1}^{m} (h_{θ} (x^{(ja)}) - y^{(ja)})^{2)} \end{aligned}

$\begin{align} J(\theta)= \frac 1 {2m} \sum_{i=1}^m (h_{\theta}(x^{(i)})-y^{(i)})^2 \end{align}$

a gradient wynosi

\begin{aligned} \frac{re jot (θ)}{re θ} = \frac{1}{m} \sum_{ja = 1}^{m} (h_{θ} (x^{(ja)}) - y^{(ja)}) x^{(ja)} \end{aligned}

$\begin{align} \frac {d J(\theta)}{d \theta}= \frac 1 {m} \sum_{i=1}^m (h_{\theta}(x^{(i)})-y^{(i)})x^{(i)} \end{align}$

dla gradientu przyzwoitego (GD) aktualizujemy parametr o

\begin{aligned} θ_{n mi w} & = θ_{o l re} - α \frac{1}{m} \sum_{ja = 1}^{m} (h_{θ} (x^{(ja)}) - y^{(ja)}) x^{(ja)} \end{aligned}

$\begin{align} \theta_{new} &=\theta_{old} - \alpha \frac 1 {m} \sum_{i=1}^m (h_{\theta}(x^{(i)})-y^{(i)})x^{(i)} \end{align}$

$1/m$ $x^{(i)},y^{(i)}$

\begin{aligned} θ_{n mi w} = θ_{o l re} - α \cdot (h_{θ} (x^{(ja)}) - y^{(ja)}) x^{(ja)} \end{aligned}

$\begin{align} \theta_{new}=\theta_{old} - \alpha \cdot (h_{\theta}(x^{(i)})-y^{(i)})x^{(i)} \end{align}$

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.1343$ $123.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.

$1000$ sq_loss_gr_approx $300$ $1000$

— 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,

@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