ในการวิเคราะห์เชิงตัวเลขและสถิติเชิงคำนวณ การสุ่มตัวอย่างแบบปฏิเสธ ( rejection sampling)เป็นเทคนิคพื้นฐานที่ใช้ในการสร้างข้อมูลสังเกตการณ์จาก1 การแจกแจงโดยทั่วไปเรียกว่าวิธีการยอมรับ-ปฏิเสธหรือ "อัลกอริทึมยอมรับ-ปฏิเสธ" และเป็นวิธีการจำลองแบบแม่นยำชนิดหนึ่ง วิธีนี้ใช้ได้กับการแจกแจงใดๆ ที่มีฟังก์ชันความหนาแน่น ${\displaystyle \mathbb {R} ^{m}}$

การสุ่มตัวอย่างแบบปฏิเสธนั้นอิงตามการสังเกตว่าในการสุ่มตัวอย่างตัวแปรสุ่มในมิติเดียว เราสามารถทำการสุ่มตัวอย่างแบบสุ่มอย่างสม่ำเสมอจากกราฟคาร์ทีเซียนสองมิติ และเก็บตัวอย่างไว้ในบริเวณใต้กราฟของฟังก์ชันความหนาแน่น^{[ 1 ] [ 2 ] [ 3 ]}โปรดทราบว่าคุณสมบัตินี้สามารถขยายไปยังฟังก์ชัน N มิติได้

อัลกอริทึมซึ่งใช้โดยJohn von Neumann ^{[ 4 ]}และย้อนกลับไปถึงBuffonและเข็มของเขาจะสุ่มตัวอย่างจากฟังก์ชันความหนาแน่นความน่าจะเป็น (เป้าหมาย) ซึ่งเป็นสัดส่วนกับโดยใช้การสุ่มจากความหนาแน่นความน่าจะเป็น (ข้อเสนอ) ที่เรียบง่ายกว่าดังต่อไปนี้: ${\displaystyle f(x)}$${\displaystyle f_{\varpropto }(x)}$${\displaystyle g(x)}$

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

ป้อนข้อมูล

ความหนาแน่นเป้าหมายความหนาแน่นข้อเสนอ ค่าคงที่โดยที่สำหรับทุกๆ${\displaystyle f(x)={\frac {f_{\varpropto }(x)}{\int f_{\varpropto }(y)dy}}}$${\displaystyle g(x)}$${\displaystyle M}$${\displaystyle f_{\varpropto }(x)\leq Mg(x)}$${\displaystyle x}$

อัลกอริทึม

1. ตัวอย่าง${\displaystyle X\sim g(x)}$
2. ตัวอย่างโดยไม่ขึ้นอยู่กับ${\displaystyle U\sim \mathrm {Unif} (0,1)}$${\displaystyle X}$
3. คำนวณอัตราส่วนความน่าจะเป็น${\displaystyle W={\dfrac {f_{\varpropto }(X)}{g(X)}}}$
4. ถ้าเป็นจริง ให้ปฏิเสธและทำซ้ำตั้งแต่ขั้นตอนที่ 1 มิฉะนั้น ให้ยอมรับและแสดงผล${\displaystyle W<M\times U}$${\displaystyle X}$${\displaystyle X}$

เอาต์พุต

ตัวอย่างที่ดึงมาจาก...${\displaystyle X}$${\displaystyle f}$

อัลกอริทึมจะนำค่าเฉลี่ยของจำนวนการปฏิเสธมาใช้เพื่อสร้างตัวอย่าง ${\displaystyle {\frac {M}{\int f_{\varpropto }(y)dy}}}$

เพื่อให้เห็นภาพแรงจูงใจเบื้องหลังการสุ่มตัวอย่างแบบปฏิเสธ ลองนึกภาพการวาดกราฟฟังก์ชันความหนาแน่นความน่าจะเป็น (PDF) ของตัวแปรสุ่มลงบนกระดานสี่เหลี่ยมขนาดใหญ่ แล้วปาลูกดอกใส่ลงไป สมมติว่าลูกดอกกระจายตัวอย่างสม่ำเสมอทั่วกระดาน จากนั้นเอาลูกดอกทั้งหมดที่อยู่นอกพื้นที่ใต้เส้นโค้งออกไป ลูกดอกที่เหลือจะกระจายตัวอย่างสม่ำเสมอภายในพื้นที่ใต้เส้นโค้ง และตำแหน่ง x ของลูกดอกเหล่านี้จะกระจายตัวตามความหนาแน่นของตัวแปรสุ่ม เนื่องจากบริเวณที่เส้นโค้งสูงที่สุดจะมีพื้นที่ให้ลูกดอกตกลงมามากที่สุด ดังนั้นความหนาแน่นของความน่าจะเป็นจึงมากที่สุด ${\displaystyle x}$

ภาพที่อธิบายไปข้างต้นเทียบเท่ากับรูปแบบเฉพาะของการสุ่มตัวอย่างแบบปฏิเสธ โดยที่ "การกระจายของข้อเสนอ" เป็นแบบสม่ำเสมอ ดังนั้นกราฟจึงเป็นรูปสี่เหลี่ยมผืนผ้า รูปแบบทั่วไปของการสุ่มตัวอย่างแบบปฏิเสธนั้นสมมติว่ากระดานไม่จำเป็นต้องเป็นรูปสี่เหลี่ยมผืนผ้า แต่มีรูปร่างตามความหนาแน่นของการกระจายของข้อเสนอ (ไม่จำเป็นต้องปรับให้เป็นมาตรฐาน) ที่เรารู้วิธีการสุ่มตัวอย่าง (ตัวอย่างเช่น การใช้การสุ่มตัวอย่างแบบผกผัน ) รูปร่างของมันต้องมีความสูงอย่างน้อยเท่ากับการกระจายที่เราต้องการสุ่มตัวอย่างในทุกจุด เพื่อให้กระดานครอบคลุมการกระจายอย่างสมบูรณ์ มิฉะนั้นจะมีส่วนโค้งที่เราต้องการสุ่มตัวอย่างซึ่งไม่สามารถเข้าถึงได้ ${\displaystyle 1}$

การสุ่มตัวอย่างแบบปฏิเสธทำงานดังนี้:

1. เลือกจุดบนแกน y จากการกระจายตัวที่เสนอ${\displaystyle x}$
2. ลากเส้นแนวตั้งที่ตำแหน่งนี้ ไปจนถึงค่า y ของฟังก์ชันความหนาแน่นความน่าจะเป็นของการแจกแจงแบบเสนอแนะ${\displaystyle x}$
3. สุ่มตัวอย่างอย่างสม่ำเสมอตามแนวเส้นนี้ หากค่าที่สุ่มได้มากกว่าค่าของการแจกแจงที่ต้องการ ณ เส้นแนวตั้งนี้ ให้ปฏิเสธค่าดังกล่าวและกลับไปที่ขั้นตอนที่ 1 มิฉะนั้นค่าดังกล่าวจะเป็นตัวอย่างจากการแจกแจงที่ต้องการ${\displaystyle x}$${\displaystyle x}$

อัลกอริทึมนี้สามารถใช้สุ่มตัวอย่างจากพื้นที่ใต้เส้นโค้งใดๆ ก็ได้ โดยไม่คำนึงว่าฟังก์ชันนั้นจะมีค่าอินทิเกรตเท่ากับ 1 หรือไม่ ที่จริงแล้ว การปรับขนาดฟังก์ชันด้วยค่าคงที่ไม่มีผลต่อตำแหน่ง ที่สุ่มได้ ดังนั้น อัลกอริทึมนี้จึงสามารถใช้สุ่มตัวอย่างจาก1การแจกแจงที่มีค่าคงที่การทำให้เป็นมาตรฐานไม่เป็นที่รู้จัก ซึ่งเป็นเรื่องปกติในสถิติเชิงคำนวณ ${\displaystyle x}$

ในการวิเคราะห์ต่อไปนี้ เพื่อความง่าย เราจะสมมติว่า . วิธีการสุ่มตัวอย่างแบบปฏิเสธ (Rejection Sampling Method) สร้างค่าตัวอย่างจากฟังก์ชัน ความหนาแน่นความน่าจะเป็นเป้าหมายโดยใช้ฟังก์ชันความหนาแน่นความน่าจะเป็น. แนวคิดคือ เราสามารถสร้างค่าตัวอย่างจาก ได้โดยการสุ่มตัวอย่างจากและยอมรับตัวอย่างจากด้วยความน่าจะ เป็น ทำซ้ำการสุ่มจากจนกว่าจะยอมรับค่าใดค่าหนึ่ง โดยที่ เป็นค่าคงที่ที่มีขอบเขตจำกัดของอัตราส่วนความน่าจะเป็นซึ่งสอดคล้องกับ บนช่วงของ; กล่าวอีกนัยหนึ่งต้องสอดคล้องกับ สำหรับทุกค่าของโปรดทราบว่าสิ่งนี้ต้องการให้ช่วงของต้องรวมถึงช่วงของ—กล่าวอีกนัยหนึ่งคือเมื่อใดก็ตามที่ ${\displaystyle f\equiv f_{\varpropto }}$${\displaystyle f(x)}$${\displaystyle g(x)}$${\displaystyle f}$${\displaystyle g}$${\displaystyle f}$${\displaystyle f(x)/(Mg(x))}$${\displaystyle g}$${\displaystyle M}$${\displaystyle f(x)/g(x)}$${\displaystyle M<\infty }$${\displaystyle f}$${\displaystyle M}$${\displaystyle f(x)\leq Mg(x)}$${\displaystyle x}$${\displaystyle g}$${\displaystyle f}$${\displaystyle g(x)>0}$${\displaystyle f(x)>0}$

การตรวจสอบความถูกต้องของวิธีนี้คือหลักการซองจดหมาย: เมื่อจำลองคู่จะได้การจำลองแบบสม่ำเสมอทั่วซับกราฟของการยอมรับเฉพาะคู่ ที่ทำให้จะได้คู่ที่กระจายอย่างสม่ำเสมอทั่วซับกราฟของและด้วยเหตุนี้ จึงเป็นการจำลองจาก${\textstyle (x,v=u\cdot Mg(x))}$${\textstyle Mg(x)}$${\textstyle u<f(x)/(Mg(x))}$${\displaystyle (x,v)}$${\displaystyle f(x)}$${\displaystyle f(x).}$

นี่หมายความว่า เมื่อมีการทำซ้ำมากพอ อัลกอริทึมจะสร้างตัวอย่างจาก1การแจกแจงที่ต้องการมีส่วนขยายหลายอย่างของอัลกอริทึมนี้ เช่นอัลกอริทึมเมโทรโพลิส ${\displaystyle f(x)}$

วิธีการนี้เกี่ยวข้องกับเทคนิค Monte Carloโดยทั่วไปรวมถึง อัลกอริธึม Markov chain Monte Carloที่ใช้การแจกแจงตัวแทนเพื่อจำลองจากการแจกแจงเป้าหมายและเป็นพื้นฐานสำหรับอัลกอริธึมต่างๆ เช่น อัลกอริธึ ม Metropolis${\displaystyle f(x)}$

ความน่าจะเป็นในการยอมรับโดยไม่มีเงื่อนไข คือ สัดส่วนของตัวอย่างที่เสนอซึ่งได้รับการยอมรับ โดยที่และค่าของแต่ละครั้งจะถูกสร้างขึ้นภายใต้ฟังก์ชันความหนาแน่นของการกระจายการเสนอ $${\displaystyle {\begin{aligned}\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)&=\operatorname {E} \mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}\\[6pt]&=\operatorname {E} \left[\operatorname {E} [\mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}|Y]\right]&{\text{(by tower property)}}\\[6pt]&=\operatorname {E} \left[\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}{\biggr |}Y\right)\right]\\[6pt]&=\operatorname {E} \left[{\frac {f(Y)}{Mg(Y)}}\right]&({\text{because }}\Pr(U\leq u)=u,{\text{when }}U{\text{ is uniform on }}(0,1))\\[6pt]&=\int \limits _{y:g(y)>0}{\frac {f(y)}{Mg(y)}}g(y)\,dy\\[6pt]&={\frac {1}{M}}\int \limits _{y:g(y)>0}f(y)\,dy\\[6pt]&={\frac {1}{M}}&({\text{since support of }}Y{\text{ includes support of }}X)\end{aligned}}}$$${\displaystyle U\sim \mathrm {Unif} (0,1)}$${\displaystyle Y}$${\displaystyle g(\cdot )}$

จำนวนตัวอย่างที่จำเป็นเพื่อให้ได้ค่าที่ยอมรับได้จึงเป็นไปตามการแจกแจงแบบเรขาคณิตด้วยความน่าจะเป็นซึ่งมีค่าเฉลี่ยโดยทั่วไปแล้วคือจำนวนรอบการทำซ้ำที่คาดหวัง ซึ่งเป็นตัววัดความซับซ้อนในการคำนวณของอัลกอริทึม ${\displaystyle g}$${\displaystyle 1/M}$${\displaystyle M}$${\displaystyle M}$

เขียนสมการข้างต้นใหม่ สังเกตว่าเนื่องจากสูตรข้างต้น โดยที่เป็นความน่าจะเป็นซึ่งสามารถมีค่าได้เฉพาะในช่วงเท่านั้นเมื่อเลือกค่า เข้าใกล้ 1 มากขึ้น ความน่าจะเป็นในการยอมรับโดยไม่มีเงื่อนไขจะสูงขึ้นเมื่ออัตราส่วนนั้นเปลี่ยนแปลงน้อยลง เนื่องจากเป็นขอบเขตบนสำหรับอัตราส่วนความน่าจะเป็นในทางปฏิบัติ ค่า ที่เข้าใกล้ 1 มากขึ้นเป็นที่ต้องการมากกว่า เนื่องจากหมายถึงจำนวนตัวอย่างที่ถูกปฏิเสธโดยเฉลี่ยน้อยลง และด้วยเหตุนี้จึงมีจำนวนการวนซ้ำของอัลกอริทึมน้อยลง ในแง่นี้ จึงควรให้ มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ (ในขณะที่ยังคงเป็นไปตามซึ่งบ่งชี้ว่าโดยทั่วไปควรมีลักษณะคล้าย กับ ในบางวิธี อย่างไรก็ตาม โปรดทราบว่าไม่สามารถเท่ากับ 1 ได้: เช่นนั้นจะหมายความว่า นั่นคือ การแจกแจงเป้าหมายและการแจกแจงข้อเสนอเป็นการแจกแจงเดียวกัน $${\displaystyle M={\frac {1}{\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}}}$$${\textstyle 1\leq M<\infty }$${\textstyle \mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}$${\displaystyle [0,1]}$${\displaystyle M}$${\displaystyle M}$${\textstyle f(x)/g(x)}$${\displaystyle M}$${\displaystyle M}$${\displaystyle f(x)\leq Mg(x)}$${\displaystyle g(x)}$${\displaystyle f(x)}$${\displaystyle M}$${\displaystyle f(x)=g(x)}$

การสุ่มตัวอย่างแบบปฏิเสธ (Rejection sampling) มักใช้ในกรณีที่รูปแบบของข้อมูลทำให้การสุ่มตัวอย่างทำได้ยาก การดำเนินการอัลกอริทึมแบบปฏิเสธเพียงครั้งเดียวจำเป็นต้องสุ่มตัวอย่างจากชุดข้อมูลที่กำหนดไว้ล่วงหน้า (proposal distribution) ดึงข้อมูลจากชุดข้อมูลแบบเอกรูป (uniform distribution) และประเมิน ค่าของ นิพจน์ ดังนั้น การสุ่มตัวอย่างแบบปฏิเสธจึงมีประสิทธิภาพมากกว่าวิธีการอื่น ๆ เมื่อใดก็ตามที่ต้นทุนของการดำเนินการเหล่านี้ (ซึ่งเป็นต้นทุนที่คาดหวังของการได้ตัวอย่างด้วยการสุ่มตัวอย่างแบบปฏิเสธ) ต่ำกว่าต้นทุนของการได้ตัวอย่างโดยใช้วิธีการอื่น ${\displaystyle f(x)}$${\displaystyle f(x)/(Mg(x))}$${\displaystyle M}$

การสุ่มตัวอย่างแบบปฏิเสธ (Rejection sampling) อาจมีประสิทธิภาพมากกว่าวิธีการแบบพื้นฐานในบางสถานการณ์ ตัวอย่างเช่น เมื่อพิจารณาปัญหาการสุ่มตัวอย่างแบบมีเงื่อนไขโดยกำหนดให้เซตเช่นบางครั้งสามารถจำลองได้ง่ายๆ โดยใช้วิธีการแบบพื้นฐาน (เช่น โดยการสุ่มตัวอย่างแบบแปลงผกผัน ): ${\textstyle X\sim F(\cdot )}$${\displaystyle X}$${\displaystyle A}$${\textstyle X|X\in A}$${\textstyle X}$

• สุ่มตัวอย่างอย่างอิสระ และเลือกเฉพาะตัวอย่างที่ตรงตามเงื่อนไข${\textstyle X\sim F(\cdot )}$${\displaystyle \{n\geq 1:X_{n}\in A\}}$
• ผลลัพธ์: (ดูเพิ่มเติมที่การตัดทอน (สถิติ) )${\displaystyle \{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}}$

ปัญหาคือ การสุ่มตัวอย่างแบบนี้อาจทำได้ยากและไม่มีประสิทธิภาพ หากจำนวนรอบการทำซ้ำที่คาดหวังจะเป็นซึ่งอาจใกล้เคียงกับอนันต์ ยิ่งไปกว่านั้น แม้ว่าคุณจะใช้วิธีการสุ่มตัวอย่างแบบปฏิเสธ (Rejection sampling) ก็ยังยากที่จะปรับขอบเขตของอัตราส่วนความน่าจะเป็นให้เหมาะสมที่สุด บ่อยครั้งที่มีขนาดใหญ่และอัตราการปฏิเสธสูง อัลกอริทึมจึงอาจไม่มีประสิทธิภาพมากนัก ตระกูลเลขชี้กำลังธรรมชาติ (Natural Exponential Family ) (ถ้ามีอยู่จริง) หรือที่รู้จักกันในชื่อการเอียงเลขชี้กำลัง (exponential tilting) เป็นกลุ่มของการแจกแจงแบบเสนอแนะ (proposal distributions) ที่สามารถลดความซับซ้อนในการคำนวณ ค่าของและเพิ่มความเร็วในการคำนวณ (ดูตัวอย่าง: การทำงานกับตระกูลเลขชี้กำลังธรรมชาติ) ${\textstyle \mathbb {P} (X\in A)\approx 0}$${\displaystyle {\frac {1}{\mathbb {P} (X\in A)}}}$${\displaystyle M}$${\displaystyle M}$${\displaystyle M}$

กำหนดให้ตัวแปรสุ่มคือการแจกแจงเป้าหมาย สมมติเพื่อความง่ายว่าฟังก์ชันความหนาแน่นสามารถเขียนได้อย่างชัดเจนเป็นเลือกข้อเสนอเป็น ${\displaystyle X\sim F(\cdot )}$${\displaystyle F(x)=\mathbb {P} (X\leq x)}$${\displaystyle f(x)}$

$${\displaystyle {\begin{aligned}F_{\theta }(x)&=\mathbb {E} \left[\exp(\theta X-\psi (\theta ))\mathbb {I} (X\leq x)\right]\\&=\int _{-\infty }^{x}e^{\theta y-\psi (\theta )}f(y)dy\\g_{\theta }(x)&=F'_{\theta }(x)=e^{\theta x-\psi (\theta )}f(x)\end{aligned}}}$$

โดยที่และ. เห็นได้ชัดว่ามาจากตระกูลเลขชี้กำลังธรรมชาติยิ่งไปกว่านั้น อัตราส่วนความน่าจะเป็นคือ ${\displaystyle \psi (\theta )=\log \left(\mathbb {E} \exp(\theta X)\right)}$${\displaystyle \Theta =\{\theta :\psi (\theta )<\infty \}}$${\displaystyle \{F_{\theta }(\cdot )\}_{\theta \in \Theta }}$

$${\displaystyle Z(x)={\frac {f(x)}{g_{\theta }(x)}}={\frac {f(x)}{e^{\theta x-\psi (\theta )}f(x)}}=e^{-\theta x+\psi (\theta )}}$$

โปรดทราบว่านั่นหมายความว่ามันเป็นฟังก์ชันสร้างค่าสะสม (cumulant-generation function ) จริงๆ นั่นคือ ${\displaystyle \psi (\theta )<\infty }$

${\displaystyle \psi (\theta )=\log \mathbb {E} {\exp(tX)}|_{t=\theta }=\log M_{X}(t)|_{t=\theta }}$.

การหาฟังก์ชันสร้างค่าสะสมของข้อเสนอและค่าสะสมของข้อเสนอนั้นทำได้ง่าย

${\displaystyle {\begin{aligned}\psi _{\theta }(\eta )&=\log \left(\mathbb {E} _{\theta }\exp(\eta X)\right)=\psi (\theta +\eta )-\psi (\theta )<\infty \\\mathbb {E} _{\theta }(X)&=\left.{\frac {\partial \psi _{\theta }(\eta )}{\partial \eta }}\right|_{\eta =0}\\\mathrm {Var} _{\theta }(X)&=\left.{\frac {\partial ^{2}\psi _{\theta }(\eta )}{\partial ^{2}\eta }}\right|_{\eta =0}\end{aligned}}}$

ยกตัวอย่างง่ายๆ สมมติว่าภายใต้, , โดยที่เป้าหมายคือการสุ่มตัวอย่าง โดย ที่การวิเคราะห์เป็นดังนี้: ${\displaystyle F(\cdot )}$${\displaystyle X\sim \mathrm {N} (\mu ,\sigma ^{2})}$${\textstyle \psi (\theta )=\mu \theta +{\frac {\sigma ^{2}\theta ^{2}}{2}}}$${\displaystyle X|X\in \left[b,\infty \right]}$${\displaystyle b>\mu }$

• เลือกรูปแบบการแจกแจงข้อเสนอโดยใช้ฟังก์ชันสร้างค่าคุมูลันต์เป็น${\displaystyle F_{\theta }(\cdot )}$

${\textstyle \psi _{\theta }(\eta )=\psi (\theta +\eta )-\psi (\theta )=(\mu +\theta \sigma ^{2})\eta +{\frac {\sigma ^{2}\eta ^{2}}{2}}}$,

ซึ่งหมายความว่าเป็นการแจกแจงแบบ ปกติ${\displaystyle \mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})}$

• ตัดสินใจเลือกวิธีการกระจายข้อเสนอที่เหมาะสมในการตั้งค่านี้ วิธีการเลือกที่เข้าใจง่ายคือการตั้งค่า${\displaystyle \theta ^{*}}$${\displaystyle \theta ^{*}}$

${\displaystyle \mathbb {E} _{\theta }(X)=\mu +\theta \sigma ^{2}=b}$,

นั่นคือการกระจายข้อเสนอจึงเป็นดังนี้${\displaystyle \theta ^{*}={\frac {b-\mu }{\sigma ^{2}}}.}$${\displaystyle g_{\theta ^{*}}(x)=\mathrm {N} (b,\sigma ^{2})}$

• ระบุเป้าหมาย ข้อเสนอ และอัตราส่วนความน่าจะเป็นอย่างชัดเจน

$${\displaystyle {\begin{aligned}f_{X|X\geq b}(x)&={\frac {f(x)\mathbb {I} (x\geq b)}{\mathbb {P} (X\geq b)}}\\g_{\theta ^{*}}(x)&=f(x)\exp(\theta ^{*}x-\psi (\theta ^{*}))\\Z(x)&={\frac {f_{X|X\geq b}(x)}{g_{\theta ^{*}}(x)}}={\frac {\exp(-\theta ^{*}x+\psi (\theta ^{*}))\mathbb {I} (x\geq b)}{\mathbb {P} (X\geq b)}}\end{aligned}}}$$

• หาขอบเขตของอัตราส่วนความน่าจะเป็นซึ่งเป็นฟังก์ชันลดลงสำหรับดังนั้น${\displaystyle M}$${\displaystyle Z(x)}$${\displaystyle x\in [b,\infty ]}$

$${\displaystyle M=Z(b)={\frac {\exp(-\theta ^{*}b+\psi (\theta ^{*}))}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} \left(\mathrm {N} (0,1)\geq {\frac {b-\mu }{\sigma }}\right)}}}$$

