Optimisasi Stokastik

Optimisasi stokastik meminimalkan suatu tujuan menggunakan estimasi gradien atau nilainya yang bising, memperbarui parameter dari subset data acak atau perturbasi acak daripada tujuan yang lengkap dan tepat.

Definition

Optimisasi stokastik adalah keluarga metode iteratif yang memperbarui estimasi parameter menggunakan estimasi acak dan tidak bias dari suatu tujuan atau gradiennya, memungkinkan optimisasi ketika tujuan penuh terlalu mahal untuk dievaluasi atau hanya diamati dengan kebisingan.

Scope

Topik ini mencakup pendekatan stokastik dalam tradisi Robbins-Monro, penurunan gradien stokastik dan varian mini-batch serta momentumnya, jadwal ukuran langkah (tingkat pembelajaran) yang mengontrol konvergensi, pertukaran antara kebisingan dan biaya komputasi, serta jaminan konvergensi. Perannya dalam menyesuaikan model statistik dan pembelajaran mesin berskala besar ditekankan.

Core questions

• Bagaimana estimasi gradien yang bising dapat mendorong konvergensi ke optimum?
• Jadwal ukuran langkah apa yang menjamin konvergensi dalam kerangka Robbins-Monro?
• Bagaimana mini-batching menukar kebisingan dengan biaya komputasi per langkah?
• Mengapa optimisasi stokastik penting untuk kumpulan data yang sangat besar?

Key concepts

• Pendekatan stokastik
• Gradien mini-batch
• Jadwal tingkat pembelajaran
• Estimasi gradien tidak bias
• Peluruhan ukuran langkah
• Konvergensi hampir pasti

Key theories

Pendekatan stokastik

Skema Robbins-Monro menemukan akar fungsi yang tidak diketahui dari pengukuran yang bising dengan mengambil langkah-langkah kecil yang ukurannya berkurang pada tingkat yang ditentukan, konvergen hampir pasti di bawah kondisi pada urutan ukuran langkah.

Metode gradien stokastik

Mengganti gradien penuh dengan estimasi tidak bias dari subset data acak menghasilkan pembaruan murah yang lintasan rata-ratanya menurunkan tujuan, dengan jadwal tingkat pembelajaran menyeimbangkan kecepatan konvergensi terhadap varians kebisingan.

Clinical relevance

Metode gradien stokastik memungkinkan penyesuaian model dengan kumpulan data yang terlalu besar untuk diproses sekaligus, dan merupakan strategi optimisasi dominan untuk melatih jaringan saraf dan regresi berskala besar, di mana penghitungan gradien penuh di setiap langkah akan sangat mahal.

History

Robbins dan Monro memperkenalkan pendekatan stokastik pada tahun 1951 untuk menemukan akar dari observasi yang bising, dan Kiefer serta Wolfowitz mengadaptasinya untuk optimisasi tidak lama setelah itu; ledakan pembelajaran mesin berskala besar menghidupkan kembali ide-ide ini sebagai penurunan gradien stokastik dan banyak varian modernnya.

Key figures

• Herbert Robbins
• Sutton Monro
• Harold Kushner
• Jack Kiefer

Seminal works

• robbins1951
• kushner2003

Frequently asked questions

Mengapa menggunakan gradien yang bising daripada gradien yang tepat?

Menghitung gradien yang tepat di atas jutaan titik data sangat mahal. Gradien yang diperkirakan dari batch acak kecil jauh lebih murah dan, meskipun bising, masih mengarah ke bawah rata-rata, sehingga banyak langkah bising yang murah dapat mengalahkan beberapa langkah yang tepat.

Mengapa ukuran langkah biasanya menyusut seiring waktu?

Mengurangi ukuran langkah meredam kebisingan gradien saat iterasi mendekati optimum, yang merupakan persyaratan kondisi Robbins-Monro untuk konvergensi. Ukuran langkah yang terlalu besar membuat estimasi memantul di sekitar solusi.