Keturunan gradien dan banyak metode lain berguna untuk menemukan minimum lokal dalam fungsi biaya. Mereka dapat menjadi efisien ketika fungsi biaya dapat dievaluasi dengan cepat di setiap titik, baik secara numerik atau analitik.

Saya memiliki apa yang bagi saya merupakan situasi yang tidak biasa. Setiap evaluasi fungsi biaya saya mahal. Saya mencoba menemukan serangkaian parameter yang meminimalkan permukaan 3D terhadap permukaan permukaan tanah. Setiap kali saya mengubah parameter, saya perlu menjalankan algoritme terhadap seluruh kohort sampel untuk mengukur efeknya. Untuk menghitung gradien, saya perlu mengubah semua 15 parameter secara independen, artinya saya harus membuat ulang semua permukaan dan membandingkan dengan kohort sampel terlalu banyak kali per gradien, dan pasti terlalu banyak selama optimasi.

Saya telah mengembangkan metode untuk menghindari masalah ini dan saat ini sedang mengevaluasinya, tetapi saya terkejut bahwa saya belum menemukan banyak dalam literatur mengenai evaluasi fungsi biaya yang mahal. Ini membuat saya bertanya-tanya apakah saya membuat masalah lebih sulit daripada itu dan bahwa mungkin ada cara yang lebih baik sudah tersedia.

Jadi pertanyaan saya pada dasarnya adalah ini: Apakah ada yang tahu metode untuk mengoptimalkan fungsi biaya, cembung atau tidak, ketika evaluasi lambat? Atau, apakah saya melakukan sesuatu yang konyol di tempat pertama dengan menjalankan kembali algoritma dan membandingkan terhadap kelompok sampel berkali-kali?

TL; DR

Saya sarankan menggunakan LIPO. Itu terbukti benar dan terbukti lebih baik daripada pencarian acak murni (PRS). Ini juga sangat sederhana untuk diimplementasikan, dan tidak memiliki hyperparameter. Saya belum melakukan analisis yang membandingkan LIPO dengan BO, tetapi harapan saya adalah bahwa kesederhanaan dan efisiensi LIPO menyiratkan bahwa itu akan melebihi kinerja BO.

(Lihat juga: Apa saja kerugian dari optimasi parameter hyper bayesian? )

Optimasi Bayesian

Metode Bayesian Optimization-type membangun model pengganti proses Gaussian untuk menjelajahi ruang parameter. Gagasan utama adalah bahwa tupel parameter yang lebih dekat bersama-sama akan memiliki nilai fungsi yang sama, sehingga asumsi struktur ko-varians di antara titik memungkinkan algoritma untuk membuat tebakan yang mendidik tentang tupel parameter terbaik apa yang paling layak untuk dicoba berikutnya. Strategi ini membantu mengurangi jumlah evaluasi fungsi; pada kenyataannya, motivasi metode BO adalah untuk menjaga agar evaluasi fungsi serendah mungkin seraya "menggunakan seluruh kerbau" untuk membuat tebakan yang baik tentang titik pengujian berikutnya. Ada angka yang berbeda dari prestasi (peningkatan yang diharapkan, peningkatan kuantil yang diharapkan, probabilitas peningkatan ...) yang digunakan untuk membandingkan poin yang akan dikunjungi berikutnya.

Bandingkan ini dengan sesuatu seperti pencarian kotak, yang tidak akan pernah menggunakan informasi apa pun dari evaluasi fungsi sebelumnya untuk menginformasikan ke mana harus pergi berikutnya.

Kebetulan, ini juga merupakan teknik optimisasi global yang kuat , dan karena itu tidak membuat asumsi tentang cembungnya permukaan. Selain itu, jika fungsinya stokastik (katakanlah, evaluasi memiliki beberapa suara acak yang melekat), ini dapat langsung diperhitungkan dalam model GP.

Di sisi lain, Anda harus mencocokkan setidaknya satu dokter umum di setiap iterasi (atau beberapa, memilih yang "terbaik", atau rata-rata atas alternatif, atau metode Bayesian sepenuhnya). Kemudian, model ini digunakan untuk membuat (mungkin ribuan) prediksi, biasanya dalam bentuk optimasi lokal multistart, dengan pengamatan bahwa jauh lebih murah untuk mengevaluasi fungsi prediksi GP daripada fungsi yang dioptimalkan. Tetapi bahkan dengan overhead komputasi ini, itu cenderung menjadi kasus bahwa bahkan fungsi nonconvex dapat dioptimalkan dengan sejumlah panggilan fungsi yang relatif kecil.

