Apakah metode pencarian garis digunakan dalam pembelajaran yang mendalam? Kenapa tidak?

18

Banyak tutorial bicara online tentang gradient descent dan hampir semuanya menggunakan ukuran langkah tetap (tingkat pembelajaran ). Mengapa tidak ada penggunaan pencarian baris (seperti pencarian garis backtracking atau pencarian baris yang tepat)?α

Haitao Du
sumber
5
"Dan hampir semuanya menggunakan ukuran langkah tetap" - apakah Anda yakin? " hyper rate belajar" parameter seharusnya menyesuaikan ukuran langkah dengan kondisi. Algoritma Adam yang sangat populer mengadaptasi ukuran langkah
Aksakal
1
hmm, sebenarnya metode gradien ukuran langkah adaptif telah ada sejak setidaknya 2011, dan mereka bahkan dikutip di halaman keturunan gradien stokastik Wikipedia . Ini bukan berita panas. Bahkan SGD vanilla hampir selalu digunakan dengan tingkat belajar yang berubah dengan jumlah iterasi ( jadwal ). Sekarang, pertanyaan yang sangat bagus adalah: mengapa, bahkan jika ada begitu banyak metode penurunan gradien adaptif, SGD masih mendominasi dunia Deep Learning? Pertanyaannya jauh lebih sepele daripada yang terlihat.
DeltaIV
1
Mundur garis pencarian mencari arah dan kemudian mencari cara untuk mengurangi fungsi. Jadi, kecuali Anda memiliki cara cerdas untuk memilih arah untuk mencari, Anda berada dalam optimasi yang membosankan.
Alex R.
1
Saya tidak melihat bahwa pencarian baris masuk akal untuk SGD (sebagai lawan dari gradient descent [batch]) - jadi saya akan mengatakan itu alasannya.
seanv507
3
Saya menduga alasan mengapa pencarian baris tidak terlalu populer adalah batching dalam gradient descent. Anda mendapatkan batch, lalu menghitung gradien. Tidak masuk akal untuk bolak-balik garis karena kebisingan dalam gradien. Lebih baik terus dengan batch berikutnya sementara mungkin anil ukuran langkah.
Aksakal

Jawaban:

14

Turunan gradien vanilla dapat dibuat lebih andal menggunakan pencarian garis; Saya sudah menulis algoritma yang melakukan ini dan itu membuat algoritma yang sangat stabil (walaupun tidak harus cepat).

Namun, hampir tidak masuk akal untuk melakukan pencarian garis untuk metode gradien stokastik . Alasan saya mengatakan ini adalah bahwa jika kita melakukan pencarian garis berdasarkan meminimalkan fungsi kerugian penuh, kita segera kehilangan salah satu motivasi utama untuk melakukan metode stokastik; kita sekarang perlu menghitung fungsi kerugian penuh untuk setiap pembaruan, yang biasanya memiliki biaya komputasi yang sebanding dengan menghitung turunan penuh pertama. Mengingat bahwa kami ingin menghindari komputasi gradien penuh karena biaya komputasi, tampaknya sangat tidak mungkin bahwa kami ingin baik-baik saja dengan menghitung fungsi kerugian penuh.

Atau, Anda mungkin berpikir untuk melakukan sesuatu seperti pencarian garis berdasarkan pada titik data sampel acak Anda. Namun, ini juga bukan ide yang baik; ini tidak akan memberi tahu Anda apakah Anda telah melangkah terlalu jauh (yang merupakan manfaat utama dari pencarian baris). Misalnya, anggap Anda sedang melakukan regresi logistik. Maka setiap hasil hanyalah 0 atau 1, dan untuk setiap sampel tunggal, kami secara sepele mendapatkan pemisahan sempurna sehingga solusi optimal untuk parameter regresi kami berdasarkan sampel 1 adalah sepele atau oleh efek Hauck Donner. Itu tidak baik.-

EDIT

@DeltaIV menunjukkan bahwa ini juga berlaku untuk mini-batch, bukan hanya sampel individual.

Cliff AB
sumber
4
sangat bagus (+1), tapi saya tidak yakin mengapa dalam contoh terakhir Anda berbicara tentang satu sampel. Saya setuju bahwa menghitung pencarian baris berdasarkan mini-batch tidak masuk akal, tetapi mini-batch masih mengandung 512 sampel (biasanya, dan ketika berbicara tentang ImageNet): tentu saja tidak ada nilai tetap untuk jumlah sampel dalam mini -batch, tapi 1 sampel mini-batch terasa agak ekstrem. Apakah Anda menggunakannya hanya untuk memperjelas maksud Anda, atau apakah saya kehilangan sesuatu?
DeltaIV
2
@DeltaIV: sampel tunggal sebagian besar untuk membuat titik tentang seberapa buruk itu bisa pada masalah yang sangat sederhana Jika kami melakukan batch mini dengan 512 sampel pada regresi logistik dengan 512+ kovariat, kami akan melihat masalah yang sama.
Cliff AB
10

