Apa perbedaan antara Bayesian Optimization (Proses Gaussian) dan Simulasi Annealing dalam praktiknya

8

Kedua proses tampaknya digunakan untuk memperkirakan nilai maksimum dari fungsi yang tidak diketahui, dan keduanya jelas memiliki cara yang berbeda untuk melakukannya.

Namun dalam praktiknya, apakah kedua metode itu pada dasarnya dapat dipertukarkan? Di mana saya ingin menggunakan salah satunya?

https://en.wikipedia.org/wiki/Simulated_annealing

http://www.iro.umontreal.ca/~bengioy/cifar/NCAP2014-summerschool/slides/Ryan_adams_140814_bayesopt_ncap.pdf

Pertanyaan Serupa
Pengoptimalan Bayesian atau gradient descent?

optimization maximum bayesian-optimization jurang289
sumber
Saya tidak berpikir ini cukup lengkap untuk menjadi jawaban, tetapi anil simulasi biasanya memerlukan sejumlah besar evaluasi fungsi untuk menemukan titik di dekat global optimal. Di sisi lain, Bayesian Optimization membangun model di setiap iterasi tetapi membutuhkan evaluasi fungsi yang relatif sedikit. Jadi tergantung pada seberapa mahal fungsi untuk mengevaluasi, Anda lebih suka yang satu karena yang lain akan memiliki waktu dinding yang lebih kecil: Bayesian Optimization dalam kasus di mana fungsi sangat mahal dan anil ketika fungsi relatif murah.
Sycorax berkata Reinstate Monica
@ Scorax Bumping 10 posting pada topik yang kurang lebih sama dalam 10 menit - agak berlebihan kan? Tampaknya tidak, tapi saya tahu.
Mark L. Stone
@ MarkL.Stone Ini lebih-atau-kurang "waktu lambat," (8:00 pada hari Jumat, pada saat pengeditan) yang merupakan waktu yang disukai untuk melakukan ini. Ada utas meta.
Sycorax berkata Reinstate Monica

Jawaban:

8

Simulated Annealing (SA) adalah algoritma yang sangat sederhana dibandingkan dengan Bayesian Optimization (BO). Tidak ada metode yang mengasumsikan cembung dari fungsi biaya dan tidak ada metode yang sangat bergantung pada informasi gradien.

SA merupakan jalan acak yang sedikit terdidik. Solusi kandidat melompati ruang solusi yang memiliki jadwal lompatan tertentu (parameter pendinginan). Anda tidak peduli di mana Anda mendarat sebelumnya, Anda tidak tahu di mana Anda akan mendarat selanjutnya. Ini adalah pendekatan Rantai Markov yang khas. Anda tidak memodelkan asumsi kuat tentang permukaan solusi yang mendasari. Optimasi MCMC telah berjalan jauh dari SA (lihat misalnya Hamiltonian Monte Carlo ) tetapi kami tidak akan memperluas lebih jauh. Salah satu masalah utama dengan SA adalah Anda perlu mengevaluasi banyak kali "cepat". Dan masuk akal, Anda perlu sampel sebanyak mungkin untuk mengeksplorasi sebanyak mungkin negara (mis. Solusi kandidat). Anda hanya menggunakan sedikit informasi gradien (bahwa Anda hampir selalu menerima solusi "lebih baik").

Lihat sekarang di BO. BO (atau regresi Gaussian Proses (GP) yang disederhanakan atas evaluasi fungsi biaya Anda) mencoba melakukan yang sebaliknya dalam hal evaluasi fungsi. Mencoba meminimalkan jumlah evaluasi yang Anda lakukan. Itu membangun model non-parametrik tertentu (biasanya dokter umum) untuk fungsi biaya Anda yang sering mengasumsikan kebisingan. Itu tidak menggunakan informasi gradien sama sekali. BO memungkinkan Anda membangun model informatif fungsi biaya Anda dengan sejumlah kecil evaluasi fungsi. Setelah itu Anda "menanyakan" fungsi yang cocok ini untuk ekstremanya. Sekali lagi iblis ada dalam rinciannya; Anda perlu mengambil sampel secara cerdas (dan menganggap bahwa prior Anda juga setengah masuk akal). Ada pekerjaan di mana untuk mengevaluasi fungsi Anda selanjutnya terutama ketika Anda tahu bahwa fungsi Anda sebenarnya berkembang sedikit dari waktu ke waktu (mis. Di sini ).

Keuntungan yang jelas dari SA daripada BO adalah bahwa di dalam SA sangat mudah untuk menempatkan kendala pada ruang solusi Anda. Misalnya, jika Anda menginginkan solusi non-negatif, Anda hanya perlu membatasi distribusi sampel Anda dalam solusi non-negatif. Hal yang sama tidak begitu langsung dalam BO karena bahkan Anda mengevaluasi fungsi Anda sesuai dengan kendala Anda (katakanlah non-negatif) Anda harus benar-benar menghambat proses Anda juga; Taske ini sementara bukan tidak mungkin lebih terlibat.

Secara umum, seseorang akan lebih suka SA jika fungsi biaya murah untuk dievaluasi dan BO dalam kasus bahwa fungsi biaya mahal untuk dievaluasi. Saya pikir SA perlahan tapi pasti tidak disukai; terutama pekerjaan optimisasi bebas-gradien (mis. NEWQUA , BOBYQA ) menghilangkan salah satu keuntungan utama dalam perbandingan dengan metode gradient descent standar yang tidak harus mengevaluasi turunan. Demikian pula pekerjaan pada MCMC adaptif (mis. Lihat referensi di atas) menjadikannya boros dalam hal optimasi MCMC untuk hampir semua kasus.

usεr11852
sumber
Terima kasih atas jawabannya. Saya melihat bahwa Anda mungkin benar tentang anil yang tidak disukai. Scipy mencabutnya demi basinhopping docs.scipy.org/doc/scipy-0.15.1/reference/generated/…
canyon289
Saya senang bisa membantu. Terima kasih atas tipnya; Saya tidak menyadari perubahan di SciPy.
usεr11852
Kecuali jika kendala benar-benar sulit, apa masalah dengan membatasi kecocokan GP? Tentu saja, ketika Anda "menanyakan" fungsi yang dipasang, Anda melakukan optimasi terbatas. Saya tidak berusaha menjadi sarkastik, saya benar-benar ingin tahu kesulitan apa yang Anda lihat. Sebagai contoh, kendala kesetaraan linear dan ketidaksetaraan harus menjadi sepotong kue. Jika Anda memiliki kendala non-cembung, seperti kendala kesetaraan nonlinier atau kendala integer, itu mungkin termasuk dalam kategori degil saya.
Mark L. Stone
@ MarkL.Stone: Bahkan kendala linier (apalagi yang degil ) dapat mempengaruhi pemasangan dalam dimensi yang lebih tinggi - bahkan jika Anda cocok dengan " sesuatu " Saya akan sangat ragu bahwa cocok ini akan menjadi representasi akurat dari apa yang Anda inginkan. Selain itu, sebagian besar hasil berbasis kontinuitas di balik optimalitas GPR keluar dari jendela ... Hanya untuk memperjelas: Saya belum menggunakan BO secara ekstensif karena selalu terbukti suboptimal untuk masalah yang saya kerjakan. Dengan asumsi metode Quasi-Newton standar gagal, saya akan selalu menganjurkan terlebih dahulu pendekatan derivatif-bebas atau HMC.
usεr11852
Nah, jika saya memiliki kendala, yang saya inginkan adalah fungsi yang pas untuk memenuhi kendala. Percayalah, saya ragu seberapa cocok GP akan menjadi representasi akurat dari apa yang saya inginkan, kendala atau tidak. Kendala yang baik dapat membantu Anda - mereka membatasi hal-hal di mana seharusnya dan menyelamatkan Anda dari membuang waktu di daerah yang buruk. Tentu saja, itu jika diterapkan dengan baik. Bisakah Anda memberikan contoh hasil berdasarkan kontinuitas di balik optimalitas GPR yang keluar jendela ketika ada kendala linier? Sebagai contoh yang valid, lebih baik berada di jendela tanpa kendala.
Mark L. Stone