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

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมการออกแบบเคอร์เนลการเปลี่ยนสถานะ (transition kernels) ที่มีการแจกแจงสถานะคงที่ที่กำหนดไว้, อัลกอริทึม Metropolis-Hastings และกฎการยอมรับ, ตัวสุ่ม Gibbs (Gibbs sampler) สำหรับการปรับปรุงแบบมีเงื่อนไข, การวินิจฉัยการลู่เข้า (convergence diagnostics) และช่วง burn-in, ผลกระทบของสหสัมพันธ์ในตัวเอง (autocorrelation) ต่อความแปรปรวนของตัวประมาณค่า, และความเชื่อมโยงระหว่างเวลาการผสม (mixing times) กับต้นทุนการคำนวณของการสุ่มตัวอย่าง

Core questions

• มาร์คอฟเชนถูกสร้างขึ้นมาอย่างไรเพื่อให้มีการแจกแจงสถานะคงที่ที่ต้องการ?
• เหตุใดกฎการยอมรับของ Metropolis-Hastings จึงสร้างกฎสถานะคงที่ที่ถูกต้อง?
• ตัวสุ่ม Gibbs ใช้ประโยชน์จากการแจกแจงแบบมีเงื่อนไขอย่างไร?
• เชนต้องรันนานแค่ไหนก่อนที่ตัวอย่างจะใช้งานได้ และประเมินสิ่งนี้อย่างไร?

Key theories

การสร้าง Metropolis-Hastings

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

ค่าเฉลี่ยแบบเออร์กอดิกและการประมาณค่าแบบมอนติคาร์โล

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

Clinical relevance

มาร์คอฟเชน มอนติคาร์โล เป็นเครื่องมือสำคัญในสถิติแบบเบย์สมัยใหม่, ฟิสิกส์เชิงสถิติ, และการเรียนรู้ของเครื่องจักร (machine learning) ซึ่งช่วยให้สามารถอนุมานค่าจากการแจกแจงภายหลัง (posterior distributions) ที่มีมิติสูง, ฟังก์ชันพาร์ทิชัน (partition functions), และภูมิทัศน์พลังงาน (energy landscapes) ที่ไม่สามารถหาปริพันธ์เชิงวิเคราะห์ได้ ความน่าเชื่อถือของมันขึ้นอยู่กับความเร็วในการผสมของเชนพื้นฐาน

History

เชนการยอมรับ-ปฏิเสธ (acceptance-rejection chain) มีต้นกำเนิดจากอัลกอริทึม Metropolis ในปี 1953 สำหรับฟิสิกส์เชิงสถิติ ได้รับการขยายโดย Hastings ในปี 1970 และถูกนำมาใช้ใหม่สำหรับสถิติผ่านตัวสุ่ม Gibbs ของ Geman และ Geman ในปี 1984 และการประยุกต์ใช้แบบเบย์ที่มีอิทธิพลของ Gelfand และ Smith ประมาณปี 1990 ซึ่งได้จุดประกายการปฏิวัติการคำนวณแบบเบย์

Key figures

• Nicholas Metropolis
• W. Keith Hastings
• Stuart Geman
• Donald Geman

Seminal works

• robertCasella2004
• hastings1970

Frequently asked questions

เหตุใดจึงใช้มาร์คอฟเชนในการสุ่มตัวอย่าง?

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

Burn-in คืออะไร?

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