Jaka jest różnica między spadkiem gradientu opartym na pędu a przyspieszeniem opadania gradientu Niestierowa?

Opadanie gradientu na podstawie pędu działa więc następująco:

$v=self.momentum*m-lr*g$

gdzie jest poprzednią aktualizacją masy, a g jest bieżącym gradientem w odniesieniu do parametrów p , l r jest szybkością uczenia się, a s e l f . m o m e n t u m jest stałą.$m$$g$$p$$lr$$self.momentum$

$p_{new} = p + v = p + self.momentum * m - lr * g$

a przyspieszone opadanie gradientu Niestierowa działa w następujący sposób:

$p_{new} = p + self.momentum * v - lr * g$

co jest równoważne z:

$p_{new} = p + self.momentum * (self.momentum * m - lr * g ) - lr * g$

lub

$p_{new} = p + self.momentum^2 * m - (1 + self.momentum) * lr * g$

źródło: https://github.com/fchollet/keras/blob/master/keras/optimizers.py

Wydaje mi się więc, że przyspieszone opadanie gradientu Niestierowa po prostu nadaje większą wagę warunkowi lr * g w stosunku do przepuszczalnego składnika zmiany masy m (w porównaniu do zwykłego starego pędu). Czy ta interpretacja jest poprawna?

Odpowiedź Arecha na temat pędu Niestierowa jest poprawna, ale kod zasadniczo robi to samo. W związku z tym metoda Nesterowa nadaje większą wagę składnikowi , a mniejszemu ciężarowi elementu v .$lr \cdot g$$v$

Aby zilustrować, dlaczego implementacja Keras jest poprawna, pożyczę przykład Geoffreya Hintona .

Metoda Niestierowa przyjmuje podejście „gamble-> korekta”.
w ′ = w + v ′ Brązowy wektor to m ⋅ v (hazard / skok), czerwony wektor to - l r ⋅ ∇ ( w + m ⋅ v ) (korekta), a zielony wektor to m ⋅ v - l r $v' = m \cdot v - lr \cdot \nabla(w+m \cdot v)$
$w' = w + v'$
$m \cdot v$$-lr \cdot \nabla(w+m \cdot v)$ (dokąd powinniśmy się przenieść). ∇ ( ⋅ ) to funkcja gradientu.$m \cdot v-lr \cdot \nabla(w+m \cdot v)$$\nabla(\cdot)$

Kod wygląda inaczej, ponieważ porusza się o brązowy wektor zamiast zielonego , ponieważ metoda Nesterowa wymaga jedynie oceny zamiast ∇ ( w ) . Dlatego na każdym kroku chcemy$\nabla(w+m \cdot v) =: g$$\nabla(w)$

1. wróć do miejsca, w którym byliśmy $(1 \rightarrow 0)$
2. podążaj za zielonym wektorem do miejsca, w którym powinniśmy być $(0 \rightarrow 2)$
3. zrobić kolejny hazard $(2 \rightarrow 3)$

Kod Keras napisany w skrócie to , i robimy matematykę$p' = p + m \cdot (m \cdot v - lr \cdot g) - lr \cdot g$

$\begin{align} p' &= p - m \cdot v + m \cdot v + m \cdot (m \cdot v - lr \cdot g) - lr \cdot g\\ &= p - m \cdot v + m \cdot v - lr \cdot g + m \cdot (m \cdot v - lr \cdot g)\\ &= p - m \cdot v + (m \cdot v-lr \cdot g) + m \cdot (m \cdot v-lr \cdot g) \end{align}$

i to dokładnie . W rzeczywistości oryginalny kod ma krótszą ścieżkę 1 → 2 → 3 . $1 \rightarrow 0 \rightarrow 2 \rightarrow 3$$1 \rightarrow 2 \rightarrow 3$

Rzeczywista wartość szacunkowa (zielony wektor) powinna wynosić , która powinna być zbliżona do p, gdy nauka się zbiega.$p - m \cdot v$$p$

Wydaje mi się, że odpowiedź na pytanie PO została już udzielona, ​​ale postaram się udzielić innego (mam nadzieję intuicyjnego) wyjaśnienia na temat pędu i różnicy między Klasycznym Momentum (CM) a Nesterovem Accelerated Gradient (NAG).

tl; dr
Wystarczy przejść do obrazu na końcu.
Rozumowanie NAG_ball to kolejna ważna część, ale nie jestem pewien, czy zrozumienie byłoby łatwe bez reszty.

$\theta$$f(\theta)$

W innych wiadomościach ostatnio pojawiły się te dwie dzikie, czujące kule:

Okazuje się (zgodnie z obserwowanym zachowaniem kulek i zgodnie z artykułem dotyczącym znaczenia inicjalizacji i pędu w głębokim uczeniu się , który opisuje zarówno CM, jak i NAG w sekcji 2), że każda piłka zachowuje się dokładnie tak, jak jedna z tych metod , dlatego nazwalibyśmy je „CM_ball” i „NAG_ball”:
(NAG_ball się uśmiecha, ponieważ ostatnio oglądał koniec wykładu 6c - Metoda pędu, autorstwa Geoffrey'a Hintona z Nitish Srivastava i Kevinem Swerskim , i dlatego wierzy bardziej niż kiedykolwiek w to, że jego zachowanie prowadzi do znalezienia minimum szybciej).

Oto jak zachowują się kule:

• 
  $\theta_t$$t$$v_t$$t$$\theta_t=\theta_{t-1}+v_t$
• $v_t$
  • $v_{t-1}$
    $v_{t-1}$
    $\mu$$0.9 \le \mu <1$$\mu v_{t-1}$
    $\mu$
    
  • 
    
    $\epsilon$$\epsilon>0$
    $\epsilon$
    $g$$-\epsilon g$
• $$v_t=\mu v_{t-1} -\epsilon g$$
• 
  $$v_{t}=\mu v_{t-1}-\epsilon\nabla f\left(\theta_{t-1}\right)$$

• 
  

  $$v_{t}=\mu v_{t-1}-\epsilon\nabla f\left(\theta_{t-1}+\mu v_{t-1}\right)$$

  Rozumowanie NAG_ball

  • Niezależnie od tego, który skok nastąpi wcześniej, mój Momentum Jump byłby taki sam.
    Powinienem więc wziąć pod uwagę sytuację, jakbym już wykonał skok pędu i mam zamiar wykonać skok skoku.
  • Teraz mój skok po zboczu zacznie się od tego momentu, ale mogę zdecydować, czy obliczyć, jaki będzie mój skok po zboczu, jak gdyby zaczął się przed skokiem pędu, czy tak, jakby zaczął się tutaj.
  • $\theta$$\theta$$\theta$
    
    

$\theta$
$f(\theta)$$7$

Dodatek 1 - Demonstracja rozumowania NAG_ball

W tym hipnotyzującym gifie Aleca Radforda możesz zobaczyć, że NAG działa zdecydowanie lepiej niż CM („Momentum” w gifie).
(Minimum to miejsce, w którym znajduje się gwiazda, a krzywe są liniami konturowymi . Aby uzyskać wyjaśnienie dotyczące linii konturowych i dlaczego są one prostopadłe do gradientu, zobacz wideo 1 i 2 legendarnego 3Blue1Brown .)

Analiza określonego momentu pokazuje rozumowanie NAG_ball:

• (Długa) fioletowa strzałka jest podetapem pędu.
• Przezroczysta czerwona strzałka jest podetapem gradientu, jeśli rozpoczyna się przed podetapem pędu.
• Czarna strzałka jest podetapem gradientu, jeśli zaczyna się po podetapie pędu.
• CM znalazłby się w celu ciemnoczerwonej strzałki.
• NAG znalazłby się w celu czarnej strzałki.

Załącznik 2 - rzeczy / warunki, które wymyśliłem (dla intuicji)

• CM_ball
• NAG_ball
• Podwójny skok
• Momentum Jump
• Pęd utracony z powodu tarcia z powietrzem
• Skok ze spadków
• Zapał piłki
• Wczoraj obserwuję piłki

Załącznik 3 - warunki, których nie wymyśliłem

• Sposób, w jaki zachowują się CM i NAG:
  • Głównie zależałem od części 2 artykułu dotyczącej znaczenia inicjalizacji i tempa w głębokim uczeniu się .
    
  • Ponadto przegląd algorytmów optymalizacji spadku gradientu (post na blogu Sebastiana Rudera) naprawdę pomógł mi zrozumieć CM i NAG (i wiele więcej).
• Współczynnik pędu - termin używany co najmniej przez papier
• Wskaźnik uczenia się

Nie wydaje mi się

Dobry opis właściwości Nesterov Momentum (aka Nesterov Accelerated Gradient) znajduje się na przykład w Sutskever, Martens i wsp. „O znaczeniu inicjalizacji i pędu w głębokim uczeniu się” 2013 .

Główna różnica polega na tym, że w pędzie klasycznym najpierw korygujesz prędkość, a następnie robisz duży krok zgodnie z tą prędkością (a następnie powtarzasz), ale w pędu Niestierowa najpierw robisz krok w kierunku prędkości, a następnie korygujesz wektor prędkości w nowej lokalizacji (następnie powtórz).

tzn. pęd klasyczny:

vW(t+1) = momentum.*Vw(t) - scaling .* gradient_F( W(t) )
W(t+1) = W(t) + vW(t+1)

Podczas gdy pęd Nesterowa jest następujący:

vW(t+1) = momentum.*Vw(t) - scaling .* gradient_F( W(t) + momentum.*vW(t) )
W(t+1) = W(t) + vW(t+1)

W rzeczywistości robi to ogromną różnicę w praktyce ...

Dodano: kurs Stanford na temat sieci neuronowych, cs231n , daje jeszcze jedną formę kroków:

v = mu * v_prev - learning_rate * gradient(x)   # GD + momentum
v_nesterov = v + mu * (v - v_prev)              # keep going, extrapolate
x += v_nesterov

Oto vprędkość, czyli krok, czyli stan, i mujest czynnikiem pędu, zwykle około 0,9. ( v, xI learning_ratemoże być bardzo długi wektory, z numpy kod jest taki sam).

vw pierwszym wierszu jest nachylenie gradientu z pędem; v_nesterovekstrapoluje, kontynuuje. Na przykład przy mu = 0,9

v_prev  v   --> v_nesterov
---------------
 0  10  -->  19
10   0  -->  -9
10  10  -->  10
10  20  -->  29

Poniższy opis składa się z 3 terminów:
sam termin 1 oznacza zwykły spadek gradientu (GD),
1 + 2 daje pęd GD +,
1 + 2 + 3 daje Nesterov GD.

$x_t \to y_t$$y_t \to x_{t+1}$

$\qquad y_t = x_t + m (x_t - x_{t-1}) \quad$ - pęd, predyktor
$\qquad x_{t+1} = y_t + h\ g(y_t) \qquad$ - gradient

$g_t \equiv - \nabla f(y_t)$$h$

$y_t$

$\qquad y_{t+1} = y_t$
$\qquad \qquad + \ h \ g_t \qquad \qquad \quad$ - gradient
$\qquad \qquad + \ m \ (y_t - y_{t-1}) \qquad$ - pęd kroku
$\qquad \qquad + \ m \ h \ (g_t - g_{t-1}) \quad$ - pęd gradientu

Ostatni termin to różnica między GD z pędem zwykłym, a GD z pędem Niestierowa.

$m$$m_{grad}$
$\qquad \qquad + \ m \ (y_t - y_{t-1}) \qquad$ - pęd kroku
$\qquad \qquad + \ m_{grad} \ h \ (g_t - g_{t-1}) \quad$ - pęd gradientu

$m_{grad} = 0$$m_{grad} = m$
$m_{grad} > 0$
$m_{grad} \sim -.1$

$m_t$$h_t$