Markov Chain Monte Carlo

Markov chain Monte Carlo mengambil sampel dari distribusi target yang kompleks dengan mensimulasikan rantai Markov yang direkayasa untuk memiliki distribusi tersebut sebagai hukum stasioner uniknya.

Definition

Markov chain Monte Carlo adalah keluarga algoritma yang mengestimasi ekspektasi di bawah distribusi probabilitas target dengan menjalankan rantai Markov ergodik yang distribusi stasionernya adalah target dan merata-ratakan suatu fungsi sepanjang jalur rantai tersebut.

Scope

Topik ini mencakup desain kernel transisi dengan distribusi stasioner yang ditentukan, algoritma Metropolis-Hastings dan aturan penerimaannya, Gibbs sampler untuk pembaruan kondisional, diagnostik konvergensi dan burn-in, efek autokorelasi pada varians estimator, dan hubungan antara waktu pencampuran dan biaya komputasi pengambilan sampel.

Core questions

• Bagaimana rantai Markov dibangun untuk memiliki distribusi stasioner yang diinginkan?
• Mengapa aturan penerimaan Metropolis-Hastings menghasilkan hukum stasioner yang benar?
• Bagaimana Gibbs sampler memanfaatkan distribusi kondisional?
• Berapa lama rantai harus berjalan sebelum sampelnya dapat digunakan, dan bagaimana ini dinilai?

Key theories

Konstruksi Metropolis-Hastings

Mengusulkan pergerakan dari kernel arbitrer dan menerimanya dengan probabilitas yang dibangun dari rasio densitas target menghasilkan rantai reversibel yang distribusi stasionernya persis sama dengan target, hanya membutuhkan target hingga konstanta normalisasi.

Rata-rata ergodik dan estimasi Monte Carlo

Karena rantai bersifat ergodik dengan target sebagai hukum stasionernya, rata-rata waktu suatu fungsi sepanjang rantai akan konvergen hampir pasti ke ekspektasi target, membenarkan penggunaan jalur simulasi sebagai sampel.

Clinical relevance

Markov chain Monte Carlo adalah tulang punggung statistika Bayesian modern, fisika statistik, dan pembelajaran mesin, memungkinkan inferensi atas distribusi posterior berdimensi tinggi, fungsi partisi, dan lanskap energi yang tidak dapat diintegrasikan secara analitis; keandalannya bergantung pada rantai dasar yang bercampur cukup cepat.

History

Rantai penerimaan-penolakan berasal dari algoritma Metropolis tahun 1953 untuk fisika statistik, digeneralisasi oleh Hastings pada tahun 1970, dan diadaptasi untuk statistika melalui Gibbs sampler oleh Geman dan Geman pada tahun 1984 serta aplikasi Bayesian yang berpengaruh oleh Gelfand dan Smith sekitar tahun 1990, yang meluncurkan revolusi Bayesian komputasi.

Key figures

• Nicholas Metropolis
• W. Keith Hastings
• Stuart Geman
• Donald Geman

Seminal works

• robertCasella2004
• hastings1970

Frequently asked questions

Mengapa menggunakan rantai Markov untuk mengambil sampel?

Untuk distribusi target berdimensi tinggi atau tidak ternormalisasi, pengambilan sampel langsung tidak mungkin dilakukan; rantai Markov yang konvergen ke target memungkinkan Anda menghasilkan sampel yang bergantung tetapi terdistribusi dengan benar setelah mencapai ekuilibrium.

Apa itu burn-in?

Ini adalah bagian awal dari rantai yang dibuang karena rantai belum konvergen ke distribusi stasionernya, sehingga keadaan awal tersebut akan membiaskan estimasi.