Markov Chain Monte Carlo (MCMC): Mengambil Sampel Distribusi Probabilitas yang Kompleks

Beberapa distribusi probabilitas terlalu kompleks untuk langsung Anda gunakan.

Saat Anda memodelkan data dunia nyata, perhitungan matematis sering kali mentok sebelum menghasilkan sesuatu yang berguna. Sering terjadi integral tampak mudah di atas kertas, tetapi menjadi tak terpecahkan begitu Anda menambahkan beberapa variabel laten. Ini sangat umum dalam inferensi Bayesian, ketika distribusi posterior menggabungkan keyakinan awal Anda dengan data yang diamati—dan hasilnya tidak dapat diringkas dengan rumus sederhana.

Gagasan dasar Markov Chain Monte Carlo adalah alih-alih langsung mengerjakan matematikanya, MCMC menelusuri distribusi melalui simulasi. Ia menghasilkan sampel yang merefleksikan bentuk distribusi tanpa perlu menghitungnya secara penuh.

Dalam artikel ini, saya akan membahas konsep inti di balik MCMC, menelusuri algoritme yang paling umum, dan menunjukkan cara menggunakannya di Python.

Apakah Anda perlu penyegaran matematika Python? Baca posting blog Mengungkap Konsep Matematika untuk Deep Learning kami untuk melihat penerapan matematika di Numpy.

Apa Itu Markov Chain Monte Carlo?

Markov Chain Monte Carlo (MCMC) adalah keluarga algoritme yang menghasilkan sampel dari distribusi probabilitas—bahkan ketika distribusi tersebut terlalu kompleks untuk digunakan secara langsung.

Namanya terbagi menjadi dua bagian. Rantai Markov mengendalikan bagaimana algoritme bergerak melalui kemungkinan keadaan. Setiap langkah hanya bergantung pada posisi Anda saat ini, bukan pada seluruh riwayat bagaimana Anda sampai di sana. Bagian Monte Carlo berarti Anda menggunakan pengambilan sampel acak untuk mengestimasi kuantitas yang diminati.

Jika digabungkan, MCMC membangun rantai sampel acak yang seiring waktu merefleksikan bentuk distribusi target Anda. Ini pada dasarnya adalah teknik sampling. Anda tidak menyelesaikan matematika secara tepat, hanya mendekatinya melalui simulasi.

Mengapa Markov Chain Monte Carlo Diperlukan

Masalah dengan distribusi data dunia nyata adalah distribusinya tidak serapi yang ada di buku teks.

Dalam inferensi Bayesian, Anda sering mencoba menghitung distribusi posterior—probabilitas terbaru dari parameter model Anda setelah melihat data. Rumusnya terlihat mudah di atas kertas: cukup kalikan prior dengan likelihood, lalu bagi dengan marginal likelihood. Istilah terakhir mengharuskan integrasi atas semua kemungkinan nilai parameter. Dalam dimensi tinggi, integral itu praktis mustahil dihitung.

Keadaannya semakin buruk saat model Anda bertambah besar. Ketika Anda menambah parameter atau variabel laten, perhitungan eksak menjadi jalan buntu. Anda akan menemui hal ini di berbagai skenario umum:

• Model hierarkis Bayesian: Ketika parameter bergantung pada parameter lain, membentuk distribusi bersarang yang tidak mudah diintegrasikan
• Posterior berdimensi tinggi: Ketika jumlah parameter membuat pendekatan berbasis grid tidak layak secara komputasi
• Prior non-konjugat: Ketika prior dan likelihood tidak bergabung menjadi distribusi yang mudah dikenali

MCMC adalah solusi yang baik dalam skenario ini. Alih-alih menghitung distribusinya, ia mengambil sampel darinya. Sampel tersebut memuat semua yang Anda perlukan tanpa pernah menyelesaikan integral.

Dua Gagasan di Balik MCMC

MCMC memadukan dua ide yang masing-masing sederhana, tetapi kuat saat digabungkan. Berikut penjelasannya.

Rantai Markov

Rantai Markov adalah urutan keadaan di mana setiap langkah hanya bergantung pada posisi Anda saat ini.

Ke mana Anda pernah berada tidak penting. Hanya keadaan saat ini yang menentukan ke mana Anda akan melangkah berikutnya. Sifat "tanpa ingatan" ini—secara formal disebut sifat Markov—yang membuat perhitungan matematis mudah dikelola dan algoritme praktis.

Rantai bergerak melalui keadaan selangkah demi selangkah, dan dengan pengaturan yang tepat, akhirnya menetap pada distribusi stasioner—pola stabil di mana probabilitas berada pada keadaan tertentu berhenti berubah. Distribusi stabil itulah yang dirancang untuk digunakan MCMC.

Metode Monte Carlo

Metode Monte Carlo menggunakan pengambilan sampel acak untuk mengestimasi kuantitas yang sulit dihitung secara langsung.

Idenya adalah mengambil cukup banyak sampel acak dari suatu distribusi, lalu mengestimasi mean, varians, atau sifat lain hanya dengan melihat sampel. Semakin banyak sampel yang Anda ambil, semakin dekat estimasi Anda ke nilai sebenarnya.

Sendirian, metode Monte Carlo mengharuskan Anda langsung mengambil sampel dari distribusi—yang justru menjadi masalah yang ingin kita atasi. Rantai Markov menangani bagian itu.

Cara Kerja Markov Chain Monte Carlo

MCMC adalah sebuah loop dengan keputusan sederhana di setiap langkah.

1. Mulai dari keadaan awal: Pilih titik awal di ruang parameter Anda, meski hanya perkiraan kasar
2. Usulkan keadaan baru: Gunakan mekanisme usulan untuk menyarankan langkah berikutnya
3. Putuskan apakah akan menerimanya: Bandingkan keadaan yang diusulkan dengan yang sekarang dan terima atau tolak berdasarkan seberapa mungkin masing-masing di bawah distribusi target
4. Ulangi: Jalankan loop ini ribuan kali, kumpulkan sampel sepanjang proses
5. Gunakan sampelnya: Estimasikan mean, interval kredibel, atau kuantitas lain yang diminati dari sampel yang terkumpul

Langkah terima/tolak inilah tempat “keajaiban” terjadi.

Dengan lebih sering menerima keadaan yang lebih baik daripada yang lebih buruk, rantai akan mengarah ke wilayah dengan probabilitas tinggi—tanpa perlu menghitung distribusi penuh.

Sampel awal dipengaruhi oleh titik awal Anda, jadi sampel tersebut dibuang. Setelah cukup iterasi, rantai melupakan titik awalnya dan sisa sampel merefleksikan bentuk sebenarnya dari distribusi target Anda.

Distribusi Target dan Distribusi Stasioner

MCMC dibangun dengan tujuan menghasilkan sampel dari distribusi target yang tidak bisa Anda sampel secara langsung.

Distribusi target adalah apa pun yang ingin Anda pelajari—biasanya distribusi posterior dalam inferensi Bayesian. Anda mengetahui bentuknya hingga konstanta normalisasi, tetapi Anda tidak bisa menghitung konstanta itu secara langsung. MCMC tidak membutuhkannya.

Setiap algoritme MCMC dirancang agar rantai Markov-nya memiliki distribusi stasioner yang sesuai dengan target. Distribusi stasioner adalah distribusi yang menjadi tempat rantai menetap setelah cukup banyak langkah.

Terus jalankan rantainya dan ia akan mulai menghasilkan sampel yang tampak seperti pengambilan langsung dari distribusi target Anda. Integral pun terlewati.

Algoritme Markov Chain Monte Carlo yang Populer

Ada beberapa algoritme MCMC yang umum digunakan. Semuanya mengikuti loop inti yang sama, tetapi berbeda dalam cara mengusulkan keadaan baru dan bagaimana memanfaatkan informasi tentang distribusi target.

Algoritme Metropolis

Algoritme Metropolis adalah algoritme MCMC paling sederhana dan yang memulai semuanya.

Di setiap langkah, ia mengusulkan keadaan baru dengan menambahkan noise acak ke keadaan saat ini. Jika keadaan yang diusulkan memiliki probabilitas lebih tinggi di bawah distribusi target, selalu diterima. Jika lebih rendah, diterima dengan probabilitas yang sebanding dengan rasio kedua probabilitas tersebut—jika tidak, rantai tetap di tempat.

Mekanisme terima/tolak ini membuat rantai menghabiskan lebih banyak waktu di wilayah berprobabilitas tinggi tanpa pernah menghitung distribusi penuh.

Algoritme Metropolis menggunakan distribusi usulan simetris, artinya sama-sama mungkin mengusulkan langkah ke arah mana pun. Ia cenderung kewalahan saat model membesar.

Algoritme Metropolis-Hastings

Algoritme Metropolis-Hastings (MH) menggeneralisasi Metropolis dengan memungkinkan distribusi usulan yang asimetris.

MH menyesuaikan probabilitas penerimaan untuk memperhitungkan bahwa beberapa usulan lebih mungkin daripada yang lain. Anda dapat menyetel usulan agar sesuai dengan bentuk distribusi target, yang menghasilkan penjelajahan lebih baik dan konvergensi lebih cepat.

Sebagian besar metode MCMC modern merupakan ekstensi MH atau dibangun di atas prinsip yang sama. Jadi jika Anda memahami Metropolis-Hastings, Anda memahami fondasi bidang ini.

Gibbs sampling

Gibbs sampling memperbarui satu variabel pada satu waktu alih-alih mengusulkan keadaan baru untuk semua parameter sekaligus.

Di setiap langkah, ia mengambil sampel tiap variabel dari distribusi kondisionalnya—distribusi variabel tersebut dengan syarat nilai variabel lain saat ini. Setelah Anda melalui semua variabel, Anda menyelesaikan satu iterasi penuh.

Ini sepenuhnya menghindari langkah terima/tolak, karena setiap pengambilan kondisional selalu diterima. Metode ini berguna ketika distribusi gabungan penuh sulit diambil sampelnya tetapi distribusi kondisionalnya terjangkau, yang umum dalam model hierarkis Bayesian.

Hamiltonian Monte Carlo

Hamiltonian Monte Carlo (HMC) adalah algoritme pertama yang membuat inferensi Bayesian modern praktis dalam skala besar.

Alih-alih secara acak mengusulkan keadaan baru, HMC menggunakan informasi gradien dari distribusi target untuk mengusulkan keadaan yang jauh dari posisi saat ini namun tetap berpeluang tinggi diterima. Ia bergerak melalui ruang parameter jauh lebih baik daripada metode random-walk. Penolakan usulan lebih sedikit dan eksplorasi distribusi berdimensi tinggi lebih baik.

Metode random-walk seperti Metropolis tidak berskala saat jumlah parameter bertambah. HMC tidak memiliki masalah itu pada tingkat yang sama.

HMC adalah mesin di balik Stan, salah satu platform pemrograman probabilistik yang paling banyak digunakan. No-U-Turn Sampler (NUTS), yang merupakan ekstensi adaptif HMC yang digunakan di PyMC, menghilangkan kebutuhan untuk menyetel ukuran langkah dan jumlah langkah secara manual.

Markov Chain Monte Carlo dalam Statistika Bayesian

Jika ada satu area di mana MCMC memberi dampak terbesar, itu adalah inferensi Bayesian.

Statistika Bayesian berpusat pada distribusi posterior, yaitu probabilitas terbaru dari parameter model Anda setelah melihat data. Menghitungnya berarti mengalikan prior dengan likelihood lalu menormalkan. Langkah normalisasi itu memerlukan integral yang jarang terjangkau.

MCMC sepenuhnya menghapus langkah ini. Anda cukup mengevaluasi posterior yang belum ternormalisasi di titik mana pun dan biarkan rantai melakukan sisanya.

Berikut contoh sederhana. Misalkan Anda mengestimasi bias sebuah koin. Anda memulai dengan keyakinan awal bahwa koin kemungkinan adil, lalu mengamati serangkaian lemparan. Untuk model koin sederhana, posteriormya memiliki bentuk tertutup. Jika Anda menambahkan struktur hierarkis, yaitu mengestimasi bias di ratusan koin secara simultan, perhitungannya menjadi mustahil.

Dengan MCMC, Anda menjalankan rantai, mengumpulkan sampel dari posterior, dan menggunakan sampel tersebut untuk menghitung apa yang Anda perlukan.

Memahami Burn-In, Konvergensi, dan Mixing

Tiga konsep ini membingungkan data scientist yang baru mengenal MCMC. Jika Anda salah memahaminya, Anda akan mendapatkan hasil, tetapi tidak tahu mengapa hasil tersebut tidak andal.

Burn-in

Ketika rantai Markov mulai berjalan, ia belum tahu di mana wilayah berprobabilitas tinggi dari distribusi target Anda berada.

Sampel awal dipengaruhi oleh titik awal Anda, bukan oleh distribusi target. Burn-in adalah praktik membuang sampel-sampel tersebut. Anda menjalankan rantai untuk sejumlah iterasi terlebih dahulu, membuang sampel itu, dan hanya menyimpan yang datang setelah rantai memiliki waktu untuk menemukan titik awal yang baik.

Tidak ada aturan universal untuk lamanya burn-in. Itu bergantung pada model Anda, titik awal, dan seberapa baik rantai melakukan mixing. Dalam praktiknya, Anda mendiagnosisnya secara visual dengan trace plot alih-alih memilih angka tetap di awal.

Konvergensi

Konvergensi berarti rantai tidak lagi dipengaruhi oleh titik awal dan kini mengambil sampel yang merefleksikan distribusi target.

Rantai yang belum konvergen menghasilkan sampel bias. Mean yang Anda hitung darinya tidak akan cocok dengan mean posterior sebenarnya. Sebaliknya, mean itu akan mencerminkan tempat rantai kebetulan tersangkut.

Konvergensi dinilai setelahnya dengan diagnostik. Menjalankan beberapa rantai dari titik awal berbeda dan memeriksa apakah hasilnya sejalan adalah salah satu cara paling andal untuk mendeteksi kegagalan konvergensi.

Mixing

Rantai yang konvergen tetapi mixing-nya buruk tetap bermasalah.

Mixing menggambarkan seberapa baik rantai menjelajahi distribusi target. Rantai yang mixing-nya baik bergerak bebas, mengunjungi wilayah berprobabilitas tinggi dan rendah, serta menghasilkan sampel yang kira-kira saling independen. Rantai yang mixing-nya buruk tetap berada di satu wilayah selama banyak iterasi sebelum bergerak, dan menghasilkan sampel yang sangat berkorelasi yang tidak merepresentasikan distribusi secara penuh.

Mixing yang buruk sering terlihat sebagai trace plot yang tampak seperti sungai berkelok lambat alih-alih pita horizontal yang bising. Jika Anda melihat itu, sampler Anda perlu disetel—usulan yang lebih baik atau algoritme yang sama sekali berbeda.

Plot perbandingan mixing

Cara Mengevaluasi Hasil MCMC

Sekarang saya akan menunjukkan empat cara mengevaluasi MCMC dan menjelaskan kapan menggunakan masing-masing.

Trace plot

Trace plot menampilkan nilai parameter yang diambil pada setiap iterasi. Ini adalah hal pertama yang harus Anda lihat setelah menjalankan MCMC.

Trace plot yang sehat terlihat seperti derau putih di sekitar mean yang stabil. Anda tidak boleh melihat tren, rentang datar panjang, atau pergeseran lambat. Jika Anda melihat rantai berkeliaran atau tersangkut di satu wilayah selama banyak iterasi, itu adalah masalah mixing dan sampel Anda tidak andal.

Trace plot divisualisasikan

Autokorelasi

Sampel MCMC tidak pernah sepenuhnya independen. Setiap sampel dipengaruhi oleh sampel sebelumnya. Autokorelasi mengukur seberapa kuat sampel berkorelasi lintas iterasi.

Autokorelasi yang tinggi berarti sampel Anda membawa informasi lebih sedikit daripada yang disiratkan jumlahnya. Dua ribu sampel yang berkorelasi mungkin memberikan informasi yang sama dengan dua ratus sampel independen. Sebagian besar pustaka MCMC menyertakan plot autokorelasi sehingga Anda dapat melihat seberapa cepat korelasi menurun saat sampel semakin berjauhan.

Plot autokorelasi divisualisasikan

Ukuran sampel efektif

Effective sample size (ESS) menerjemahkan autokorelasi tersebut menjadi angka praktis: berapa banyak sampel independen yang setara dengan rantai Anda.

Jika Anda mengambil 5.000 sampel tetapi ESS-nya 200, Anda bekerja dengan daya statistik setara 200 pengambilan independen. ESS yang rendah berarti Anda perlu menjalankan rantai lebih lama, menyetel sampler, atau keduanya. Sebagian besar praktisi menargetkan ESS setidaknya beberapa ratus per parameter sebelum mempercayai estimasi mereka.

Diagnostik konvergensi

Saat Anda menjalankan beberapa rantai, Anda dapat menguji secara formal apakah rantai-rantai tersebut telah konvergen ke distribusi yang sama. Diagnostik Gelman-Rubin, yang dilaporkan sebagai R-hat, membandingkan varians dalam setiap rantai dengan varians antarrantai.

R-hat yang mendekati 1,0 berarti rantai-rantai tersebut sejalan, yang merupakan tanda baik. Nilai di atas 1,01 atau 1,05 (tergantung ambang yang digunakan pustaka Anda) menunjukkan rantai belum konvergen dan Anda memerlukan lebih banyak iterasi. Sebagian besar pustaka modern seperti PyMC secara otomatis menghitung R-hat dan memberi peringatan saat nilainya terlalu tinggi.

Markov Chain Monte Carlo di Python

Python memiliki beberapa pustaka untuk MCMC, masing-masing dengan filosofi berbeda.

• PyMC: Opsi yang paling mudah didekati bagi kebanyakan data scientist. Anda mendefinisikan model menggunakan sintaks Python, dan PyMC menangani proses sampling di balik layar menggunakan NUTS (versi adaptif HMC). Ini adalah pilihan utama untuk pemodelan Bayesian di Python.
• CmdStanPy / PyStan: Antarmuka Python ke Stan, bahasa pemrograman probabilistik khusus. Stan mengompilasi model Anda ke C++ sebelum menjalankannya, sehingga cepat dan cocok untuk model hierarkis yang kompleks. Konsekuensinya adalah kurva pembelajaran yang lebih curam.
• NumPy: Tidak ada pustaka MCMC khusus, tetapi Anda dapat mengimplementasikan algoritme seperti Metropolis-Hastings dari nol. Berguna untuk memahami apa yang terjadi di balik layar sebelum beralih ke alat tingkat lebih tinggi.

Untuk sebagian besar pekerjaan praktis, PyMC adalah tempat Anda memulai. Ini yang akan saya gunakan, jadi jika Anda mengikuti, pastikan untuk memasang pustakanya terlebih dahulu:

pip install pymc

Untuk menjaga tetap sederhana, saya akan berpegang pada contoh mudah, yakni mengestimasi bias suatu koin dari serangkaian lemparan.

Langkah 1: Definisikan model

import pymc as pm
import numpy as np

# 1 = heads, 0 = tails
observed_flips = np.array([1, 0, 1, 1, 0, 1, 1, 1, 0, 1])

with pm.Model() as coin_model:
    # Prior: we believe the coin is probably fair
    bias = pm.Beta("bias", alpha=2, beta=2)

    # Likelihood: observed flips given the bias
    flips = pm.Bernoulli("flips", p=bias, observed=observed_flips)

Prior pm.Beta menyandikan keyakinan lemah bahwa koin tersebut adil. Likelihood pm.Bernoulli menghubungkan model ke data yang diamati.

Langkah 2: Jalankan sampler

with coin_model:
    trace = pm.sample(2000, tune=1000, return_inferencedata=True)

Keluaran saat menjalankan sampler

tune menetapkan jumlah langkah burn-in—sampel tersebut dibuang. sample mengambil 2000 sampel posterior per rantai setelah penyetelan.

Langkah 3: Periksa posterior

import arviz as az

az.plot_trace(trace, var_names=["bias"])
az.summary(trace, var_names=["bias"])

Trace plot model dan ringkasan hasil

az.summary() memberi mean posterior, deviasi standar, dan R-hat untuk setiap parameter. Jika R-hat mendekati 1,0, rantai telah konvergen. az.plot_trace() menampilkan trace dan distribusi posterior berdampingan untuk setiap parameter.

Untuk dataset ini—7 kepala dari 10 lemparan—mean posterior sama dengan 0,642 dengan deviasi standar 0,124. Ini mencerminkan bukti pada data sekaligus tetap dekat dengan prior koin adil. R-hat adalah 1,00 dan ESS jauh di atas 2000, sehingga rantai telah konvergen dan sampel dapat diandalkan.

Kesalahan Umum dengan MCMC

MCMC mudah dijalankan, tetapi juga mudah disalahgunakan. Berikut kesalahan yang paling sering muncul.

• Beranggapan konvergensi terlalu dini: Hanya karena sampler berjalan tanpa error bukan berarti sudah konvergen. Selalu periksa R-hat dan trace plot sebelum mempercayai hasil Anda. Rantai bisa tampak stabil namun tetap tersangkut di satu wilayah ruang parameter.
• Mengabaikan burn-in: Sampel awal condong ke titik awal Anda, bukan ke distribusi target. Buanglah. Sebagian besar pustaka menanganinya otomatis melalui parameter tune, tetapi pastikan Anda tidak secara tidak sengaja memasukkan sampel tersebut dalam analisis.
• Mixing yang buruk: Rantai yang bergerak terlalu lambat menghasilkan sampel yang sangat berkorelasi sehingga membawa informasi lebih sedikit daripada jumlahnya. Jika trace plot Anda tampak seperti pergeseran lambat alih-alih pita horizontal yang bising, distribusi usulan Anda perlu disetel, atau Anda memerlukan algoritme yang lebih baik. Beralih dari Metropolis ke NUTS sering kali langsung memperbaikinya.
• Terlalu sedikit sampel: Effective sample size (ESS) yang rendah berarti estimasi Anda tidak andal, meski rantai secara teknis telah konvergen. Jika ESS Anda hanya sebagian kecil dari total pengambilan, jalankan rantai lebih lama atau perbaiki mixing sebelum menarik kesimpulan.

MCMC vs Metode Sampling Lain

MCMC bukan satu-satunya cara mendekati suatu distribusi. Berikut perbandingannya dengan alternatif lain.

• Rejection sampling mengambil usulan dari distribusi yang lebih sederhana dan menerimanya berdasarkan kecocokan dengan target. Ini tepat ketika berhasil, tetapi tingkat penerimaan ambruk dalam dimensi tinggi.
• Importance sampling memberi bobot pada sampel dari distribusi usulan untuk mendekati ekspektasi di bawah target. Cepat dan bekerja baik di dimensi rendah, tetapi varians bobot meledak seiring meningkatnya dimensi. Dalam praktik, segelintir sampel membawa hampir semua bobot, sehingga estimasi menjadi tidak andal.
• Variational inference (VI) menyesuaikan distribusi yang lebih sederhana untuk mendekati target dengan meminimalkan ukuran divergensi. VI jauh lebih cepat daripada MCMC dan berskala ke dataset besar, tetapi memperkenalkan galat pendekatan. Distribusi yang dipasang mungkin melewatkan struktur posterior yang dapat ditangkap MCMC.

Versi singkatnya:

MCMC dibanding alternatif

MCMC adalah pilihan tepat ketika akurasi lebih penting daripada kecepatan. Jika Anda perlu berskala ke dataset besar atau menjalankan inferensi secara waktu nyata, variational inference mungkin sepadan dengan kompromi akurasi.

Kesimpulan

MCMC adalah salah satu alat yang tampak menakutkan dari luar tetapi menjadi masuk akal setelah Anda memahami apa yang sebenarnya dilakukan—membangun rantai sampel yang secara bertahap merefleksikan bentuk distribusi yang tidak bisa Anda hitung secara langsung.

Ini juga jauh lebih mudah dipahami saat Anda memecahnya menjadi bagian-bagian: Rantai Markov dan metode Monte Carlo.

Perannya dalam statistika Bayesian sulit dilebih-lebihkan. Distribusi posterior yang sebaliknya di luar jangkauan menjadi dapat diatasi begitu Anda memiliki sampler yang andal. Itulah mengapa MCMC berada di inti pustaka pemrograman probabilistik seperti PyMC dan Stan.

Namun sebelum terjun ke implementasi, Anda harus memahami intuisinya. Pahami mengapa rantai perlu burn-in, apa arti mixing sebenarnya, dan bagaimana membaca trace plot. Kodenya sendiri adalah bagian yang mudah, karena pustaka Python menyembunyikan semua abstraksi di balik pemanggilan fungsi sederhana.

Jika Anda ingin mahir dalam machine learning, daftarlah ke jalur Machine Learning Scientist in Python kami. Materi selama 85 jam akan membantu Anda siap kerja pada 2026.