Apakah mungkin untuk melatih jaringan saraf tanpa backpropagation?

94

Banyak buku dan tutorial jaringan saraf menghabiskan banyak waktu pada algoritma backpropagation, yang pada dasarnya adalah alat untuk menghitung gradien.

Mari kita asumsikan kita sedang membangun model dengan ~ 10K parameter / bobot. Apakah mungkin untuk menjalankan pengoptimalan menggunakan beberapa algoritma pengoptimalan bebas gradien?

Saya pikir menghitung gradien numerik akan terlalu lambat, tetapi bagaimana dengan metode lain seperti Nelder-Mead, Simulated Annealing atau Algoritma Genetika?

Semua algoritma akan menderita dari minimum lokal, mengapa terobsesi dengan gradien?

Haitao Du
sumber
6
@FranckDernoncourt Saya menafsirkan pertanyaan lain sebagai "mengapa tidak menggunakan teknik optimasi global untuk melatih jaringan saraf?", Sedangkan yang satu ini lebih "mengapa tidak menggunakan pengoptimal bebas derivatif ...".
GeoMatt22
6
Dengan 3 jawaban tervvotasikan, ini sepertinya tidak terlalu luas untuk dijawab oleh saya.
gung
5
Ya, Anda tidak perlu terlalu khawatir tentang Nelder-Mead terjebak pada minimum lokal, karena Anda akan beruntung jika itu berguna di mana saja.
Mark L. Stone
1
BTW, ultra L-BFGS, berikan pusaran. itu mungkin baik, tetapi sangat tidak jelas mungkin tidak ada yang mencobanya di jaringan saraf. Lihat persamaan 2.9 pada hal. 12 (Anda perlu membaca beberapa halaman sebelumnya untuk memahami formula, dari) maths.dundee.ac.uk/nasc/na-reports/NA149_RF.pdf (tidak disebut ultra BFGS di koran), yang kemudian perlu masuk ke versi "L" (memori terbatas) menjadi ultra L-BFGS, bukan ultra BFGS. Versi non-L diletakkan di atas kertas. Ultra BFGS pada dasarnya adalah BFGS yang disiapkan ("hot rod") - bisa lebih cepat, tetapi mungkin sedikit lebih liar.
Mark L. Stone

Jawaban:

80

Dua algoritma pertama yang Anda sebutkan (Nelder-Mead dan Simulated Annealing) umumnya dianggap cukup usang di lingkaran optimisasi, karena ada banyak alternatif yang lebih baik yang keduanya lebih dapat diandalkan dan lebih murah. Algoritma genetika mencakup beragam, dan beberapa di antaranya masuk akal.

Namun, dalam kelas yang lebih luas dari algoritma derivatif-bebas optimasi (DFO), ada banyak yang secara signifikan lebih baik daripada "klasik" ini, karena ini telah menjadi area penelitian aktif dalam beberapa dekade terakhir. Jadi, bisakah beberapa pendekatan baru ini masuk akal untuk pembelajaran yang mendalam?

Makalah yang relatif baru membandingkan keadaan seni adalah sebagai berikut:

Rios, LM, & Sahinidis, NV (2013) Optimalisasi bebas-derivatif: tinjauan algoritma dan perbandingan implementasi perangkat lunak. Jurnal Optimasi Global.

Ini adalah kertas bagus yang memiliki banyak wawasan menarik tentang teknik terbaru. Misalnya, hasilnya jelas menunjukkan bahwa pengoptimal lokal terbaik semua "berbasis model", menggunakan berbagai bentuk pemrograman kuadratik sekuensial (SQP).

Namun, seperti dicatat dalam abstrak mereka, "Kami menemukan bahwa kemampuan semua pemecah ini untuk mendapatkan solusi yang baik berkurang dengan meningkatnya ukuran masalah." Untuk memberikan gambaran tentang angka-angka, untuk semua masalah, pemecah diberi anggaran evaluasi fungsi 2.500, dan ukuran masalah maksimum ~ 300 parameter untuk dioptimalkan. Di luar parameter O [10], sangat sedikit pengoptimal ini berkinerja sangat baik, dan bahkan yang terbaik menunjukkan penurunan kinerja yang nyata ketika ukuran masalah meningkat.

Jadi untuk masalah dimensi yang sangat tinggi, algoritma DFO tidak kompetitif dengan yang berbasis turunan. Untuk memberikan beberapa perspektif, optimasi berbasis PDE (persamaan diferensial parsial) adalah area lain dengan masalah dimensi yang sangat tinggi (misalnya beberapa parameter untuk setiap sel dari grid elemen hingga 3D yang besar). Di dunia ini, " metode adjoint " adalah salah satu metode yang paling banyak digunakan. Ini juga merupakan pengoptimal gradien-turun berdasarkan diferensiasi otomatis dari kode model maju.

Yang paling dekat dengan pengoptimal DFO dimensi tinggi mungkin adalah Ensemble Kalman Filter , yang digunakan untuk mengasimilasi data ke dalam simulasi PDE yang kompleks, misalnya model cuaca. Menariknya, ini pada dasarnya adalah pendekatan SQP, tetapi dengan interpretasi Bayesian-Gaussian (jadi model kuadratik adalah pasti positif, yaitu tidak ada poin pelana). Tetapi saya tidak berpikir bahwa jumlah parameter atau pengamatan dalam aplikasi ini sebanding dengan apa yang terlihat dalam pembelajaran mendalam.

Catatan tambahan (minimum lokal): Dari sedikit yang saya baca tentang pembelajaran mendalam, saya pikir konsensus adalah bahwa itu adalah poin pelana daripada minimum lokal, yang paling bermasalah untuk ruang parameter NN-dimensi tinggi.

Sebagai contoh, ulasan baru - baru ini di Nature mengatakan, "Hasil teoritis dan empiris baru - baru ini sangat menyarankan bahwa minimum lokal secara umum bukan masalah. Sebagai gantinya, lanskap tersebut dikemas dengan sejumlah besar titik pelana di mana gradiennya nol, dan permukaan kurva di sebagian besar dimensi dan kurva di sisanya. "

Kekhawatiran terkait adalah tentang pengoptimalan lokal vs. global (misalnya pertanyaan ini ditunjukkan dalam komentar). Meskipun saya tidak melakukan pembelajaran yang mendalam, dalam pengalaman saya overfitting jelas merupakan masalah yang valid. Menurut pendapat saya, metode optimasi global paling cocok untuk masalah desain teknik yang tidak terlalu bergantung pada data "alami". Dalam masalah Data asimilasi, setiap minima global saat ini bisa dengan mudah mengubah pada penambahan data baru (peringatan: Pengalaman saya adalah terkonsentrasi di masalah geoscience, dimana data umumnya "jarang" relatif terhadap kapasitas model).

Perspektif yang menarik mungkin

O. Bousquet & L. Bottou (2008) Pengorbanan pembelajaran skala besar. NIPS.

yang memberikan argumen semi-teoretis tentang mengapa dan kapan perkiraan optimasi mungkin lebih disukai dalam praktiknya.

Catatan akhir (optimisasi-meta): Walaupun teknik berbasis gradien tampaknya lebih dominan untuk jaringan pelatihan, mungkin ada peran DFO dalam tugas-tugas meta-optimisasi terkait.

Salah satu contohnya adalah penyetelan hyper-parameter. (Menariknya, pengoptimal DFO berbasis model yang sukses dari Rios & Sahinidis dapat dilihat sebagai pada dasarnya memecahkan serangkaian masalah desain-percobaan / permukaan respon .)

Contoh lain mungkin mendesain arsitektur, dalam hal pengaturan lapisan (misalnya jumlah, jenis, urutan, node / lapisan). Dalam konteks optimasi diskrit ini, algoritma gaya genetika mungkin lebih tepat. Perhatikan bahwa di sini saya memikirkan kasus di mana konektivitas ditentukan secara implisit oleh faktor-faktor ini (misalnya, lapisan yang sepenuhnya terhubung, lapisan konvolusional, dll.). Dengan kata lain konektivitas dioptimalkan secara meta secara eksplisit. (Kekuatan koneksi akan jatuh di bawah pelatihan, di mana mis sparsity dapat dipromosikan oleh regularisasi dan / atau aktivasi ReLU ... namun pilihan ini dapat dioptimalkan secara meta.)O[N2]notL1

GeoMatt22
sumber
1
'Ulasan' yang Anda kutip adalah dari pendukung utama jaring saraf; Saya akan mempertanyakan klaim tentang minimum lokal - kritik teoritis terkenal NNs adalah bahwa setiap model kompleks tidak dapat dioptimalkan oleh gradient descent karena akan terjebak dalam minimum lokal. Tidak jelas apakah hanya kesuksesan nns yang dapat diselesaikan dengan latar belakang dan Anda tidak mendengar tentang kegagalan.
seanv507
2
@ GeoMatt22 Divergensi kontras adalah pendekatan khusus terhadap gradien kelas model khusus, yang termasuk dalam RBM. Perlu dicatat bahwa RBM adalah model probabilistik yang menyiratkan jenis distribusi tertentu, di mana gradien estimasi kemungkinan maksimum tidak dapat diterapkan. Jaringan saraf adalah model komputasi, yang dapat digunakan tanpa titik awal probabilistik, misalnya dengan mengoptimalkan kehilangan engsel. Singkat cerita, CD bukanlah sarana umum untuk mengoptimalkan jaringan saraf.
bayerj
2
@ seanv507 Sementara klaim telah dibuat oleh para pendukung utama, ada artikel peer review dari konferensi atas pembelajaran mesin yang mengevaluasi klaim-klaim tersebut dengan teliti, misalnya arxiv.org/abs/1406.2572 . Sekarang, klaim itu diterima secara luas dalam komunitas ML yang lebih luas, sebagian besar karena argumen teoretis superior dan bukti empirisnya. Saya kira argumen ad hominem tidak memadai di sini.
bayerj
1
Saya setuju bahwa teori DL kurang. Anda masih harus mengakui bahwa artikel seperti ini semakin maju. Jika Anda merasa bahwa artikel tersebut menyatakan hasil yang salah dan kesimpulan (seperti "minimum lokal kurang masalah daripada poin saddle") tidak valid, Anda harus melakukan lebih baik daripada menyatakan serangan ad hominem lain, kali ini ditujukan untuk Komunitas ML secara keseluruhan.
bayerj
1
Karya terbaru menunjukkan bahwa dengan inisialisasi acak, gradient descent menyatu ke minimum lokal (bukan titik sadel). Makalah di sini: arxiv.org/abs/1602.04915 dan posting blog di sini: offconvex.org/2016/03/24/saddles-again Di sisi lain, ada (kurang) hipotesis baru-baru ini bahwa dalam jaringan saraf besar, minimum lokal adalah tentang sebagus global, dibahas di sini: stats.stackexchange.com/questions/203288/...
DavidR
12

Ada segala macam algoritma pencarian lokal yang dapat Anda gunakan, backpropagation baru saja terbukti menjadi yang paling efisien untuk tugas yang lebih kompleks secara umum ; ada keadaan di mana pencarian lokal lainnya lebih baik.

Anda dapat menggunakan pendakian bukit secara acak pada jaringan saraf untuk menemukan solusi yang baik dengan cepat, tetapi tidak mungkin untuk menemukan solusi yang mendekati optimal.

Wikipedia (saya tahu, bukan sumber terbesar, tetapi masih) kata

