Apakah ada teknik berbasis gradient descent untuk mencari minimum absolut (maksimum) dari suatu fungsi dalam ruang multidimensi?

11

Saya kenal dengan algoritma gradient descent yang dapat menemukan minimum lokal (maksimum) dari fungsi yang diberikan.

Apakah ada modifikasi keturunan gradien yang memungkinkan untuk menemukan minimum absolut (maksimum), di mana fungsinya memiliki beberapa ekstrema lokal?

Adakah teknik umum, bagaimana cara meningkatkan algoritma yang dapat menemukan ekstrem lokal, untuk menemukan ekstrem absolut?

ds.algorithms approximation-algorithms machine-learning Roma
sumber

Anda mungkin ingin memeriksa Cross Divalidasi atau Tanya Jawab AI yang ditautkan dari FAQ .

Kaveh

Saya pikir itu salah satu kelemahan dari gradient descent - itu bisa macet di ekstrem lokal. Teknik-teknik lain seperti simulasi anil mungkin kurang rentan terhadap ini, tetapi masih tidak dapat membuat jaminan, dari apa yang saya mengerti.

Joe

1

Saya tidak yakin apa yang harus dilakukan 'ruang multidimensi' dengan ini. bahkan sebuah fungsi untuk R dapat memiliki beberapa ekstrema lokal yang akan mengalami masalah dengan pencarian gradien.

Suresh Venkat

Saya cukup yakin ada teorema sepanjang garis bahwa jika fungsi ini kontinu, dan sampel pada titik yang cukup, Anda dapat menjamin bahwa gradient descent akan menemukan minimum global mulai dari beberapa titik. yaitu sesuatu di sepanjang garis algoritma Powell. literatur sangat luas sehingga teorema seperti ini mungkin diterbitkan di suatu tempat, tetapi belum pernah mendengarnya. itu juga membuktikan bahwa optimalisasi lokal dapat mendekati optimum global di bawah pengambilan sampel yang cukup, saat pengambilan sampel meningkat.

vzn

agak terkait lihat juga komentar di sini yang sangat berargumen bahwa NN global atau metode numerik / pendekatan tipe heuristik bukanlah "algoritma perkiraan"

vzn

17

Saya kira Anda berbicara tentang minimisasi tanpa kendala. Pertanyaan Anda harus menentukan apakah Anda sedang mempertimbangkan struktur masalah tertentu. Kalau tidak, jawabannya adalah tidak.

Pertama saya harus menghilangkan mitos. Metode gradient descent klasik (juga disebut curved descent method) bahkan tidak dijamin untuk menemukan minimizer lokal. Itu berhenti ketika telah menemukan titik kritis orde pertama, yaitu, di mana gradien menghilang. Bergantung pada fungsi tertentu yang diperkecil dan titik awal, Anda mungkin berakhir pada titik pelana atau bahkan pada pemaksimal global!

$f(x,y) = x^2 - y^2$ $(x_0,y_0) := (1,0)$ $-\nabla f(1,0) = (-2,0)$ $(0,0)$ $f(x,y) = x^2 - 10^{-16} y^2$ $(0,0)$ $\nabla^2 f(x^*,y^*)$ $-10^{-16}$ $+10^{-16}$

f (x) = {\begin{cases} 1 & if x \leq 0 \\ \cos (x) & if 0 < x < π \\ - 1 & if x \geq π . \end{cases}

$f(x) = \begin{cases} 1 & \text{if } x \leq 0 \\ \cos(x) & \text{if } 0 < x < \pi \\ -1 & \text{if } x \geq \pi. \end{cases}$

$x_0 = -2$

Sekarang hampir semua metode optimasi berbasis gradien menderita karena desain ini. Pertanyaan Anda sebenarnya tentang pengoptimalan global . Sekali lagi, jawabannya adalah tidak, tidak ada resep umum untuk memodifikasi suatu metode untuk menjamin bahwa minimizer global teridentifikasi. Tanyakan kepada diri Anda: jika algoritma mengembalikan nilai dan mengatakan itu adalah minimizer global, bagaimana Anda memeriksa apakah itu benar?

Ada kelas metode dalam optimasi global. Beberapa memperkenalkan pengacakan. Beberapa menggunakan strategi multi-mulai. Beberapa mengeksploitasi struktur masalah, tetapi itu untuk kasus-kasus khusus. Ambil buku tentang optimasi global. Kau akan menikmatinya.

Dominique
sumber

@ Roman: Sangat menyambut.

Dominique

3

Mungkin tidak ada jawaban satu ukuran untuk semua pertanyaan Anda. Tetapi Anda mungkin ingin melihat ke dalam algoritma anil simulasi , atau pendekatan lain yang mengandalkan metode rantai Markov Monte Carlo (MCMC). Ini juga dapat dikombinasikan dengan metode lokal seperti gradient descent.

mrig
sumber

1

ada banyak referensi tentang "optimisasi global jaringan saraf". tekniknya mirip dengan anil simulasi [lihat jawaban lain]. ide dasarnya adalah memulai kembali penurunan gradien jaringan mulai dari banyak titik awal berat yang berbeda, disampel secara acak atau sistematis. setiap hasil dari gradient descent kemudian seperti "sampel". semakin banyak sampel yang diambil, semakin tinggi probabilitas bahwa salah satu sampel adalah optimum global, terutama jika fungsi target "berperilaku baik" dalam arti terus menerus, dapat dibedakan, dan sebagainya.

referensi online

[1] Optimalisasi Global dari Berat Jaringan Saraf Tiruan oleh Hamm et al

[2] Pendekatan optimasi global untuk pelatihan jaringan saraf Voglis / Lagaris

[3] Mengkalibrasi Jaringan Syaraf Tiruan oleh Global Optimization Pinter

[4] Optimalisasi Global dari Jaringan Saraf Tiruan menggunakan Pendekatan Deterministik Hibrid Beliakov

[5] Optimalisasi Global untuk Pelatihan Neural Network Shang / Wah

vzn
sumber

1

Secara umum sulit untuk mengoptimalkan fungsi nonconvex multivariat. Kekerasannya datang dalam berbagai rasa (kriptografi, NP-keras). Salah satu cara untuk melihat ini adalah bahwa model campuran (seperti campuran Guassians atau HMM) sulit dipelajari, tetapi akan mudah (*) jika memungkinkan untuk secara efisien memaksimalkan kemungkinan. Untuk hasil pada kekerasan belajar HMM, lihat http://alex.smola.org/journalclub/AbeWar92.pdf http://link.springer.com/chapter/10.1007%2F3-540-45678-3_36 http: // www.math.ru.nl/~terwijn/publications/icgiFinal.pdf

(*) memodulasi kondisi nondegenerasi dan identifikasi yang biasa

Aryeh
sumber

0

saya harus tidak setuju dengan Dominique. itu ditunjukkan oleh hajek pada pertengahan 1980-an bahwa anil masalah nonconvex dalam kondisi ketat tertentu dijamin untuk mencapai minimum global: http://dx.doi.org/10.1287/moor.13.2.311

Aaron Brick
sumber

2

Mengingat hasil kekerasan yang disebutkan di atas, kondisi tersebut memang harus cukup ketat!

Aryeh

Apakah ada teknik berbasis gradient descent untuk mencari minimum absolut (maksimum) dari suatu fungsi dalam ruang multidimensi?

Jawaban: