Bagaimana keturunan gradien stokastik dapat menghindari masalah minimum lokal?

Saya tahu bahwa keturunan gradien stokastik memiliki perilaku acak, tetapi saya tidak tahu mengapa.
Apakah ada penjelasan tentang ini?

machine-learning random-variable gradient-descent SunshineAtNoon
sumber

Apa hubungannya pertanyaan Anda dengan judul Anda?

Neil G

Jawaban:

Algoritma stochastic gradient (SG) berperilaku seperti algoritma simulated annealing (SA), di mana tingkat pembelajaran SG terkait dengan suhu SA. Keacakan atau kebisingan yang diperkenalkan oleh SG memungkinkan untuk melarikan diri dari minimum lokal untuk mencapai minimum yang lebih baik. Tentu saja, itu tergantung pada seberapa cepat Anda menurunkan tingkat belajar. Baca bagian 4.2, dari Stochastic Gradient Learning di Neural Networks (pdf) , di mana dijelaskan lebih terinci.

clara
sumber

Jangan membuka Bagian 4.1 dengan baik, di mana teorema kedua adalah untuk kasus fungsi nonconvex yang terbatas, dengan mengatakan itu hanya menyatu (dengan sampel tak terbatas) ke beberapa titik dengan gradien 0. Mungkin tidak minimum global atau bahkan bisa menjadi maksimum . SGD lebih menarik karena alasan yang lebih praktis seperti pembelajaran yang didistribusikan, tidak pasti bahwa itu akan "menghindari" minimum lokal.

nihil

Dalam keturunan gradien stokastik parameter diperkirakan untuk setiap pengamatan, sebagai lawan seluruh sampel dalam keturunan gradien biasa (batch gradient descent). Inilah yang memberinya banyak keacakan. Jalur penurunan gradien stokastik berkeliaran di lebih banyak tempat, dan dengan demikian lebih mungkin untuk "melompat" dari minimum lokal, dan menemukan minimum global (Catatan *). Namun, penurunan gradien stokastik masih bisa terjebak di minimum lokal.

Catatan: Adalah umum untuk menjaga laju pembelajaran tetap konstan, dalam hal ini penurunan gradien stokastik tidak menyatu; itu hanya berkeliaran di sekitar titik yang sama. Namun, jika tingkat pembelajaran menurun dari waktu ke waktu, katakanlah, itu berbanding terbalik dengan jumlah iterasi maka penurunan gradien stokastik akan menyatu.

Akavall
sumber

Tidak benar bahwa keturunan gradien stokastik tidak benar-benar bertemu dan hanya bertanya-tanya di sekitar titik tertentu. Itu akan menjadi kasus jika tingkat pembelajaran tetap konstan. Namun, tingkat pembelajaran cenderung nol karena dengan cara ini, ketika algoritma mendekati minimum fungsi cembung, ia berhenti berosilasi dan bertemu. Kunci bukti konvergensi gradien stokastik adalah kondisi yang dikenakan pada rangkaian tingkat pembelajaran. Lihat persamaan (6) dan (27) dari makalah asli Robbins dan Monro.

clara

Seperti yang telah disebutkan dalam jawaban sebelumnya, penurunan gradien stokastik memiliki permukaan kesalahan yang jauh lebih berisik karena Anda mengevaluasi setiap sampel secara berulang. Saat Anda mengambil langkah menuju global minimum dalam gradient batch batch pada setiap zaman (melewati rangkaian pelatihan), langkah-langkah individual dari gradient descent gradient stochastic Anda tidak harus selalu mengarah ke minimum global tergantung pada sampel yang dievaluasi.

Untuk memvisualisasikan ini menggunakan contoh dua dimensi, berikut adalah beberapa gambar dan gambar dari kelas pembelajaran mesin Andrew Ng.

Penurunan gradien pertama:

masukkan deskripsi gambar di sini

Kedua, penurunan gradien stokastik:

masukkan deskripsi gambar di sini

Lingkaran merah pada gambar yang lebih rendah harus menggambarkan bahwa penurunan gradien stokastik akan "terus memperbarui" di suatu tempat di sekitar minimum global jika Anda menggunakan laju pembelajaran yang konstan.

Jadi, berikut adalah beberapa tips praktis jika Anda menggunakan penurunan gradien stokastik:

1) kocok pelatihan yang ditetapkan sebelum setiap zaman (atau iterasi dalam varian "standar")

2) menggunakan tingkat pembelajaran adaptif untuk "anil" lebih dekat ke minimum global

sumber

Mengapa Anda ingin mengocok set pelatihan sebelum setiap zaman? Algoritma SGD mengambil contoh pelatihan secara acak.

Vladislavs Dovgalecs

Pengocokan pada dasarnya adalah salah satu cara untuk membuatnya mengambil sampel pelatihan secara acak. Dalam implementasi saya, saya biasanya mengocok set pelatihan sebelum setiap zaman dan kemudian hanya for

Hm, di wikipedia, algoritma SGD digambarkan sebagai "tanpa penggantian", namun, Bottou menggambarkannya seperti yang Anda lakukan (Bottou, Léon. "Pembelajaran mesin skala besar dengan penurunan gradien stokastik." Prosiding COMPSTAT'2010. Physica-Verlag HD, 2010. 177-186.), Dan saya pikir di sini saya akan cenderung lebih mempercayai Bottou daripada entri Wikipedia ini.

@xeon Periksa makalah ini , yang berpendapat bahwa pengambilan sampel tanpa penggantian lebih baik. Pemahaman saya adalah bahwa tanpa penggantian cenderung lebih unggul secara empiris, tetapi analisis teoritis tidak tersedia sampai saat ini.

Dougal

@xeon Saya hanya melihat slide PDF saya dari kursus Andrew Ng, dan sepertinya dia menggambarkannya di Wikipedia (varian "tanpa penggantian") tidak seperti Bottou. Saya mengunggah tangkapan layar di sini