Skip to content
กลับไปยังผลการค้นหา

Markov Chain Monte Carlo (MCMC) — Metropolis-Hastings และ Gibbs Sampling

ผู้เสนอ
Metropolis et al. (1953); Gibbs sampler formalised by Geman & Geman (1984)
ปี
1953 (Metropolis-Hastings); 1984 (Gibbs)
ประเภท
Simulation-based Bayesian inference / numerical integration

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

Markov Chain Monte Carlo (MCMC) เป็นกลุ่มของอัลกอริทึมการจำลองที่สร้าง Markov chain ซึ่งการแจกแจงแบบคงที่ (stationary distribution) คือการแจกแจงภายหลัง (posterior distribution) เป้าหมาย ทำให้สามารถอนุมานแบบเบย์ (Bayesian inference) และคำนวณปริพันธ์มิติสูง (high-dimensional integral computation) ที่หากไม่เช่นนั้นแล้วจะไม่มีรูปแบบปิดเชิงวิเคราะห์ (analytically intractable) MCMC ซึ่งริเริ่มโดย Metropolis และคณะในปี 1953 และพัฒนาต่อโดย Hastings ในปี 1970 เป็นรากฐานของสถิติแบบเบย์สมัยใหม่ รูปแบบที่นิยมใช้กันมากที่สุดสองรูปแบบคือ Metropolis-Hastings ซึ่งเสนอการเคลื่อนที่จากฟังก์ชันการเสนอ (proposal distribution) ทั่วไป และ Gibbs sampling ซึ่งสุ่มเลือกพารามิเตอร์แต่ละตัวตามลำดับจากฟังก์ชันเงื่อนไขเต็ม (full conditional distribution) ของมัน

แนวคิดเบื้องหลังวิธีการ

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

ประวัติศาสตร์

อัลกอริทึม Metropolis พื้นฐานได้รับการตีพิมพ์ในปี 1953 โดย Metropolis, Rosenbluth, Rosenbluth, Teller และ Teller สำหรับการจำลองโมเลกุล Hastings (1970) ได้ขยายอัลกอริทึมให้ใช้ฟังก์ชันการเสนอแบบไม่สมมาตร ทำให้เกิดอัลกอริทึม Metropolis-Hastings Geman และ Geman (1984) ได้นำเสนอ Gibbs sampling ในบริบทของการฟื้นฟูภาพ อัลกอริทึมได้กลายเป็นเครื่องมือทางสถิติหลักในช่วงต้นทศวรรษ 1990 หลังจาก Gelfand และ Smith (1990) แสดงให้เห็นถึงความสามารถในการประยุกต์ใช้ในวงกว้างสำหรับการคำนวณแบบเบย์ และ Gelman และ Rubin (1992) ได้นำเสนอการวินิจฉัยการลู่เข้า R̂ การพัฒนา Hamiltonian Monte Carlo โดย Duane et al. (1987) และรูปแบบอัตโนมัติ NUTS โดย Hoffman และ Gelman (2014) ได้ขยาย MCMC ไปสู่ปัญหาที่มีมิติสูง Bayesian Data Analysis ของ Gelman et al. (2013) และ Handbook of Markov Chain Monte Carlo ของ Brooks et al. (2011) เป็นแหล่งอ้างอิงที่ครอบคลุมมาตรฐาน

ควรใช้เมื่อใด

MCMC เป็นเครื่องมือที่เหมาะสมเมื่อมีการกำหนดแบบจำลองแบบเบย์และไม่สามารถคำนวณการแจกแจงภายหลังเชิงวิเคราะห์ได้ ซึ่งเป็นกรณีทั่วไปสำหรับแบบจำลองที่มีพารามิเตอร์มากกว่าสองสามตัวหรือมี prior ที่ไม่เป็น conjugate (non-conjugate priors) นอกจากนี้ยังเป็นแนวทางมาตรฐานสำหรับแบบจำลองตัวแปรแฝง (latent-variable models) แบบจำลองลำดับชั้น (hierarchical models) และสถานการณ์ใดๆ ที่ต้องมีการแพร่กระจายความไม่แน่นอนอย่างเต็มที่ผ่านกระบวนการที่ซับซ้อน ไม่จำเป็นต้องมีข้อสมมติฐานเกี่ยวกับการแจกแจงของข้อมูลนอกเหนือจากการระบุฟังก์ชันความควรจะเป็น ข้อกำหนดที่สำคัญในทางปฏิบัติคือจำนวนการวนซ้ำที่เพียงพอเพื่อให้ห่วงโซ่ลู่เข้า: ตัวอย่างหลังช่วง burn-in น้อยกว่าประมาณ 1,000 ตัวอย่างมักจะไม่ให้การอธิบายการแจกแจงภายหลังที่น่าเชื่อถือ และในกรณีที่มีมิติสูง จำเป็นต้องมีจำนวนมากกว่านั้นมาก เมื่อปริภูมิพารามิเตอร์มีมิติสูงมาก Hamiltonian Monte Carlo (HMC) หรือ No-U-Turn Sampler (NUTS) — ส่วนขยายอัตโนมัติของแนวคิด MCMC — มีประสิทธิภาพมากกว่า Metropolis-Hastings พื้นฐานอย่างมาก

ข้อจำกัดและข้อควรพิจารณา

  • การลู่เข้าไม่ได้รับประกันในเวลาจำกัด ห่วงโซ่ที่ดูเหมือนจะลู่เข้าแล้วอาจยังคงติดอยู่ในบริเวณเฉพาะของการแจกแจงภายหลัง
  • ความสัมพันธ์ในตัวเองระหว่างตัวอย่างที่ต่อเนื่องกันหมายความว่าขนาดตัวอย่างที่มีประสิทธิผลมีค่าน้อยกว่าจำนวนการวนซ้ำดิบ ทำให้ต้องการการทำงานที่นานกว่าที่ตัวอย่างอิสระที่เทียบเท่ากันจะต้องการ
  • ในปริภูมิพารามิเตอร์มิติสูง random-walk Metropolis-Hastings จะผสมผสานได้ไม่ดี จำเป็นต้องใช้ Hamiltonian Monte Carlo หรือ NUTS เพื่อการสำรวจที่มีประสิทธิภาพ
  • การระบุแบบจำลองกำหนดให้นักวิเคราะห์ต้องเลือก prior อย่างรอบคอบ และ prior ที่เลือกไม่ดีหรือฟังก์ชันความควรจะเป็นที่ระบุผิดพลาดอาจทำให้การแจกแจงภายหลังมีอคติในลักษณะที่ตรวจจับได้ยาก

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

จุดแข็ง

  • ช่วยให้สามารถอนุมานแบบเบย์ที่แม่นยำ (ในทาง asymptotic) สำหรับแบบจำลองที่การแจกแจงภายหลังไม่มีรูปแบบปิด ครอบคลุมแบบจำลองลำดับชั้น ปัญหาข้อมูลสูญหาย และฟังก์ชันความควรจะเป็นที่ซับซ้อน
  • สร้างตัวอย่างการแจกแจงภายหลังร่วมที่สมบูรณ์ ดังนั้นปริมาณใดๆ การทำนาย หรือการตัดสินใจที่ได้มา สามารถคำนวณได้โดยมีการแพร่กระจายความไม่แน่นอนอย่างเหมาะสม
  • ใช้ได้กับผลลัพธ์แบบต่อเนื่อง แบบทวิภาค และแบบนับ และไม่มีข้อสมมติฐานเกี่ยวกับการแจกแจงของข้อมูลนอกเหนือจากฟังก์ชันความควรจะเป็นที่กำหนดโดยผู้ออกแบบ
  • การดำเนินการหลายห่วงโซ่แบบขนานทำให้การตรวจสอบการลู่เข้าเป็นระบบผ่านการวินิจฉัย Gelman-Rubin R̂

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

  • การปรับแบบจำลองลำดับชั้นแบบเบย์ในจิตวิทยา การศึกษา และการแพทย์ ที่ข้อมูลมีการจัดกลุ่มและต้องการการรวมบางส่วน (partial pooling)
  • การประมาณค่าพารามิเตอร์ของแบบจำลองส่วนประกอบทางระบาดวิทยา (SIR, SEIR) จากจำนวนผู้ป่วยที่สังเกตได้ รวมถึงการวัดปริมาณความไม่แน่นอน
  • การสร้างแบบจำลองสมการโครงสร้างแบบเบย์และแบบจำลองตัวแปรแฝงในการวิจัยสังคมศาสตร์
  • การอนุมานภายหลังสำหรับแบบจำลองทฤษฎีการตอบสนองข้อสอบ (IRT) ในการวัดผลทางการศึกษา
  • การปรับเทียบแบบจำลองการจำลองที่ซับซ้อนกับข้อมูลที่สังเกตได้ เมื่อมีฟังก์ชันความควรจะเป็นแต่ไม่เป็น conjugate
  • การสร้างแบบจำลองความเสี่ยงทางการเงินและการกำหนดราคาออปชันภายใต้ความไม่แน่นอนของพารามิเตอร์แบบเบย์

วิธีการทำงาน

วิธีการทำงาน

1

นักวิเคราะห์กำหนดแบบจำลองแบบเบย์: ฟังก์ชันความควรจะเป็น (likelihood function) ที่เชื่อมโยงพารามิเตอร์กับข้อมูลที่สังเกตได้ และการแจกแจงก่อน (prior distributions) ที่เข้ารหัสความเชื่อเกี่ยวกับพารามิเตอร์แต่ละตัวก่อนที่จะเห็นข้อมูล สิ่งเหล่านี้ร่วมกันกำหนดการแจกแจงภายหลังที่ไม่ถูกทำให้เป็นมาตรฐาน (unnormalised posterior) ที่ MCMC จะสำรวจ การเลือก prior และตระกูลของฟังก์ชันความควรจะเป็นจะเป็นตัวกำหนดโครงสร้างของห่วงโซ่ และต้องมีพื้นฐานมาจากความรู้เฉพาะทาง

2

เลือกค่าเริ่มต้นสำหรับพารามิเตอร์ทั้งหมด และกำหนดจำนวนห่วงโซ่ ระยะเวลาช่วงปรับตัว (warm-up หรือ burn-in) และจำนวนการวนซ้ำทั้งหมดหลังช่วงปรับตัว การดำเนินการหลายห่วงโซ่ที่เป็นอิสระต่อกัน — โดยทั่วไปคือสี่ห่วงโซ่ — จากจุดเริ่มต้นที่แตกต่างกันเป็นแนวปฏิบัติมาตรฐาน เนื่องจากช่วยให้สามารถประเมินการลู่เข้า (convergence) ได้โดยการเปรียบเทียบห่วงโซ่ต่างๆ แทนที่จะอาศัยเส้นทางเดียว

3

ในการวนซ้ำแต่ละครั้ง อัลกอริทึมจะเสนอการเคลื่อนที่ในปริภูมิพารามิเตอร์ ภายใต้ Metropolis-Hastings ตัวเลือกจะถูกสุ่มจากฟังก์ชันการเสนอและยอมรับด้วยความน่าจะเป็นที่ขึ้นอยู่กับอัตราส่วนของความหนาแน่นภายหลัง ณ ตำแหน่งตัวเลือกและตำแหน่งปัจจุบัน เพื่อให้แน่ใจว่าการแจกแจงแบบคงที่ของห่วงโซ่คือการแจกแจงภายหลังเป้าหมาย ภายใต้ Gibbs sampling พารามิเตอร์แต่ละตัวจะถูกอัปเดตตามลำดับโดยการสุ่มโดยตรงจากฟังก์ชันเงื่อนไขเต็ม ซึ่งหลีกเลี่ยงความจำเป็นในการยอมรับอย่างชัดเจน เนื่องจากตัวอย่างที่ต่อเนื่องกันจะแบ่งปันข้อมูล ห่วงโซ่จึงแสดงความสัมพันธ์ในตัวเอง (autocorrelation) การทำให้ผอมบาง (thinning) — การเก็บเฉพาะทุกๆ การสุ่มครั้งที่ k — สามารถลดสิ่งนี้ได้โดยแลกกับการมีตัวอย่างที่เก็บไว้น้อยลง

4

หลังจากทิ้งช่วง burn-in แล้ว จะประเมินการลู่เข้า สถิติ Gelman-Rubin R̂ เปรียบเทียบความแปรปรวนภายในห่วงโซ่กับความแปรปรวนระหว่างห่วงโซ่ในหลายห่วงโซ่ ค่าที่ต่ำกว่า 1.05 บ่งชี้ว่าห่วงโซ่ได้ผสมผสานและลู่เข้าสู่การแจกแจงเดียวกัน แผนภาพเส้นทาง (trace plots) (ลำดับของค่าที่สุ่มตามจำนวนการวนซ้ำ) และขนาดตัวอย่างที่มีประสิทธิผล (effective sample size) ก็จะถูกตรวจสอบเช่นกัน หาก R̂ มีค่ามากหรือแผนภาพเส้นทางแสดงการผสมผสานที่ไม่ดี แบบจำลอง prior หรือการตั้งค่า sampler จะต้องได้รับการแก้ไขก่อนที่จะดำเนินการอนุมาน