Makalah yang banyak dikutip tentang topik ini adalah Jones et al , "Optimalisasi Global Efisien dari Fungsi Kotak Hitam yang Mahal." Tetapi ada banyak variasi pada ide ini.

Pencarian Acak

Bahkan ketika fungsi biayanya mahal untuk dievaluasi, pencarian acak tetap bisa bermanfaat. Pencarian acak sangat mudah diterapkan. Satu-satunya pilihan bagi seorang peneliti untuk membuat adalah menetapkan p probabilitas bahwa Anda ingin hasil Anda terletak pada q kuantil tertentu ; sisanya dihasilkan secara otomatis menggunakan hasil dari probabilitas dasar.$p$ $q$

$q = 0.95$$p=0.95$$100\times (1-q)=5$$n$$q^n = 0.95^n$$1 - 0.95^n$. Menyatukan semuanya, kita miliki

$n \ge 59$

$n=60$$n=60$

Karena Anda memiliki jaminan probabilistik tentang seberapa bagus hasilnya, itu bisa menjadi alat persuasif untuk meyakinkan atasan Anda bahwa tidak perlu melakukan lebih banyak eksperimen.

LIPO dan variannya

Ini adalah kedatangan yang mengasyikkan yang, jika bukan hal baru , tentu baru bagi saya. Ini hasil dengan bergantian antara menempatkan batas informasi pada fungsi, dan pengambilan sampel dari batas terbaik, dan menggunakan perkiraan kuadratik. Saya masih mengerjakan semua detail, tapi saya pikir ini sangat menjanjikan. Ini adalah artikel blog yang bagus , dan makalahnya adalah Cédric Malherbe dan Nicolas Vayatis " Optimalisasi global fungsi Lipschitz ."

$f(x)$$x$

Saya akan mengatakan bahwa standar emas saat ini untuk evaluasi fungsi kotak hitam (sangat) mahal adalah (global) optimasi Bayesian (BO). Sycorax sudah menjelaskan beberapa fitur BO, jadi saya hanya menambahkan beberapa informasi yang mungkin berguna.

Sebagai titik awal, Anda mungkin ingin membaca makalah tinjauan umum ini 1 . Ada juga yang lebih baru [2].

Optimalisasi Bayes telah tumbuh dengan mantap sebagai bidang dalam beberapa tahun terakhir, dengan serangkaian lokakarya khusus (misalnya, BayesOpt , dan lihat video - video ini dari lokakarya Sheffield di BO), karena memiliki aplikasi yang sangat praktis dalam pembelajaran mesin, seperti untuk mengoptimalkan hyper-parameter algoritma ML - lihat misalnya makalah ini [3] dan kotak alat terkait, SpearMint . Ada banyak paket lain dalam berbagai bahasa yang menerapkan berbagai jenis algoritma optimasi Bayesian.

Seperti yang saya sebutkan, persyaratan mendasarnya adalah bahwa setiap evaluasi fungsi sangat mahal, sehingga perhitungan yang terkait dengan BO menambah overhead yang dapat diabaikan. Untuk memberikan rata-rata, BO dapat sangat membantu jika fungsi Anda mengevaluasi dalam urutan menit atau lebih. Anda juga dapat menerapkannya untuk perhitungan yang lebih cepat (mis. Puluhan detik), tetapi tergantung pada algoritma yang Anda gunakan, Anda mungkin harus mengadopsi berbagai perkiraan. Jika fungsi Anda mengevaluasi dalam skala waktu detik , saya pikir Anda mencapai batas penelitian saat ini dan mungkin metode lain mungkin menjadi lebih berguna. Juga, saya harus mengatakan, BO jarang benar-benar kotak hitam dan Anda sering harus mengubah algoritma, kadang - kadang banyak , untuk membuatnya bekerja pada potensi penuh dengan masalah dunia nyata tertentu.

Selain BO, untuk ulasan metode optimisasi bebas turunan umum, Anda dapat melihat ulasan ini [4] dan memeriksa algoritma yang memiliki sifat baik konvergensi cepat. Sebagai contoh, Pencarian Koordinat Bertingkat (MCS) biasanya menyatu dengan sangat cepat ke lingkungan minimum (tidak selalu minimum global, tentu saja). MCS dianggap untuk optimasi global, tetapi Anda dapat membuatnya lokal dengan menetapkan batasan terikat yang sesuai.

Akhirnya, Anda tertarik pada BO untuk fungsi target yang mahal dan berisik , lihat jawaban saya untuk pertanyaan ini .

Referensi:

1 Brochu et al., "Tutorial tentang Optimalisasi Bayesian dari Fungsi Biaya Mahal, dengan Aplikasi untuk Pemodelan Pengguna Aktif dan Pembelajaran Penguatan Hierarkis" (2010).

[2] Shahriari et al., "Mengambil Manusia dari Lingkaran: Tinjauan Bayesian Optimization" (2015).

[3] Snoek et al., "Optimalisasi Bayesian Praktis dari Algoritma Pembelajaran Mesin", NIPS (2012).

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

Saya sendiri tidak tahu algoritmanya, tetapi saya yakin jenis algoritme pengoptimalan yang Anda cari adalah pengoptimalan bebas turunan , yang digunakan saat sasarannya mahal atau berisik .

Misalnya, lihat makalah ini (Björkman, M. & Holmström, K. "Optimalisasi Global dari Fungsi Nonconvex yang Mahal Menggunakan Fungsi Radial Basis." Optimasi dan Rekayasa (2000) 1: 373. doi: 10.1023 / A: 1011584207202) abstrak yang sepertinya mengindikasikan ini persis seperti yang Anda inginkan:

Makalah ini mempertimbangkan optimalisasi global dari fungsi objektif yang mahal, yaitu masalah menemukan minimum global ketika ada beberapa minimum lokal dan masing-masing nilai fungsi membutuhkan waktu CPU yang cukup untuk menghitung. Masalah seperti itu sering muncul dalam aplikasi industri dan keuangan, di mana nilai fungsi bisa merupakan hasil dari simulasi atau optimasi komputer yang menghabiskan waktu. Derivatif paling sering sulit diperoleh, dan algoritma yang disajikan tidak menggunakan informasi tersebut.

Anda tidak sendiri.

Sistem mahal untuk mengevaluasi sangat umum dalam rekayasa, seperti model metode elemen hingga (FEM) dan model dinamika fluida komputasional (CFD). Optimalisasi model mahal komputasi ini sangat diperlukan dan menantang karena algoritma evolusioner sering membutuhkan puluhan ribu evaluasi masalah yang bukan merupakan pilihan untuk masalah mahal untuk mengevaluasi. Untungnya, ada banyak metode (algoritma) yang tersedia untuk menyelesaikan masalah ini. Sejauh yang saya tahu, kebanyakan dari mereka didasarkan pada model pengganti (metamodel). Beberapa tercantum di bawah ini.

• Efficient Global Optimization (EGO) [1]. Algoritma EGO telah disebutkan di atas dan mungkin merupakan algoritma optimasi berbasis pengganti yang paling terkenal. Ini didasarkan pada model Kriging dan kriteria pengisi yang disebut fungsi perbaikan yang diharapkan (EI). Paket R termasuk algoritma EGO adalah DiceOptim dan DiceKriging.
• Metode Mode-mengejar sampel (MPS) [2]. Algoritma MPS dibangun pada model RBF dan strategi sampling adptive digunakan untuk mengambil poin kandidat. Kode MATLAB dipublikasikan oleh penulis di http://www.sfu.ca/~gwa5/software.html . Algoritma MPS mungkin memerlukan lebih banyak evaluasi untuk mendapatkan yang optimal, tetapi dapat menangani masalah yang lebih rumit daripada algoritma EGO dari pengalaman pribadi saya.
• Ensemble model pengganti oleh Juliane Müller [3]. Dia menggunakan beberapa pengganti untuk meningkatkan kemampuan pencarian. Toolbox MATLAB MATSuMoTo tersedia di https://github.com/Piiloblondie/MATSuMoTo .

Dalam musim panas, algoritme pengoptimalan berbasis pengganti ini mencoba menemukan optimum global masalah menggunakan sesedikit mungkin evaluasi. Hal ini dicapai dengan memanfaatkan sepenuhnya informasi yang diberikan oleh pengganti (surrogate). Ulasan tentang pengoptimalan masalah yang relatif mahal ada di [4-6].

Referensi:

