Memaksimalkan fungsi bising yang tidak dikenal

Saya tertarik memaksimalkan fungsi , di mana . $f(\mathbf \theta)$ $\theta \in \mathbb R^p$

Masalahnya adalah saya tidak tahu bentuk analitik fungsi, atau turunannya. Satu-satunya hal yang dapat saya lakukan adalah mengevaluasi fungsi point-wise, dengan memasukkan nilai $\theta_*$ dan mendapatkan estimasi NOISY $\hat{f}(\theta_*)$ pada saat itu. Jika saya mau, saya bisa mengurangi variabilitas estimasi ini, tetapi saya harus membayar biaya komputasi yang meningkat.

Inilah yang saya coba sejauh ini:

Stochastic keturunan paling curam dengan perbedaan yang terbatas: ia dapat bekerja tetapi membutuhkan banyak penyetelan (misalnya urutan kenaikan, faktor penskalaan) dan seringkali sangat tidak stabil.
Simulated annealing: ini bekerja dan dapat diandalkan, tetapi membutuhkan banyak evaluasi fungsi jadi saya merasa sangat lambat.

Jadi saya meminta saran / ide tentang kemungkinan metode optimasi alternatif yang dapat bekerja dalam kondisi ini. Saya menjaga masalah ini seumum mungkin untuk mendorong saran dari bidang penelitian yang berbeda dengan saya. Saya harus menambahkan bahwa saya akan sangat tertarik dengan metode yang dapat memberi saya perkiraan Hessian pada konvergensi. Ini karena saya bisa menggunakannya untuk memperkirakan ketidakpastian parameter $\theta$ . Kalau tidak, saya harus menggunakan perbedaan hingga sekitar maksimum untuk mendapatkan perkiraan.

optimization monte-carlo simulation Jugurtha
sumber

Jika Anda tidak dapat mengatakan sesuatu yang lebih spesifik tentang kebisingan yang terkait dengan output fungsi Anda, saya tidak yakin ada yang lebih canggih daripada simulasi annealing (Anda bahkan harus menyetel ini, sampai batas tertentu), akan membantu.

Aron Ahmadia

Sayangnya saya tidak tahu banyak tentang gangguan acak yang terkait dengan setiap evaluasi fungsi. Penyebarannya tidak diketahui, dan itu bisa menjadi fungsi . Di sisi lain suara-suara yang mempengaruhi evaluasi fungsi berturut-turut adalah independen. Jelas saya berasumsi bahwa varian kebisingan tidak besar, jika tidak maksimalisasi tidak mungkin.

θ

$\theta$

Jugurtha

Di sisi lain anggaplah saya tahu sesuatu tentang distribusi kebisingan, misalnya . Apakah pengetahuan ini membantu saya?

\hat{f} (θ_{*}) \sim N (f (θ_{*}), σ)

$\hat{f}(\theta_*) \sim N(f(\theta_*),\sigma)$

Jugurtha

Sepertinya saya berdiri dikoreksi oleh Prof. Neumaier :)

Aron Ahmadia

Fisikawan di sini, saya menggunakan CMA-ES untuk pembentukan fase optik (mengoptimalkan fase pulsa laser melalui pulseshaper), yang cukup berisik.

tillsten

Jawaban:

Paket Matlab kami SnobFit dibuat tepat untuk tujuan ini. Tidak diperlukan asumsi tentang distribusi kebisingan. Selain itu, nilai-nilai fungsi dapat diberikan melalui file teks, sehingga Anda dapat menerapkannya pada fungsi yang diimplementasikan dalam sistem apa pun yang dapat menulis file teks. Lihat
http://www.mat.univie.ac.at/~neum/software/snobfit/

SnobFit telah dikembangkan untuk aplikasi di mana fungsi yang akan dioptimalkan bahkan tidak ada, dan nilai fungsi (ukuran kualitas manufaktur) diperoleh oleh peralatan khusus yang mahal yang membuat produk sampel dan mengukurnya dengan tangan, menghasilkan sekitar 50 fungsi evaluasi per hari.

Arnold Neumaier
sumber

Terimakasih banyak atas jawaban Anda. Saya sudah mulai membaca artikel Anda mengenai paket SnobFit, dan menurut saya itu sangat menarik. Juga, ketika membaca pengantar artikel Anda, saya menyadari bahwa masalah yang saya hadapi (dalam konteks statistik) cukup sering terjadi dalam matematika industri. Ada banyak sekali literatur yang sama sekali tidak saya sadari. Sebenarnya pendekatan yang saya kerjakan agak mirip dengan pendekatan kuadratik Powell (2002).

Jugurtha

Apakah snobfit bekerja dengan baik dengan 128 derajat kebebasan? Hanya untuk mengetahui itu layak untuk dicoba untuk kasus saya.

tillsten

@tillsten: Tidak ada metode untuk masalah bising yang bekerja dengan baik dengan 128 dof kecuali Anda dapat menghabiskan sejumlah besar nilai fungsi. Anda dapat mencoba VXQR1 kami, yang untuk masalah tidak berisik, tetapi kadang-kadang menangani masalah berisik dengan baik.

Arnold Neumaier

Batas untuk Snobfit adalah sekitar 20 variabel. jika Anda memiliki lebih banyak, Anda perlu memilih oleh kelompok-kelompok akal sehat dari 20 variabel yang sebagian Anda optimalkan pada gilirannya. Atau Anda dapat membiarkan slide beberapa variabel secara bersamaan sehingga dimensi berkurang.

Arnold Neumaier

Ada beberapa teknik optimasi Bayesian yang bisa Anda coba. Paling mudah didasarkan pada proses Gaussian:

Harold J. Kushner. Metode baru untuk menemukan maksimum kurva multipeak sembarang di hadapan kebisingan. Jurnal Teknik Dasar, halaman 86: 97-106, Maret 1964.
J. Mockus. Pendekatan Bayesian untuk optimasi global. Catatan Kuliah di Ilmu Kontrol dan Informasi, 38: 473–481, 1982.
Niranjan Srinivas, Andreas Krause, Sham Kakade, dan Matthias Seeger. Optimalisasi proses Gaussian dalam pengaturan bandit: Tidak ada penyesalan dan desain eksperimental. Dalam Proc. Konferensi Internasional tentang Pembelajaran Mesin (ICML), 2010.
Andreas Krause, Ajit Singh, dan Carlos Guestrin. Penempatan sensor Near-Optimal dalam proses Gaussian: Teori, algoritma yang efisien dan studi empiris. J. Mach. Belajar. Res., 9: 235–284, Juni 2008.

Mereka beroperasi dengan membentuk posterior atas fungsi yang masuk akal memberikan pengamatan sejauh ini, dan menyarankan titik berikutnya untuk dengan cepat mempelajari fungsi serta menemukan global maxima (lihat posting blog saya ).

Keuntungan lain adalah bahwa Anda dapat memperkirakan Hessian dengan maksimal. Namun, Anda perlu menentukan model noise.

Memming
sumber

Algoritma SPSA James Spall (kependekan dari Stochastic Perturbation Simulated Annealing, jika saya ingat dengan benar) telah dirancang untuk masalah seperti ini. Dia memiliki beberapa kertas di mana dia menggunakannya untuk masalah seperti yang Anda gambarkan.

Wolfgang Bangerth
sumber

Saya telah mencoba pendekatan Spall berdasarkan versi stokastik dari penurunan paling curam dan Raphson Newton. Saya mencoba Simulasi Annealing, tetapi bukan versi yang disarankan oleh Spall, saya harus mencobanya. Saya tidak terlalu antusias dengan annealing yang disimulasikan, karena saya tidak bisa mendapatkan perkiraan Hessian pada konvergensi (sementara, misalnya, dengan Staphastic Raphson Newton saya bisa mendapatkan perkiraan ke Hessian "gratis").

Jugurtha