Apa perbedaan antara penurunan gradien berbasis momentum dan percepatan penurunan gradien Nesterov?

48

Jadi penurunan gradien berbasis momentum bekerja sebagai berikut:

v=self.momentummlrg

di mana adalah pembaruan berat sebelumnya, dan adalah gradien saat ini sehubungan dengan parameter , adalah tingkat pembelajaran, dan adalah konstanta.g p l r s e l f . m o m e n t u mmgplrself.momentum

pnew=p+v=p+self.momentummlrg

dan percepatan gradient descent Nesterov bekerja sebagai berikut:

pnew=p+self.momentumvlrg

yang setara dengan:

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

atau

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

sumber: https://github.com/fchollet/keras/blob/master/keras/optimizers.py

Jadi bagi saya tampaknya penurunan gradien dipercepat Nesterov hanya memberikan bobot lebih untuk lr * g istilah selama periode perubahan berat badan sebelumnya m (dibandingkan dengan momentum lama polos). Apakah interpretasi ini benar?

Sari apel
sumber
7
Apakah meminta Anda untuk mengetik akan meminta terlalu banyak? LATEX
Rodrigo de Azevedo

Jawaban:

35

Jawaban Arech tentang momentum Nesterov benar, tetapi kode dasarnya melakukan hal yang sama. Jadi dalam hal ini metode Nesterov memang memberikan bobot lebih untuk istilah , dan lebih sedikit bobot untuk istilah .vlrgv

Untuk menggambarkan mengapa penerapan Keras benar, saya akan meminjam contoh Geoffrey Hinton .
masukkan deskripsi gambar di sini

Metode Nesterov mengambil pendekatan "koreksi-judi". Vektor coklat adalah (taruhan / lompatan), vektor merahnya adalah (koreksi), dan vektor hijau adalah (di mana kita seharusnya benar-benar pindah ke). adalah fungsi gradien.
w = w + v m v - l r ( w + m v ) m v - l r ( w + m v ) ( )v=mvlr(w+mv)
w=w+v
mvlr(w+mv)mvlr(w+mv)()

Kode terlihat berbeda karena bergerak dengan vektor cokelat dan bukan vektor hijau , karena metode Nesterov hanya memerlukan evaluasi bukan . Karena itu di setiap langkah kami ingin( w )(w+mv)=:g(w)

  1. kembali ke tempat kita sebelumnya(10)
  2. ikuti vektor hijau ke tempat kita seharusnya(02)
  3. bertaruh lagi(23)

Kode keras 'ditulis untuk singkat adalah , dan kami melakukan beberapa matematikap=p+m(mvlrg)lrg

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

dan itu persis . Sebenarnya kode asli mengambil jalur yang lebih pendek . 1023123

Nilai estimasi aktual (vektor hijau) harus , yang harus dekat dengan ketika belajar menyatu.pmvp

dontloo
sumber
2
@youkaichao coba youtube.com/watch?v=LdkkZglLZ0Q
dontloo
13

Tampaknya bagi saya bahwa pertanyaan OP sudah dijawab, tetapi saya akan mencoba memberikan penjelasan (semoga intuitif) lain tentang momentum dan perbedaan antara Momentum Klasik (CM) dan Gradien Akselerasi Gradien (NAG) Nesterov.


tl; dr Langsung
saja ke gambar di bagian akhir.
Alasan NAG_ball adalah bagian penting lainnya, tetapi saya tidak yakin itu akan mudah dipahami tanpa sisanya.



CM dan NAG keduanya metode untuk memilih vektor berikutnya dalam ruang parameter, untuk menemukan minimum fungsi .θf(θ)

Dalam berita lain, akhir-akhir ini kedua bola liar ini muncul:
CM_ball NAG_ball

Ternyata (sesuai dengan perilaku bola yang diamati, dan menurut makalah tentang pentingnya inisialisasi dan momentum dalam pembelajaran yang mendalam , yang menggambarkan CM dan NAG di bagian 2) bahwa setiap bola berperilaku persis seperti salah satu metode ini , dan jadi kami akan memanggil mereka "CM_ball" dan "NAG_ball":
(NAG_ball sedang tersenyum, karena ia baru-baru ini menyaksikan akhir Kuliah 6c - Metode momentum, oleh Geoffrey Hinton dengan Nitish Srivastava dan Kevin Swersky , dan dengan demikian percaya lebih dari sebelumnya bahwa perilakunya mengarah pada penemuan minimum yang lebih cepat.)

Beginilah perilaku bola:

  • Alih-alih bergulir seperti bola normal, mereka melompat di antara titik dalam ruang parameter.
    Biarkan menjadi lokasi ke- bola di ruang parameter, dan biarkan menjadi lompat ke- bola . Kemudian melompat di antara titik-titik dalam ruang parameter dapat dijelaskan dengan .θttvttθt=θt1+vt
  • Mereka tidak hanya melompat daripada roll, tetapi juga melompat mereka istimewa: Setiap melompat sebenarnya adalah Double Jump, yang merupakan komposisi dari dua melompat: vt
    • Momentum Jump - lompatan yang menggunakan momentum dari , Double Jump terakhir. Sebagian kecil dari momentum hilang karena gesekan dengan udara. Biarkan menjadi fraksi dari momentum yang tersisa (bola cukup aerodinamis, jadi biasanya ). Kemudian Momentum Jump sama dengan . (Dalam CM dan NAG, adalah hiperparameter yang disebut "koefisien momentum".)vt1
      vt1
      μ0.9μ<1μvt1
      μ
    • Lereng Lompatan - lompatan yang mengingatkan saya pada hasil menempatkan bola normal di permukaan - bola mulai bergulir ke arah kemiringan paling curam ke bawah, sedangkan lereng yang curam, semakin besar akselerasi.
      Demikian pula, Lompatan Lompat ke arah kemiringan paling curam ke bawah (arah yang berlawanan dengan gradien), dan semakin besar gradien, semakin jauh lompatan.
      Slope Jump juga tergantung pada , tingkat semangat bola (tentu saja, ): Semakin bersemangat bola, semakin jauh Slope Jump akan mengambilnya. (Dalam CM dan NAG, adalah hiperparameter yang disebut "tingkat pembelajaran".) Mariϵϵ>0
      ϵ
      gmenjadi gradien di lokasi awal Slope Jump. Kemudian Lompatan Lereng sama dengan .ϵg
  • Jadi untuk kedua bola, Double Jump sama dengan: Satu-satunya perbedaan antara bola adalah urutan dua lompatan dalam Double Jump.
    vt=μvt1ϵg
  • CM_ball tidak menganggap itu penting, jadi dia memutuskan untuk selalu memulai dengan Slope Jump.
    Jadi, Double Jump CM_ball adalah:
    vt=μvt1ϵf(θt1)
  • Sebaliknya, NAG_ball memikirkannya selama beberapa waktu, dan kemudian memutuskan untuk selalu memulai dengan Momentum Jump.
    Oleh karena itu, Lompat Ganda NAG_ball adalah:

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

    Alasan NAG_ball

    • Apapun lompatan yang lebih dulu, Lompatan Momentum saya akan sama.
      Jadi saya harus mempertimbangkan situasinya seolah-olah saya sudah membuat Momentum Jump saya, dan saya akan membuat Slope Jump saya.
    • Sekarang, Lompatan Lereng saya secara konseptual akan dimulai dari sini, tetapi saya dapat memilih apakah akan menghitung seperti apa Lompatan Lereng saya seolah-olah itu dimulai sebelum Lompat Momentum, atau seolah-olah itu dimulai di sini.
    • Memikirkannya dengan cara ini membuatnya cukup jelas bahwa yang terakhir lebih baik, seperti umumnya, gradien di beberapa titik kira-kira mengarahkan Anda ke arah dari ke minimum (dengan besarnya relatif tepat), sedangkan gradien di beberapa titik lainnya cenderung mengarahkan Anda ke arah dari ke minimum (dengan besaran yang relatif tepat).θθθ

Akhirnya, kemarin saya cukup beruntung untuk mengamati setiap bola yang melompat-lompat dalam ruang parameter 1 dimensi.
Saya pikir bahwa melihat posisi mereka yang berubah di ruang parameter tidak akan banyak membantu dalam mendapatkan intuisi, karena ruang parameter ini adalah sebuah garis.
Jadi sebagai gantinya, untuk setiap bola saya membuat sketsa grafik 2 dimensi di mana sumbu horizontal adalah . Kemudian saya menggambar menggunakan kuas hitam, dan juga menggambar setiap bola di posisi pertamanya, bersama dengan angka untuk menunjukkan urutan kronologis dari posisi tersebut. Terakhir, saya menggambar panah hijau untuk menunjukkan jarak dalam ruang parameter (yaitu jarak horizontal dalam grafik) dari setiap Momentum Jump dan Slope Jump.θf ( θ ) 7
f(θ)7

Contoh CM_ball vs NAG_ball


Lampiran 1 - Demonstrasi alasan NAG_ball

Dalam gif yang memukau ini oleh Alec Radford , Anda dapat melihat NAG tampil lebih baik daripada CM ("Momentum" di gif).
(Minimum adalah di mana bintang berada, dan kurva adalah garis kontur . Untuk penjelasan tentang garis kontur dan mengapa mereka tegak lurus terhadap gradien, lihat video 1 dan 2 oleh 3Blue1Brown yang legendaris .)

NAG lebih baik dari CM (Momentum)

Analisis momen tertentu menunjukkan alasan NAG_ball:

CM vs NAG pada saat tertentu

  • Panah ungu (panjang) adalah momentum sub-langkah.
  • Panah merah transparan adalah sub-langkah gradien jika dimulai sebelum sub-langkah momentum.
  • Panah hitam adalah sub-langkah gradien jika dimulai setelah sub-langkah momentum.
  • CM akan berakhir pada target panah merah gelap.
  • NAG akan berakhir di target panah hitam.

Lampiran 2 - hal / istilah yang saya buat (demi intuisi)

  • CM_ball
  • NAG_ball
  • Lompat Ganda
  • Momentum Jump
  • Momentum hilang karena gesekan dengan udara
  • Lereng Lompat
  • Semangat bola
  • Saya mengamati bola kemarin

Lampiran 3 - istilah yang saya tidak pakai

Oren Milman
sumber
1
Saya menemukan bagian dari "Ini adalah bagaimana bola berperilaku: ..." menjadi "untuk mengarahkan Anda ke arah dari θ ke minimum (dengan besaran yang relatif tepat)." sangat baik sebagai penjelasan perbedaan.
Poete Maudit
12

Saya kira tidak.

Ada deskripsi yang bagus tentang properti Nesterov Momentum (alias Nesterov Accelerated Gradient) di, misalnya, Sutskever, Martens dkk. "Tentang pentingnya inisialisasi dan momentum dalam pembelajaran mendalam" 2013 .

Perbedaan utama adalah dalam momentum klasik, Anda pertama-tama mengoreksi kecepatan Anda dan kemudian membuat langkah besar sesuai dengan kecepatan itu (dan kemudian mengulangi), tetapi dalam momentum Nesterov Anda pertama-tama membuat langkah ke arah kecepatan dan kemudian membuat koreksi terhadap vektor kecepatan berdasarkan di lokasi baru (lalu ulangi).

yaitu momentum Klasik:

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

Sementara momentum Nesterov adalah ini:

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

Sebenarnya, ini membuat perbedaan besar dalam latihan ...

Arech
sumber
5

Ditambahkan: kursus Stanford pada jaringan saraf, cs231n , memberikan bentuk lain dari langkah-langkah:

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

Inilah vkecepatan alias langkah alias keadaan, dan mumerupakan faktor momentum, biasanya 0,9 atau lebih. ( v, xdan learning_ratebisa jadi vektor yang sangat panjang; dengan numpy, kodenya sama.)

vpada baris pertama adalah gradient descent dengan momentum; v_nesterovekstrapolasi, terus berjalan. Misalnya, dengan mu = 0,9,

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

Deskripsi berikut memiliki 3 istilah:
istilah 1 saja adalah keturunan gradien polos (GD),
1 + 2 memberi momentum GD +,
1 + 2 + 3 memberi Nesterov GD.

Nesterov GD biasanya digambarkan sebagai langkah momentum bergantian dan langkah gradien :xtytytxt+1

yt=xt+m(xtxt1) - momentum, prediktor - gradien
xt+1=yt+h g(yt)

di mana adalah gradien negatif, dan adalah stepsize alias tingkat pembelajaran.gtf(yt)h

Gabungkan dua persamaan ini menjadi satu dalam saja, titik di mana gradien dievaluasi, dengan memasukkan persamaan kedua ke yang pertama, dan mengatur ulang istilah:yt

yt+1=yt
+ h gt - gradien - langkah momentum - momentum gradien
+ m (ytyt1)
+ m h (gtgt1)

Istilah terakhir adalah perbedaan antara GD dengan momentum biasa, dan GD dengan momentum Nesterov.


Seseorang dapat menggunakan istilah momentum terpisah, misal dan : - momentum langkah - momentum gradienmmgrad
+ m (ytyt1)
+ mgrad h (gtgt1)

Kemudian memberikan momentum yang jelas, Nesterov. menguatkan noise (gradien bisa sangat bising), adalah filter smoothing IIR.m g r a d = m m g r a d > 0 m g r a d- .1mgrad=0mgrad=m
mgrad>0
mgrad.1

By the way, momentum dan stepsize dapat bervariasi dengan waktu, dan , atau per komponen (ADA * berkoordinasi keturunan), atau keduanya - lebih metode dari uji kasus.h tmtht


Plot yang membandingkan momentum polos dengan momentum Nesterov pada test case 2d sederhana, :
(x/[cond,1]100)+ripple×sin(πx)

masukkan deskripsi gambar di sini

denis
sumber