Bagaimana cara menentukan kondisi terminasi untuk gradient descent?

Sebenarnya, saya ingin bertanya kepada Anda bagaimana saya bisa menentukan kondisi terminating untuk gradient descent.

Dapatkah saya menghentikannya berdasarkan jumlah iterasi, yaitu mempertimbangkan nilai parameter untuk, katakanlah, 100 iterasi?

Atau haruskah saya menunggu sedemikian rupa sehingga perbedaan dalam dua nilai parameter 'baru' dan 'lama' sangat kecil untuk urutan katakanlah ? Ini pasti akan memakan banyak waktu. $10^{-6}$

Apakah cara terbaiknya? Dalam kasus saya, bahkan satu iterasi membutuhkan waktu yang signifikan. Dalam situasi ini jika saya menunggu kondisi ke-2 bahkan mungkin butuh berminggu-minggu kurasa.

Jadi pendekatan mana yang harus saya gunakan. Bagaimana cara mengatasi skenario ini?

algorithms optimization gradient-descent pengguna31820
sumber

Itu tidak secara eksplisit dinyatakan, tetapi saya berasumsi bahwa Anda sedang berusaha menemukan MLE. Hasil Anda benar-benar tergantung sepenuhnya pada ruang parameter Anda, fungsi kemungkinan Anda dan kebutuhan Anda (alias, yang terbaik tidak didefinisikan dengan baik). Jika Anda hanya mencari pembenaran teoretis seperti efisiensi asimptotik; dalam kondisi Le'Cam Anda bisa menggunakan MLE satu langkah (Di bawah asumsi lebih lanjut adalah bahwa Anda menggunakan Metode Newton dan fungsi skor untuk penurunan gradien Anda). Ini mensyaratkan bahwa nilai awal Anda sedemikian rupa sehingga dalam probabilitas.

n^{1 / 2} {\hat{θ}}_{0} \to θ

$n^{1/2}\hat{\theta}_0 \rightarrow \theta$

Jonathan Lisic

jadi tunggu, ketika Anda mengatakan "baru" - "lama" cukup kecil, apakah itu kondisi pemutusan yang salah untuk gradient descent? (jika titik tetap seperti teorema berlaku, kondisi itu harusnya ok?)

Charlie Parker

Satu bisa berhenti ketika salah satu dari: nilai fungsi , atau gradien , atau parameter , tampaknya berhenti bergerak, baik relatif atau absolut. Tetapi dalam praktiknya parameter .. terlalu banyak sehingga terlipat, tetapi setiap program melakukannya secara berbeda. Lihat toleransi Mathworks dan kriteria berhenti untuk gambar.

f_{i}

$f_i$

\nabla f_{i}

$\nabla f_i$

x_{i}

$x_i$

3 \times 2

$3 \times 2$ ftolabs ftolrelxtolabs

denis

Pertanyaan yang bagus Saya telah melihat banyak aturan berhenti dalam literatur, dan ada kelebihan dan kekurangan untuk masing-masing, tergantung pada konteksnya. The optimfungsi dalam R, misalnya, memiliki setidaknya tiga aturan berhenti berbeda:

maxit, yaitu jumlah iterasi maksimum yang telah ditentukan. Alternatif lain yang serupa yang saya lihat dalam literatur adalah jumlah detik maksimum sebelum waktu habis. Jika yang Anda butuhkan hanyalah solusi perkiraan, ini bisa menjadi sangat masuk akal. Bahkan, ada kelas model (terutama model linier) yang penghentian awal mirip dengan menempatkan Gaussian sebelum nilai parameter Anda. Seorang frequentist akan mengatakan Anda memiliki "norma L2" daripada yang sebelumnya, tetapi mereka juga akan menganggapnya sebagai hal yang wajar untuk dilakukan. Saya hanya membaca sekilas makalah ini , tetapi ini berbicara tentang hubungan antara berhenti dini dan regularisasi dan mungkin membantu mengarahkan Anda ke informasi lebih lanjut. Tetapi versi singkatnya adalah, ya, berhenti lebih awal bisa menjadi hal yang sangat terhormat untuk dilakukan, tergantung pada apa yang Anda lakukan.
abstol, yaitu, berhenti ketika fungsi mendapat "cukup dekat" ke nol. Ini mungkin tidak relevan untuk Anda (sepertinya Anda tidak mengharapkan nol), jadi saya akan melewatkannya.
reltol, yang seperti saran kedua Anda - berhenti ketika peningkatannya turun di bawah ambang batas. Saya tidak benar-benar tahu berapa banyak teori yang ada tentang ini, tetapi Anda mungkin akan cenderung mendapatkan minima lebih rendah dengan cara ini daripada dengan jumlah iterasi maksimum yang kecil. Jika itu penting bagi Anda, mungkin ada baiknya menjalankan kode untuk iterasi lebih lanjut.