1. DR Jones, M. Schonlau, dan WJ Welch, "Optimalisasi global yang efisien dari fungsi kotak hitam yang mahal," Journal of Global Optimization, vol. 13, hlm. 455-492, 1998.
2. L. Wang, S. Shan, dan GG Wang, "Metode pengambilan sampel mode untuk optimasi global pada fungsi kotak hitam yang mahal," Rekayasa Optimasi, vol. 36, hlm. 419-438, 2004.
3. J. Müller, "Algoritma Model Pengganti untuk Masalah Optimalisasi Global Black-Box Komputasi Mahal," Universitas Teknologi Tampere, 2012.
4. GG Wang dan S. Shan, "Tinjauan teknik metamodeling dalam mendukung optimasi desain teknik," Journal of Mechanical Design, vol. 129, hlm. 370-380, 2007.
5. AI Forrester dan AJ Keane, "Kemajuan terbaru dalam optimasi berbasis pengganti," Kemajuan dalam Ilmu Aerospace, vol. 45, hlm. 50-79, 2009.
6. FAC Viana, TW Simpson, V. Balabanov, dan V. Toropov, "Metamodeling dalam Optimalisasi Desain Multidisiplin: Seberapa Jauh Kita Datang?", "Jurnal AIAA, vol. 52, hlm. 670-690, 2014/04/01 2014.

Dua strategi sederhana yang berhasil saya gunakan di masa lalu adalah:

1. Jika memungkinkan, cobalah untuk menemukan fungsi pengganti yang lebih sederhana yang mendekati evaluasi fungsi biaya penuh Anda - biasanya model analitis yang menggantikan simulasi. Optimalkan fungsi yang lebih sederhana ini. Kemudian validasi dan sesuaikan solusi yang dihasilkan dengan fungsi biaya tepat Anda.
2. Jika memungkinkan, cobalah untuk menemukan cara untuk mengevaluasi tepat "delta-biaya" fungsi - yang tepat sebagai lawan menjadi pendekatan dari menggunakan gradien. Yaitu, dari titik 15 dimensi awal di mana Anda memiliki biaya penuh yang dievaluasi, temukan cara untuk menurunkan bagaimana biaya akan berubah dengan membuat perubahan kecil menjadi satu (atau beberapa) dari 15 komponen dari titik Anda saat ini. Anda perlu mengeksploitasi properti lokalisasi dari gangguan kecil jika ada dalam kasus khusus Anda dan Anda mungkin perlu menentukan, menyimpan, dan memperbarui variabel status internal di sepanjang jalan.

Strategi-strategi itu sangat spesifik untuk kasus, saya tidak tahu apakah itu dapat diterapkan dalam kasus Anda atau tidak, maaf jika tidak. Keduanya dapat diterapkan (seperti dalam kasus penggunaan saya): menerapkan strategi "biaya-delta" untuk model analitis yang lebih sederhana - kinerja dapat meningkat dengan beberapa urutan besaran.

Strategi lain adalah dengan menggunakan metode urutan kedua yang biasanya cenderung mengurangi jumlah iterasi (tetapi setiap iterasi lebih kompleks) - misalnya, algoritma Levenberg-Marquardt . Tetapi mengingat Anda sepertinya tidak memiliki cara untuk secara langsung dan efisien mengevaluasi gradien, ini mungkin bukan pilihan yang layak dalam kasus ini.

Seperti yang disebutkan orang lain, model pengganti (juga disebut permukaan respon) adalah pendekatan yang kuat. Menurut pendapat saya, satu hal penting yang dilupakan orang adalah Anda dapat melakukan beberapa evaluasi fungsi secara paralel , jika menggunakan CPU multicore.

Saya sarankan melihat kode ini , ia menggunakan model respons sederhana, tetapi skala pada multicore CPU, yang memberikan kecepatan sama dengan jumlah core yang digunakan. Matematika di balik metode ini dijelaskan dalam makalah ini .

Ada banyak trik yang digunakan dalam penurunan gradien stokastik yang dapat juga diterapkan pada evaluasi fungsi objektif. Gagasan keseluruhan mencoba mendekati fungsi tujuan menggunakan subset data .

Jawaban saya dalam dua tulisan ini membahas mengapa penurunan gradien stokastik bekerja: intuisi di baliknya adalah perkiraan gradien menggunakan subset data.

Bagaimana penurunan gradien stokastik dapat menghemat waktu dibandingkan dengan penurunan gradien standar?

Bagaimana menjalankan regresi linier secara paralel / terdistribusi untuk pengaturan data besar?

Trik yang sama berlaku untuk fungsi tujuan.

$\|Ax-b\|^2$$A$$A$$b$