• เกณฑ์การสุ่มตัวอย่างแบบปฏิเสธ: สำหรับถ้า${\displaystyle U\sim \mathrm {Unif} (0,1)}$

$${\displaystyle U\leq {\frac {Z(x)}{M}}=e^{-\theta ^{*}(x-b)}\mathbb {I} (x\geq b)}$$

หากค่าที่ได้ตรงกับเงื่อนไข ให้ยอมรับค่าดังกล่าวหากไม่ตรงกับเงื่อนไข ให้สุ่มตัวอย่างค่าใหม่ ไปเรื่อยๆ จนกว่าจะยอมรับได้ ${\displaystyle X}$${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$${\textstyle U\sim \mathrm {Unif} (0,1)}$

จากตัวอย่างข้างต้น ในการวัดประสิทธิภาพ จำนวนรอบการทำซ้ำโดยเฉลี่ยของวิธีการสุ่มตัวอย่างแบบปฏิเสธโดยใช้ตระกูลเลขชี้กำลังธรรมชาติจะมีลำดับเป็นซึ่งก็คือในขณะที่วิธีการแบบง่ายๆ นั้น จำนวนรอบการทำซ้ำโดยเฉลี่ยคือซึ่งไม่มีประสิทธิภาพมากกว่ามาก ${\displaystyle b}$${\displaystyle M(b)=O(b)}$${\textstyle {\frac {1}{\mathbb {P} (X\geq b)}}=O(b\cdot e^{\frac {(b-\mu )^{2}}{2\sigma ^{2}}})}$

โดยทั่วไปการเอียงแบบเอกซ์โปเนนเชียลในกลุ่มพารามิเตอร์ของการแจกแจงแบบเสนอแนะ ช่วยแก้ปัญหาการหาค่าเหมาะสมที่สุดได้อย่างสะดวก ด้วยคุณสมบัติที่เป็นประโยชน์ซึ่งบ่งบอกลักษณะเฉพาะของการแจกแจงแบบเสนอแนะโดยตรง สำหรับปัญหาประเภทนี้ เพื่อจำลองแบบมีเงื่อนไขบนในกลุ่มของการแจกแจงแบบง่าย เทคนิคคือการใช้ตระกูลเอกซ์โปเนนเชียลธรรมชาติ ซึ่งช่วยให้ควบคุมความซับซ้อนได้มากขึ้นและเร่งความเร็วในการคำนวณได้อย่างมาก อันที่จริง มีเหตุผลทางคณิตศาสตร์ที่ลึกซึ้งสำหรับการใช้ตระกูลเอกซ์โปเนนเชียลธรรมชาติ ${\displaystyle X}$${\displaystyle X\in A}$

การสุ่มตัวอย่างแบบปฏิเสธจำเป็นต้องทราบการกระจายตัวของเป้าหมาย (โดยเฉพาะอย่างยิ่ง ความสามารถในการประเมิน PDF ของเป้าหมาย ณ จุดใด ๆ ก็ได้)

การสุ่มตัวอย่างแบบปฏิเสธ (Rejection sampling) อาจทำให้ได้ตัวอย่างที่ไม่ต้องการจำนวนมาก หากฟังก์ชันที่กำลังสุ่มตัวอย่างนั้นมีความเข้มข้นสูงในบริเวณใดบริเวณหนึ่ง เช่น ฟังก์ชันที่มีจุดสูงสุดอยู่ที่ตำแหน่งใดตำแหน่งหนึ่ง สำหรับการแจกแจงหลายๆ แบบ ปัญหานี้สามารถแก้ไขได้โดยใช้ส่วนขยายแบบปรับตัว (adaptive extension) (ดูadaptive rejection sampling ) หรือด้วยการเปลี่ยนตัวแปรที่เหมาะสมโดยใช้วิธีอัตราส่วนของค่าสม่ำเสมอ (ratio of uniforms ) นอกจากนี้ เมื่อมิติของปัญหาใหญ่ขึ้น อัตราส่วนของปริมาตรที่ฝังตัวต่อ "มุม" ของปริมาตรที่ฝังตัวจะเข้าใกล้ศูนย์ ดังนั้นจึงอาจมีการปฏิเสธเกิดขึ้นมากมายก่อนที่จะได้ตัวอย่างที่มีประโยชน์ ทำให้ขั้นตอนวิธีไม่มีประสิทธิภาพและใช้งานไม่ได้จริง ดูคำสาปของมิติ (curse of dimensionality ) ในมิติสูง จำเป็นต้องใช้วิธีการที่แตกต่างออกไป โดยทั่วไปคือวิธีการมาร์คอฟเชน มอนเตคาร์โล เช่นการสุ่มตัวอย่างแบบเมโทรโพลิส (Metropolis sampling) หรือการสุ่มตัวอย่างแบบกิบส์ (Gibbs sampling ) (อย่างไรก็ตาม การสุ่มตัวอย่างแบบกิบส์ ซึ่งแบ่งปัญหาการสุ่มตัวอย่างหลายมิติออกเป็นชุดของตัวอย่างมิติที่ต่ำกว่า อาจใช้การสุ่มตัวอย่างแบบปฏิเสธเป็นหนึ่งในขั้นตอน)

เมื่อไม่มีค่าคงที่จำกัดที่ ตรง ตามเงื่อนไข หรือการคำนวณค่าคงที่จำกัดที่เหมาะสมนั้นยากเกินไป เวอร์ชันที่แก้ไขของอัลกอริธึมการสุ่มตัวอย่างแบบปฏิเสธยังคงสามารถใช้เพื่อจำลอง (โดยประมาณ) จากเป้าหมายได้ดังต่อไปนี้^{[ 5 ]}${\displaystyle M}$${\displaystyle M\geq \sup _{x}{\frac {f_{\varpropto }(x)}{g(x)}}}$${\displaystyle M<\infty }$${\displaystyle f}$

การสุ่มตัวอย่างแบบปฏิเสธแบบสร้างใหม่

ป้อนข้อมูล

ความหนาแน่นเป้าหมายความหนาแน่นข้อเสนอ ค่า คง ที่ขนาดใหญ่ ${\displaystyle f(x)={\frac {f_{\varpropto }(x)}{\int f_{\varpropto }(y)dy}}}$${\displaystyle g(x)}$${\displaystyle M}$

อัลกอริทึม

ตั้งค่าตัวนับ ${\displaystyle t\leftarrow 0}$

1. ตัวอย่างและการเพิ่มค่า${\displaystyle X\sim g(x)}$${\displaystyle t\leftarrow t+1}$
2. คำนวณอัตราส่วนความน่าจะเป็น${\displaystyle W_{t}={\dfrac {f_{\varpropto }(X)}{g(X)}}}$
3. ถ้าเป็นจริง ให้ปฏิเสธและทำซ้ำตั้งแต่ขั้นตอนที่ 1 มิฉะนั้น ให้ยอมรับและแสดงผล${\displaystyle W_{1}+\cdots +W_{t}<M}$${\displaystyle X}$${\displaystyle X}$

เอาต์พุต

ตัวอย่างที่สุ่มมาโดยประมาณจาก.${\displaystyle X}$${\displaystyle f}$

ความแตกต่างเพียงอย่างเดียวระหว่างเวอร์ชันการสร้างใหม่ข้างต้นกับการสุ่มตัวอย่างแบบปฏิเสธแบบคลาสสิกคือ การตัดสินใจยอมรับนั้นขึ้นอยู่กับว่าผลรวมสะสมของอัตราส่วนความน่าจะเป็นทั้งหมดเกินค่าที่ กำหนดหรือไม่ (นั่นคือ) แทนที่จะขึ้นอยู่กับว่าอัตราส่วนความน่าจะเป็นปัจจุบันเกินค่าที่ กำหนดหรือไม่ (นั่นคือ) ${\displaystyle W_{1}+\cdots +W_{t}}$${\displaystyle M}$${\displaystyle W_{1}+\cdots +W_{t}>M}$${\displaystyle W_{t}}$${\displaystyle M\times U}$${\displaystyle W_{t}>M\times U}$

สามารถแสดงได้ว่า เมื่อตัวแปรเอาต์พุตของอัลกอริทึม จะลู่เข้าสู่เป้าหมายที่ต้องการด้วยความหนาแน่นตามการ กระจาย ^{[ 5 ]}${\displaystyle M\rightarrow \infty }$${\displaystyle X=X_{M}}$${\displaystyle f}$

แนวทางอื่นที่ไม่ต้องอาศัยความรู้เกี่ยวกับค่าคงที่ขอบเขตที่เหมาะสม คือวิธีการสุ่มตัวอย่างการปฏิเสธค่าสูงสุดเชิงประจักษ์^{[ 6 ]}${\displaystyle \sup _{x}{\frac {f_{\varpropto }(x)}{g(x)}}}$

สำหรับการแจกแจงจำนวนมาก การหาการแจกแจงแบบเสนอที่ครอบคลุมการแจกแจงที่กำหนดโดยไม่เสียพื้นที่มากเกินไปนั้นเป็นเรื่องยาก การสุ่มตัวอย่างแบบปฏิเสธที่ขยายเพิ่มเติมซึ่งสามารถใช้เพื่อเอาชนะความยากลำบากนี้และสุ่มตัวอย่างได้อย่างมีประสิทธิภาพจากการแจกแจงที่หลากหลาย (โดยมีเงื่อนไขว่าการแจกแจงเหล่านั้นมี ฟังก์ชันความหนาแน่น แบบลอการิทึมเว้าซึ่งในความเป็นจริงแล้วเป็นเช่นนั้นสำหรับการแจกแจงทั่วไปส่วนใหญ่ แม้แต่การแจกแจงที่มี ฟังก์ชัน ความหนาแน่นไม่เป็นแบบเว้าก็ตาม) เรียกว่าการสุ่มตัวอย่างแบบปฏิเสธแบบปรับตัว (Adaptive Rejection Sampling: ARS )

เทคนิคนี้มีแนวคิดพื้นฐานสามประการตามที่ Gilks ​​นำเสนอในที่สุดในปี 1992: ^{[ 7 ]}

1. หากเป็นประโยชน์ ให้กำหนดการกระจายซองจดหมายของคุณในพื้นที่ลอการิทึม (เช่น ความน่าจะเป็นลอการิทึม หรือความหนาแน่นลอการิทึม) แทน นั่นคือ ทำงานกับมันแทนที่จะใช้โดยตรง ${\displaystyle h\left(x\right)=\log g\left(x\right)}$${\displaystyle g\left(x\right)}$
   • บ่อยครั้งที่การแจกแจงที่มีฟังก์ชันความหนาแน่นที่ยุ่งยากทางพีชคณิต มักจะมีฟังก์ชันความหนาแน่นแบบลอการิทึมที่เรียบง่ายกว่า (เช่น เมื่อการแจกแจงแบบพีชคณิตยุ่งยาก ฟังก์ชันความหนาแน่นแบบลอการิทึมอาจจัดการได้ง่ายกว่า หรืออย่างน้อยก็ใกล้เคียงกับแบบเชิงเส้นเป็นช่วงๆ)${\displaystyle f\left(x\right)}$${\displaystyle \log f\left(x\right)}$
2. แทนที่จะใช้ฟังก์ชันความหนาแน่นซองจดหมายแบบสม่ำเสมอเพียงฟังก์ชันเดียว ให้ใช้ ฟังก์ชัน ความหนาแน่นเชิงเส้น แบบแบ่งช่วง เป็นซองจดหมายแทน
   • ทุกครั้งที่คุณต้องปฏิเสธตัวอย่าง คุณสามารถใช้ค่าที่คุณประเมินไว้เพื่อปรับปรุงการประมาณค่าแบบแบ่งช่วงได้ดังนั้นจึงลดโอกาสที่ความพยายามครั้งต่อไปของคุณจะถูกปฏิเสธ ในทางทฤษฎีแล้ว ความน่าจะเป็นที่จะต้องปฏิเสธตัวอย่างของคุณควรลู่เข้าสู่ศูนย์ และในทางปฏิบัติ มักจะเกิดขึ้นอย่างรวดเร็วมาก${\displaystyle f\left(x\right)}$${\displaystyle h\left(x\right)}$
   • ตามที่เสนอไว้ เมื่อใดก็ตามที่เราเลือกจุดที่ถูกปฏิเสธ เราจะกระชับขอบเขตด้วยส่วนของเส้นตรง อีกเส้นหนึ่ง ที่สัมผัสกับเส้นโค้ง ณ จุดที่มีพิกัด x เดียวกันกับจุดที่เลือก
   • แบบจำลอง เชิงเส้นแบบ แบ่งช่วงของฟังก์ชันการแจกแจงลอการิทึมที่เสนอ จะส่งผลให้เกิดชุดของการแจกแจงเอกซ์โพเนนเชียลแบบแบ่งช่วง (กล่าวคือ ส่วนต่าง ๆ ของการแจกแจงเอกซ์โพเนนเชียลหนึ่งหรือมากกว่านั้น ที่ต่อกันเป็นปลาย) การแจกแจงเอกซ์โพเนนเชียลนั้นมีพฤติกรรมที่ดีและเข้าใจได้ง่ายลอการิทึมของการแจกแจงเอกซ์โพเนนเชียลเป็นเส้นตรง ดังนั้นวิธีการนี้จึงเกี่ยวข้องกับการล้อมรอบลอการิทึมของความหนาแน่นด้วยชุดของส่วนของเส้นตรง นี่คือที่มาของข้อจำกัดลอการิทึมเว้า: ถ้าการแจกแจงเป็นแบบลอการิทึมเว้า ลอการิทึมของมันจะเว้า (มีรูปร่างเหมือนตัวยูคว่ำ) ซึ่งหมายความว่าส่วนของเส้นตรงที่สัมผัสกับเส้นโค้งจะผ่านเส้นโค้งเสมอ
   • หากไม่ได้ทำงานในพื้นที่ลอการิทึม ฟังก์ชันความหนาแน่นเชิงเส้นแบบแบ่งส่วนยังสามารถสุ่มตัวอย่างผ่านการกระจายสามเหลี่ยมได้อีกด้วย^{[ 8 ]}
3. เราสามารถใช้ประโยชน์จากข้อกำหนดเรื่องความเว้า (แบบลอการิทึม) ได้มากยิ่งขึ้น เพื่อหลีกเลี่ยงค่าใช้จ่ายในการประเมินว่าตัวอย่างของคุณได้รับการยอมรับ เมื่อใด${\displaystyle f\left(x\right)}$
   • เช่นเดียวกับที่เราสามารถสร้างขอบเขตบนเชิงเส้นแบบแบ่งช่วง (ฟังก์ชัน "ซองจดหมาย") โดยใช้ค่าที่เราต้องประเมินในลำดับการปฏิเสธปัจจุบัน เราก็สามารถสร้างขอบเขตล่างเชิงเส้นแบบแบ่งช่วง (ฟังก์ชัน "การบีบอัด") โดยใช้ค่าเหล่านี้ได้เช่นกัน${\displaystyle h\left(x\right)}$
   • ก่อนที่จะทำการประเมิน (ซึ่งอาจมีค่าใช้จ่ายสูง) เพื่อดูว่าตัวอย่างของคุณจะได้รับการยอมรับหรือไม่ เราอาจทราบได้แล้ว ว่าตัวอย่างของคุณ จะได้รับการยอมรับหรือไม่ โดยการเปรียบเทียบกับฟังก์ชันการบีบอัด (ซึ่งโดยทั่วไปแล้วจะถูกกว่า) (หรือในกรณีนี้) ที่มีอยู่${\displaystyle f\left(x\right)}$${\displaystyle g_{l}\left(x\right)}$${\displaystyle h_{l}\left(x\right)}$
   • ขั้นตอนการบีบอัดนี้เป็นขั้นตอนเสริม แม้ว่า Gilks ​​จะแนะนำก็ตาม อย่างดีที่สุด มันช่วยประหยัดเวลาในการประเมินความหนาแน่นเป้าหมาย (ที่ยุ่งยากและ/หรือมีราคาแพง) เพียงครั้งเดียวเท่านั้น อย่างไรก็ตาม สำหรับฟังก์ชันความหนาแน่นที่มีราคาแพงเป็นพิเศษ (และสมมติว่าอัตราการปฏิเสธลู่เข้าสู่ศูนย์อย่างรวดเร็ว) ขั้นตอนนี้อาจสร้างความแตกต่างอย่างมากในเวลาการทำงานโดยรวม

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

น่าเสียดายที่ ARS สามารถใช้ได้เฉพาะกับการสุ่มตัวอย่างจากความหนาแน่นเป้าหมายแบบ log-concave เท่านั้น ด้วยเหตุนี้ จึงมีการเสนอส่วนขยายของ ARS หลายอย่างในเอกสารวิจัยเพื่อจัดการกับการกระจายเป้าหมายที่ไม่ใช่ log-concave ^{[ 9 ] [ 10 ] [ 11 ]}นอกจากนี้ ยังมีการออกแบบการผสมผสานระหว่าง ARS และวิธีการ Metropolis-Hastings ที่แตกต่างกันเพื่อให้ได้ตัวสุ่มตัวอย่างสากลที่สร้างความหนาแน่นข้อเสนอที่ปรับแต่งตัวเองได้ (กล่าวคือ ข้อเสนอที่สร้างขึ้นและปรับให้เข้ากับเป้าหมายโดยอัตโนมัติ) วิธีการประเภทนี้มักเรียกว่าอัลกอริธึม Adaptive Rejection Metropolis Sampling (ARMS) [ ^{12 ] [ 13 ] เทคนิค}การปรับตัวที่ได้นั้นสามารถนำไปใช้ได้เสมอ แต่ตัวอย่างที่สร้างขึ้นจะมีความสัมพันธ์กันในกรณีนี้ (แม้ว่าความสัมพันธ์จะหายไปอย่างรวดเร็วเป็นศูนย์เมื่อจำนวนรอบการทำซ้ำเพิ่มขึ้น)

• การสุ่มตัวอย่างการแปลงผกผัน
• อัตราส่วนของเครื่องแบบ
• การสุ่มตัวเลขแบบเทียม
• อัลกอริทึมซิกกูแรต

• Robert, CP; Casella, G. (2004). วิธีการทางสถิติแบบมอนเตคาร์โล (ฉบับที่สอง). นิวยอร์ก: Springer-Verlag.