5

ชุดของตัวอย่างหลังช่วง burn-in จะเป็นการประมาณการแจกแจงภายหลังเชิงประจักษ์ สามารถคำนวณค่าประมาณจุด (posterior mean หรือ median) ช่วงความเชื่อ (credible intervals) และการแจกแจงการทำนายภายหลัง (posterior predictive distributions) ได้โดยตรงจากตัวอย่าง เนื่องจากตัวอย่างเป็นการสุ่มจากการแจกแจงภายหลังร่วม (joint posterior) ปริมาณใดๆ ที่ได้มา — อัตราส่วน ผลต่าง ฟังก์ชันไม่เชิงเส้นของพารามิเตอร์ — สามารถประมาณได้โดยการใช้ฟังก์ชันเดียวกันกับตัวอย่างแต่ละตัวและสรุปการแจกแจงที่ได้

ข้อผิดพลาดที่พบบ่อย

  • การข้ามหรือลดระยะเวลา burn-in หมายความว่าส่วนต้นของห่วงโซ่ที่ไม่คงที่ (non-stationary) ปนเปื้อนค่าประมาณภายหลัง — ควรทิ้งช่วง warm-up ที่เพียงพอเสมอ
  • การดำเนินการเพียงห่วงโซ่เดียวทำให้ไม่สามารถตรวจจับได้ว่า sampler ลู่เข้าแล้วหรือติดอยู่ในบริเวณใดบริเวณหนึ่ง — ควรดำเนินการอย่างน้อยสี่ห่วงโซ่ที่เป็นอิสระต่อกันเสมอ
  • การปฏิบัติต่อจำนวนการวนซ้ำดิบจำนวนมากว่าเป็นหลักฐานของการลู่เข้าโดยไม่ได้คำนวณ R̂ หรือตรวจสอบแผนภาพเส้นทาง อาจให้ความมั่นใจที่ผิดพลาด — จำเป็นต้องมี R̂ < 1.05 ไม่ใช่แค่จำนวนการวนซ้ำมาก
  • การละเลยความสัมพันธ์ในตัวเองและการรายงานขนาดตัวอย่างที่มีประสิทธิผลราวกับว่าเป็นจำนวนดิบ เป็นการประเมินค่าความแม่นยำสูงเกินไป — ควรรายงานขนาดตัวอย่างที่มีประสิทธิผลควบคู่ไปกับจำนวนดิบ
  • การใช้ MCMC กับแบบจำลองที่มีจำนวนการวนซ้ำหลัง burn-in น้อยกว่าประมาณ 1,000 ครั้ง โดยทั่วไปจะไม่ให้ผลลัพธ์การแจกแจงภายหลังที่น่าเชื่อถือ — หากงบประมาณในการคำนวณมีจำกัด ควรพิจารณาใช้วิธีการแบบเบย์เชิงวิเคราะห์หรือแบบจำลอง conjugate

คำถามที่พบบ่อย

ฉันจะทราบได้อย่างไรว่าห่วงโซ่ MCMC ของฉันลู่เข้าแล้ว?

การวินิจฉัยหลักคือสถิติ Gelman-Rubin R̂ ซึ่งคำนวณโดยการดำเนินการอย่างน้อยสี่ห่วงโซ่ที่เป็นอิสระจากจุดเริ่มต้นที่แตกต่างกัน และเปรียบเทียบความแปรปรวนภายในห่วงโซ่กับความแปรปรวนระหว่างห่วงโซ่ ค่า R̂ ที่ต่ำกว่า 1.05 สำหรับพารามิเตอร์ทั้งหมดเป็นเกณฑ์มาตรฐาน แผนภาพเส้นทางควรแสดงให้เห็นว่าห่วงโซ่ต่างๆ ทับซ้อนกันและสำรวจบริเวณเดียวกัน เส้นทางที่มีรูปร่างเหมือนกรวย (funnel-shaped) หรือมีการเคลื่อนที่ (drifting) บ่งชี้ถึงการผสมผสานที่ไม่ดี ควรตรวจสอบขนาดตัวอย่างที่มีประสิทธิผลด้วย — ขนาดตัวอย่างที่มีประสิทธิผลที่เล็กมากเมื่อเทียบกับจำนวนดิบ บ่งชี้ถึงความสัมพันธ์ในตัวเองสูงและความต้องการการวนซ้ำมากขึ้น หรือ sampler ที่ดีขึ้น

