การสุ่มตัวอย่างแบบปฏิเสธ (Rejection Sampling)

การสุ่มตัวอย่างแบบปฏิเสธ (Rejection sampling) เป็นการสุ่มตัวอย่างที่แม่นยำจากความหนาแน่นเป้าหมาย โดยเสนอตัวอย่างจากฟังก์ชันความหนาแน่นครอบ (envelope density) ที่ง่ายกว่า และยอมรับแต่ละข้อเสนอด้วยความน่าจะเป็นที่แปรผันตามอัตราส่วนของความหนาแน่นเป้าหมายต่อความหนาแน่นครอบ ส่วนที่เหลือจะถูกทิ้งไป

Definition

การสุ่มตัวอย่างแบบปฏิเสธ (Rejection sampling) เป็นเทคนิคการจำลองแบบมอนติคาร์โล (Monte Carlo technique) ที่สร้างตัวเลือกจากฟังก์ชันความหนาแน่นเสนอ (proposal density) ที่ครอบงำเป้าหมายได้ถึงค่าคงที่ จากนั้นยอมรับตัวเลือกด้วยความน่าจะเป็นที่เท่ากับอัตราส่วนความหนาแน่นเป้าหมายต่อขอบเขต ทำให้ค่าที่ยอมรับมีการกระจายตัวอย่างแม่นยำตามเป้าหมาย

Scope

หัวข้อนี้ครอบคลุมอัลกอริทึมการยอมรับ-ปฏิเสธพื้นฐานและความถูกต้องของอัลกอริทึม บทบาทของฟังก์ชันความหนาแน่นครอบและค่าคงที่ขอบเขตในการกำหนดประสิทธิภาพ เทคนิคการบีบ (squeeze technique) เพื่อหลีกเลี่ยงการประเมินความหนาแน่นที่มีค่าใช้จ่ายสูง และการสร้างแบบปรับตัว เช่น การสุ่มตัวอย่างแบบปฏิเสธแบบปรับตัว (adaptive rejection sampling) สำหรับความหนาแน่นแบบล็อกเว้า (log-concave densities) ซึ่งเชื่อมโยงกับขั้นตอนการยอมรับภายในวิธีการลูกโซ่มาร์คอฟ (Markov chain methods)

Core questions

• เหตุใดตัวเลือกที่ได้รับการยอมรับจึงมีการกระจายตัวอย่างแม่นยำตามความหนาแน่นเป้าหมาย?
• ค่าคงที่ขอบเขตควบคุมจำนวนข้อเสนอที่คาดหวังต่อการสุ่มที่ได้รับการยอมรับได้อย่างไร?
• ฟังก์ชันการบีบ (squeeze functions) ช่วยลดจำนวนการประเมินความหนาแน่นที่มีค่าใช้จ่ายสูงได้อย่างไร?
• จะสร้างและปรับปรุงฟังก์ชันความหนาแน่นครอบสำหรับความหนาแน่นแบบล็อกเว้า (log-concave densities) โดยอัตโนมัติได้อย่างไร?

Key concepts

• ฟังก์ชันความหนาแน่นครอบ (Envelope distribution)
• ค่าคงที่ขอบเขต (Bounding constant)
• ความน่าจะเป็นในการยอมรับ (Acceptance probability)
• ฟังก์ชันการบีบ (Squeeze function)
• ความเป็นล็อกเว้า (Log-concavity)

Key theories

หลักการยอมรับ-ปฏิเสธ (Acceptance-rejection principle)

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

การสุ่มตัวอย่างแบบปฏิเสธแบบปรับตัว (Adaptive rejection sampling)

สำหรับความหนาแน่นแบบล็อกเว้า (log-concave densities) ฟังก์ชันความหนาแน่นครอบแบบเอกซ์โพเนนเชียลเป็นช่วงๆ ที่สร้างจากเส้นสัมผัสและคอร์ดสามารถปรับปรุงได้ที่จุดที่ถูกปฏิเสธแต่ละจุด ซึ่งจะผลักดันอัตราการยอมรับให้เข้าใกล้หนึ่งโดยไม่จำเป็นต้องทราบค่าคงที่ทำให้เป็นมาตรฐาน (normalizing constant)

Clinical relevance

การสุ่มตัวอย่างแบบปฏิเสธสร้างตัวแปรจากความหนาแน่นที่ทราบได้ถึงค่าคงที่ ซึ่งเกิดขึ้นอย่างต่อเนื่องในการคำนวณแบบเบย์ (Bayesian computation) โดยเฉพาะอย่างยิ่งการสุ่มตัวอย่างแบบปฏิเสธแบบปรับตัว (adaptive rejection sampling) จะให้การสุ่มแบบมีเงื่อนไขเต็มรูปแบบ (full-conditional draws) ภายในตัวสุ่มกิบบ์ส (Gibbs samplers) จำนวนมาก ทำให้เป็นองค์ประกอบสำคัญของการจำลองแบบภายหลัง (posterior simulation) ที่ใช้งานได้จริง

History

วอน นอยมันน์ (Von Neumann) ได้อธิบายแนวคิดการยอมรับ-ปฏิเสธในช่วงแรกของการคำนวณแบบมอนติคาร์โล (Monte Carlo computation) ต่อมามีการขยายขอบเขตของฟังก์ชันความหนาแน่นครอบ เพิ่มขั้นตอนการบีบ (squeeze steps) เพื่อเพิ่มประสิทธิภาพ และพัฒนาแผนการปรับตัว (adaptive schemes) ที่กระชับฟังก์ชันความหนาแน่นครอบโดยอัตโนมัติสำหรับเป้าหมายแบบล็อกเว้า (log-concave targets) ที่ใช้ในการสุ่มตัวอย่างแบบเบย์ (Bayesian sampling)

Key figures

• John von Neumann
• Luc Devroye
• Walter Gilks
• Christian P. Robert

Seminal works

• devroye1986
• gilks1992

Frequently asked questions

อะไรที่ทำให้การสุ่มตัวอย่างแบบปฏิเสธมีประสิทธิภาพหรือไม่มีประสิทธิภาพ?

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

เหตุใดการสุ่มตัวอย่างแบบปฏิเสธจึงมีประโยชน์เมื่อไม่ทราบค่าคงที่ทำให้เป็นมาตรฐาน (normalizing constant)?

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