มอนเตการ์โลห่วงโซ่มาร์คอฟ

มอนเตการ์โลลูกโซ่มาร์คอฟ (Markov chain Monte Carlo) มักเรียกย่อเป็น MCMC เป็นคำเรียกทั่วไปสำหรับขั้นตอนวิธี ต่าง ๆ ที่ใช้สุ่มตัวอย่างการแจกแจงความน่าจะเป็นโดยการสร้างลูกโซ่มาร์คอฟ ซึ่งมีการแจกแจงความน่าจะเป็นที่ต้องการเป็นการแจกแจงคงที่ โดยจะทำการสร้างค่าสุ่มตัวถัดไปตามร่วมไปเรื่อย ๆ วิธีการ MCMC ที่เป็นที่รู้จักอย่างดีได้แก่ และ เป็นต้น

ภาพรวม

ตัวอย่างความพยายามในการประมาณการแจกแจงเส้นสีน้ำเงินโดยใช้การแจกแจงเส้นสีส้มด้วย ซึ่งเป็น MCMC แบบหนึ่ง

สถานะของลูกโซ่มาร์คอฟหลังจากการสุ่มตัวอย่างด้วย MCMC จำนวนมากเพียงพอจะใช้เป็นตัวอย่างของการกระจายเป้าหมายที่ต้องการ เมื่อจำนวนการทดลองเพิ่มขึ้น คุณภาพของตัวอย่างก็จะดีขึ้นเช่นกัน

โดยปกติแล้วการสร้างลูกโซ่มาร์คอฟที่มีสมบัติที่ต้องการไม่ใช่เรื่องยาก ปัญหาคือการกำหนดจำนวนครั้งในการทำจนกว่าจะมาบรรจบกันเป็นการแจกแจงคงที่ในระดับความผิดพลาดที่ยอมรับได้ หากกำหนดโซ่ได้เหมาะสม ก็จะสามารถลู่เข้าสู่การแจกแจงคงที่ได้อย่างรวดเร็วไม่ว่าลูกโซ่จะเริ่มต้นจากตำแหน่งใดก็ตาม เรียกว่าเป็น การผสมอย่างรวดเร็ว (rapid mixing)

วิธี MCMC โดยพื้นฐานจะได้รับผลจากการกำหนดค่าเริ่มต้นทำให้สามารถทำการประมาณได้แค่การแจกแจงเป้าหมายได้เท่านั้น ขั้นตอนวิธีที่ยืนพื้นจาก MCMC ที่ซับซ้อนมากขึ้น เช่น วิธี (CFTP) สามารถสร้างตัวอย่างที่สมบูรณ์ได้ แต่ก็จะมีความซับซ้อนในการคำนวณมากขึ้นและต้องใช้เวลาในการคำนวณอย่างไม่มีขีดจำกัด

การประยุกต์ใช้

การประยุกต์ใช้ขั้นตอนวิธีนี้โดยทั่วไปเช่นการคำนวณเชิงตัวเลข สมมติว่ากลุ่มของอนุภาคเดินไปมาแบบสุ่ม แต่ละครั้งที่อนุภาคผ่านจุดหนึ่ง ค่าฟังก์ชันของปริพันธ์ ณ จุดนั้นจะถูกบวกเข้ากับปริพันธ์ จากนั้นอนุภาคจะค้นหาตำแหน่งที่ส่งผลต่อปริพันธ์สูงแล้วเคลื่อนที่ชั่วคราวหลายครั้ง วิธีนี้เรียกว่าวิธีเดินสุ่ม ซึ่งเป็นวิธีจำลองตัวเลขสุ่มหรือ วิธีมอนเตการ์โล แม้ว่าตัวอย่างแบบสุ่มของปริพัทธ์ที่ใช้ในวิธีมอนเตการ์โลแบบดั้งเดิมจะมีความเป็นอิสระ แต่ตัวอย่างที่ใช้ใน MCMC ก็มีสหสัมพันธ์ต่อกัน

ปริพันธ์หลายชั้นมักปรากฏใน ฯลฯ ดังนั้น MCMC จึงถูกนำมาใช้กันอย่างแพร่หลายในสาขาดังกล่าว

การใช้ MCMC ทำให้สามารถคำนวณโครงข่ายแบบเบส์หลายลำดับขั้นขนาดใหญ่ซึ่งต้องทำการหาปริพันธ์เป็นร้อยเป็นพันครั้งได้

อ้างอิง

1. 完壁にサンプリングしよう！一第一話 遥かなる過去から－
2. Kasim, M.F.; Bott, A.F.A.; Tzeferacos, P.; Lamb, D.Q.; Gregori, G.; Vinko, S.M. (September 2019). "Retrieving fields from proton radiography without source profiles". Physical Review E. 100 (3): 033208. :1905.12934. Bibcode:2019PhRvE.100c3208K. doi:10.1103/PhysRevE.100.033208. PMID 31639953. S2CID 170078861.
3. Gupta, Ankur; Rawlings, James B. (April 2014). "Comparison of Parameter Estimation Methods in Stochastic Chemical Kinetic Models: Examples in Systems Biology". AIChE Journal. 60 (4): 1253–1268. Bibcode:2014AIChE..60.1253G. doi:10.1002/aic.14409. PMC 4946376. PMID 27429455.
4. Gill, Jeff (2008). Bayesian methods: a social and behavioral sciences approach. London: Chapman and Hall/CRC. ISBN .
5. Robert, Christian P; Casella, G (2004). Monte Carlo statistical methods. New York: Springer. ISBN .
6. Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. (2014-09-12). Hierarchical Modeling and Analysis for Spatial Data (Second ed.). CRC Press. p. xix. ISBN .