25

Diberikan fungsi biaya cembung, menggunakan SGD untuk optimisasi, kami akan memiliki gradien (vektor) pada titik tertentu selama proses optimasi.

Pertanyaan saya adalah, mengingat titik pada cembung, apakah gradien hanya menunjuk pada arah di mana fungsi naik / turun tercepat, atau gradien selalu menunjuk pada titik optimal / ekstrim dari fungsi biaya ?

Yang pertama adalah konsep lokal, yang terakhir adalah konsep global.

SGD akhirnya dapat menyatu ke nilai ekstrem dari fungsi biaya. Saya bertanya-tanya tentang perbedaan antara arah gradien yang diberikan titik sembarang pada cembung dan arah yang menunjuk pada nilai ekstrim global.

Arah gradien harus menjadi arah di mana fungsi naik / turun tercepat pada titik itu, kan?

neural-networks optimization gradient-descent sgd convex Tyler 十三将士归玉门
sumber

6

Pernahkah Anda berjalan lurus menuruni bukit dari gunung, hanya untuk menemukan diri Anda di lembah yang terus menurun ke arah yang berbeda? Tantangannya adalah membayangkan situasi seperti itu dengan topografi cembung: pikirkan ujung pisau di mana punggungan paling curam di bagian atas.

Whuber

4

Tidak, karena itu keturunan gradien stokastik, bukan keturunan gradien. Inti dari SGD adalah bahwa Anda membuang beberapa informasi gradien dengan imbalan peningkatan efisiensi komputasi - tetapi jelas dalam membuang beberapa informasi gradien Anda tidak lagi akan memiliki arah gradien asli. Ini sudah mengabaikan masalah apakah gradien reguler mengarah ke arah penurunan optimal, tetapi intinya adalah, bahkan jika gradien reguler turun, tidak ada alasan untuk mengharapkan penurunan gradien stokastik untuk melakukannya.

Chill2Macht

3

@ Tyler, mengapa pertanyaan Anda secara khusus tentang keturunan gradien stokastik . Apakah Anda membayangkan sesuatu yang berbeda dibandingkan dengan penurunan gradien standar?

Sextus Empiricus

2

Gradien akan selalu mengarah ke optimal dalam arti bahwa sudut antara gradien dan vektor ke optimum akan memiliki sudut kurang dari , dan berjalan ke arah gradien jumlah yang sangat kecil akan membuat Anda lebih dekat ke optimal.

\frac{π}{2}

$\frac{\pi}{2}$

Pasang kembali Monica

5

Jika gradien menunjuk langsung ke minimizer global, optimisasi cembung akan menjadi sangat mudah, karena kita bisa melakukan pencarian garis satu dimensi untuk menemukan minimizer global. Ini terlalu banyak untuk diharapkan.

littleO

36

Mereka mengatakan gambar bernilai lebih dari seribu kata. Dalam contoh berikut (milik MS Paint, alat yang berguna untuk ahli statistik amatir dan profesional keduanya) Anda dapat melihat permukaan fungsi cembung dan titik di mana arah penurunan curam jelas berbeda dari arah menuju optimal.

Pada catatan yang serius: Ada jawaban yang jauh lebih unggul di utas ini yang juga patut mendapat pujian.

Jan Kukacka
sumber

27

Dan contoh tandingan hari ini adalah ... alpukat!

JDL

11

Anda melihat bahwa saat memotong alpukat, Anda harus memotong arah penurunan curam untuk menghindari benih dan kemungkinan cedera .

Jan Kukacka

28

Metode keturunan gradien menggunakan kemiringan permukaan.
Ini tidak selalu (atau bahkan kemungkinan besar tidak) menunjuk langsung ke titik ekstrem.

Pandangan intuitif adalah membayangkan jalur keturunan yang merupakan jalur melengkung. Lihat misalnya contoh di bawah ini.

Sebagai analogi: Bayangkan saya menutup mata Anda dan menempatkan Anda di suatu tempat di gunung dengan tugas untuk berjalan kembali ke titik ekstrim (rendah). Di bukit, jika Anda hanya memiliki informasi lokal , maka Anda tidak tahu ke arah mana dasar danau akan berada.

