Apa alternatif dari Gradient Descent?

46

Gradient Descent memiliki masalah terjebak di Minima Lokal. Kita perlu menjalankan gradient descent kali eksponensial untuk menemukan minimum global.

Adakah yang bisa memberi tahu saya tentang alternatif penurunan gradien seperti yang diterapkan dalam pembelajaran jaringan saraf, bersama dengan pro dan kontra mereka.

Tropa
sumber

Jawaban:

38

Ini lebih merupakan masalah yang harus dilakukan dengan fungsi yang diminimalkan daripada metode yang digunakan, jika menemukan global minimum yang sebenarnya itu penting, maka gunakan metode seperti anil yang disimulasikan . Ini akan dapat menemukan minimum global, tetapi mungkin membutuhkan waktu yang sangat lama untuk melakukannya.

Dalam kasus jaring saraf, minimum lokal tidak selalu menjadi masalah. Beberapa minimum lokal disebabkan oleh kenyataan bahwa Anda bisa mendapatkan model yang identik secara fungsional dengan meng-permutasi unit layer tersembunyi, atau meniadakan input dan bobot output jaringan dll. Juga jika minimum lokal hanya sedikit tidak optimal, maka perbedaan kinerja akan minimal dan jadi itu tidak masalah. Terakhir, dan ini adalah poin penting, masalah utama dalam pemasangan jaringan saraf adalah over-fitting, sehingga secara agresif mencari minimum global dari fungsi biaya cenderung mengakibatkan overfitting dan model yang berkinerja buruk.

Menambahkan istilah regularisasi, misalnya pembusukan berat badan, dapat membantu memperlancar fungsi biaya, yang dapat sedikit mengurangi masalah minimum lokal, dan merupakan sesuatu yang akan saya rekomendasikan sebagai cara untuk menghindari overfitting.

Namun metode terbaik untuk menghindari minima lokal dalam jaringan saraf adalah dengan menggunakan model Proses Gaussian (atau jaringan saraf Fungsi Radial Basis Function), yang memiliki lebih sedikit masalah dengan minima lokal.

Dikran Marsupial
sumber
9
Sangat benar. Masalah tidak menemukan minimum global adalah berlebihan.
bayerj
2
Overfitting terjadi ketika Anda menggunakan banyak parameter dalam suatu model (kasus penggunaan NN khas), itu tidak terkait dengan minimum lokal - setidaknya tidak dengan cara yang jelas. Anda dapat terjebak dalam minimum lokal yang buruk bahkan dengan NN kecil, yaitu dengan sangat sedikit parameter gratis.
carlosayam
1
@DikranMarsupial, Anda dapat memiliki banyak minimum lokal, bahkan dengan parameter model tunggal. Itu tergantung pada bentuk fungsi kerugiannya. Contoh dibuat tetapi sederhana: , di mana adalah tetangga terdekat dan terdekat ke . Sangat mudah untuk melihat ada minimum lokal antara setiap dua poin berturut-turut, yaitu semakin banyak data semakin banyak minimum lokal! Global dicapai antara titik terdekat dalam dataset. Ini ekstrem, saya tahu, tetapi saya telah melihat perilaku serupa memecahkan masalah titik-perubahan. x ( 1 ) , x ( 2 ) ωL(ω)=(x(1)ω)2+(x(2)ω)2x(1),x(2)ω
carlosayam
1
@DikranMarsupial - Saya tidak punya cukup karakter untuk menyelesaikan kalimat saya :) Saya telah melihat perilaku serupa memecahkan masalah titik-perubahan ... menggunakan jaringan saraf. Dalam masalah seperti ini, minimum lokal biasanya buruk; jadi saya tidak setuju bahwa masalah ini berlebihan.
carlosayam
1
@carlosayam "berlebihan" tidak berarti "tidak penting", hanya saja itu adalah masalah dengan jaringan saraf yang umumnya dilebih-lebihkan. Akan selalu ada masalah dengan semua metode pembelajaran, tidak ada obat mujarab untuk semuanya, dan Anda selalu perlu mendiagnosis masalah dengan model apa pun.
Dikran Marsupial
24

Gradient descent adalah algoritma optimasi .

Ada banyak algoritma optimasi yang beroperasi pada jumlah tetap dari nilai-nilai nyata yang berkorelasi ( non-separable ). Kami dapat membaginya secara kasar dalam 2 kategori: pengoptimal berbasis gradien dan pengoptimal bebas derivatif. Biasanya Anda ingin menggunakan gradien untuk mengoptimalkan jaringan saraf dalam pengaturan yang diawasi karena secara signifikan lebih cepat daripada optimasi derivatif-bebas. Ada banyak algoritma optimasi berbasis gradien yang telah digunakan untuk mengoptimalkan jaringan saraf:

  • Stochastic Gradient Descent (SGD) , minibatch SGD, ...: Anda tidak harus mengevaluasi gradien untuk seluruh rangkaian pelatihan tetapi hanya untuk satu sampel atau minibatch sampel, ini biasanya jauh lebih cepat daripada keturunan gradient batch. Minibatch telah digunakan untuk menghaluskan gradien dan memparalelkan maju dan backpropagation. Keuntungan lebih dari banyak algoritma lain adalah bahwa setiap iterasi dalam O (n) (n adalah jumlah bobot di NN Anda). SGD biasanya tidak terjebak di minimum lokal (!) Karena bersifat stokastik.
  • Gradient Konjugat Nonlinear : tampaknya sangat berhasil dalam regresi, O (n), memerlukan gradien batch (karenanya, mungkin bukan pilihan terbaik untuk kumpulan data besar)
  • L-BFGS : tampaknya sangat sukses dalam klasifikasi, menggunakan pendekatan Goni, membutuhkan gradien bets
  • Levenberg-Marquardt Algorithm (LMA) : Ini sebenarnya adalah algoritma optimasi terbaik yang saya tahu. Ini memiliki kekurangan bahwa kompleksitasnya kira-kira O (n ^ 3). Jangan menggunakannya untuk jaringan besar!

Dan ada banyak algoritma lain yang diusulkan untuk optimasi jaringan saraf, Anda bisa google untuk optimasi bebas-Goniak atau v-SGD (ada banyak jenis SGD dengan tingkat pembelajaran adaptif, lihat misalnya di sini ).

Pengoptimalan untuk NN bukan masalah yang dipecahkan! Dalam pengalaman saya, tantangan terbesar adalah tidak menemukan minimum lokal yang baik. Namun, tantangannya adalah keluar dari daerah yang sangat datar, berurusan dengan fungsi kesalahan yang tidak terkondisi dll. Itulah alasan mengapa LMA dan algoritma lain yang menggunakan perkiraan Hessian biasanya bekerja dengan sangat baik dalam prakteknya dan orang-orang mencoba mengembangkan versi stokastik yang menggunakan informasi urutan kedua dengan kompleksitas rendah. Namun, seringkali parameter yang disetel dengan sangat baik untuk minibatch SGD lebih baik daripada algoritma optimasi yang kompleks.

Biasanya Anda tidak ingin mencari yang optimal secara global. Karena itu biasanya memerlukan data pelatihan yang berlebihan.

alfa
sumber
16

Alternatif yang menarik untuk gradient descent adalah algoritma pelatihan berbasis populasi seperti algoritma evolusioner (EA) dan optimasi partikel swarm (PSO). Gagasan dasar di balik pendekatan berbasis populasi adalah bahwa populasi solusi kandidat (vektor bobot NN) dibuat, dan solusi kandidat secara iteratif mengeksplorasi ruang pencarian, bertukar informasi, dan akhirnya melakukan konvergen pada minimal. Karena banyak titik awal (solusi kandidat) digunakan, peluang konvergensi pada minimum global meningkat secara signifikan. PSO dan EA telah terbukti berperforma sangat kompetitif, seringkali (walaupun tidak selalu) mengungguli gradient descent pada masalah pelatihan NN yang kompleks.

anna-earwen
sumber
+1 Patut diingat bahwa mengoptimalkan kriteria pelatihan secara agresif cenderung mengarah pada pemasangan yang berlebihan, kecuali jika langkah-langkah diambil untuk mencegahnya, jadi saya akan menghindari PSO dan EA kecuali kriteria pelatihan mencakup beberapa bentuk regularisasi atau kompleksitas lainnya berdasarkan penalti.
Dikran Marsupial
5
@ anna-earwen, bisakah Anda memberikan beberapa referensi di mana PSO berkinerja kompetitif dibandingkan dengan SGD?
emrea
8

Saya tahu utas ini cukup lama dan yang lain telah melakukan pekerjaan yang bagus untuk menjelaskan konsep-konsep seperti minima lokal, overfitting dll. Namun, ketika OP sedang mencari solusi alternatif, saya akan mencoba untuk berkontribusi satu dan berharap ini akan menginspirasi ide-ide yang lebih menarik.

Idenya adalah untuk mengganti setiap bobot w ke w + t, di mana t adalah angka acak berikut distribusi Gaussian. Output akhir dari jaringan adalah output rata-rata dari semua nilai t yang mungkin. Ini dapat dilakukan secara analitis. Anda kemudian dapat mengoptimalkan masalah dengan gradient descent atau LMA atau metode optimasi lainnya. Setelah optimisasi selesai, Anda memiliki dua opsi. Salah satu opsi adalah untuk mengurangi sigma dalam distribusi Gaussian dan melakukan optimasi lagi dan lagi sampai sigma mencapai 0, maka Anda akan memiliki minimum lokal yang lebih baik (tetapi berpotensi dapat menyebabkan overfitting). Pilihan lain adalah tetap menggunakan yang nomor acak dalam bobotnya, biasanya memiliki properti generalisasi yang lebih baik.

Pendekatan pertama adalah trik optimasi (saya menyebutnya sebagai tunneling convolutional, karena menggunakan konvolusi atas parameter untuk mengubah fungsi target), itu menghaluskan permukaan lanskap fungsi biaya dan menyingkirkan beberapa minimum lokal, dengan demikian membuatnya lebih mudah untuk menemukan minimum global (atau minimum lokal yang lebih baik).

Pendekatan kedua terkait dengan injeksi suara (pada beban). Perhatikan bahwa ini dilakukan secara analitik, artinya hasil akhir adalah satu jaringan tunggal, bukan beberapa jaringan.

Berikut ini adalah contoh output untuk masalah dua-spiral. Arsitektur jaringan adalah sama untuk ketiganya: hanya ada satu lapisan tersembunyi dari 30 node, dan lapisan output adalah linier. Algoritma optimasi yang digunakan adalah LMA. Gambar kiri untuk pengaturan vanila; tengah menggunakan pendekatan pertama (yaitu berulang kali mengurangi sigma ke 0); yang ketiga menggunakan sigma = 2.

Hasil masalah dua-spiral dengan tiga pendekatan

Anda dapat melihat bahwa solusi vanilla adalah yang terburuk, tunneling convolutional melakukan pekerjaan yang lebih baik, dan injeksi noise (dengan tunneling convolutional) adalah yang terbaik (dalam hal properti generalisasi).

Baik tunneling convolutional dan cara analitis injeksi kebisingan adalah ide asli saya. Mungkin mereka adalah alternatif yang mungkin diminati seseorang. Rinciannya dapat ditemukan di makalah saya Menggabungkan Nomor Infinity Jaringan Neural Menjadi Satu . Peringatan: Saya bukan penulis akademis profesional dan makalah ini tidak diulas bersama. Jika Anda memiliki pertanyaan tentang pendekatan yang saya sebutkan, silakan tinggalkan komentar.

Bo Tian
sumber
1

Mesin Pembelajaran Ekstrim Pada dasarnya mereka adalah jaringan saraf di mana bobot yang menghubungkan input ke node tersembunyi ditetapkan secara acak dan tidak pernah diperbarui. Bobot antara node tersembunyi dan output dipelajari dalam satu langkah dengan menyelesaikan persamaan linear (matriks invers).

alex
sumber
0

Ketika datang ke tugas Global Optimization (yaitu berusaha mencari minimum global dari fungsi objektif) Anda mungkin ingin melihat pada:

  1. {vi}
  2. Algoritma Genetika yang menggunakan konsep mutasi, crossover dan seleksi untuk menentukan populasi titik yang akan dievaluasi pada iterasi selanjutnya dari optimasi.
  3. Partikel Swarm Optimization yang mendefinisikan satu set partikel yang "berjalan" melalui ruang mencari minimum.
  4. Optimasi Pengganti yang menggunakanmodel pengganti untuk memperkirakan fungsi tujuan. Metode ini dapat digunakan ketika fungsi objektif mahal untuk dievaluasi.
  5. Multi-objective Optimization (juga dikenal sebagai Pareto optimization ) yang dapat digunakan untuk masalah yang tidak dapat diekspresikan dalam bentuk yang memiliki fungsi objektif tunggal (melainkan vektor tujuan).
  6. Simulated Annealing , yang menggunakan konsep annealing (atau suhu) untuk menukar eksplorasi dan eksploitasi. Ini mengusulkan poin baru untuk evaluasi pada setiap iterasi, tetapi ketika jumlah iterasi meningkat, "suhu" turun dan algoritme menjadi semakin kecil kemungkinannya untuk menjelajahi ruang sehingga "berkumpul" menuju kandidat terbaik saat ini.

Seperti disebutkan di atas, Simulated Annealing, Particle Swarm Optimization dan Genetic Algorithms adalah algoritma optimisasi global yang baik yang menavigasi dengan baik melalui ruang pencarian yang besar dan tidak seperti Gradient Descent yang tidak memerlukan informasi tentang gradien dan dapat digunakan dengan sukses dengan fungsi dan masalah objektif kotak hitam. yang membutuhkan simulasi berjalan.

Tomasz Bartkowiak
sumber