Tutorial berbicara tentang gradient descent mungkin karena itu adalah salah satu algoritma paling sederhana yang digunakan untuk optimasi, sehingga mudah untuk dijelaskan. Karena sebagian besar tutorial semacam itu agak singkat, mereka fokus pada hal-hal sederhana. Setidaknya ada beberapa algoritma optimasi populer di luar keturunan gradien sederhana yang digunakan untuk pembelajaran mendalam. Sebenarnya orang sering menggunakan algoritma yang berbeda dari gradient descent karena mereka biasanya lebih cepat konvergen. Beberapa dari mereka memiliki tingkat belajar yang tidak konstan (misalnya menurun dari waktu ke waktu). Untuk ulasan tentang algoritma tersebut, Anda dapat memeriksa ikhtisar tentang algoritme optimasi penurunan gradien yang dikirim oleh Sebastian Ruder (atau makalah arXived ).

Tim
sumber
2
@DeltaIV: Semua metode mewah "lainnya" dibangun di atas SGD. Masalah utama adalah bahwa metode lain memanfaatkan pengetahuan lokal untuk membuat lompatan yang lebih efisien, bukan hanya titik pengambilan sampel secara acak untuk menghitung gradien aktif. Tetapi SGD sangat sederhana dan cepat, dan itu tidak sepenuhnya mengerikan.
Alex R.
2
@AlexR. intinya bukan SGD yang sederhana dan / atau cepat. Kesederhanaan tidak masalah, karena semua perpustakaan yang layak menerapkan SGD, Adam, AdaGrad dan RMSProp (dan lebih banyak, kadang-kadang). Kecepatan lebih penting lagi, karena waktu yang dihabiskan oleh, misalnya, Adam, untuk menghitung pembaruan tingkat parameter sangat kecil dibandingkan dengan waktu pelatihan keseluruhan model seperti ResNet. Satu-satunya titik adalah bahwa, untuk beberapa alasan kita tidak sepenuhnya mengerti hari ini, SGD menggeneralisasi lebih baik daripada mereka Jadi pada dasarnya jika Anda ingin mengalahkan SOTA, Anda sering dipaksa untuk menggunakannya, atau setidaknya untuk mengubahnya nanti saat pelatihan.
DeltaIV
3
@DeltaIV Sangat menarik. Saya membuka makalah yang Anda tautkan, dan referensi cetakan Wilson et al 2017 untuk klaim bahwa SGD menggeneralisasi lebih baik daripada Adam dll.; jadi ketika Anda mengatakan bahwa itu "terkenal", maksud Anda terkenal sejak sekitar setengah tahun, kan?
Amoeba berkata Reinstate Monica
2
@DeltaIV Terima kasih. Saya sendiri tidak melakukan banyak pembelajaran mendalam, dan saya tidak menyadarinya sama sekali. Kembali pada tahun 2012 atau lebih ketika saya menonton kuliah Hinton's Coursera, dia terutama menganjurkan RMSprop dan dalam 1-2 tahun terakhir kesan saya adalah bahwa semua orang menggunakan Adam (yang menggantikan RMSprop, menurut surat kabar Adam). Ketika saya bermain dengan autoencoder tahun lalu, saya menyadari bahwa Adam bekerja jauh lebih cepat daripada SGD, dan sejak itu saya berasumsi bahwa Adam adalah pilihan default saat ini.
Amuba mengatakan Reinstate Monica
3
@CliffAB Ya, hubungan antara penghentian awal dan regularisasi dapat dilihat dengan jelas untuk kuadrat terkecil, di mana gradient descent beroperasi dalam basis nilai eigen dan nilai eigen kecil adalah yang terakhir untuk konvergen; sedangkan penalti ridge juga menghukum nilai eigen kecil. Sekarang saya hanya melihat sekilas ke Wilson et al. ditautkan di atas, tetapi setidaknya dalam kuadrat terkecilnya contoh SGD vs Adam berbeda tidak dijelaskan oleh penghentian awal dan terlambat. Mereka mengklaim bahwa mereka bertemu dengan solusi yang berbeda.
Amuba kata Reinstate Monica