Apakah teknik optimasi memetakan ke teknik pengambilan sampel?

Dari setiap algoritma pengambilan sampel generik, seseorang dapat memperoleh suatu algoritma optimasi.

Memang, untuk memaksimalkan fungsi sewenang-wenang , cukup untuk mengambil sampel dari . Untuk cukup kecil, sampel-sampel ini akan mendekati maksimum global (atau maksimum lokal dalam praktik) dari fungsi . $f: \textbf{x} \rightarrow f(\textbf{x})$ $g \sim e^{f/T}$ $T$ $f$

Maksud "sampling" yang saya maksud, menggambar sampel pseudo-acak dari distribusi yang diberi fungsi log-likelihood yang dikenal hingga konstanta. Misalnya, pengambilan sampel MCMC, pengambilan sampel Gibbs, Pengambilan Sampel Balok, dll. Dengan "optimalisasi" yang saya maksud adalah upaya untuk menemukan parameter yang memaksimalkan nilai fungsi yang diberikan.

Apakah mungkin sebaliknya? Mengingat heuristik untuk menemukan fungsi maksimum atau ekspresi kombinatorial, dapatkah kita mengekstraksi prosedur pengambilan sampel yang efisien?

HMC misalnya tampaknya memanfaatkan informasi gradien. Bisakah kita membuat prosedur pengambilan sampel yang mengambil keuntungan dari pendekatan Hessian seperti BFGS? (sunting: rupanya ya: http://papers.nips.cc/paper/4464-quasi-newton-methods-for-markov-chain-monte-carlo.pdf ) Kita dapat menggunakan MCTS dalam masalah kombinatorial, dapatkah kita menerjemahkannya menjadi prosedur pengambilan sampel?

Konteks: kesulitan dalam pengambilan sampel sering kali sebagian besar massa dari distribusi probabilitas terletak di wilayah yang sangat kecil. Ada teknik yang menarik untuk menemukan daerah tersebut, tetapi mereka tidak secara langsung diterjemahkan ke dalam prosedur pengambilan sampel yang tidak memihak.

Sunting: Saya sekarang memiliki perasaan yang tersisa bahwa jawaban untuk pertanyaan itu agak setara dengan kesetaraan kelas kompleksitas #P dan NP, membuat jawabannya cenderung "tidak". Itu menjelaskan mengapa setiap teknik pengambilan sampel menghasilkan teknik optimasi tetapi tidak sebaliknya.

sampling optimization Arthur B.
sumber

Meskipun saya pikir saya memiliki pemahaman konvensional tentang sebagian besar kata dalam pertanyaan ini, saya tidak yakin apa yang didapat setelahnya. Bisakah Anda menyatakan sedikit lebih tepatnya apa yang Anda maksud dengan "pengambilan sampel" dan apa yang sebenarnya akan "dioptimalkan"? Anda tampaknya berasumsi secara implisit bahwa pembaca Anda memikirkan pengaturan tertentu di mana "distribusi" (atau keluarga daripadanya?) Terlibat dan di mana tujuan tertentu diasumsikan, tetapi orang hanya dapat menebak apa yang sebenarnya Anda inginkan ketika Anda membuat pernyataan luas seperti yang muncul dalam paragraf terakhir.

whuber

Arthur B.

Ada pemetaan alami antara Simulated annealing dan MCMC sampling. Ada pemetaan yang kurang langsung antara HMC dan gradient descent (jika Anda menyipitkan mata). Pertanyaan saya adalah apakah ini bisa dibuat lebih sistematis. Kesulitan dalam pengambilan sampel adalah sering bahwa sebagian besar massa dari distribusi probabilitas terletak di wilayah yang sangat kecil. Ada teknik menarik untuk menemukan wilayah ini, tetapi mereka tidak secara langsung menerjemahkan ke dalam prosedur pengambilan sampel yang tidak memihak.

Arthur B.

Harap edit pertanyaan Anda untuk memasukkan klarifikasi ini. Itu penting karena Anda (agak terspesialisasi) menggunakan kata "sampling", meskipun sesuai untuk konteks Anda, berbeda dari apa yang mungkin dipahami banyak pembaca. Juga, penjelasan Anda tentang "optimasi", meskipun benar, tampaknya tidak membantu dalam membuat maknanya dengan cukup tepat di sini: mengkarakterisasi apa "fungsi yang diberikan" itu dan bagaimana hal itu mungkin terkait dengan "pengambilan sampel" akan menjadi tambahan yang berguna.

Whuber

Apakah sekarang lebih baik?

Arthur B.

Apakah teknik optimasi memetakan ke teknik pengambilan sampel?

Jawaban: