detail implementasi praktis dari Bayesian Optimization

8

Saya memberikan Bayesian Optimization, mengikuti Snoek, Larochelle, dan Adams [ http://arxiv.org/pdf/1206.2944.pdf] , menggunakan GPML [ http://www.gaussianprocess.org/gpml/code/matlab / doc /] . Saya telah mengimplementasikan fungsi akuisisi Peningkatan yang Diharapkan yang dijelaskan pada halaman 3, dan saya berasumsi bahwa saya benar bahwa untuk memutuskan ke mana harus mencari query selanjutnya, saya harus mengambil yang memaksimalkan:x

aEI(x;(xn,yn,θ))

Tapi sepertinya saya tidak dapat menemukan panduan tentang apa yang harus dipertimbangkan oleh set kandidat . Secara teoritis, saya ingin mencari yang terbaik di seluruh domain, dan makalah ini ditulis sedemikian rupa sehingga tampaknya menyarankan ini mungkin ("[EI] juga memiliki formulir tertutup di bawah proses Gaussian" ). Tetapi sebagai hal yang praktis, saya perlu menghitung rata-rata dan varian prediktif posterior pada apa pun yang dapat saya pertimbangkan sebelum saya dapat menghitung dan sementara posisi ini memiliki formulir tertutup, saya masih perlu menghitungnya menggunakan aljabar matriks, jadi saya tidak bisa melihat cara untuk berkeliling memilih sekelompok .xxxaEI(x)x

Pertanyaannya: (?? Menengah kecil) apa adalah metode praktis untuk memilih besar set kandidat 's lebih yang saya memaksimalkan EI (atau fungsi akuisisi lainnya)? (Apakah ini ada di koran di suatu tempat dan saya baru saja melewatkannya?)x

Saat ini, saya hanya mengambil set saya saat ini , mengambil sampelnya dengan penggantian 2000 kali, dan kemudian menambahkan beberapa noise Gaussian ke setiap titik. Sepertinya tidak apa-apa, kurasa.xi

stackoverflax
sumber
Saya belum membaca makalah ini, tetapi apakah Anda sudah mempertimbangkan pengambilan sampel dari domain yang diminati menggunakan Desain Hypercube Latin? en.wikipedia.org/wiki/Latin_hypercube_sampling
RustyStatistician
Alternatifnya adalah dengan mem-grid domain (jika mungkin) dan kemudian mengevaluasi setiap titik pada domain grid.
RustyStatistician
Ini adalah saran yang masuk akal, terima kasih! Tidak tahu banyak tentang hypercubes Latin, tetapi domain kotak-kotak yang teratur berarti aljabar Toeplitz dan Kronecker dapat digunakan, yang akan membuat semuanya menyenangkan dan efisien bahkan dengan grid yang sangat besar.
stackoverflax

Jawaban:

6

Normalnya adalah menggunakan pengoptimal global yang Anda suka. Masalahnya adalah bahwa permukaan EI sangat multi-modal dan terputus; Mengoptimalkan fungsi akuisisi ini adalah masalah yang bukan masalah sendiri.

Pilihan umum yang saya lihat di berbagai makalah adalah algoritma DIRECT ; kadang-kadang saya pernah melihat CMA-ES yang merupakan metode canggih dalam optimasi nonlinier. Dalam pengalaman saya untuk bentuk pengoptimalan lainnya, MCS ( Pencarian Koordinat Multi Tingkat ) cenderung bekerja relatif baik. Anda dapat menemukan ulasan pengoptimal global bebas derivatif di sini :

  • Rios dan Sahinidis, "Optimalisasi bebas-derivatif: tinjauan algoritma dan perbandingan implementasi perangkat lunak", Journal of Global Optimization (2013).

Omong-omong, EI bersifat analitis jadi jika mau, Anda juga dapat menghitung gradiennya untuk memandu pengoptimalan, tetapi ini tidak perlu. Teknik yang efektif adalah menjalankan pengoptimal global terlebih dahulu untuk menemukan solusi yang menjanjikan dan kemudian menjalankan pengoptimal lokal untuk memperbaikinya (misalnya, metode kuasi-Newton seperti BFGS, yaitu fminunc di MATLAB; atau fmincon jika Anda memiliki kendala).

Akhirnya, jika kecepatan optimalisasi fungsi akuisisi merupakan faktor (yang bukan merupakan skenario BO "tradisional"), saya telah menemukan hasil yang layak dengan memulai dengan desain Hypercube Latin atau desain urutan Sobol acak-acak, kemudian disempurnakan dengan beberapa langkah dari pengoptimal lokal dari titik terbaik; lihat juga @ user777 komentar. Karena ini bukan skenario BO standar, saya tidak punya referensi khusus yang benar-benar menggunakan metode ini.


Contoh makalah yang merujuk pada DIRECT atau CMA-ES:

  • Calandra, R., Seyfarth, A., Peters, J., & Deisenroth, MP (2015). Optimalisasi Bayesian untuk mempelajari ukuran di bawah ketidakpastian. Sejarah Matematika dan Kecerdasan Buatan, 1-19 ( tautan ).
  • Mahendran, N., Wang, Z., Hamze, F., & Freitas, ND (2012). MCMC adaptif dengan optimasi Bayesian. Dalam Konferensi Internasional tentang Kecerdasan Buatan dan Statistik (hal. 751-760) ( tautan ).
  • Gunter, T., Osborne, MA, Garnett, R., Hennig, P., & Roberts, SJ (2014). Pengambilan sampel untuk inferensi dalam model probabilistik dengan quadrature Bayesian cepat. Dalam Kemajuan dalam sistem pemrosesan informasi saraf (hal. 2789-2797) ( tautan ).

Anda hanya dapat google "Bayesian optimasi" + algoritma optimasi global yang diinginkan, dan Anda akan menemukan banyak makalah. Plus, di hampir setiap makalah lain tentang BO Anda akan menemukan kalimat seperti :

[...] BO biasanya memerlukan pengoptimal global tambahan di setiap iterasi untuk mengoptimalkan fungsi akuisisi. Merupakan kebiasaan dalam literatur BO untuk menggunakan DIECTED RECTangles (DIRECT) untuk menyelesaikan tugas seperti itu. Algoritma optimisasi global lainnya seperti CMA-ES juga dapat diterapkan.

Lacerbi
sumber
Ini sebenarnya mengejutkan bagi saya! Bisakah Anda mengarahkan saya ke makalah optimalisasi Bayesian yang Anda pikirkan yang menggunakan DIRECT atau CMA-ES? Terima kasih.
stackoverflax
Mengapa ini mengejutkan? Ini adalah norma - Anda akan menemukan referensi untuk DIRECT atau pengoptimal global lainnya di hampir setiap kertas BO. Mungkin sangat terkenal di masyarakat sehingga beberapa makalah bahkan tidak repot untuk menyebutkan - itu hanya diberikan begitu saja. Saya menambahkan beberapa referensi dalam komentar utama saya di atas.
lacerbi
Ini belum tentu solusi yang baik , tetapi saya telah menemukan itu bisa lebih murah untuk hanya mengevaluasi EI pada satu set poin sampel menggunakan HyperCubes Latin dalam kasus di mana Anda hanya perlu mendekati minimum tetapi tidak harus di atasnya.
Sycorax berkata Reinstate Monica
@ user777: Ya, jika kecepatan dipertaruhkan, saya telah menggunakan urutan kuasi-acak LH dan Sobol sebagai desain awal (menemukan sedikit keuntungan dengan yang terakhir, tetapi mungkin tergantung pada masalah), dan kemudian menjalankan pengoptimal lokal seperti BFGS dari titik terbaik. Saya akan menambahkan ini ke komentar utama.
lacerbi
Salah satu cara untuk membenarkan sifat ad hoc dari pendekatan LHS adalah bahwa menemukan minimum fungsi stokastik (permukaan) tidak diperlukan karena kesalahan dalam estimasi minimum akan membengkokkan perolehan menit dalam presisi. Ini adalah jawaban yang sangat bagus. Saya senang ada orang lain di sini yang peduli tentang BO. :-)
Sycorax berkata Reinstate Monica