Keluarga lain dari aturan berhenti harus dilakukan dengan mengoptimalkan fungsi biaya pada set data validasi (atau dengan validasi silang) daripada pada data pelatihan. Tergantung pada apa Anda ingin menggunakan model Anda, Anda mungkin ingin berhenti sebelum Anda mencapai minimum lokal pada data pelatihan Anda, karena itu bisa melibatkan overfitting. Saya cukup yakin Trevor Hastie telah menulis tentang cara-cara yang baik untuk melakukan ini, tetapi saya tidak dapat mengingat kutipannya.

Opsi lain yang memungkinkan untuk menemukan minima lebih rendah dalam jumlah waktu yang wajar dapat mencakup:

Stochastic gradient descent, yang hanya memerlukan estimasi gradien untuk sebagian kecil data Anda sekaligus (mis. Satu titik data untuk SGD "murni", atau bets mini kecil).
Fungsi optimisasi yang lebih maju (mis. Metode tipe Newton atau Konjugat Gradien), yang menggunakan informasi tentang kelengkungan fungsi objektif Anda untuk membantu Anda menunjuk ke arah yang lebih baik dan mengambil ukuran langkah yang lebih baik saat Anda bergerak menuruni bukit.
Istilah "momentum" dalam aturan pembaruan Anda, sehingga pengoptimal Anda melakukan pekerjaan yang lebih baik untuk menuruni bukit alih-alih melompati dinding ngarai dalam fungsi tujuan Anda.

Semua pendekatan ini dibahas dalam catatan kuliah yang saya temukan online ini.

Semoga ini membantu!

Sunting oh, dan Anda juga dapat mencoba untuk mendapatkan nilai awal yang lebih baik (misalnya dengan memecahkan versi masalah yang lebih sederhana) sehingga diperlukan lebih sedikit iterasi untuk mendekati optimal dari "permulaan hangat" Anda.

David J. Harris
sumber

masalah dengan memilih jumlah iterasi yang tetap, adalah bahwa kecuali Anda dapat dengan jelas memetakan kurva biaya Anda (dan memiliki noise kecil), maka sulit untuk mengetahui berapa banyak iterasi yang terlalu banyak, khususnya jika fungsi optimasi rumit dan siapa yang tahu berapa banyak minimum lokal yang dimilikinya dan jika Anda memiliki inisialisasi acak, ini semakin memperburuk masalah, karena semakin sulit untuk menebak berapa jumlah iterasi "kecil" yang baik. Bagaimana Anda mengatasi masalah ini dalam kenyataan jika Anda ingin benar-benar menggunakan penghentian dini? Bagaimana Anda memastikan Anda tidak terlalu banyak menembak atau terlalu banyak melakukan undershoot?

Charlie Parker

Saya ingin mengklarifikasi apa reltolartinya (yaitu ketika berhenti menjadi "perbaikan") artinya. Peningkatan pertama berarti penurunan fungsi biaya. Jadi saya akan berasumsi bahwa apa yang Anda maksudkan adalah, ketika fungsi biaya berhenti menurun cukup (atau mulai meningkat) satu berhenti, kan? Seseorang tidak benar-benar melakukan "| lama - baru |" jenis aturan pembaruan, bukan?

Charlie Parker

The abstolparameter hanya masuk akal jika Anda mengambil toleransi gradien dari fungsi biaya, tidak fungsi biaya sendiri. Dalam pengoptimal lokal, nilai gradien adalah nol; tapi bukan nilai fungsinya.

Mario Becerra

"permulaan yang hangat" adalah trik yang sangat cerdas! terima kasih

Mehdi LAMRANI

Bagaimana cara menentukan kondisi terminasi untuk gradient descent?

Jawaban: