Mengapa dinamika Hamilton lebih baik daripada proposal berjalan acak di MCMC dalam beberapa kasus?

Dalam beberapa kasus, dinamika Hamilton selalu lebih baik daripada random walk dalam algoritma Metropolis. Bisakah seseorang menjelaskan alasannya dengan kata-kata sederhana tanpa terlalu banyak matematika?

Pertama-tama, izinkan saya menyatakan bahwa saya tidak percaya bahwa tingkat penerimaan untuk HMC (Hamiltonian Monte Carlo) selalu lebih tinggi daripada untuk algoritma Metropolis. Seperti dicatat oleh @JuhoKokkala, tingkat penerimaan Metropolis dapat disesuaikan dan tingkat penerimaan yang tinggi tidak berarti algoritma Anda melakukan pekerjaan yang baik untuk mengeksplorasi distribusi posterior. Jika Anda hanya menggunakan distribusi proposal yang sangat sempit (misalnya dengan sangat kecil ), Anda akan mendapatkan tingkat penerimaan yang sangat tinggi, tetapi hanya karena Anda pada dasarnya tetap selalu di tempat yang sama, tanpa menjelajahi distribusi posterior penuh.$T(q|q')=\mathcal{N}(q',\sigma I)$$\sigma$

Apa yang saya pikir Anda benar-benar tanyakan (dan jika saya benar, maka silakan edit pertanyaan Anda sesuai) adalah mengapa Hamiltonian Monte Carlo memiliki (dalam beberapa kasus) kinerja yang lebih baik daripada Metropolis. Dengan "kinerja yang lebih baik" Maksud saya, untuk banyak aplikasi, jika Anda membandingkan rantai yang dihasilkan oleh HMC dengan rantai yang sama panjangnya (jumlah sampel ) yang dihasilkan oleh algoritma Metropolis, rantai HMC mencapai kondisi mantap lebih cepat daripada Rantai Metropolis, menemukan nilai yang lebih rendah untuk kemungkinan log negatif (atau nilai yang serupa, tetapi dalam iterasi yang lebih sedikit), ukuran sampel efektif lebih kecil, autokorelasi sampel meluruh lebih cepat dengan lag, dll.$N$

Saya akan mencoba memberikan ide mengapa itu terjadi, tanpa terlalu banyak membahas detail matematis. Jadi, pertama-tama ingat bahwa algoritma MCMC secara umum berguna untuk menghitung integral dimensi tinggi (harapan) dari suatu fungsi (atau lebih banyak fungsi) sehubungan dengan kepadatan target , terutama ketika kita tidak memiliki cara untuk langsung mencicipi dari kerapatan target:$f$$\pi(q)$

$\mathbb{E}_{\pi}{[f]}=\int_{\mathcal{Q}} f(q)\pi(q)\text{d}q_1\dots\text{d}q_d$

di mana adalah vektor parameter di mana dan bergantung, dan adalah ruang parameter. Sekarang, dalam dimensi tinggi, volume ruang parameter yang memberikan kontribusi paling besar pada integral di atas bukanlah lingkungan mode (yaitu, itu bukan volume sempit di sekitar estimasi MLE ), karena di sini besar, tetapi volumenya sangat kecil.$q$$d$$f$$\pi$$\mathcal{Q}$$\pi(q)$$q$$\pi(q)$

Misalnya, Anda ingin menghitung jarak rata-rata suatu titik dari asal , ketika koordinatnya adalah variabel Gaussian independen dengan nol rata-rata dan varians unit. Kemudian integral di atas menjadi:$q$$\mathbb{R}^d$

$\mathbb{E}_{\pi}{[X]}=\int_{\mathcal{Q}} ||q||(2\pi)^{-d/2}\exp{(-||q||^2/2)}\text{d}q_1\dots\text{d}q_d$

Sekarang, kepadatan target jelas maksimum pada 0. Namun, dengan mengubah untuk koordinat bola dan memperkenalkan, Anda dapat melihat bahwa integrand menjadi proporsional dengan . Fungsi ini jelas maksimum pada jarak tertentu dari titik asal. Wilayah di dalam yang memberikan kontribusi paling besar pada nilai integral disebut set tipikal , dan untuk integral ini set tipikal adalah cangkang bundar jari-jari . r = | | q | | r d - 1 exp ( - r 2 / 2 ) d r Q R a $\pi(q)=(2\pi)^{-d/2}\exp{(-||q||^2/2)}$$r=||q||$$r^{d-1}\exp{(-r^2/2)} \text{d}r$$\mathcal{Q}$$R\propto\sqrt{d}$

Sekarang, orang dapat menunjukkan bahwa, dalam kondisi ideal, rantai Markov yang dihasilkan oleh MCMC pertama kali bertemu ke suatu titik di set yang khas, kemudian mulai menjelajahi seluruh set, dan akhirnya terus mengeksplorasi detail set. Dalam melakukan ini, estimasi MCMC dari ekspektasi menjadi lebih dan lebih akurat, dengan bias dan varians yang berkurang dengan meningkatnya jumlah langkah.

Namun, ketika geometri himpunan tipikal rumit (misalnya, jika memiliki puncak dalam dua dimensi), maka algoritma Metropolis walk-acak standar memiliki banyak kesulitan dalam mengeksplorasi detail "patologis" himpunan. Ini cenderung melompat secara acak "di sekitar" daerah ini, tanpa menjelajahi mereka. Dalam praktiknya, ini berarti bahwa nilai estimasi untuk integral cenderung berosilasi di sekitar nilai yang benar, dan mengganggu rantai pada sejumlah langkah terbatas akan menghasilkan estimasi bias yang buruk.

Hamiltonian Monte Carlo mencoba mengatasi masalah ini, dengan menggunakan informasi yang terdapat dalam distribusi target (dalam gradiennya) untuk menginformasikan proposal titik sampel baru, daripada hanya menggunakan distribusi proposal yang tidak terkait dengan target. Jadi, itulah mengapa kami mengatakan bahwa HMC menggunakan turunan dari target distribusi untuk mengeksplorasi ruang parameter lebih efisien. Namun, gradien dari distribusi target, dengan sendirinya, tidak cukup untuk menginformasikan langkah proposal. Seperti pada contoh jarak rata-rata titik acak dari asal$\mathbb{R}^d$, gradien dari distribusi target, dengan sendirinya, mengarahkan kita ke mode distribusi, tetapi wilayah di sekitar mode tidak selalu merupakan wilayah yang memberikan kontribusi paling besar ke integral di atas, yaitu, itu bukan set khas.

Untuk mendapatkan arah yang benar, dalam HMC kami memperkenalkan seperangkat variabel bantu, yang disebut variabel momentum . Analog fisik dapat membantu di sini. Sebuah satelit yang mengorbit di sekitar sebuah planet, akan tetap berada di orbit yang stabil hanya jika momentumnya memiliki nilai "benar", jika tidak ia akan terseret ke ruang terbuka, atau ia akan terseret ke planet ini dengan gaya tarik gravitasi (di sini berperan gradien dari kepadatan target, yang "menarik" ke arah mode). Dengan cara yang sama, parameter momentum memiliki peran menjaga sampel baru di dalam set tip, daripada membiarkannya melayang ke arah ekor atau ke mode.

Ini adalah ringkasan kecil dari makalah yang sangat menarik oleh Michael Betancourt tentang menjelaskan Hamiltonian Monte Carlo tanpa matematika yang berlebihan. Anda dapat menemukan kertas, yang lebih detail, di sini .

Satu hal yang tidak dibahas dalam makalah dengan cukup detail, IMO, adalah kapan dan mengapa HMC bisa lebih buruk daripada Metropolis yang berjalan secara acak. Ini tidak sering terjadi (dalam pengalaman saya yang terbatas), tetapi itu bisa terjadi. Bagaimanapun, Anda memperkenalkan gradien, yang membantu Anda menemukan jalan Anda di ruang parameter dimensi tinggi, tetapi Anda juga menggandakan dimensi masalah. Secara teori, bisa terjadi perlambatan yang disebabkan oleh peningkatan dimensi mengatasi percepatan yang diberikan oleh eksploitasi gradien. Juga (dan ini tercakup dalam kertas) jika himpunan khas memiliki daerah kelengkungan tinggi, HMC dapat "melampaui", yaitu, ia dapat mulai mengambil sampel titik-titik yang tidak berguna yang sangat jauh di bagian ekor yang tidak berkontribusi apa pun pada harapan. Namun, ini menyebabkan ketidakstabilan integrator symplectic yang digunakan dalam praktik untuk mengimplementasikan HMC secara numerik. Dengan demikian, masalah seperti ini mudah didiagnosis.

Seperti @JuhoKokkala disebutkan dalam komentar, tingkat penerimaan yang tinggi tidak selalu memberikan kinerja yang baik. Tingkat penerimaan Metropolis Hastings dapat ditingkatkan dengan menyusutkan distribusi proposal. Tapi, ini akan menyebabkan langkah yang lebih kecil untuk diambil, membuatnya butuh waktu lebih lama untuk mengeksplorasi target distribusi. Dalam praktiknya, ada tradeoff antara ukuran langkah dan tingkat penerimaan, dan keseimbangan yang tepat diperlukan untuk mendapatkan kinerja yang baik.

Hamiltonian Monte Carlo cenderung mengungguli Metropolis Hastings karena dapat mencapai poin yang lebih jauh dengan probabilitas penerimaan yang lebih tinggi. Jadi, pertanyaannya adalah: mengapa HMC cenderung memiliki probabilitas penerimaan yang lebih tinggi daripada MH untuk poin yang lebih jauh ?

MH kesulitan mencapai titik jauh karena proposal dibuat tanpa menggunakan informasi tentang target distribusi. Distribusi proposal biasanya isotropik (misalnya Gaussian simetris). Jadi, di setiap titik, algoritma mencoba untuk memindahkan jarak acak ke arah acak. Jika jaraknya relatif kecil dibandingkan dengan seberapa cepat distribusi target berubah ke arah itu, ada peluang bagus bahwa kerapatan pada titik saat ini dan baru akan serupa, memberikan setidaknya peluang masuk akal untuk diterima. Pada jarak yang lebih jauh, distribusi target mungkin telah berubah sedikit relatif terhadap titik saat ini. Jadi, kesempatan untuk secara acak menemukan titik dengan kepadatan yang sama atau (semoga) lebih tinggi mungkin buruk, terutama saat dimensionalitas meningkat. Misalnya, jika titik saat ini terletak di punggungan sempit, ada

Sebaliknya, HMC mengeksploitasi struktur target distribusi. Mekanisme proposal dapat dianggap menggunakan analogi fisik, seperti yang dijelaskan dalam Neal (2012). Bayangkan keping meluncur di permukaan berbukit, tanpa gesekan. Lokasi keping mewakili titik saat ini, dan ketinggian permukaan mewakili log negatif dari target distribusi. Untuk mendapatkan titik yang diusulkan baru, keping diberi momentum dengan arah dan besaran acak, dan dinamika kemudian disimulasikan saat meluncur di atas permukaan. Keping akan mempercepat ke arah menurun dan menurun ke arah yang lebih tinggi (bahkan mungkin berhenti dan meluncur kembali ke bawah lagi). Lintasan yang bergerak menyamping di sepanjang dinding lembah akan melengkung ke bawah. Jadi, lanskap itu sendiri memengaruhi lintasan dan menariknya ke arah daerah dengan probabilitas lebih tinggi. Momentum dapat memungkinkan keping untuk puncak bukit kecil, dan juga melampaui lembah kecil. Lokasi keping setelah sejumlah langkah waktu memberikan titik yang diusulkan baru, yang diterima atau ditolak menggunakan aturan Metropolis standar. Mengeksploitasi distribusi target (dan gradiennya) adalah apa yang memungkinkan HMC untuk mencapai titik jauh dengan tingkat penerimaan yang tinggi.

Ini ulasan yang bagus:

Neal (2012) . MCMC menggunakan dinamika Hamiltonian.

Sebagai jawaban longgar (yang sepertinya adalah apa yang Anda cari) metode Hamiltonian memperhitungkan turunan dari kemungkinan log, sedangkan algoritma MH standar tidak.