## PEMODELAN RANTAI MARKOV MENGGUNAKAN ALGORITMA METROPOLIS-HASTINGS

## THE MARKOV CHAIN MODELING USING METROPOLIS-HASTINGS ALGORITHM
Harizahayu §
Politeknik Negeri Medan, Indonesia [Email: harizahayu@polmed.ac.id] § Corresponding Author
Received Oktober 2020; Accepted November 2020; Published Desember 2020;

## Abstrak
Pada  tulisan  ini  akan  dijelaskan  bentuk  distribusi  posterior  P(probabilitas  klaim)  =  Beta  (β│α)  dengan proses  simulasi  implementasi  algoritma  yang  disederhanakan  dan  penerapan  algoritma  Markov  Chain Monte Carlo dengan mengunkan analisis sistem Bayes dengan pendekatan model Markov Monte Carlo. Algoritma  Markov  Chain  Monte  Carlo  adalah  suatu  kelas  algoritma  untuk  melakukan  sampling  dari distribusi  probabilitas  dengan  membangun  rantai  Markov  pada  suatu  distribusi  tertentu  yang  stasioner. Algoritma  Metropolis  merupakan  algoritma  untuk  membangkitkan  barisan  sampel  menggunakan mekanisme penerimaan dan penolakan ( accept-reject ) dari suatu distribusi probabilitas yang sulit untuk dilakukan  penarikan  sampel.  Penggunaan  perangkat  lunak  R  sebagai  media  untuk  mengeksplorasi algoritma  dan  diagnostik  yang  umum  untuk  implementasi  MCMC.  Hampir  semua  program  dapat dijalankan  dengan  fungsionalitas  dasar  R  yang  berarti  tidak  diperlukan  overhead  penyetelan  untuk menjalankan blok kode selain versi kerja R dan tersedia gratis secara online untuk semua sistem operasi. Kata Kunci : Distribusi Posterior, Rantai Markov Monte Carlo, Metropolish, Peluang Klaim

## Abstract
In this paper, we will describe the form of the posterior distribution of (claim probability) = ( | ) with A simplified algorithm implementation simulation process and the application of the Markov Chain Monte  Carlo  algorithm  are  given  by  the  Bayes  system  analysis  with  the  Markov  Monte  Carlo  model approach.  The  Monte  Carlo  algorithm  of  the  Markov  Chain  is  a  class  of  algorithms  for  sampling  the distribution  of  probability  through  the  construction  of  a  Markov  chain  in  a  particular  stationary distribution. The Metropolis-Hastings algorithm is an algorithm used to produce sample sequences from a  probability  distribution  that  is  difficult  for  sampling  using  an  accept-reject  mechanism.  Usage  of  R program as a platform for MCMC implementations to explore popular algorithms and diagnostics. It is possible to run almost any program with simple R features, which means that no overhead configuration is needed to run code blocks other than the working version of R, and all operating systems are available online free of charge.
Keywords :  Posterior  Distribution,  Monte  Carlo  Markov  Chain,  Metropolish,  Claims  Probability

## 1. Pendahuluan
Metode  pengambilan  sampel Monte  Carlo (MC)  diterapkan  secara  luas  dalam  sistem
Harizahayu                                                                                                                                                                Pemodelan Rantai Markov…
inferensi  Bayesian  simulasi  dan  masalah optimasi.  Algoritma Markov  Chain  Monte  Carlo (MCMC) adalah metode MC yang menghasilkan rantai Markov dengan  yang diinginkan distribusi invarian.  Dalam  penelitian  ini  difokus  pada sampler Metropolis-Hastings (MH),  yang  dapat dianggap  sebagai  atom/inti  bagi  teknik  MCMC, yang  memperkenalkan  pengertian  dasar  dan properti  yang  berbeda  dan  menjelaskan  secara rinci  semua  elemen-elemen  yang  terlibat  dalam algoritma  MH  dan  varian  yang  paling  relevan. Beberapa  perbaikan  dan  perluasan  terbaru diusulkan  dalam  literatur  juga  dibahas  secara singkat,  memberikan  gambaran  yang  cepat  tapi lengkap  tentang  arus  pengambilan  sampel  nyata berbasis Metropolis [5].
Teori  penskalaan  optimal  menghasilkan kondisi  untuk  tingkat  penerimaan  optimal  tanpa gejala  pada  algoritma  Metropolis  menjadi  0,234 ketika  diterapkan  pada  target  distribusi  multi- dimensi  tertentu.  Distribusi  target  berdimensi ini dibentuk dari komponen independen, masing- masing  diskalakan  menurut  fungsinya  dari . Penelitian ini menunjukkan bahwa ketika kondisi tidak  terpenuhi  maka  proses  pembatas  dari algoritma harus diubah/diganti agar menghasilkan tingkat penerimaan yang optimal secara asimtotik yang  mungkin  akan  berbeda  secara  drastis  dari
0,234 biasanya. Secara khusus, telah membuktikan  bahwa membentuk  urutan
proses  stokastik  pada  komponen  ke- dari  tiap- tiap  rantai  markov  yang  selalu  konvergen  pada proses  difusi  Langevin  dengan  sebuah  ukuran kecepatan baru , kecuali dalam kasus tertentu di mana  ia  menyatu  dengan  algoritma  Metropolis
satu dimensi dengan aturan penerimaan [1].
Teorema  penskalaan  optimal  semuanya terbukti  di  bawah  sangat  terbatas  dan  tidak realistis  asumsi  (misalnya,  distribusi  target dengan  koordinat  independen),  tampaknya memberikan pedoman  yang berguna secara lebih umum.  Secara  khusus,  hasil  tentang  penerimaan asimtotic  rate memberikan  tolok  ukur  yang berguna  untuk  algoritma  Meteropolis  dalam berbagai  pengaturan.  Algoritma  MCMC  adaptif tampaknya  menyediakan  metode  pencarian  yang sederhana  dan  intuitif  rantai  Markov  yang menyatu  dengan  cepat  tanpa  usaha  keras  dari pengguna  (selain  dari  pemrograman  awal,  dan bahkan  ada  beberapa  perangkat  lunak  generik yang tersedia. hasil ini menunjukkan perkembangan  penerapan  dari  keduanya  optimal penskalaan  dan  algoritma  MCMC  adaptif  ke beberapa pengaturan MCMC yang berbeda [7].
Untuk membantu memperkuat algoritma yang paling sederhana yaitu algoritma Metropolis yang telah  menyediakan  implementasi  dasar  dengan perangkat  lunak  R  [3]  dan    juga  menggunakan keluaran  sampler  Metropolis  kami  untuk menjelajahi  sejumlah  diagnosis  yang  berguna dalam  Bayesian  untuk  menganalisis  dan memeriksa  tingkat  kekonvergenan  sampel  ,  titik stasioner,  gabungan  dari  multiple  chain,  dan untuk menentukan tingkat efisiensi dengan tujuan akhir  serta  memastikan  representasi  yang  sesuai dari distribusi posterior.
Sistematika tulisan ini terdiri dari pendahulu yang  berisikan  penelitian  dan  kajian  dari beberapa  penulis  sebelumnya,  tinjaun  pustaka berisikan  dalil  bayes,  distribusi  beta,  rantai
Harizahayu                                                                                                                                                                Pemodelan Rantai Markov…
markov, algoritma metropolis, dan cara pemilihan proposal yang akan digunakan pada penelitian ini, hasil  dan  pembahasan  berisikan  kajian  dan  alur yang dikerjakan oleh penulis untuk mendapatkan output dari tujuan penelitian ini, dan kesimpulan.

## 2. Tinjauan Pustaka
Tinjauan  pustaka  yang  digunakan  dalam tulisan ini adalah sebagai berikut:
Dalil  Bayes  2.1. [2],[9] Misalkan  kejadian merupakan himpunan ruang sampel
dengan ( ) untuk .
Misalkan suatu  kejadian  sebarang  dalam dengan ( ) , maka:
( | ) ( ) ∑ ( ) ( ) ( | ) ∑ ( ) ( | )

## Untuk
Bukti. Menurut definisi peluang bersyarat, bila diketahui dinyatakan dengan ( | ) , maka
( | ) (     ) ( ) ( )
Sehingga diperoleh persamaan:
( | ) ( ) ( )
Dengan menggunakan teorema jumlah peluang penyebut
( | ) ( ) ∑ ( )
Dan dengan menggunakan aturan perkalian pada pembilang dan penyebut, diperoleh:
( | ) ( ) ( | ) ∑ ( ) ( | )

## 2.1. Distribusi Beta
Peubah  acak  mempunyai  distribusi  Beta dengan  parameter dan [2][10],  jika  peubah tersebut  bernilai (   ) dengan  fungsi  pdf adalah
( )   { (     ) ( ) ( ) (     )
Dimana:
dan : parameter distribusi beta
( ) : fungsi gamma: ∫
Untuk dan
( ) : fungsi gamma: ∫
Untuk dan

## 2.2. Model Rantai Markov
Suatu  proses  stokastik  [1],[2] ( ) yang  mengikuti  sifat  bahwa  kejadian pada  saat yaitu  peubah  acak hanya dipengaruhi  oleh  kejadian  satu  langkah  yang merupakan  proses  stokastik  khusus  yang mengikuti  sifat  rantai  markov,  secara  matamatis sifat rantai markov adalah sebagai berikut:
( | )
( | ) Peluang  bersyarat ( | ) disebut peluang transisi satu langkah, yaitu proses dalam keadaan pada  waktu jika  mula-mula  proses apada  keadaan pada  waktu .  Sedangkan peluang  transisi langkah  jika ( )
Harizahayu                                                                                                                                                                Pemodelan Rantai Markov…
( | ) .  Suatu  rantai  markov mempunyai sebaran stasioner ( ) jika keadaan dan pada semua berlaku:
( | )    ( | )

## 2.3. Algoritma Metropolis
Algoritma  Meropolis  merupakan  salah  satu algoritma  yang  paling  popular  dan  merupakan modifikasi  dari  algoritma  MCMC.  Perbedaanya terletak  pada  penggunaan  bobot  pada  setiap pengulangan dati  iterasi Monte-Carlo . Algoritma
Metropolis - Hastings bekerja dengan
menghasilkan  urutan  nilai  sampel  sedemikian rupa  sehingga,  dengan  semakin  banyak  nilai sampel yang dihasilkan, distribusi nilai mendekati distribusi yang diinginkan ( ) . Nilai sampel ini diproduksi  secara  berulang,  dengan  distribusi sampel  berikutnya  hanya  bergantung  pada  nilai sampel saat ini ,sehingga membuat urutan sampel menjadi  rantai  Markov.  Secara  khusus,  di  setiap iterasi,  algoritma  memilih  target  untuk  nilai sampel  berikutnya  berdasarkan  nilai  sampel  saat ini.  Kemudian,  dengan  beberapa  kemungkinan, target  diterima  (dalam  hal  nilai  target  ini digunakan  dalam  iterasi  berikutnya)  atau  jika ditolak (dalam hal ini nilai kandidat dibuang, dan nilai  saat  ini  digunakan  kembali  pada  iterasi berikutnya).  Probabilitas  penerimaan  ditentukan dengan  membandingkan  nilai-nilai  fungsi ( ) dari  nilai  sampel  saat  ini  dan  terget  sehubungan dengan distribusi yang diinginkan ( ) [8].

## 2.4. Pilihan Khusus Bentuk Proposal
Beberapa  kasus  menarik,  tergantung  pada pemilihan  density  proposal  [5].  Ada  beberapa
cara pemilihan proposal:

## a. Proposal Simetrik
Jika proposal memenuhi kesetaraan ( | )
( | ) , sehingga probability penerimaannya sederhana.
( | )       * ( ) ( ) +
Tergantung  pada  evaluasi  dari  fungsi  target .  Khusus  pada  kasus  ini  sangat  menarik karena kasus ini menjelaskan hubungan yang erat antara masalah pengambilan sampel dan pengoptimalan kasus. Sehingga penyelesaian kasus  ini  memperoleh  persamaan  sebagai berikut:
( | )   { ( )    ( ) ( ) ( ) ( )    ( )
Sampel  memberikan  nilai  yang  lebih  tinggi dari selalu diterima, sedangkan sampelnya memberikan  nilai  yang  lebih  kecil  dari hanya diterima menurut probabilitas tertentu.

## b. Independent Proposal
Jika proposal pdf independen pada inisialisasi  selanjutnya  di  rantai,  contoh:
( | )    ( ) .  Probabilitas  penerimaan adalah:
( | )       [ ( ) ( ) ( ) ( ) ]       [ ( ) ( ) ] Dimana ( ) ( ) ( ) adalah bobot yang terkait dengan sampel dalam  standar teknik pengambilan sampel.

## c. Proposal Optimal
Jika ( )    ̅( ) , contoh: proposal tersebut sesuai dengan target pdf ̅( )    ( ) , untuk
Harizahayu                                                                                                                                                                Pemodelan Rantai Markov…
(    ) . Sehingga, semua sampel yang diusulkan diterima karena didistribusikan sebagai ̅( ) yang menghasilkan nilai yang
independen dan tidak memiliki korelasi satu sama lain.

## d. Proposal Random Walk
Pada  kasus  ini  ketika  proposal  pdf  dapat diformulasikan  sebagai ( | )    (     ) , contoh : berperan sebagai parameter lokasi
( mean ). Pilihan  ini  menyajikan  perilaku eksploratif  yang  menarik  karena  lokasi proposal  mengikuti  sebuah  perjalanan    acak di  sekitar  ruang  parameter  pada  inisialiasi nilai pada rantai.

## 3. Hasil Dan Pembahasan
Adapun  hasil  dan  pembahasan  dari  adalah sebagai berikut:

## 3.1. Alur Algoritma Metropolis
1. Pilih nilai awal ( ) . 2. Untuk . a. Buatlah sampel ( | (   ) )
b. Terima nilai baru, ( ) , dengan
kemungkinan
( (   ) )    [ ( ) ( (   ) | ) ( (   ) ) ( | (   ) ) ]
jika tidak , maka set ulang ( ) (   ) .
Algoritma  mengembalikan  urutan  status { ( ) ( ) ( ) ( ) } atau  menghapus  sub himpunan  anggota  dengan  periode burn-in jika untuk  memeperoleh  estimasi  membutuhkan durasi  waktu  yang  panjang.  Nilai  awal selanjutnya ( ) dapat  menjadi  sampel  yang diusulkan (dengan  nilai  kemungkinan )  atau
nilai  awal  berikutnya
(   ) (dengan  nilai kemungkinan ).

## 3.2. Elemen-elemen pada metode M-H
Algoritma  MH  terdiri  dari  3  elemen-elemen berikut:
1. Density proposal ( | )
2. Probabilitas penerimaan ( | )
3. Fungsi target ( )
Semuanya  dapat  divariasikan,  ditingkatkan atau  diperpanjang  untuk  meningkatkan  kinerja algoritma,  dan  selalu  memastikan  ergodisitas rantai.  Proposal  pdf q harus  dipilih  sedekat mungkit  dengan  target π .  Penerimaan  yang berbeda pada probabilitas α dapat digunakan, dan secara  umum  metode  MH  fungsi  penerimaan yang  sesuai  harus  dirancang  untuk  menjamin keergodikan  rantai  yang  dihasilkan.  Selanjutnya di  beberapa  skenario  tertentu,  peningkatan  ruang parameter buatan dapat berguna untuk meningkatkan  kinerja.  Lebih  khusus  lagi, peningkatan  fungsi  target akan  dipelajarin  di
beberapa  kasus.  Target dibangun  untuk memperoleh  posterior  pdf  πyang  sebenarnya sebagai marginal density [5].

## 3.3. Sumber Data
Data  diambil  dari  hasil  ulangan  100  orang mahasiswa  untuk  mata  kuliah  Matematika  yang lulus  ulangan  berjumlah  45  orang.  Adapun  pada tahap  selanjutnya  dilaksanakan  remedial  bagi  50 orang mahasiswa yang tidak lulus dan tidak hadir pada  saat  ulangan  dan  terdapat  25  mahasiswa yang lulus ulangan pada tahap remedial.
Harizahayu                                                                                                                                                                Pemodelan Rantai Markov…

## 3.4. Pemilihan Prior Beta
Distribusi  beta  adalah  konjugasi  prior  dari
distribusi binomial, artinya jika fungsi kemungkinan adalah binomial dan distribusi prior adalah  beta  posterior  juga  beta  [6].  Secara spesifik,  misalkan likelihood   distribusi  binomial
( | ) untuk diketahui  dan parameter  yang tidak  diketahui  dan  data merupakan  bilangan integer antara dan ,  sehingga  prior  dari  beta dapat diperoleh sebagai berikut:
Hipotesis : dan data:
Prior:  Beta ( | )
(     ) Likelihood: Binomial ( | ) (     ) (1) Posterior: Beta (                ) (     ) (2)
Persamaan  tersebut  disederhanakan  dengan menuliskan koefisien normalisasi  masing-masing sebagai , , dan sebagai berikut:
(         )
(     )  (     )
( ) (     )
(             )
(         )  (             )
Adapun  data  yang  diinput  kan  dengan menggunkan program R 3.5.3 sebagai berikut: mahasiswa_1 <- 100; n_kuis <- 45 mahasiswa_2 <-50 ; r_kuis <- 25
Prior: ( | ) a <- 5; b <- 10 a <- 10; b <- 5 a <- 10; b <- 10
Kemudian  dengan  menggunakan  bantuan perangkat  lunak  R  akan  ditentukan  nilai  dari likelihood dan posteriornya [4].

## 3.5. Hasil Analisis Data dengan Metode M-H
Berdasarkan nilai prior distribusi beta: mahasiswa_1 <- 100; n_kuis <- 45 mahasiswa_2 <-50 ; r_kuis <- 25 untuk prior: ( |  ) a <- 5; b <- 10
Kemudian dicari nilai likelihood dan posterior dengan  menggunakan  rumus  (1)  dan  (2). Selanjutnya  akan  dibentuk  matriks  densitas  dari distribusi joint prior ( | ) dimana merupakan jumlah mahasiswa yang mengikuti ulangan dan jumlah  mahasiswa  yang  lulus  passing  grade. Sehingga secara matematika dapat dibentuk rmus sebagai berikut:
( | )    ( ) , untuk dan ( | )    ( )   ( ) ( |    ) (    | ) ( | ) ∫ ∫  (    | ) ( | )
Berdasarkan  asumsi  di  atas joint  distibution dapat  difaktorkan  menjadi  dua  konjungsi distribusi  beta  yang  independen.  Adapun  output plot  ketiga  komponen  prior  density,  joint posterior,  dan  joint  likelihood  untuk  distribusi ( |  ) dengan  menampilkan  aplikasi  dalam bentuk 2 dimensi sebagai berikut:
Harizahayu                                                                                                                                                                Pemodelan Rantai Markov…

## Gambar 1. Plot Prior, Posterior dan Likelihood
Selanjutnya  akan  dilakukan  perhitungan posterior  secara  analitik  dengan  algoritma metropolis  untuk  proposal  dsitribusi  bivariat normal  dan  varians ,mengasumsikan matriks  kovarians  kedalam  variabel cov_mat , serta  mengambil  sampel  sebanyak  20000  untuk melihat  perbandingan  nilai  eksak  dengan  nilai aprroksimasinya.
Kemudian
dengan
memanfaatkan package library (MASS)
diperoleh  output  pemanggilan  fungsi  posterior sebagai berikut:
> quant_thetas exact_theta_1 apprx_theta_1 exact_theta_2 apprx_theta_2
2.5%      0.3451191     0.3438779     0.3462152 0.3472135 5%        0.3599487     0.3595262     0.3634803 0.3624527 25%       0.4028621     0.4041664     0.4205574 0.4201944 50%       0.4345967     0.4349983     0.4620781 0.4623245 75%       0.4657141     0.4667697     0.5028922 0.5028516 95%       0.5096200     0.5111512     0.5633470 0.5613928 97.5%     0.5249114     0.5273480     0.5807633
0.5816204

## Berikut ini adalah plot Quantil dari distribusi posterior:
Gambar 2. Plot Quantile Distribusi Posterior
Berdasarkan  output  quantil  distribusi posterior di atas dapat diamati bahwa penggunaan algoritma  metropolis  untuk  menentukan  nilai eksak  dari  theta_1  hampir  sama  dengan  nilai approksimasinya  dari  theta_1  mulai  dari  tingkat kuantil  2,5%,  5%,  25%,  50%,  75%,  95%,  dan 97,5%  begitu  juaga  dengan  nilai  aprroksimasi theta_2  yang  hampir  sama  dengan  nilain eksaknya.  Nilai  proposal  merupakan  nilai  awal yang  diberikan  unutk  menentukan  nilai  posterior dari suatu distribusi.
Harizahayu                                                                                                                                                                Pemodelan Rantai Markov…

## 4. Kesimpulan Dan Saran
Berdasarkan  hasil  dan  pembahasan  dapat diambil kesimpulan sebagai berikut:
1. Distribusi posterior dibentuk dari sampel dan distribusi awal ( prior ).
2. Analisis  data  bayesian  adalah  metode fleksibel  untuk  menyesuaikan  semua  jenis model statistik.
3. Maksimum  likelihood  adalah  kasus  khusus pada model Bayesian.
4. Jumlah iterasi sangat menentukan nilai eksak dan  nilai  aproksimasi  pada  algoritma metropolish.
5. Algoritma  Markov  chain  Monte  Carlo  yang termasuk dalam bagian algoritma
aproksimasi  yang  menggunakan  teknik simulasi menggunakan bantuan komputer.

## 5. Ucapan Terima Kasih
Pada  penelitian  ini  penulis  mengucapkan terima kasih banyak kepada rekan-rekan  yang telah  membantu  penulis  dalam  perbaikan tulisan dan saran revisi sourcecode pemograman  R  sehingga    penelitian  ini  dapat selesai tepat waktu.

## Daftar Pustaka
[1]  Bédard, M. 2008. Optimal acceptance rates for Metropolis algorithms: Moving beyond 0.234. Stochastic Processes and Their Applications , 118(12), 2198–2222. https://doi.org/10.1016/j.spa.2007.12.005
[2]  Bain, L.J and  Engelhardt, M. 1992, Introduction to Probability and Mathematical Statistics ,   ed, California: PWS-Kent Publising Company.
[3]  Ford, P., & Cspa, F. 2018. MCMC Algorithms . April, 1–28.
[4]  Hornik, K. 2009. Use R ! Robert Gentleman. In Media . http://www.springerlink.com/index/10.1007/ 978-0-387-88698-5
[5]  Martino, L., Elvira, V., & Camps-Valls, G. 2017. Group metropolis sampling. 25th European Signal Processing Conference , EUSIPCO 2017, 2017-Janua(2), 201–205. https://doi.org/10.23919/EUSIPCO.2017.808 1197
[6]  Orloff, J., & Bloom, J. 2014. Normal Beta Conjugate . https://ocw.mit.edu/courses /mathematics/18-05-introduction-to-
probability-and-statistics-spring-2014
/readings/MIT18_05S14_Reading15a.pdf [7]  Rosenthal, J. S. 2011. Optimal proposal distributions and adaptive MCMC. Handbook of Markov Chain Monte Carlo .1, 93–112. https://doi.org/10.1201/b10905-5
[8]  Rupert, M., & Katie, R. 2012 . Reproduced with permission of the copyright owner . Further reproduction prohibited without. Journal of Allergy and Clinical Immunology .130(2), 556. http://dx.doi.org/10.1016/ j.jaci.2012.05.050
[9] Safitri, D. 2010. Metode Bayes dengan model rantai  Markov  Monte  Carlo  untuk  menaksir jumlah klaim asuransi (Doctoral dissertation .  Universitas  Islam  Negeri Maulana Malik Ibrahim). [10]  Walpole, Ronald E., Raymond H Myers.
1995. Ilmu Peluang Dan Statistika untuk Insinyur dan Ilmuawan , edisi ke-4, Penerbit ITB, Bandung.