Jika Anda dapat menganggap cembung

Maka Anda tahu bahwa hanya ada satu titik ekstrem.
Maka Anda tahu bahwa Anda pasti akan mencapai titik ekstrim selama Anda bergerak ke bawah.
Dan kemudian Anda juga tahu bahwa sudut antara arah penurunan paling curam dan arah optimal selalu paling banyak $\pi/2$ , seperti yang disebutkan Solomonoff's Secret dalam komentar.

Tanpa cembung

Sudut mungkin melebihi $\pi/2$ . Pada gambar di bawah ini ditekankan dengan menggambar panah arah keturunan untuk titik tertentu di mana solusi akhir berada di belakang garis yang tegak lurus dengan arah keturunan.

Dalam masalah cembung ini tidak mungkin. Anda bisa mengaitkan ini dengan isoline untuk fungsi biaya memiliki kelengkungan semua dalam arah yang sama ketika masalahnya cembung.

Dalam Keturunan Gradien Stochastic

Anda mengikuti arah paling curam untuk satu titik (dan Anda berulang kali mengambil langkah untuk titik yang berbeda). Dalam contoh masalahnya adalah cembung, tetapi mungkin ada lebih dari satu solusi. Dalam contoh, nilai ekstrim berada pada garis (bukan titik tunggal), dan dari sudut pandang khusus ini Anda dapat mengatakan bahwa Arah penurunan paling curam, dapat menunjuk langsung ke "optimal" (meskipun hanya optimal untuk fungsi) dari titik sampel pelatihan tertentu)

Di bawah ini adalah pandangan lain untuk empat titik data . Masing-masing dari empat gambar menunjukkan permukaan untuk satu titik berbeda. Setiap langkah titik yang berbeda dipilih sepanjang gradien dihitung. Ini membuat bahwa hanya ada empat arah di mana langkah dibuat, tetapi ukuran langkah berkurang ketika kita semakin dekat dengan solusi.

Gambar di atas adalah untuk 4 titik data yang dihasilkan oleh fungsi:

y_{i} = e^{- 0.4 x_{i}} - e^{- 0.8 x_{i}} + ϵ_{i}

$y_i = e^{-0.4x_i}-e^{-0.8 x_i} + \epsilon_i$

x = 0      2      4      6           
y = 0.006  0.249  0.153  0.098

yang mengakibatkan:

$S (a, b) = \sum_{i = 1} {(y_{i} - (e^{- a x_{i}} - e^{- b x_{i}}))}^{2}$ $S(a,b) = \sum_{i=1} \left( y_i - (e^{-ax_i}-e^{-b x_i}) \right)^2$ $\nabla S (a, b) = [\begin{matrix} \sum_{i = 1} 2 x_{i} e^{- a x_{i}} (y_{i} - e^{- a x_{i}} - e^{- b x_{i}}) \\ \sum_{i = 1} - 2 x_{i} e^{- b x_{i}} (y_{i} - e^{- a x_{i}} - e^{- b x_{i}}) \end{matrix}]$ $\nabla S(a,b) = \begin{bmatrix} \sum_{i=1} 2 x_i e^{-a x_i}\left( y_i - e^{-ax_i}-e^{-b x_i} \right) \\ \sum_{i=1} -2 x_i e^{-b x_i}\left( y_i - e^{-ax_i}-e^{-b x_i} \right) \end{bmatrix}$
$S (a, b) = \sum_{i = 1} {(y_{i} - (a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}))}^{2}$ $S(a,b) = \sum_{i=1} \left( y_i - (a e^{-0.4 x_i}- b e^{-0.8 x_i} )\right)^2$ $\nabla S (a, b) = [\begin{matrix} \sum_{i = 1} - 2 e^{- 0.4 x_{i}} (y_{i} - a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}) \\ \sum_{i = 1} 2 e^{- 0.8 x_{i}} (y_{i} - a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}) \end{matrix}]$ $\nabla S(a,b) = \begin{bmatrix} \sum_{i=1} -2 e^{-0.4x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \\ \sum_{i=1} 2 e^{-0.8x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \end{bmatrix}$
$i$
$S (a, b) = {(y_{i} - (a e^{- 0.4 b x_{i}} - b e^{- 0.8 x_{i}}))}^{2}$ $S(a,b) = \left( y_i - (a e^{-0.4 b x_i}- b e^{-0.8 x_i}) \right)^2$ $\nabla S (a, b) = [\begin{matrix} - 2 e^{- 0.4 x_{i}} (y_{i} - a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}) \\ 2 e^{- 0.8 x_{i}} (y_{i} - a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}) \end{matrix}]$ $\nabla S(a,b) = \begin{bmatrix} -2 e^{-0.4x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \\ 2 e^{-0.8x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \end{bmatrix}$ $a$ $b$ $S = 0$

Ditulis oleh StackExchangeStrike

Sextus Empiricus
sumber

17

Keturunan curam dapat menjadi tidak efisien bahkan jika fungsi objektif sangat cembung.

Keturunan gradien biasa

Maksud saya "tidak efisien" dalam arti bahwa penurunan paling curam dapat mengambil langkah-langkah yang berosilasi liar dari optimal, bahkan jika fungsinya sangat cembung atau bahkan kuadratik.

$f(x)=x_1^2 + 25x_2^2$ $x=[0,0]^\top$

\nabla f (x) = [\begin{matrix} 2 x_{1} \\ 50 x_{2} \end{matrix}]

$\nabla f(x)= \begin{bmatrix} 2x_1 \\ 50x_2 \end{bmatrix}$

$\alpha=0.035$ $x^{(0)}=[0.5, 0.5]^\top,$

x^{(1)} = x^{(0)} - α \nabla f (x^{(0)})

$x^{(1)} =x^{(0)}-\alpha \nabla f\left(x^{(0)}\right)$

yang menunjukkan kemajuan berosilasi liar menuju minimum.

$\theta$ $(x^{(i)}, x^*)$ $(x^{(i)}, x^{(i+1)})$

$x_2$ $x_1$ $\nabla^2 f(x)$

Jalur langsung ke minimum adalah bergerak "secara diagonal" alih-alih dengan cara ini yang sangat didominasi oleh osilasi vertikal. Namun, gradient descent hanya memiliki informasi tentang kecuraman lokal, sehingga "tidak tahu" bahwa strategi akan lebih efisien, dan tunduk pada keanehan Hessian yang memiliki nilai eigen pada skala yang berbeda.

Penurunan gradien stokastik

SGD memiliki sifat yang sama, dengan pengecualian bahwa pembaruannya berisik, menyiratkan bahwa permukaan kontur terlihat berbeda dari satu iterasi ke yang berikutnya, dan karena itu gradiennya juga berbeda. Ini menyiratkan bahwa sudut antara arah langkah gradien dan optimal juga akan memiliki noise - bayangkan saja plot yang sama dengan beberapa jitter.

Informasi lebih lanjut:

Jawaban ini meminjam contoh dan gambar ini dari Neural Networks Design (2nd 2nd.) Bab 9 oleh Martin T. Hagan, Howard B. Demuth, Mark Hudson Beale, Orlando De Jesús.

Sycorax berkata Reinstate Monica
sumber

13

Arah curam lokal tidak sama dengan arah optimal global. Jika ya, maka arah gradien Anda tidak akan berubah; karena jika Anda pergi ke arah optimal Anda selalu, vektor arah Anda akan selalu menunjuk optimal. Tapi, bukan itu masalahnya. Jika itu masalahnya, mengapa repot menghitung gradien Anda setiap iterasi?

senjata
sumber

3

Jawaban lain menyoroti beberapa masalah tingkat konvergensi yang mengganggu untuk GD / SGD, tetapi komentar Anda "SGD akhirnya dapat menyatu ..." tidak selalu benar (mengabaikan komentar penggunaan yang berlebihan tentang kata "bisa" karena sepertinya Anda maksudkan "akan").

(x_{0}, y_{0}) = (1, 0)

$(x_0,y_0)=(1,0)$

α

$\alpha$

f (x, α) = \sqrt{α^{2} - α x} .

$f(x,\alpha)=\sqrt{\alpha^2-\alpha x}.$

(f (x_{0}, α) - y_{0})^{2} = α^{2} - α,

$(f(x_0,\alpha)-y_0)^2=\alpha^2-\alpha,$

β

$\beta$

α_{n + 1} = α_{n} - β (2 α_{n} - 1) = α_{n} - (2 α_{n} - 1) = 1 - α_{n} .

$\alpha_{n+1}=\alpha_n-\beta(2\alpha_n-1)=\alpha_n-(2\alpha_n-1)=1-\alpha_n.$

α = \frac{1}{2}

$\alpha=\frac12$ $p=\frac12$

p

$p$

1 - p

$1-p$

Saya tidak yakin apakah cembung cukup untuk memecah beberapa perilaku buruk yang ada untuk SGD umum, tetapi jika Anda mengizinkan fungsi yang serumit kubik untuk fungsi biaya Anda maka SGD dapat memantul pada subset domain yang padat dan tidak pernah bertemu di mana pun. atau mendekati siklus apa pun.

$\infty$ $\pm\infty$

Satu hal yang menarik tentang keseluruhan situasi adalah bahwa ada banyak fungsi yang tak terhitung banyaknya (seperti SGD) yang mengambil fungsi cembung sewenang-wenang sebagai input dan kemudian mengeluarkan aturan pembaruan yang selalu dengan cepat konvergen ke minimum global (jika ada). Meskipun secara konseptual ada banyak dari mereka, upaya terbaik kami untuk optimasi cembung semua memiliki contoh tandingan patologis. Entah bagaimana gagasan aturan pembaruan sederhana / intuitif / berkinerja bertentangan dengan gagasan aturan pembaruan yang terbukti benar.

Hans Musgrave
sumber

1

β = 1

$\beta=1$

1

Perhatikan bahwa bukti konvergensi SGD mengasumsikan ukuran langkah menurun ...

Jan Kukacka

@ MartijnWeterings Pengamatan yang bagus. Saya kira contoh saya benar-benar menunjukkan arah yang benar. Haruskah saya memperbaruinya dengan contoh 2D yang tidak pernah menunjukkan arah dan penyimpangan yang benar?

Hans Musgrave

β = 1

$\beta=1$

β > 0

$\beta>0$

β

$\beta$

f (x, α) = \sqrt{\frac{α^{2} - α x}{β}} .

$f(x,\alpha)=\sqrt{\frac{\alpha^2-\alpha x}{\beta}}.$

f

$f$

β

$\beta$

2

Mungkin jawaban untuk pertanyaan ini perlu pembaruan cepat. Sepertinya SGD menghasilkan minimum global juga dalam kasus non-cembung (cembung hanya kasus khusus itu):

SGD Konvergen ke Global Minimum In Deep Learning melalui Star-Convex Path, penulis anonim , Makalah dalam tinjauan double-blind di ICLR 2019

https://openreview.net/pdf?id=BylIciRcYQ

Para penulis menetapkan konvergensi SGD ke minimum global untuk masalah optimisasi nonconvex yang umumnya ditemui dalam pelatihan jaringan saraf. Argumen mengeksploitasi dua sifat penting berikut: 1) kehilangan pelatihan dapat mencapai nilai nol (kurang-lebih); 2) SGD mengikuti jalur bintang-cembung. Dalam konteks seperti itu, walaupun SGD telah lama dianggap sebagai algoritma acak, makalah ini mengungkapkan bahwa SGD konvergen secara intrinsik deterministik ke minimum global.

Ini harus diambil dengan sebutir garam sekalipun. Makalah ini masih dalam peninjauan.

Gagasan jalur cembung-bintang memberikan petunjuk tentang ke arah mana gradien akan menunjuk pada setiap iterasi.

Tolga Birdal
sumber

Untuk masalah cembung, apakah gradien dalam Stochastic Gradient Descent (SGD) selalu menunjuk pada nilai ekstrim global?

Jawaban:

Jika Anda dapat menganggap cembung

Tanpa cembung

Dalam Keturunan Gradien Stochastic

Keturunan gradien biasa

Penurunan gradien stokastik