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

48

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

v=self.momentummlrg

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łą.mgplrself.momentum

pnew=p+v=p+self.momentummlrg

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

pnew=p+self.momentumvlrg

co jest równoważne z:

pnew=p+self.momentum(self.momentummlrg)lrg

lub

pnew=p+self.momentum2m(1+self.momentum)lrg

ź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?

cydr
źródło
7
Poprosiłbym Cię o wpisanie pyta za dużo? LATEX
Rodrigo de Azevedo

Odpowiedzi:

35

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 .lrgv

Aby zilustrować, dlaczego implementacja Keras jest poprawna, pożyczę przykład Geoffreya Hintona .
wprowadź opis zdjęcia tutaj

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=mvlr(w+mv)
w=w+v
mvlr(w+mv) (dokąd powinniśmy się przenieść). ( ) to funkcja gradientu.mvlr(w+mv)()

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(w+mv)=:g(w)

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

Kod Keras napisany w skrócie to , i robimy matematykęp=p+m(mvlrg)lrg

p=pmv+mv+m(mvlrg)lrg=pmv+mvlrg+m(mvlrg)=pmv+(mvlrg)+m(mvlrg)

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

Rzeczywista wartość szacunkowa (zielony wektor) powinna wynosić , która powinna być zbliżona do p, gdy nauka się zbiega.pmvp

dontloo
źródło
2
@youkaichao spróbuj tego youtube.com/watch?v=LdkkZglLZ0Q
dontloo
13

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.



θf(θ)

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

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:


  • θttvttθt=θt1+vt
  • vt
    • vt1
      vt1
      μ0.9μ<1μvt1
      μ


    • ϵϵ>0
      ϵ
      gϵg
  • vt=μvt1ϵg

  • vt=μvt1ϵf(θt1)

  • vt=μvt1ϵf(θt1+μvt1)

    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.
    • θθθ



θ
f(θ)7

Przykład CM_ball vs. NAG_ball


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

NAG lepszy niż CM (Momentum)

Analiza określonego momentu pokazuje rozumowanie NAG_ball:

CM vs NAG w określonym momencie

  • (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

Oren Milman
źródło
1
Znajduję część z „Oto jak zachowują się kule: ...” do „, aby skierować cię w kierunku od θ do minimum (o względnie odpowiedniej wielkości).” doskonałe jako wyjaśnienie różnicy.
Poete Maudit
12

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 ...

Arech
źródło
5

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.

xtytytxt+1

yt=xt+m(xtxt1) - pęd, predyktor
xt+1=yt+h g(yt) - gradient

gtf(yt)h

yt

yt+1=yt
+ h gt - gradient
+ m (ytyt1) - pęd kroku
+ m h (gtgt1) - pęd gradientu

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


mmgrad
+ m (ytyt1) - pęd kroku
+ mgrad h (gtgt1) - pęd gradientu

mgrad=0mgrad=m
mgrad>0
mgrad.1

mtht



(x/[cond,1]100)+ripple×sin(πx)

wprowadź opis zdjęcia tutaj

denis
źródło