Untuk masalah di mana menemukan optimum global yang tepat kurang penting daripada menemukan optimum lokal yang dapat diterima dalam jumlah waktu yang tetap, anil simulasi mungkin lebih disukai daripada alternatif seperti gradient descent.

sumber

Adapun algoritma genetika, saya akan melihat Backpropagation vs Genetic Algorithm untuk pelatihan Neural Network

Kasus utama yang akan saya buat untuk backprop adalah bahwa ini sangat banyak digunakan dan telah mengalami banyak peningkatan besar . Gambar-gambar ini benar - benar menunjukkan beberapa kemajuan luar biasa untuk backpropagation vanilla.

Saya tidak akan menganggap backprop sebagai satu algoritma, tetapi sebuah kelas algoritma.

Saya juga ingin menambahkan bahwa untuk jaringan saraf, parameter 10k adalah kacang kecil. Pencarian lain akan berhasil, tetapi pada jaringan yang dalam dengan jutaan parameter, ini hampir tidak praktis.

Liam McInroy
sumber
12

Nah, jaringan saraf asli, sebelum revolusi backpropagation di tahun 70-an, "dilatih" dengan tangan. :)

Yang telah dibilang:

Ada "sekolah" pembelajaran mesin yang disebut mesin pembelajaran ekstrim yang tidak menggunakan backpropagation.

Apa yang mereka lakukan adalah membuat jaringan saraf dengan banyak, banyak, banyak node - dengan bobot acak - dan kemudian melatih lapisan terakhir menggunakan kuadrat minimum (seperti regresi linier). Mereka kemudian memangkas jaringan saraf setelahnya atau mereka menerapkan regularisasi pada langkah terakhir (seperti laso) untuk menghindari overfitting. Saya telah melihat ini diterapkan pada jaringan saraf dengan satu lapisan tersembunyi saja. Tidak ada pelatihan, jadi ini sangat cepat. Saya melakukan beberapa tes dan mengejutkan, jaringan saraf ini "dilatih" dengan cara ini cukup akurat.

Kebanyakan orang, setidaknya yang bekerja sama dengan saya, memperlakukan mesin ini dengan belajar "sekolah" dengan cemoohan dan mereka adalah kelompok yang terbuang dengan konferensi mereka sendiri dan seterusnya, tetapi saya benar-benar berpikir itu agak cerdik.


Satu hal lain: dalam backpropagation, ada alternatif yang jarang disebutkan seperti backproagation tangguh , yang diimplementasikan dalam R dalam neuralnetpaket, yang hanya menggunakan besarnya turunan. Algoritma ini dibuat dari kondisi if-else dan bukan aljabar linier. Mereka memiliki beberapa keunggulan dibandingkan backpropagation tradisional, yaitu Anda tidak perlu menormalkan data Anda karena mereka tidak menderita masalah gradien hilang .

Ricardo Cruz
sumber
Cab Anda melakukan (sebagian besar atau semua) spiel di paragraf ke-4 Anda, dan kemudian menggunakan hasilnya sebagai titik awal untuk optimasi berbasis turunan untuk "menyempurnakan".
Mark L. Stone
1
@ MarkL.Stone Saya tidak tahu siapa pun yang telah melakukan backpropagation dengan terlebih dahulu menerapkan regresi linier ke lapisan terakhir. Kedengarannya menarik.
Ricardo Cruz
1
Sejauh yang saya tahu, kontroversi seputar ELM sebagian besar disebabkan oleh aspek etika, bukan implementasi. Schmidt et al sudah menyentuh subjek pada tahun 1992, dengan Feedforward Network mereka dengan bobot acak.
Firebug
3

