มาร์คอฟเชน มอนติคาร์โล

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมการสร้างเชนที่มีฟังก์ชันการแจกแจงสถานะคงที่ที่กำหนดไว้ล่วงหน้าผ่านสมดุลละเอียด (detailed balance), ขั้นตอนวิธีเมโทรโพลิส-เฮสติงส์ (Metropolis-Hastings algorithm) และกลไกการเสนอ (proposal mechanisms), การวินิจฉัยการลู่เข้าและการผสม (convergence and mixing diagnostics), ช่วงเริ่มต้น (burn-in) และสหสัมพันธ์ในตัวเอง (autocorrelation), และการประมาณค่าความคลาดเคลื่อนมาตรฐานมอนติคาร์โล (Monte Carlo standard errors) จากการสุ่มตัวอย่างที่มีความสัมพันธ์กัน ตัวสุ่มกิบบส์ (Gibbs sampler) ถือเป็นหัวข้อที่เกี่ยวข้องแต่แยกต่างหาก และมีการกล่าวถึงรูปแบบแฮมิลตัน (Hamiltonian) และแบบปรับตัว (adaptive variants) ในฐานะส่วนขยาย

Core questions

• จะสร้างมาร์คอฟเชนได้อย่างไรเพื่อให้ฟังก์ชันการแจกแจงสถานะคงที่ของมันเป็นเป้าหมายที่กำหนดไว้ล่วงหน้า?
• ขั้นตอนการยอมรับ-ปฏิเสธของเมโทรโพลิส-เฮสติงส์ (Metropolis-Hastings accept-reject step) บังคับใช้สมดุลละเอียด (detailed balance) สำหรับการเสนอแบบสุ่มได้อย่างไร?
• จะประเมินการลู่เข้าสู่สถานะคงที่ได้อย่างไร และจะวินิจฉัยความเร็วในการผสมได้อย่างไร?
• จะคำนวณความคลาดเคลื่อนมาตรฐานมอนติคาร์โล (Monte Carlo standard errors) จากการสุ่มตัวอย่างที่มีสหสัมพันธ์ในตัวเองได้อย่างไร?

Key concepts

• ฟังก์ชันการแจกแจงสถานะคงที่
• สมดุลละเอียด
• อัตราการยอมรับ
• ช่วงเริ่มต้น
• สหสัมพันธ์ในตัวเองและการผสม
• การวินิจฉัยการลู่เข้า

Key theories

สมดุลละเอียดและสถานะคงที่

หากเคอร์เนลการเปลี่ยนสถานะ (transition kernel) เป็นไปตามสมดุลละเอียดเมื่อเทียบกับฟังก์ชันการแจกแจงเป้าหมาย ฟังก์ชันการแจกแจงนั้นจะเป็นสถานะคงที่ จากนั้นค่าเฉลี่ยแบบเออร์กอดิกของเชนที่ได้จะลู่เข้าสู่ค่าคาดหวังภายใต้เป้าหมาย

ขั้นตอนวิธีเมโทรโพลิส-เฮสติงส์

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

Clinical relevance

มาร์คอฟเชน มอนติคาร์โล ทำให้การอนุมานแบบเบย์เซียนเต็มรูปแบบ (fully Bayesian inference) สามารถนำไปใช้ได้จริงสำหรับแบบจำลองแบบลำดับชั้น (hierarchical) และแบบจำลองที่มีมิติสูง (high-dimensional models) และถูกนำไปประยุกต์ใช้ในสาขาพันธุศาสตร์เชิงสถิติ (statistical genetics), นิเวศวิทยา (ecology), ระบาดวิทยา (epidemiology), เศรษฐมิติ (econometrics) และวิทยาศาสตร์กายภาพ ในทุกที่ที่ต้องสำรวจฟังก์ชันการแจกแจงภายหลัง (posterior) หรือฟังก์ชันการแจกแจงโบลต์ซมันน์ (Boltzmann distributions) แต่ไม่สามารถสุ่มตัวอย่างได้โดยตรง

History

ขั้นตอนวิธีเมโทรโพลิส (Metropolis algorithm) ปรากฏขึ้นในปี 1953 ในสาขาฟิสิกส์เชิงสถิติ เฮสติงส์ (Hastings) ได้ขยายแนวคิดนี้ในปี 1970 และในช่วงต้นทศวรรษ 1990 นักสถิติได้นำมาร์คอฟเชน มอนติคาร์โล มาใช้เป็นกลไกมาตรฐานของการคำนวณแบบเบย์เซียน ซึ่งต่อมาได้มีการขยายโดยมอนติคาร์โลแบบแฮมิลตัน (Hamiltonian Monte Carlo) และตัวสุ่มแบบปรับตัว (adaptive samplers)

Debates

การประเมินการลู่เข้า

เนื่องจากการรันที่จำกัดไม่สามารถพิสูจน์ได้ว่าเชนได้ถึงฟังก์ชันการแจกแจงสถานะคงที่แล้ว ผู้ปฏิบัติงานจึงอาศัยการวินิจฉัยและเชนหลายชุด มีการถกเถียงกันอย่างต่อเนื่องว่าการวินิจฉัยใดที่น่าเชื่อถือ และช่วงเริ่มต้น (burn-in) และความยาวของการรันควรจะอนุรักษ์นิยมเพียงใด

Key figures

• Nicholas Metropolis
• W. Keith Hastings
• Christian P. Robert
• Andrew Gelman

Seminal works

• metropolis1953
• hastings1970

Frequently asked questions

เหตุใดตัวอย่างมาร์คอฟเชน มอนติคาร์โล จึงมีความสัมพันธ์กัน?

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

ช่วงเริ่มต้น (burn-in) คืออะไร?

ช่วงเริ่มต้นคือส่วนเริ่มต้นของเชนที่ถูกทิ้งไป เนื่องจากยังคงสะท้อนจุดเริ่มต้นที่กำหนดเองมากกว่าฟังก์ชันการแจกแจงเป้าหมาย การทิ้งช่วงนี้จะช่วยลดอคติจากการเริ่มต้นก่อนที่จะหาค่าเฉลี่ยของการสุ่มตัวอย่างที่เหลือ