Bagaimana Anda menjelaskan Markov Chain Monte Carlo (MCMC) kepada orang awam?

Mungkin konsepnya, mengapa itu digunakan, dan sebuah contoh.

Pertama, kita perlu memahami apa itu rantai Markov. Perhatikan contoh cuaca berikut dari Wikipedia. Misalkan cuaca pada hari tertentu dapat diklasifikasikan menjadi dua negara saja: cerah dan hujan. Berdasarkan pengalaman sebelumnya, kami tahu yang berikut:

$P(\text{Next day is Sunny}\,\vert \,\text{Given today is Rainy)}=0.50$

Karena, cuaca hari berikutnya cerah atau hujan, maka berikut ini:

$P(\text{Next day is Rainy}\,\vert \,\text{Given today is Rainy)}=0.50$

Demikian pula, biarkan:

$P(\text{Next day is Rainy}\,\vert \,\text{Given today is Sunny)}=0.10$

Oleh karena itu, dapat disimpulkan bahwa:

$P(\text{Next day is Sunny}\,\vert \,\text{Given today is Sunny)}=0.90$

Keempat angka di atas dapat direpresentasikan secara kompak sebagai matriks transisi yang mewakili probabilitas cuaca bergerak dari satu negara ke negara lain sebagai berikut:

$P = \begin{bmatrix} & S & R \\ S& 0.9 & 0.1 \\ R& 0.5 & 0.5 \end{bmatrix}$

Kami mungkin mengajukan beberapa pertanyaan yang jawabannya mengikuti:

T1: Jika cuaca cerah hari ini, apa yang akan terjadi besok?

A1: Karena, kita tidak tahu apa yang akan terjadi dengan pasti, yang terbaik yang dapat kita katakan adalah bahwa ada kemungkinan kemungkinannya cerah dan hujan akan turun.10 $90\%$$10\%$

T2: Bagaimana dengan dua hari dari hari ini?

A2: Prediksi satu hari: cerah, hujan. Karenanya, dua hari dari sekarang:10 $90\%$$10\%$

Hari pertama bisa cerah dan hari berikutnya juga bisa cerah. Peluang terjadinya ini adalah: .$0.9 \times 0.9$

Atau

Hari pertama bisa hujan dan hari kedua bisa cerah. Peluang terjadinya ini adalah: .$0.1 \times 0.5$

Oleh karena itu, kemungkinan cuaca akan cerah dalam dua hari adalah:

$P(\text{Sunny 2 days from now} = 0.9 \times 0.9 + 0.1 \times 0.5 = 0.81 + 0.05 = 0.86$

Demikian pula, kemungkinan hujan akan:

$P(\text{Rainy 2 days from now} = 0.1 \times 0.5 + 0.9 \times 0.1 = 0.05 + 0.09 = 0.14$

Dalam aljabar linier (matriks transisi) perhitungan ini sesuai dengan semua permutasi dalam transisi dari satu langkah ke langkah berikutnya (cerah-ke-cerah ( ), cerah-ke-hujan ( ), hujan-ke-cerah ( ) atau rainy-to-rainy ( )) dengan probabilitas yang dihitung:S 2 R R 2 S R 2$S_2S$$S_2R$$R_2S$$R_2R$

Pada bagian bawah gambar kita melihat bagaimana menghitung probabilitas keadaan masa depan ( atau ) mengingat probabilitas (fungsi massa probabilitas, ) untuk setiap negara (cerah atau hujan) pada waktu nol (sekarang atau ) sebagai perkalian matriks sederhana.t + 2 P M F t $t+1$$t+2$$PMF$$t_0$

Jika Anda terus meramalkan cuaca seperti ini, Anda akan melihat bahwa pada akhirnya ramalan hari ke- , di mana sangat besar (katakanlah ), menetap pada probabilitas 'kesetimbangan' berikut:n $n$$n$$30$

$P(\text{Sunny}) = 0.833$

dan

$P(\text{Rainy}) = 0.167$

Dengan kata lain, perkiraan Anda untuk hari -th dan hari -th tetap sama. Selain itu, Anda juga dapat memeriksa bahwa probabilitas 'kesetimbangan' tidak bergantung pada cuaca hari ini. Anda akan mendapatkan perkiraan cuaca yang sama jika Anda memulai dengan mengasumsikan bahwa cuaca hari ini cerah atau hujan.n + $n$$n+1$

Contoh di atas hanya akan berfungsi jika probabilitas transisi negara memenuhi beberapa kondisi yang tidak akan saya bahas di sini. Tapi, perhatikan fitur berikut dari rantai Markov yang 'bagus' ini (nice = probabilitas transisi memenuhi kondisi):

Terlepas dari keadaan awal awal kita akhirnya akan mencapai distribusi probabilitas keseimbangan negara.

Markov Chain Monte Carlo mengeksploitasi fitur di atas sebagai berikut:

Kami ingin menghasilkan undian acak dari distribusi target. Kami kemudian mengidentifikasi cara untuk membangun rantai Markov 'bagus' sedemikian rupa sehingga distribusi probabilitas keseimbangannya adalah distribusi target kami.

Jika kita dapat membangun rantai seperti itu maka kita sewenang-wenang mulai dari beberapa titik dan mengulangi rantai Markov berkali-kali (seperti bagaimana kita meramalkan cuaca kali). Akhirnya, undian yang kami hasilkan akan muncul seolah-olah berasal dari distribusi target kami.$n$

Kami kemudian memperkirakan jumlah bunga (misalnya rata-rata) dengan mengambil rata-rata sampel undian setelah membuang beberapa undian awal yang merupakan komponen Monte Carlo.

Ada beberapa cara untuk membangun rantai Markov yang 'bagus' (mis., Gibbs sampler, algoritma Metropolis-Hastings).

Saya pikir ada intuisi yang bagus dan sederhana yang didapat dari algoritma Metropolis-Hastings (rantai-kemerdekaan).

Pertama, apa tujuannya? Tujuan MCMC adalah untuk mengambil sampel dari beberapa distribusi probabilitas tanpa harus mengetahui tingginya tepat di titik mana pun. Cara MCMC mencapai ini adalah untuk "berkeliaran" pada distribusi sedemikian rupa sehingga jumlah waktu yang dihabiskan di setiap lokasi sebanding dengan tinggi distribusi. Jika proses "berkeliling" diatur dengan benar, Anda dapat memastikan bahwa proporsionalitas ini (antara waktu yang dihabiskan dan tinggi distribusi) tercapai.

Secara intuitif, apa yang ingin kita lakukan adalah berjalan-jalan di atas permukaan (kental) sedemikian rupa sehingga jumlah waktu yang kita habiskan (atau # sampel diambil) di setiap lokasi sebanding dengan ketinggian permukaan di lokasi itu. Jadi, misalnya, kami ingin menghabiskan dua kali lebih banyak waktu di puncak bukit yang berada di ketinggian 100m seperti yang kami lakukan di bukit terdekat yang berada di ketinggian 50m. Yang menyenangkan adalah kita bisa melakukan ini bahkan jika kita tidak tahu ketinggian absolut dari titik-titik di permukaan: yang harus kita ketahui adalah ketinggian relatif . mis., jika satu puncak bukit A dua kali lebih tinggi dari puncak bukit B, maka kami ingin menghabiskan dua kali lebih banyak waktu di A daripada yang kami habiskan di B.

Varian paling sederhana dari algoritma Metropolis-Hastings (pengambilan sampel dengan rantai kemandirian) mencapai hal ini sebagai berikut: asumsikan bahwa dalam setiap langkah waktu (diskrit), kami memilih lokasi "usulan" acak baru (dipilih secara seragam di seluruh permukaan). Jika lokasi yang diusulkan lebih tinggi dari tempat kita berdiri sekarang, pindahlah ke sana. Jika lokasi yang diusulkan lebih rendah, maka pindah ke lokasi baru dengan probabilitas p, di mana p adalah rasio ketinggian titik itu dengan ketinggian lokasi saat ini. (yaitu, melempar koin dengan probabilitas p untuk mendapatkan kepala; jika muncul kepala, pindah ke lokasi baru; jika muncul ekor, tetap di tempat kita berada). Menyimpan daftar lokasi yang pernah Anda kunjungi di setiap langkah waktu, dan daftar itu akan (secara mesir) memiliki proporsi waktu yang tepat untuk digunakan di setiap bagian permukaan.

Ada skema yang lebih rumit untuk mengusulkan lokasi baru dan aturan untuk menerimanya, tetapi gagasan dasarnya masih: (1) memilih lokasi "yang diusulkan" baru; (2) mencari tahu seberapa tinggi atau lebih rendah lokasi itu dibandingkan dengan lokasi Anda saat ini; (3) secara probabilistik tinggal menempatkan atau pindah ke lokasi itu dengan cara yang menghormati tujuan keseluruhan menghabiskan waktu sebanding dengan ketinggian lokasi.

Apa gunanya ini? Misalkan kita memiliki model probabilistik cuaca yang memungkinkan kita untuk mengevaluasi A * P (cuaca), di mana A adalah konstanta yang tidak diketahui. (Ini sering terjadi - banyak model yang nyaman untuk dirumuskan sedemikian rupa sehingga Anda tidak dapat menentukan apa itu A). Jadi kita tidak bisa mengevaluasi P ("hujan besok"). Namun, kita dapat menjalankan MCMC sampler untuk sementara waktu dan kemudian bertanya: berapa fraksi sampel (atau "lokasi") yang berakhir dalam keadaan "hujan besok". Fraksi itu akan menjadi prakiraan cuaca probabilistik (berbasis model).

Saya mungkin akan mengatakan sesuatu seperti ini:

"Kapan pun kami ingin berbicara tentang probabilitas, kami benar-benar mengintegrasikan kepadatan. Dalam analisis Bayesian, banyak kepadatan yang kami temukan tidak dapat ditelusuri secara analitis: Anda hanya dapat mengintegrasikannya - jika Anda dapat mengintegrasikannya sama sekali - dengan banyak penderitaan. Jadi yang kita lakukan adalah mensimulasikan banyak variabel acak, dan kemudian mencari tahu probabilitas dari angka acak yang disimulasikan. Jika kita ingin mengetahui probabilitas bahwa X kurang dari 10, kita menghitung proporsi hasil variabel acak disimulasikan kurang dari 10 dan menggunakannya sebagai perkiraan kami.Itu adalah bagian "Monte Carlo", ini merupakan estimasi probabilitas berdasarkan dari angka acak. Dengan cukup angka acak simulasi, estimasi ini sangat baik, tetapi masih secara acak acak.

"Jadi mengapa" Rantai Markov "? Karena dalam kondisi teknis tertentu, Anda dapat menghasilkan proses tanpa memori (alias yang Markovian) yang memiliki distribusi pembatas yang sama dengan variabel acak yang Anda coba simulasikan. Anda dapat mengulangi jumlah berbagai jenis proses simulasi yang menghasilkan angka acak berkorelasi (hanya berdasarkan nilai saat ini dari angka-angka itu), dan Anda dijamin bahwa setelah Anda mengumpulkan cukup hasil, Anda akan berakhir dengan tumpukan angka yang terlihat " seolah-olah "Anda entah bagaimana berhasil mengambil sampel independen dari distribusi rumit yang ingin Anda ketahui.

"Jadi misalnya, jika saya ingin memperkirakan probabilitas bahwa variabel acak normal standar kurang dari 0,5, saya dapat menghasilkan sepuluh ribu realisasi independen dari distribusi normal standar dan menghitung jumlahnya kurang dari 0,5; katakanlah saya mendapat 6905 yang merupakan kurang dari 0,5 dari total 10.000 sampel; perkiraan saya untuk P (Z <0,5) akan menjadi 0,6905, yang tidak jauh dari nilai aktual. Itu akan menjadi estimasi Monte Carlo.

daftar angka yang saya dapatkan dari prosedur akan didistribusikan seperti sejumlah besar penarikan dari sesuatu yang menghasilkan variabel acak normal. Ini akan memberi saya simulasi Markov Chain Monte Carlo untuk variabel acak normal standar. Jika saya menggunakan ini untuk memperkirakan probabilitas, itu akan menjadi estimasi MCMC. "

Bayangkan Anda ingin menemukan strategi yang lebih baik untuk mengalahkan teman-teman Anda di papan permainan Monopoly. Sederhanakan hal-hal yang penting dalam permainan untuk pertanyaan: properti apa yang paling banyak didaratkan orang? Jawabannya tergantung pada struktur papan, aturan permainan dan lemparan dua dadu.

Salah satu cara untuk menjawab pertanyaan adalah ini. Cukup ikuti satu bagian di papan saat Anda melempar dadu dan ikuti aturan. Hitung berapa kali Anda mendarat di masing-masing properti (atau program komputer untuk melakukan pekerjaan untuk Anda). Akhirnya, jika Anda memiliki cukup kesabaran atau Anda telah memprogram aturan dengan cukup baik di komputer Anda, Anda akan membangun gambaran bagus tentang properti mana yang paling banyak bisnis. Ini akan membantu Anda menang lebih sering.

Apa yang telah Anda lakukan adalah analisis Markov Chain Monte Carlo (MCMC). Dewan mendefinisikan aturan. Di mana Anda mendarat selanjutnya hanya bergantung pada di mana Anda berada sekarang, bukan di mana Anda sebelumnya dan probabilitas spesifik ditentukan oleh distribusi lemparan dua dadu. MCMC adalah aplikasi ide ini untuk sistem matematika atau fisik seperti apa cuaca besok atau di mana butiran serbuk sari yang secara acak dihantam oleh molekul gas akan berakhir.

OK, inilah upaya terbaik saya untuk penjelasan yang tidak resmi dan kasar.

Rantai Markov adalah proses acak yang memiliki properti yang masa depan hanya bergantung pada kondisi saat ini dari proses dan bukan masa lalu yaitu tidak memiliki memori. Contoh dari proses acak dapat berupa pertukaran saham. Contoh Rantai Markov adalah permainan papan seperti Monopoli atau Snakes and Ladders di mana posisi masa depan Anda (setelah menggulirkan dadu) hanya akan bergantung pada di mana Anda mulai dari sebelum roll, bukan posisi Anda sebelumnya. Contoh buku teks dari Rantai Markov adalah "pemabuk jalan". Bayangkan seseorang yang mabuk dan hanya bisa bergerak ke kiri atau kanan dengan satu langkah. Pemabuk bergerak ke kiri atau kanan dengan probabilitas yang sama. Ini adalah Rantai Markov di mana masa depan / posisi mabuk si pemabuk hanya bergantung pada di mana ia berada saat ini.

Metode Monte Carlo adalah algoritma komputasi (hanya set instruksi) yang secara acak mengambil sampel dari beberapa proses yang sedang dipelajari. Mereka adalah cara memperkirakan sesuatu yang terlalu sulit atau memakan waktu untuk menemukan secara deterministik. Mereka pada dasarnya adalah bentuk simulasi komputer dari beberapa proses matematika atau fisik. Moniker Monte Carlo berasal dari analogi antara kasino dan generasi angka acak. Kembali ke contoh permainan papan kami sebelumnya, mungkin kami ingin tahu apakah beberapa properti di papan Monopoli dikunjungi lebih sering daripada yang lain. Eksperimen Monte Carlo akan melibatkan pengguliran dadu berulang kali dan menghitung berapa kali Anda mendarat di setiap properti. Ini juga dapat digunakan untuk menghitung integral numerik. (Sangat informal, kita dapat menganggap integral sebagai area di bawah grafik beberapa fungsi. ) Integrasi Monte Carlo bekerja sangat baik pada fungsi dimensi tinggi dengan mengambil sampel acak titik fungsi dan menghitung beberapa jenis rata-rata di berbagai titik ini. Dengan menambah ukuran sampel, hukum angka besar memberi tahu kita bahwa kita dapat meningkatkan akurasi perkiraan kita dengan mencakup lebih banyak fungsi.

Kedua konsep ini dapat disatukan untuk memecahkan beberapa masalah sulit di bidang-bidang seperti inferensi Bayesian, biologi komputasi, dll di mana integral multi-dimensi perlu dihitung untuk memecahkan masalah umum. Idenya adalah untuk membangun Rantai Markov yang menyatu dengan distribusi probabilitas yang diinginkan setelah beberapa langkah. Keadaan rantai setelah sejumlah besar langkah kemudian digunakan sebagai sampel dari distribusi yang diinginkan dan proses diulang. Ada banyak algoritma MCMC berbeda yang menggunakan teknik berbeda untuk menghasilkan Rantai Markov. Yang umum termasuk Metropolis-Hastings dan Gibbs Sampler.

Kutipan dari Metode Bayesian untuk Peretas

Lanskap Bayesian

$N$$N$$p_1$$p_2$

$\text{Exp}(3)$$\text{Exp}(10)$

Visualisasi di bawah ini menunjukkan ini. Semakin gelap warnanya, semakin besar probabilitas sebelumnya bahwa yang tidak diketahui berada di lokasi itu. Sebaliknya, area dengan warna biru gelap menunjukkan bahwa prior kami menetapkan probabilitas sangat rendah untuk yang tidak diketahui berada di sana.

Ini adalah contoh sederhana dalam ruang 2D, di mana otak kita dapat memahami permukaan dengan baik. Dalam praktiknya, ruang dan permukaan yang dihasilkan oleh prior kita dapat memiliki dimensi yang jauh lebih tinggi.

$X$$X$mendorong permukaan asli untuk membuat gunung tinggi . Jumlah dorongan naik ditentang oleh probabilitas sebelumnya, sehingga probabilitas sebelumnya yang lebih sedikit berarti lebih banyak resistensi. Jadi dalam kasus eksponensial-sebelumnya ganda di atas, sebuah gunung (atau beberapa gunung) yang mungkin meletus di dekat sudut (0,0) akan jauh lebih tinggi daripada gunung yang meletus lebih dekat ke (5,5), karena ada lebih banyak perlawanan di dekat (5,5). Gunung, atau mungkin lebih umum, pegunungan, mencerminkan probabilitas posterior di mana parameter sebenarnya mungkin ditemukan.

$\lambda$

$\text{Uniform}(0,5)$

Titik hitam mewakili parameter sebenarnya. Bahkan dengan 1 titik sampel, seperti apa yang disimulasikan di atas, pegunungan mencoba memuat parameter sebenarnya. Tentu saja, kesimpulan dengan ukuran sampel 1 adalah sangat naif, dan memilih ukuran sampel sekecil itu hanya ilustrasi.

Menjelajahi lanskap menggunakan MCMC

$N$$N$$N$dari distribusi posterior, bukan distribusi itu sendiri. Merentangkan analogi pegunungan kami hingga batasnya, MCMC melakukan tugas yang serupa dengan berulang kali bertanya, "Seberapa besar kemungkinan kerikil yang saya temukan ini berasal dari gunung yang saya cari?", Dan menyelesaikan tugasnya dengan mengembalikan ribuan kerikil yang diterima dengan harapan merekonstruksi kembali. gunung aslinya. Dalam istilah MCMC dan PyMC, urutan kembali "kerikil" adalah sampel, lebih sering disebut jejak .

Ketika saya mengatakan pencarian MCMC cerdas, maksud saya MCMC mudah - mudahan akan bertemu ke daerah-daerah probabilitas posterior tinggi. MCMC melakukan ini dengan menjelajahi posisi terdekat dan pindah ke area dengan probabilitas lebih tinggi. Sekali lagi, mungkin "konvergen" bukanlah istilah yang akurat untuk menggambarkan perkembangan MCMC. Konvergen biasanya menyiratkan bergerak menuju titik di ruang angkasa, tetapi MCMC bergerak menuju area yang lebih luas di ruang tersebut dan berjalan secara acak di area itu, mengambil sampel dari area itu.

Pada awalnya, mengembalikan ribuan sampel kepada pengguna mungkin terdengar seperti cara yang tidak efisien untuk menggambarkan distribusi posterior. Saya berpendapat bahwa ini sangat efisien. Pertimbangkan kemungkinan alternatif ::

1. Mengembalikan rumus matematika untuk "pegunungan" akan melibatkan menggambarkan permukaan N-dimensi dengan puncak dan lembah sewenang-wenang.
2. Mengembalikan "puncak" lanskap, sementara secara matematis dimungkinkan dan hal yang masuk akal untuk dilakukan karena titik tertinggi sesuai dengan perkiraan yang paling mungkin dari yang tidak diketahui, mengabaikan bentuk lanskap, yang sebelumnya kami katakan sangat penting dalam menentukan kepercayaan posterior pada yang tidak diketahui.

Selain alasan komputasi, kemungkinan alasan terkuat untuk mengembalikan sampel adalah bahwa kita dapat dengan mudah menggunakan Hukum Angka Besar untuk memecahkan masalah yang tidak dapat dipecahkan. Saya menunda diskusi ini untuk bab berikutnya.

Algoritma untuk melakukan MCMC

Ada keluarga besar algoritma yang melakukan MCMC. Secara sederhana, sebagian besar algoritma dapat diekspresikan pada level tinggi sebagai berikut:

1. Start at current position.
2. Propose moving to a new position (investigate a pebble near you ).
3. Accept the position based on the position's adherence to the data 
and prior distributions (ask if the pebble likely came from the mountain).
4. If you accept: Move to the new position. Return to Step 1.
5. After a large number of iterations, return the positions.

Dengan cara ini kami bergerak ke arah umum menuju daerah-daerah di mana distribusi posterior ada, dan mengumpulkan sampel dengan hemat dalam perjalanan. Setelah kami mencapai distribusi posterior, kami dapat dengan mudah mengumpulkan sampel karena semuanya kemungkinan termasuk dalam distribusi posterior.

Jika posisi saat ini dari algoritma MCMC berada di daerah dengan probabilitas sangat rendah, yang sering terjadi ketika algoritma dimulai (biasanya di lokasi acak di ruang), algoritma akan bergerak di posisi yang kemungkinan bukan dari posterior tetapi lebih baik daripada segala sesuatu di dekatnya. Dengan demikian langkah pertama dari algoritma tidak mencerminkan posterior.

Jadi ada banyak jawaban di sini diparafrasekan dari statistik / buku teks probabilitas, Wikipedia, dll. Saya percaya kita memiliki "orang awam" tempat saya bekerja; Saya pikir mereka ada di departemen pemasaran. Jika saya harus menjelaskan sesuatu yang teknis kepada mereka, saya menerapkan aturan "tunjukkan jangan beri tahu." Dengan mengingat aturan itu, saya mungkin akan menunjukkan kepada mereka sesuatu seperti ini.

Idenya di sini adalah untuk mencoba kode algoritma yang dapat saya ajarkan mengeja - bukan dengan mempelajari semua ratusan (ribuan?) Aturan seperti Ketika menambahkan akhiran kata yang diakhiri dengan e diam, jatuhkan e akhir jika akhiran dimulai dengan vokal . Salah satu alasan yang tidak akan berhasil adalah saya tidak tahu aturan-aturan itu (saya bahkan tidak yakin yang saya ucapkan itu benar). Alih-alih, saya akan mengajarkannya mengeja dengan menunjukkannya sejumlah kata yang dieja dengan benar dan membiarkannya mengekstrak aturan dari kata-kata itu, yang lebih atau kurang merupakan esensi dari Pembelajaran Mesin, terlepas dari algoritma - ekstraksi pola dan pengenalan pola .

Kriteria sukses adalah mengeja dengan benar kata yang belum pernah dilihat oleh algoritma (saya menyadari bahwa itu bisa terjadi secara kebetulan, tetapi itu tidak akan terjadi pada orang-orang pemasaran, jadi saya akan mengabaikan - plus saya akan memiliki algoritma mencoba mengeja bukan satu kata, tetapi banyak, jadi kemungkinan besar kita tidak akan tertipu oleh beberapa tebakan beruntung).

Sekitar satu jam yang lalu, saya mengunduh (sebagai file teks biasa) dari Project Gutenberg Site yang sangat baik, novel Herman Hesse Siddhartha . Saya akan menggunakan kata-kata dalam novel ini untuk mengajarkan algoritma bagaimana mengeja.

Jadi saya memberi kode pada algoritma di bawah ini yang memindai novel ini, tiga huruf sekaligus (setiap kata memiliki satu karakter tambahan di akhir, yaitu 'spasi putih', atau akhir kata). Urutan tiga huruf dapat memberi tahu Anda banyak - misalnya, huruf 'q' hampir selalu diikuti oleh 'u'; urutan 'ty' biasanya terjadi di akhir kata; z jarang melakukannya, dan sebagainya. (Catatan: Saya bisa dengan mudah memberinya seluruh kata untuk melatihnya berbicara dalam kalimat lengkap - ide yang persis sama, hanya beberapa tweak untuk kode.)

Namun semua ini tidak melibatkan MCMC, yang terjadi setelah pelatihan, ketika kami memberikan algoritma beberapa huruf acak (sebagai seed) dan mulai membentuk 'kata-kata'. Bagaimana algoritma membangun kata-kata? Bayangkan ada blok 'qua'; surat apa yang ditambahkan selanjutnya? Selama pelatihan, algoritma ini membangun matriks frekuensi * urutan eter-urutan besar * dari ribuan kata dalam novel. Di suatu tempat dalam matriks itu adalah blok tiga huruf 'qua' dan frekuensi untuk karakter yang dapat mengikuti urutan. Algoritma memilih surat berdasarkan frekuensi yang mungkin bisa mengikutinya. Jadi huruf yang dipilih algoritma tergantung pada - dan hanya pada - tiga terakhir dalam antrian konstruksi kata.

Jadi itulah algoritma Markov Chain Monte Carlo.

Saya pikir mungkin cara terbaik untuk menggambarkan cara kerjanya adalah dengan menunjukkan hasil berdasarkan berbagai tingkat pelatihan. Level pelatihan bervariasi dengan mengubah jumlah lintasan yang dibuat oleh algoritma melalui novel - semakin banyak lintasan, semakin besar kesetiaan matriks frekuensi urutan-hurufnya. Di bawah ini adalah hasil - dalam bentuk output string 100-karakter oleh algoritma - setelah pelatihan pada novel 'Siddharta'.

Satu kali melewati novel, Siddhartha :

lalu whoicks ger wiff semua mothany stand ar kamu lart theartim mudull sullintionexpraid his sible nya

(Langsung, itu dipelajari untuk berbicara bahasa Welsh yang hampir sempurna; aku tidak menyangka itu.)

Setelah dua melewati novel:

ack wor prenskinith acara adalah twor dilihat thhehe theatin tanah rhatingle adalah ov ada

Setelah 10 berlalu:

meskipun tetapi harus berdoa dengan ACK sekarang memiliki air kaki tuas anjingnya masing-masing bukan memori lemah

Dan ini kodenya (dengan Python, saya hampir yakin ini bisa dilakukan di R menggunakan paket MCMC, yang ada beberapa, hanya dalam 3-4 baris)

def create_words_string(raw_string) :
  """ in case I wanted to use training data in sentence/paragraph form; 
      this function will parse a raw text string into a nice list of words;
      filtering: keep only words having  more than 3 letters and remove 
      punctuation, etc.
  """
  pattern = r'\b[A-Za-z]{3,}\b'
  pat_obj = re.compile(pattern)
  words = [ word.lower() for word in pat_obj.findall(raw_string) ]
  pattern = r'\b[vixlm]+\b'
  pat_obj = re.compile(pattern)
  return " ".join([ word for word in words if not pat_obj.search(word) ])

def create_markov_dict(words_string):
  # initialize variables
  wb1, wb2, wb3 = " ", " ", " "
  l1, l2, l3 = wb1, wb2, wb3
  dx = {}
  for ch in words_string :
    dx.setdefault( (l1, l2, l3), [] ).append(ch)
    l1, l2, l3 = l2, l3, ch
  return dx

def generate_newtext(markov_dict) :
  simulated_text = ""
  l1, l2, l3 = " ", " ", " "
  for c in range(100) :
    next_letter = sample( markov_dict[(l1, l2, l3)], 1)[0]
    simulated_text += next_letter
    l1, l2, l3 = l2, l3, next_letter
  return simulated_text

if __name__=="__main__" :
  # n = number of passes through the training text
  n = 1
  q1 = create_words_string(n * raw_str)
  q2 = create_markov_dict(q1)
  q3 = generate_newtext(q2)
  print(q3)

MCMC biasanya digunakan sebagai alternatif untuk teknik simulasi Monte Carlo. Baik MCMC dan teknik Monte Carlo lainnya digunakan untuk mengevaluasi integral yang sulit tetapi MCMC dapat digunakan secara lebih umum.

Sebagai contoh, masalah umum dalam statistik adalah untuk menghitung hasil rata-rata yang berkaitan dengan beberapa model probabilistik / stokastik. Baik teknik MCMC dan Monte Carlo akan memecahkan masalah ini dengan menghasilkan urutan hasil simulasi yang dapat kita gunakan untuk memperkirakan mean sebenarnya.

Baik teknik MCMC maupun Monte Carlo yang kasar berfungsi sebagai proporsi jangka panjang dari simulasi yang sama dengan hasil yang diberikan akan sama * dengan probabilitas model hasil itu. Oleh karena itu, dengan menghasilkan simulasi yang cukup, hasil yang dihasilkan oleh kedua metode akan akurat.

* Saya katakan sama walaupun secara umum saya harus berbicara tentang set yang terukur. Namun, orang awam mungkin tidak akan tertarik dengan hal ini *

Namun, sementara minyak mentah Monte Carlo melibatkan pembuatan banyak simulasi independen, masing-masing didistribusikan sesuai dengan model distribusi, MCMC melibatkan menghasilkan jalan acak yang dalam "kunjungan" jangka panjang setiap hasil dengan frekuensi yang diinginkan.

Trik untuk MCMC, oleh karena itu, memilih jalan acak yang akan "mengunjungi" setiap hasil dengan frekuensi jangka panjang yang diinginkan.

Contoh sederhana mungkin untuk mensimulasikan dari model yang mengatakan probabilitas hasil "A" adalah 0,5 dan hasil "B" adalah 0,5. Dalam hal ini, jika saya memulai jalan acak pada posisi "A" dan menentukan bahwa pada setiap langkah beralih ke posisi lain dengan probabilitas 0,2 (atau probabilitas lain yang lebih besar dari 0), saya bisa memastikan bahwa setelah banyak sejumlah langkah jalan acak akan mengunjungi masing-masing "A" dan "B" di sekitar 50% langkah - konsisten dengan probabilitas yang ditentukan oleh model kami.

Ini jelas contoh yang sangat membosankan. Namun, ternyata MCMC sering diterapkan dalam situasi di mana sulit untuk menerapkan standar Monte Carlo atau teknik lainnya.

Anda dapat menemukan artikel yang membahas dasar-dasar apa itu dan mengapa ia bekerja di sini:

http://wellredd.uk/basics-markov-chain-monte-carlo/

Saya seorang analis DNA yang menggunakan perangkat lunak genotip probabilistik yang sepenuhnya berkesinambungan untuk menafsirkan bukti DNA dan saya harus menjelaskan bagaimana ini bekerja pada juri. Harus diakui, kami terlalu menyederhanakan dan saya menyadari sebagian dari penyederhanaan ini mengorbankan keakuratan detail spesifik atas nama meningkatkan pemahaman secara keseluruhan. Tapi, dalam konteks juri yang memahami bagaimana proses ini digunakan dalam interpretasi DNA tanpa gelar akademis dan pengalaman profesional bertahun-tahun, mereka mendapatkan intinya :)

Latar belakang: Perangkat lunak ini menggunakan metropolis Hastings MCMC dan model biologis yang meniru perilaku profil DNA yang diketahui (model dibangun berdasarkan data validasi yang dihasilkan oleh laboratorium yang menganalisis banyak profil DNA dari kondisi yang diketahui yang mewakili kisaran yang dijumpai dalam kasus kerja yang tidak diketahui). Ada 8 rantai independen dan kami mengevaluasi konvergensi untuk menentukan apakah akan menjalankan kembali meningkatkan pembakaran dan menerima penerimaan (default burnin 100k accepts dan post 400k accepts)

Ketika ditanya oleh penuntutan / pembelaan tentang MCMC: kami menjelaskannya adalah singkatan dari rantai markov Monte Carlo dan mewakili kelas / jenis khusus dari algoritma yang digunakan untuk pemecahan masalah yang kompleks dan bahwa suatu algoritma hanyalah sebuah kata mewah yang merujuk pada serangkaian prosedur atau rutin dilakukan oleh komputer ... algoritma mcmc beroperasi dengan mengusulkan solusi, mensimulasikan solusi itu, kemudian mengevaluasi seberapa baik simulasi itu mencerminkan data bukti aktual yang diamati ... simulasi yang sesuai dengan bukti pengamatan juga memiliki probabilitas lebih tinggi daripada simulasi yang tidak sesuai dengan pengamatan ... lebih banyak pengambilan sampel / tebakan berulang dari solusi yang diusulkan, rantai Markov menjauh dari solusi probabilitas rendah menuju solusi probabilitas tinggi yang lebih sesuai / menjelaskan profil bukti yang diamati, sampai akhirnya keseimbangan tercapai. tercapai,artinya algoritma memiliki kemampuan terbatas untuk mencicipi proposal baru yang menghasilkan probabilitas yang meningkat secara signifikan

Ketika ditanya tentang metropolis Hastings: kami menjelaskan ini merupakan penyempurnaan dari algoritma MCMC yang menggambarkan proses pengambilan keputusannya menerima atau menolak proposal ... biasanya ini dijelaskan dengan analogi permainan anak-anak "panas / dingin" tetapi saya mungkin telah mempertimbangkan untuk menggunakan " geser ke kanan atau kiri "ketika juri masih sangat muda !! : p Tetapi menggunakan analogi panas / dingin kami, kami selalu menerima tebakan panas dan kadang-kadang akan menerima tebakan dingin sebagian kecil dari waktu dan menjelaskan tujuan kadang-kadang menerima tebakan dingin adalah untuk memastikan rantai mengambil sampel berbagai kemungkinan yang lebih luas seperti menentang terjebak di satu proposal tertentu sebelum keseimbangan aktual

Diedit untuk menambah / memperjelas: dengan analogi panas / dingin kami menjelaskan bahwa dalam permainan anak-anak, pemimpin memilih objek / area target di dalam ruangan dan para pemain bergiliran membuat tebakan arah mana yang bergerak relatif terhadap posisi / posisi mereka saat ini. Pemimpin memberi tahu mereka untuk mengubah posisi mereka / bergerak jika itu adalah tebakan panas dan mereka kehilangan giliran / tetap di posisi jika itu tebakan dingin. Demikian pula, dalam perangkat lunak kami, keputusan untuk memindahkan / menerima hanya bergantung pada probabilitas proposal dibandingkan dengan probabilitas posisi yang saat ini dipegang ... NAMUN, targetnya ditentukan / diketahui oleh pemimpin dalam permainan anak-anak sedangkan target dalam perangkat lunak kami tidak ditentukan sebelumnya - itu benar-benar tidak diketahui (juga mengapa '

Seperti saya katakan, super super mendasar dan benar-benar kurang detail teknis demi meningkatkan pemahaman - kami berusaha untuk menjelaskan tentang tingkat pendidikan sekolah menengah. Jangan ragu untuk memberikan saran. Saya akan memasukkan mereka.

Pertanyaan ini luas namun jawabannya sering kali biasa saja. Atau, Anda dapat melihat makalah ini yang memberikan deskripsi matematis singkat tentang kelas luas dari algoritma MCMC termasuk algoritma Metropolis-Hastings, sampling Gibbs, metode Metropolis-dalam-Gibbs dan variabel tambahan, sampel slice, proposal rekursif, sampel directional, Langevin dan Hamiltonian Monte Carlo, NUTS sampling, algoritma Metropolis-Hastings pseudo-marginal, dan Hamiltonian Monte Carlo pseudo-marginal, seperti yang dibahas oleh penulis.

Ulasan yang kredibel diberikan di sini

Saya akan menemukan lebih banyak waktu untuk menguraikan isinya dalam format stackexchange.

$f(x,y)=z=x^2+2*x*y$$(x,y)$$f(x,y)$$f(x,y)$

$f(x,y,z,t,s,...,zzz)$

Video ini (mulai jam 5:50) memiliki pernyataan intuisi yang sangat bagus.

Bayangkan Anda ingin sampel poin yang ada di cabang hijau (multi-dimensi) dalam gambar ini. Jika Anda melempar poin ke seluruh super-space hitam dan memeriksa nilainya, Anda membuang banyak energi (pencarian) sampling. Jadi akan lebih masuk akal untuk mengontrol strategi pengambilan sampel Anda (yang dapat diotomatisasi) untuk memilih poin yang lebih dekat dengan cabang hijau (yang penting). Cabang hijau dapat ditemukan dengan dipukul sekali secara tidak sengaja (atau dikendalikan), dan sisa upaya pengambilan sampel (titik merah) akan dihasilkan sesudahnya. Alasan merah tertarik ke garis hijau adalah karena matriks transisi rantai Markov yang berfungsi sebagai mesin pengambilan sampel Anda.

Jadi dalam istilah awam, MCMC adalah metode pengambilan sampel hemat energi (biaya rendah), terutama ketika bekerja di ruang yang besar dan 'gelap' (multi dimensi).