Apakah itu mudah? Saya mencoba
Alexey Kuzmin, direktur pengembangan data dan bekerja di DomKlik, dosen Ilmu Data di Netologi, menerjemahkan sebuah artikel oleh Rahul Agarwal tentang bagaimana metode Monte Carlo bekerja dengan rantai Markov untuk memecahkan masalah dengan ruang negara yang besar.Semua orang yang terkait dengan Ilmu Data pernah mendengar metode Monte Carlo dengan rantai Markov (MCMC). Terkadang topik tersebut disentuh ketika mempelajari statistik Bayesian, kadang-kadang ketika bekerja dengan alat-alat seperti Nabi.
Tetapi MCMC sulit dimengerti. Setiap kali saya membaca tentang metode ini, saya perhatikan bahwa esensi MCMC tersembunyi di lapisan dalam kebisingan matematika, dan sulit untuk melihat di balik kebisingan ini. Saya harus menghabiskan waktu berjam-jam untuk memahami konsep ini.
Dalam artikel ini, upaya untuk menjelaskan metode Monte Carlo dengan rantai Markov tersedia, sehingga menjadi jelas untuk apa mereka digunakan. Saya akan fokus pada beberapa cara lagi untuk menggunakan metode ini di posting saya berikutnya.
Jadi mari kita mulai. MCMC terdiri dari dua istilah: rantai Monte Carlo dan Markov. Mari kita bicara tentang mereka masing-masing.
Monte Carlo
Dalam istilah yang paling sederhana
, metode Monte Carlo dapat didefinisikan sebagai simulasi sederhana.
Metode Monte Carlo mendapatkan nama mereka dari Kasino Monte Carlo di Monako. Dalam banyak permainan kartu, Anda perlu mengetahui kemungkinan memenangkan dealer. Kadang-kadang perhitungan probabilitas ini bisa rumit secara matematis atau sulit dilakukan. Tetapi kita selalu dapat menjalankan simulasi komputer untuk memainkan seluruh game berkali-kali dan mempertimbangkan probabilitas sebagai jumlah kemenangan dibagi dengan jumlah game yang dimainkan.
Ini semua yang perlu Anda ketahui tentang metode Monte Carlo. Ya, itu hanya teknik pemodelan sederhana dengan nama mewah.
Rantai Markov
Karena istilah MCMC terdiri dari dua bagian, Anda masih perlu memahami apa itu
rantai Markov . Tetapi sebelum beralih ke rantai Markov, mari kita bicara sedikit tentang properti Markov.
Misalkan ada sistem status M-mungkin, dan Anda berpindah dari satu negara ke yang lain. Jangan biarkan apa pun membingungkan Anda. Contoh spesifik dari sistem tersebut adalah cuaca, yang berubah dari panas ke dingin menjadi sedang. Contoh lain adalah pasar saham, yang melompat dari bearish ke keadaan bullish dan stagnan.
Properti Markov menunjukkan bahwa untuk proses yang diberikan yang dalam keadaan X
n pada saat tertentu dalam waktu, probabilitas X
n + 1 = k (di mana k adalah salah satu dari negara-negara M di mana proses dapat berjalan) hanya bergantung pada apa kondisi ini saat ini. Dan bukan tentang bagaimana mencapai kondisi saat ini.
Dalam istilah matematika, kita dapat menulis ini dalam bentuk rumus berikut:
Untuk kejelasan, Anda tidak peduli tentang urutan kondisi yang diambil pasar untuk menjadi bullish. Probabilitas bahwa negara berikutnya akan "bearish" hanya ditentukan oleh kenyataan bahwa pasar saat ini dalam keadaan "bullish". Ini juga masuk akal dalam praktik.
Proses dengan properti Markov disebut proses Markov. Mengapa rantai Markov penting? Karena distribusi stasionernya.
Apa distribusi stasioner?
Saya akan mencoba menjelaskan distribusi stasioner dengan menghitungnya untuk contoh di bawah ini. Misalkan Anda memiliki proses Markov untuk pasar saham, seperti yang ditunjukkan di bawah ini.
Anda memiliki matriks probabilitas transisi yang menentukan probabilitas transisi dari kondisi X
i ke X
j .
Matriks Probabilitas Transisi, Q
Dalam matriks probabilitas transisi Q yang diberikan, probabilitas bahwa keadaan berikutnya adalah "bull", mengingat status "bull" saat ini = 0,9; probabilitas bahwa keadaan selanjutnya akan "bearish" jika keadaan saat ini adalah "bull" = 0,075. Dan sebagainya.
Baiklah, mari kita mulai dengan kondisi tertentu. Negara kita akan diatur oleh vektor [banteng, beruang, stagnasi]. Jika kita mulai dengan keadaan "bearish", vektornya akan seperti ini: [0,1,0]. Kita dapat menghitung distribusi probabilitas untuk keadaan berikutnya dengan mengalikan vektor keadaan saat ini dengan matriks probabilitas transisi.
Perhatikan bahwa probabilitas bertambah hingga 1.Distribusi status berikut dapat ditemukan dengan rumus:
Dan sebagainya. Pada akhirnya, Anda akan mencapai status stasioner di mana kondisi stabil:
Untuk matriks probabilitas transisi Q yang dijelaskan di atas, distribusi stasioner adalah
Anda bisa mendapatkan distribusi stasioner dengan kode berikut:
Q = np.matrix([[0.9,0.075,0.025],[0.15,0.8,0.05],[0.25,0.25,0.5]]) init_s = np.matrix([[0, 1 , 0]]) epsilon =1 while epsilon>10e-9: next_s = np.dot(init_s,Q) epsilon = np.sqrt(np.sum(np.square(next_s - init_s))) init_s = next_s print(init_s) ------------------------------------------------------------------ matrix([[0.62499998, 0.31250002, 0.0625 ]])
Anda juga dapat memulai dari negara bagian lain - dapatkan distribusi alat tulis yang sama. Ubah status awal dalam kode jika Anda ingin memastikan ini.
Sekarang kita dapat menjawab pertanyaan mengapa distribusi stasioner sangat penting.
Distribusi stasioner penting karena dapat digunakan untuk menentukan probabilitas suatu sistem berada dalam keadaan tertentu secara acak.
Sebagai contoh kita, kita dapat mengatakan bahwa dalam 62,5% kasus pasar akan berada dalam kondisi "bullish", 31,25% dalam kondisi "bearish" dan stagnasi 6,25%.
Secara intuitif, Anda bisa melihat ini sebagai pengembaraan acak di sekitar rantai.
Berjalan acak
Anda berada pada titik tertentu dan memilih negara berikutnya, mengamati distribusi probabilitas negara berikutnya, dengan mempertimbangkan keadaan saat ini. Kita dapat mengunjungi beberapa node lebih sering daripada yang lain, berdasarkan probabilitas dari node-node ini.
Inilah cara Google memecahkan masalah pencarian di awal Internet. Masalahnya adalah menyortir halaman, tergantung pada kepentingannya. Google memecahkan masalah menggunakan algoritma Pagerank. Algoritma Google Pagerank harus mempertimbangkan status sebagai sebuah halaman, dan probabilitas suatu halaman dalam distribusi stasioner sebagai kepentingan relatifnya.
Sekarang kita beralih langsung ke pertimbangan metode MCMC.
Apa itu Metode Monte Carlo dengan Rantai Markov (MCMC)
Sebelum menjawab apa MCMC, izinkan saya mengajukan satu pertanyaan. Kami tahu tentang distribusi beta. Kita tahu fungsi kerapatan kemungkinannya. Tetapi bisakah kita mengambil sampel dari distribusi ini? Bisakah Anda menemukan cara untuk melakukan ini?
Pikirkan ...
MCMC memungkinkan Anda untuk memilih dari distribusi probabilitas apa pun. Ini sangat penting ketika Anda perlu memilih dari distribusi posterior.
Angka tersebut menunjukkan teorema Bayes.
Misalnya, Anda perlu membuat sampel dari distribusi posterior. Tetapi apakah mudah untuk menghitung komponen posterior bersama dengan konstanta normalisasi (bukti)? Dalam kebanyakan kasus, Anda dapat menemukannya dalam bentuk produk kemungkinan dan probabilitas apriori. Tetapi untuk menghitung konstanta normalisasi (p (D)) tidak berfungsi. Mengapa Mari kita lihat lebih dekat.
Misalkan H hanya mengambil 3 nilai:
p (D) = p (H = H1) .p (D | H = H1) + p (H = H2) .p (D | H = H2) + p (H = H3) .p (D | H = H3)
Dalam hal ini, p (D) mudah untuk dihitung. Tetapi bagaimana jika nilai H kontinu? Apakah mungkin untuk menghitung ini dengan mudah, terutama jika H mengambil nilai yang tak terbatas? Untuk ini, integral yang kompleks harus dipecahkan.
Kami ingin membuat pemilihan acak dari distribusi posterior, tetapi juga ingin menganggap p (D) sebagai konstanta.
Wikipedia
menulis :
Metode Monte Carlo dengan rantai Markov adalah kelas algoritma untuk pengambilan sampel dari distribusi probabilitas, berdasarkan pada konstruksi rantai Markov, yang sebagai distribusi stasioner memiliki bentuk yang diinginkan. Status rantai setelah serangkaian langkah kemudian digunakan sebagai pilihan dari distribusi yang diinginkan. Kualitas pengambilan sampel meningkat dengan meningkatnya jumlah langkah.
Mari kita lihat sebuah contoh. Katakanlah Anda memerlukan sampel dari
distribusi beta . Kepadatannya:
di mana C adalah konstanta normalisasi. Sebenarnya, ini adalah beberapa fungsi dari α dan β, tapi saya ingin menunjukkan bahwa itu tidak diperlukan untuk sampel dari distribusi beta, jadi kami akan menganggapnya sebagai konstanta.
Masalah distribusi beta sangat sulit, jika tidak praktis tidak larut. Pada kenyataannya, Anda mungkin harus bekerja dengan fungsi distribusi yang lebih kompleks, dan kadang-kadang Anda tidak akan tahu konstanta normalisasi.
Metode MCMC membuat hidup lebih mudah dengan menyediakan algoritma yang dapat membuat rantai Markov yang memiliki distribusi beta sebagai distribusi stasioner, mengingat bahwa kita dapat memilih dari distribusi yang seragam (yang relatif sederhana).
Jika kita mulai dengan keadaan acak dan beralih ke keadaan berikutnya berdasarkan beberapa algoritma beberapa kali, kita akhirnya akan membuat rantai Markov dengan distribusi beta sebagai distribusi stasioner. Dan keadaan yang kita temukan dalam waktu yang lama dapat digunakan sebagai sampel dari distribusi beta.
Salah satu algoritma MCMC ini adalah algoritma
Metropolis-Hastings.Algoritma Metropolis-Hastings
Intuisi:
Jadi apa tujuannya?
Secara intuitif, kami ingin berjalan di sepanjang permukaan (rantai Markov kami) sedemikian rupa sehingga jumlah waktu yang kami habiskan di setiap lokasi sebanding dengan ketinggian permukaan di tempat itu (kepadatan probabilitas yang diinginkan dari mana kami ingin menentukan pilihan).
Jadi, misalnya, kami ingin menghabiskan waktu dua kali lebih banyak di puncak bukit setinggi 100 meter dari pada bukit tetangga setinggi 50 meter. Adalah baik bahwa kita dapat melakukan ini bahkan jika kita tidak tahu ketinggian absolut dari titik-titik di permukaan: yang perlu Anda ketahui adalah ketinggian relatif. Misalnya, jika puncak bukit A dua kali lebih tinggi dari puncak bukit B, maka kami ingin menghabiskan waktu dua kali lebih banyak di A daripada di B.
Ada skema yang lebih kompleks untuk mengusulkan tempat dan aturan baru untuk adopsi mereka, tetapi gagasan utamanya adalah sebagai berikut:
- Pilih lokasi "disarankan" baru.
- Cari tahu seberapa tinggi atau lebih rendah lokasi ini dibandingkan dengan yang sekarang.
- Tetap di tempat atau pindah ke tempat baru dengan probabilitas sebanding dengan ketinggian tempat.
Tujuan dari MCMC adalah untuk memilih dari beberapa distribusi probabilitas tanpa harus mengetahui tingginya yang tepat pada titik mana pun (tidak perlu tahu C).
Jika proses "mengembara" diatur dengan benar, Anda dapat memastikan bahwa proporsionalitas ini (antara waktu yang dihabiskan dan tinggi distribusi) tercapai .
Algoritma:
Sekarang mari kita mendefinisikan dan menggambarkan tugas dalam istilah yang lebih formal. Misalkan s = (s1, s2, ..., sM) menjadi distribusi stasioner yang diinginkan. Kami ingin membuat rantai Markov dengan distribusi stasioner seperti itu. Kita mulai dengan rantai Markov yang berubah-ubah dengan M-state dengan matriks transisi P, sehingga pij mewakili probabilitas transisi dari state i ke j.
Secara intuitif, kita tahu bagaimana menjelajah rantai Markov, tetapi rantai Markov tidak memiliki distribusi stasioner yang diperlukan. Rantai ini memiliki beberapa distribusi stasioner (yang tidak kita butuhkan). Tujuan kami adalah mengubah cara kami menjelajahi rantai Markov sehingga rantai memiliki distribusi stasioner yang diinginkan.
Untuk melakukan ini:
- Mulai dengan keadaan awal acak i.
- Secara acak pilih keadaan diasumsikan baru dengan melihat probabilitas transisi di baris ke-i dari matriks transisi P.
- Hitung ukuran yang disebut probabilitas keputusan, yang didefinisikan sebagai: aij = min (sj.pji / si.pij, 1).
- Sekarang lempar koin, yang mendarat di permukaan elang dengan probabilitas aij. Jika seekor elang jatuh, terimalah tawaran itu, yaitu pergi ke keadaan berikutnya, jika tidak, tolak tawaran itu, yaitu, tetap dalam keadaan saat ini.
- Ulangi berkali-kali.
Setelah sejumlah besar tes, rantai ini akan bertemu dan memiliki distribusi stasioner. Kemudian kita dapat menggunakan status rantai sebagai sampel dari distribusi apa pun.
Dengan melakukan ini untuk mengambil sampel distribusi beta, satu-satunya waktu Anda harus menggunakan kepadatan probabilitas adalah untuk mencari probabilitas membuat keputusan. Untuk melakukan ini, bagi sj dengan si (yaitu, konstanta normalisasi C dibatalkan).
Seleksi Beta
Sekarang kita beralih ke masalah pengambilan sampel dari distribusi beta.
Distribusi beta adalah distribusi kontinu pada [0,1] dan dapat memiliki nilai tak hingga pada [0,1]. Misalkan rantai P Markov yang berubah-ubah dengan status tak terbatas pada [0,1] memiliki matriks transisi P sehingga pij = pji = semua elemen dalam matriks.
Kita tidak perlu Matrix P, seperti yang akan kita lihat nanti, tetapi saya ingin deskripsi masalahnya sedekat mungkin dengan algoritma yang kami usulkan.
- Mulai dengan keadaan awal acak i diperoleh dari distribusi seragam pada (0,1).
- Secara acak pilih keadaan diasumsikan baru dengan melihat probabilitas transisi di baris ke-i dari matriks transisi P. Misalkan kita memilih negara lain Unif (0,1) sebagai keadaan diasumsikan j.
- Hitung ukurannya, yang disebut probabilitas membuat keputusan:
Yang disederhanakan menjadi:
Karena pji = pij, dan di mana
- Sekarang lempar koin. Dengan probabilitas aij seekor elang akan jatuh. Jika elang jatuh, maka Anda harus menerima tawaran itu, yaitu, pindah ke negara bagian berikutnya. Kalau tidak, ada baiknya menolak tawaran itu, yaitu tetap dalam keadaan yang sama.
- Ulangi tes ini berkali-kali.
Kode:
Saatnya beralih dari teori ke praktik. Kami akan menulis sampel beta kami dengan Python.
impo rt rand om
Bandingkan hasilnya dengan distribusi beta yang sebenarnya.
impo rt num py as np import pylab as pl import scipy.special as ss %matplotlib inline pl.rcParams['figure.figsize'] = (17.0, 4.0)
Seperti yang Anda lihat, nilainya sangat mirip dengan distribusi beta. Dengan demikian, jaringan MCMC telah mencapai kondisi stasioner
Dalam kode di atas, kami membuat sampler beta, tetapi konsep yang sama berlaku untuk distribusi lain dari mana kami ingin membuat pilihan.
Kesimpulan
Itu adalah pos yang bagus. Selamat jika Anda membacanya sampai akhir.
Intinya, metode MCMC bisa rumit, tetapi mereka memberi kita fleksibilitas yang besar. Anda dapat memilih dari fungsi distribusi apa saja menggunakan pilihan melalui MCMC. Biasanya, metode ini digunakan untuk mengambil sampel dari distribusi posterior.
Anda juga dapat menggunakan MCMC untuk memecahkan masalah dengan ruang keadaan besar. Misalnya, dalam masalah ransel atau untuk dekripsi. Saya akan mencoba memberi Anda contoh-contoh yang lebih menarik di posting
selanjutnya . Tetap disini.
Dari para editor