อะไรคือความแตกต่างระหว่าง Metropolis-Hastings และ Gibbs sampling?

Metropolis-Hastings เสนอการเคลื่อนที่สำหรับพารามิเตอร์ทั้งหมดพร้อมกัน (หรือเป็นกลุ่ม) จากฟังก์ชันการเสนอที่ผู้ใช้กำหนด และยอมรับหรือปฏิเสธข้อเสนอด้วยความน่าจะเป็นที่รักษาการแจกแจงภายหลังเป้าหมายไว้เป็นการแจกแจงแบบคงที่ ในทางกลับกัน Gibbs sampling จะอัปเดตพารามิเตอร์แต่ละตัวทีละตัวโดยการสุ่มโดยตรงจากฟังก์ชันเงื่อนไขเต็ม — การแจกแจงของพารามิเตอร์นั้นเมื่อกำหนดพารามิเตอร์อื่นๆ และข้อมูลทั้งหมดแล้ว Gibbs sampling ต้องการให้ฟังก์ชันเงื่อนไขเต็มเหล่านี้มีอยู่ในรูปแบบปิด ซึ่งเป็นกรณีสำหรับแบบจำลอง conjugate จำนวนมาก เมื่อมีอยู่ Gibbs จะมีประสิทธิภาพสูงเนื่องจากทุกข้อเสนอจะได้รับการยอมรับ Metropolis-Hastings สามารถประยุกต์ใช้ได้กว้างขวางกว่า แต่ต้องการการปรับฟังก์ชันการเสนอเพื่อให้ได้อัตราการยอมรับที่ยอมรับได้

เมื่อใดที่ฉันควรใช้ Hamiltonian Monte Carlo แทน Metropolis-Hastings?

Hamiltonian Monte Carlo (HMC) และรูปแบบอัตโนมัติ NUTS ใช้ข้อมูลความชัน (gradient information) จาก log-posterior เพื่อเสนอการเคลื่อนที่ขนาดใหญ่และมีข้อมูล ซึ่งได้รับการยอมรับด้วยความน่าจะเป็นสูง ทำให้มีประสิทธิภาพมากกว่า random-walk Metropolis-Hastings อย่างมากในปริภูมิพารามิเตอร์มิติสูง ซึ่งการเสนอแบบสุ่มเกือบทั้งหมดจะถูกปฏิเสธ ตามกฎทั่วไป หากแบบจำลองของคุณมีพารามิเตอร์มากกว่าประมาณสิบตัว หรือหากห่วงโซ่ Metropolis-Hastings แสดงการผสมผสานที่ไม่ดีและมีขนาดตัวอย่างที่มีประสิทธิผลต่ำมาก การเปลี่ยนไปใช้ HMC หรือ NUTS จะเป็นที่แนะนำ

ฉันต้องการการวนซ้ำกี่ครั้ง?

ไม่มีคำตอบที่เป็นสากล แต่จุดเริ่มต้นทั่วไปคือ 1,000 ครั้งสำหรับการปรับตัว (burn-in) บวก 2,000 ครั้งสำหรับการสุ่มตัวอย่างต่อห่วงโซ่ ในสี่ห่วงโซ่ ทำให้ได้ 8,000 ตัวอย่างหลัง burn-in ความเพียงพอของจำนวนนี้ขึ้นอยู่กับความสัมพันธ์ในตัวเองของห่วงโซ่และความซับซ้อนของการแจกแจงภายหลัง ห่วงโซ่จะเพียงพอเมื่อ R̂ < 1.05 สำหรับพารามิเตอร์ทั้งหมด และขนาดตัวอย่างที่มีประสิทธิผลมีมากพอที่จะอธิบายลักษณะของการแจกแจงภายหลังที่น่าสนใจ — โดยทั่วไปคืออย่างน้อยสองสามร้อยตัวอย่างที่มีประสิทธิผลสำหรับค่าเฉลี่ย และสองสามพันสำหรับควอนไทล์หาง

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Gelman, A., Carlin, J.B., Stern, H.S., Dunson, D.B., Vehtari, A. & Rubin, D.B. (2013). Bayesian Data Analysis (3rd ed.). Chapman & Hall/CRC.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Brooks, S., Gelman, A., Jones, G.L. & Meng, X.-L. (Eds.) (2011). Handbook of Markov Chain Monte Carlo. Chapman & Hall/CRC.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว