Hamiltonian Monte Carlo: bagaimana memahami proposal Metropolis-Hasting?

9

Saya mencoba memahami pekerjaan dalam Hamiltonian Monte Carlo (HMC), tetapi tidak dapat sepenuhnya memahami bagian ketika kita mengganti integrasi waktu deterministik dengan proposal Metropolis-Hasting. Saya membaca makalah pengantar yang luar biasa A Pengantar Konseptual untuk Hamiltonian Monte Carlo oleh Michael Betancourt, jadi saya akan mengikuti notasi yang sama yang digunakan di dalamnya.

Latar Belakang

Tujuan umum Markov Chain Monte Carlo (MCMC) adalah untuk memperkirakan distribusi dari variabel target .π(q)q

Ide HMC adalah untuk memperkenalkan tambahan "momentum" variabel , dalam hubungannya dengan variabel asli yang dimodelkan sebagai "posisi". Pasangan posisi-momentum membentuk ruang fase yang diperluas dan dapat dijelaskan oleh dinamika Hamilton. Distribusi gabungan dapat ditulis dalam istilah dekomposisi mikrokanonikal:halqπ(q,hal)

π(q,hal)=π(θE|E)π(E) ,

di mana mewakili parameter pada tingkat energi diberikan , juga dikenal sebagai himpunan tipikal . Lihat Gbr. 21 dan Gbr. 22 kertas untuk ilustrasi.θE(q,hal)E

masukkan deskripsi gambar di sini

Prosedur HMC asli terdiri dari dua langkah bergantian berikut:

  • Langkah stokastik yang melakukan transisi acak antara level energi, dan

  • Langkah deterministik yang melakukan integrasi waktu (biasanya diimplementasikan melalui integrasi numerik leapfrog) di sepanjang tingkat energi yang diberikan.

Dalam makalah ini, dikatakan bahwa leapfrog (atau integrator symplectic) memiliki kesalahan kecil yang akan menyebabkan bias numerik. Jadi, alih-alih memperlakukannya sebagai langkah deterministik, kita harus mengubahnya menjadi proposal Metropolis-Hasting (MH) untuk menjadikan langkah ini stokastik, dan prosedur yang dihasilkan akan menghasilkan sampel yang tepat dari distribusi.

L.

Sebuah(qL.,-halL.|q0,hal0)=msayan(1,exp(H(q0,hal0)-H(qL.,-halL.)))

Pertanyaan

Pertanyaan saya adalah:

1) Mengapa modifikasi ini mengubah integrasi waktu deterministik menjadi proposal MH membatalkan bias numerik sehingga sampel yang dihasilkan mengikuti persis target distribusi?

2) Dari sudut pandang fisika, energi dilestarikan pada tingkat energi tertentu. Itu sebabnya kami dapat menggunakan persamaan Hamilton:

dqdt=Hhal,dhaldt=-Hq

H(q0,hal0)H(qL.,-halL.)

cwl
sumber

Jawaban:

7

Lintasan Hamiltonian deterministik berguna hanya karena mereka konsisten dengan distribusi target. Secara khusus, lintasan-lintasan dengan proyek energi tipikal ke daerah-daerah dengan probabilitas tinggi dari target distribusi. Jika kita dapat mengintegrasikan persamaan Hamilton secara tepat dan membangun lintasan Hamilton yang eksplisit maka kita akan memiliki algoritma yang lengkap dan tidak memerlukan langkah penerimaan apa pun .

Sayangnya di luar beberapa contoh yang sangat sederhana, kami tidak dapat mengintegrasikan persamaan Hamilton dengan tepat. Itu sebabnya kita harus membawa integrator symplectic . Integrator symplectic digunakan untuk membangun perkiraan numerik akurasi tinggi untuk lintasan Hamilton yang tepat yang tidak dapat kita pecahkan secara analitis. Kesalahan kecil yang melekat pada integrator symplectic menyebabkan lintasan numerik ini menyimpang dari lintasan yang benar, dan karenanya proyeksi lintasan numerik akan menyimpang jauh dari set khas dari target distribusi. Kita perlu memperkenalkan cara untuk memperbaiki penyimpangan ini.

Implementasi asli Hamiltonian Monte Carlo dianggap sebagai titik akhir dalam lintasan panjang tetap sebagai proposal, dan kemudian menerapkan prosedur penerimaan Metropolis untuk proposal tersebut. Jika lintasan numerik telah mengakumulasi terlalu banyak kesalahan, dan karenanya menyimpang terlalu jauh dari energi awal, maka usulan itu akan ditolak. Dengan kata lain, prosedur penerimaan membuang proposal yang akhirnya memproyeksikan terlalu jauh dari set khas target distribusi sehingga satu-satunya sampel yang kami simpan adalah yang masuk dalam set tip.

Perhatikan bahwa implementasi yang lebih modern yang saya anjurkan dalam makalah Konseptual sebenarnya bukan algoritma Metropolis-Hastings. Mengambil sampel lintasan acak dan kemudian titik acak dari lintasan acak itu adalah cara yang lebih umum untuk memperbaiki kesalahan numerik yang diperkenalkan oleh integrator symplectic. Metropolis-Hastings hanyalah salah satu cara untuk mengimplementasikan algoritma yang lebih umum ini, tetapi pengambilan sampel slice (seperti yang dilakukan dalam NUTS) dan pengambilan sampel multinomial (seperti yang saat ini dilakukan di Stan) bekerja dengan baik jika tidak lebih baik. Tetapi intuisi pada dasarnya sama - kami probabilistically memilih poin dengan kesalahan numerik kecil untuk memastikan sampel yang tepat dari distribusi target.

Michael Betancourt
sumber
H(qL.,-halL.)H(q0,hal0)
1
Ya, tetapi karena bagaimana volume dalam ruang dimensi tinggi bekerja (selalu lebih banyak volume menuju bagian luar permukaan daripada ke bagian dalamnya), lintasan menghabiskan lebih banyak waktu secara eksponensial menyimpang ke energi yang lebih tinggi daripada energi yang lebih rendah. Akibatnya ketika Anda menggabungkan proposal (yang mendukung energi lebih tinggi) dengan penerimaan (yang mendukung energi lebih rendah), Anda memulihkan keseimbangan di sekitar energi awal.
Michael Betancourt