Anda dapat menggunakan hampir semua algoritma optimasi numerik untuk mengoptimalkan bobot jaringan saraf. Anda juga dapat menggunakan algoritme optimisasi campuran kontinu-diskrit untuk mengoptimalkan tidak hanya bobot, tetapi juga tata letak itu sendiri (jumlah lapisan, jumlah neuron di setiap lapisan, bahkan jenis neuron). Namun tidak ada algoritma optimasi yang tidak menderita "kutukan dimensi" dan optimas lokal dalam beberapa cara

pejalan kaki
sumber
3

Anda juga dapat menggunakan jaringan lain untuk memberi saran bagaimana parameter harus diperbarui.

Ada Decoupled Neural Interfaces (DNI) dari Google Deepmind. Alih-alih menggunakan backpropagation, ia menggunakan jaringan neural lain untuk memprediksi cara memperbarui parameter, yang memungkinkan pembaruan parameter paralel dan asinkron.

Makalah ini menunjukkan bahwa DNI meningkatkan kecepatan pelatihan dan kapasitas model RNN, dan memberikan hasil yang sebanding untuk RNN ​​dan FFNN pada berbagai tugas.


Makalah ini juga mendaftar dan membandingkan banyak metode nonpropagasi lainnya

Model gradien sintetis kami paling analog dengan fungsi nilai yang digunakan untuk kenaikan gradien [2] atau fungsi nilai yang digunakan untuk bootstrap. Sebagian besar pekerjaan lain yang bertujuan untuk menghapus backpropagation melakukannya dengan tujuan melakukan penugasan kredit yang masuk akal secara biologis, tetapi ini tidak menghilangkan pembaruan penguncian antar lapisan. Misalnya propagasi target [3, 15] menghilangkan ketergantungan pada melewatkan gradien antar lapisan, dengan menghasilkan aktivasi target yang harus dipasang. Namun target ini masih harus dihasilkan secara berurutan, menyebar ke belakang melalui jaringan dan lapisan karena itu masih memperbarui- dan mundur terkunci. Algoritme lain menghapus penguncian mundur dengan membiarkan kehilangan atau hadiah disiarkan langsung ke setiap lapisan - misalnya REINFORCE [21] (mengingat semua aktivasi adalah tindakan),1, dan Policy Gradient Coagent Networks [20] - tetapi masih tetap terkunci terkunci karena membutuhkan imbalan yang akan dihasilkan oleh suatu output (atau kritik global). Sementara Pembelajaran Berulang Real-Time [22] atau perkiraan seperti [17] mungkin tampak cara yang menjanjikan untuk menghapus penguncian pembaruan, metode ini membutuhkan mempertahankan gradien penuh (atau perkiraan) dari keadaan saat ini sehubungan dengan parameter. Ini pada dasarnya tidak dapat diskalakan dan juga membutuhkan pengoptimal untuk memiliki pengetahuan global tentang kondisi jaringan. Sebaliknya, dengan membingkai interaksi antara lapisan sebagai masalah komunikasi lokal dengan DNI, kami menghilangkan kebutuhan akan pengetahuan global tentang sistem pembelajaran. Karya-karya lain seperti [4, 19] memungkinkan pelatihan lapisan secara paralel tanpa backpropagation,

dontloo
sumber
2

Selama ini adalah pertanyaan komunitas, saya pikir saya akan menambahkan respons lain. "Back Propagation" hanyalah algoritma gradient descent. Ini melibatkan hanya menggunakan turunan pertama dari fungsi yang satu mencoba untuk menemukan minima atau maxima lokal. Ada metode lain yang disebut metode Newton atau Newton-Raphson yang melibatkan menghitung Hessian dan menggunakan turunan kedua. Ini dapat berhasil dalam kasus di mana gradient descent gagal. Saya diberitahu oleh orang lain yang lebih berpengetahuan daripada saya, dan ya ini adalah permintaan pihak kedua kepada otoritas, bahwa itu tidak digunakan dalam jaring saraf karena menghitung semua turunan kedua terlalu mahal dalam hal perhitungan.

aginensky
sumber