अस्वीकृति नमूनाकरण

संख्यात्मक विश्लेषण और कम्प्यूटेशनल आंकड़ों में, अस्वीकृति नमूनाकरण एक मूल तकनीक है जिसका उपयोग संभाव्यता वितरण से अवलोकन उत्पन्न करने के लिए किया जाता है। इसे सामान्यतः स्वीकृति-अस्वीकृति विधि या स्वीकार-अस्वीकार एल्गोरिथम भी कहा जाता है और यह एक प्रकार की सटीक सिमुलेशन विधि है। विधि किसी भी वितरण के लिए काम करती है $\mathbb {R} ^{m}$ संभाव्यता घनत्व फलन के साथ।

अस्वीकृति नमूनाकरण अवलोकन पर आधारित है कि एक आयाम में एक यादृच्छिक चर का नमूना लेने के लिए, द्वि-आयामी कार्टेशियन ग्राफ का एक समान रूप से यादृच्छिक नमूनाकरण कर सकता है, और इसके घनत्व समारोह के ग्राफ के तहत क्षेत्र में नमूने रख सकता है। ध्यान दें कि इस संपत्ति को n-आयाम कार्यों तक बढ़ाया जा सकता है।

विवरण

रिजेक्शन सैंपलिंग के पीछे की प्रेरणा की कल्पना करने के लिए, एक बड़े आयताकार बोर्ड पर एक यादृच्छिक चर के घनत्व फ़ंक्शन को ग्राफ़ करने और उस पर डार्ट्स फेंकने की कल्पना करें। मान लें कि डार्ट्स समान रूप से बोर्ड के चारों ओर वितरित किए जाते हैं। अब उन सभी डार्ट्स को हटा दें जो वक्र के नीचे के क्षेत्र से बाहर हैं। शेष डार्ट्स वक्र के अंतर्गत क्षेत्र के भीतर समान रूप से वितरित किए जाएंगे, और इन डार्ट्स के एक्स-पोजिशन को यादृच्छिक चर के घनत्व के अनुसार वितरित किया जाएगा। ऐसा इसलिए है क्योंकि डार्ट्स के लिए सबसे अधिक जगह है जहां वक्र उच्चतम है और इस प्रकार संभाव्यता घनत्व सबसे बड़ा है।

विज़ुअलाइज़ेशन जैसा कि अभी वर्णित किया गया है, अस्वीकृति नमूनाकरण के एक विशेष रूप के बराबर है जहाँ प्रस्ताव वितरण एक समान है (इसलिए इसका ग्राफ़ एक आयत है)। अस्वीकृति नमूनाकरण का सामान्य रूप मानता है कि बोर्ड आवश्यक रूप से आयताकार नहीं है, लेकिन कुछ प्रस्ताव वितरण के घनत्व के अनुसार आकार दिया गया है, जिसे हम जानते हैं कि कैसे नमूना लेना है (उदाहरण के लिए, उलटा नमूनाकरण का उपयोग करके), और जो कम से कम हर बार उच्च है उस वितरण के रूप में इंगित करें जिससे हम नमूना लेना चाहते हैं, ताकि पूर्व पूरी तरह से उत्तरार्द्ध को घेर ले। (अन्यथा, घुमावदार क्षेत्र के कुछ हिस्से होंगे जिनसे हम नमूना लेना चाहते हैं, कभी नहीं पहुंचा जा सकता।)

अस्वीकृति नमूना निम्नानुसार काम करता है:

1. प्रस्ताव वितरण से x-अक्ष पर एक बिंदु का नमूना लें।
2. प्रस्ताव वितरण के प्रायिकता घनत्व फ़ंक्शन के अधिकतम y- मान तक, इस x- स्थिति पर एक लंबवत रेखा बनाएं।
3. इस रेखा के साथ समान रूप से 0 से अधिकतम संभाव्यता घनत्व फ़ंक्शन का नमूना लें। यदि नमूनाकृत मान इस लंबवत रेखा पर वांछित वितरण के मान से अधिक है, तो x-मान को अस्वीकार करें और चरण 1 पर वापस लौटें; अन्यथा x-मान वांछित वितरण से एक नमूना है।

इस एल्गोरिथ्म का उपयोग किसी भी वक्र के तहत क्षेत्र से नमूना लेने के लिए किया जा सकता है, भले ही फ़ंक्शन 1 को एकीकृत करता हो या नहीं। वास्तव में, किसी फ़ंक्शन को स्थिरांक द्वारा स्केल करने से नमूना x-स्थितियों पर कोई प्रभाव नहीं पड़ता है। इस प्रकार, एल्गोरिथ्म का उपयोग एक ऐसे वितरण से नमूना लेने के लिए किया जा सकता है जिसका सामान्यीकरण स्थिरांक अज्ञात है, जो कम्प्यूटेशनल आंकड़ों में आम है।

सिद्धांत

रिजेक्शन सैंपलिंग पद्धति लक्ष्य वितरण से सैंपलिंग मान उत्पन्न करती है $X$ मनमाने ढंग से संभाव्यता घनत्व समारोह के साथ $f(x)$ प्रस्ताव वितरण का उपयोग करके $Y$ संभाव्यता घनत्व के साथ $g(x)$. विचार यह है कि कोई एक नमूना मूल्य उत्पन्न कर सकता है $X$ इसके बजाय से नमूना लेना $Y$ और से नमूना स्वीकार करना $Y$ संभावना के साथ $f(x)/(Mg(x))$, ड्रॉ को दोहराते हुए $Y$ जब तक कोई मान स्वीकार नहीं किया जाता। $M$ यहाँ संभावना अनुपात पर एक स्थिर, परिमित सीमा है $f(x)/g(x)$, संतुष्टि देने वाला $1<M<\infty$ के समर्थन (गणित) पर $X$; दूसरे शब्दों में, एम को संतुष्ट करना चाहिए $f(x)\leq Mg(x)$ के सभी मूल्यों के लिए $x$. ध्यान दें कि इसके लिए समर्थन की आवश्यकता है $Y$ का समर्थन शामिल करना चाहिए $X$-दूसरे शब्दों में, $g(x)>0$ जब कभी भी $f(x)>0$.

इस पद्धति का सत्यापन लिफाफा सिद्धांत है: जोड़ी का अनुकरण करते समय ${\textstyle (x,v=u\cdot Mg(x))}$, एक के सबग्राफ पर एक समान सिमुलेशन का उत्पादन करता है ${\textstyle Mg(x)}$. केवल ऐसी जोड़ियों को स्वीकार करना ${\textstyle u<f(x)/(Mg(x))}$ फिर जोड़े पैदा करता है $(x,v)$ के सबग्राफ पर समान रूप से वितरित $f(x)$ और इस प्रकार, आंशिक रूप से, एक अनुकरण $f(x).$ इसका मतलब यह है कि, पर्याप्त प्रतिकृति के साथ, एल्गोरिथम वांछित वितरण से एक नमूना उत्पन्न करता है $f(x)$. इस एल्गोरिथम के लिए कई एक्सटेंशन हैं, जैसे महानगर एल्गोरिथम ।

यह विधि मोंटे कार्लो पद्धति तकनीकों के सामान्य क्षेत्र से संबंधित है, जिसमें मार्कोव चेन मोंटे कार्लो एल्गोरिदम शामिल हैं जो लक्ष्य वितरण से अनुकरण प्राप्त करने के लिए प्रॉक्सी वितरण का भी उपयोग करते हैं। $f(x)$. यह मेट्रोपोलिस एल्गोरिथम जैसे एल्गोरिदम के लिए आधार बनाता है।

बिना शर्त स्वीकृति संभावना प्रस्तावित नमूनों का अनुपात है जो स्वीकार किए जाते हैं, जो है

$${\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]&=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]&=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}}$$

कहाँ $U\sim \mathrm {Unif} (0,1)$, और का मूल्य $y$ हर बार घनत्व समारोह के तहत उत्पन्न होता है $g(\cdot )$ प्रस्ताव वितरण के संबंध में $Y$.

से आवश्यक नमूनों की संख्या $Y$ एक स्वीकृत मूल्य प्राप्त करने के लिए इस प्रकार संभाव्यता के साथ एक ज्यामितीय वितरण होता है $1/M$, जिसका मतलब है $M$. सहज रूप से, $M$ एल्गोरिथम की कम्प्यूटेशनल जटिलता के माप के रूप में आवश्यक पुनरावृत्तियों की अपेक्षित संख्या है।

उपरोक्त समीकरण को फिर से लिखें,

$$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)}$ एक प्रायिकता है जो अंतराल में केवल मान ले सकती है $[0,1]$. कब $M$ एक के करीब चुना जाता है, बिना शर्त स्वीकृति की संभावना उतनी ही अधिक होती है, जितना कम अनुपात भिन्न होता है, क्योंकि $M$ संभावना अनुपात के लिए ऊपरी सीमा है ${\textstyle f(x)/g(x)}$. व्यवहार में, का एक मूल्य $M$ 1 के करीब को प्राथमिकता दी जाती है क्योंकि इसका तात्पर्य कम अस्वीकृत नमूनों से है, औसतन, और इस प्रकार एल्गोरिथम के कम पुनरावृत्तियों। इस अर्थ में, कोई लेना पसंद करता है $M$ जितना संभव हो उतना छोटा (अभी भी संतुष्ट करते हुए $f(x)\leq Mg(x)$, जिससे पता चलता है $g(x)$ आम तौर पर समान होना चाहिए $f(x)$ किसी तरह। हालाँकि, ध्यान दें $M$ 1 के बराबर नहीं हो सकता: ऐसा इसका मतलब होगा $f(x)=g(x)$, यानी कि लक्ष्य और प्रस्ताव वितरण वास्तव में समान वितरण हैं।

अस्वीकृति नमूनाकरण का उपयोग अक्सर उन मामलों में किया जाता है जहां प्रपत्र $f(x)$ नमूनाकरण को कठिन बनाता है। अस्वीकृति एल्गोरिथम के एकल पुनरावृत्ति के लिए प्रस्ताव वितरण से नमूने लेने, एक समान वितरण से आरेखण करने और प्रस्ताव का मूल्यांकन करने की आवश्यकता होती है $f(x)/(Mg(x))$ अभिव्यक्ति। इस प्रकार अस्वीकृति नमूनाकरण किसी अन्य विधि की तुलना में अधिक कुशल होता है जब भी इन कार्यों की एम गुना लागत - जो अस्वीकृति नमूनाकरण के साथ नमूना प्राप्त करने की अपेक्षित लागत होती है - अन्य विधि का उपयोग करके नमूना प्राप्त करने की लागत से कम होती है।

एल्गोरिथम

एल्गोरिथम, जिसका उपयोग जॉन वॉन न्यूमैन द्वारा किया गया था और जॉर्जेस-लुई लेक्लेर, कॉम्टे डे बफन और बफन की सुई के समय से है, वितरण से एक नमूना प्राप्त करता है $X$ घनत्व के साथ $f$ वितरण से नमूने का उपयोग करना $Y$ घनत्व के साथ $g$ निम्नलिखित नुसार:

• नमूना प्राप्त करें $y$ वितरण से $Y$ और एक नमूना $u$ से $\mathrm {Unif} (0,1)$ (इकाई अंतराल पर समान वितरण)।
• चेक करें या नहीं ${\textstyle u<f(y)/Mg(y)}$.
  • यदि यह मान्य है, तो स्वीकार करें $y$ से लिए गए नमूने के रूप में $f$;
  • यदि नहीं, के मूल्य को अस्वीकार करें $y$ और नमूनाकरण कदम पर लौटें।

एल्गोरिदम औसत लेगा $M$ नमूना प्राप्त करने के लिए पुनरावृत्तियाँ।

भोली विधियों का उपयोग करके नमूनाकरण पर लाभ

कुछ स्थितियों में सरल तरीकों की तुलना में अस्वीकृति नमूनाकरण कहीं अधिक कुशल हो सकता है। उदाहरण के लिए, नमूनाकरण के रूप में एक समस्या दी गई है ${\textstyle X\sim F(\cdot )}$ सशर्त रूप से $X$ सेट दिया $A$, अर्थात।, ${\textstyle X|X\in A}$, कभी-कभी ${\textstyle X}$ भोली विधियों का उपयोग करके आसानी से अनुकरण किया जा सकता है (उदाहरण के लिए प्रतिलोम रूपांतरण नमूनाकरण द्वारा):

• नमूना ${\textstyle X\sim F(\cdot )}$ स्वतंत्र रूप से, और उन्हें संतुष्ट करने वालों को छोड़ दें $\{n\geq 1:X_{n}\in A\}$ * आउटपुट: $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$

समस्या यह है कि यह नमूनाकरण कठिन और अक्षम हो सकता है, यदि ${\textstyle \mathbb {P} (X\in A)\approx 0}$. पुनरावृत्तियों की अपेक्षित संख्या होगी ${\frac {1}{\mathbb {P} (X\in A)}}$, जो अनंत के करीब हो सकता है। इसके अलावा, जब आप अस्वीकृति नमूनाकरण विधि लागू करते हैं, तब भी बाउंड को अनुकूलित करना हमेशा कठिन होता है $M$ संभावना अनुपात के लिए अधिक से अधिक, $M$ बड़ा है और अस्वीकृति दर अधिक है, एल्गोरिथ्म बहुत अक्षम हो सकता है। प्राकृतिक घातीय परिवार (यदि यह मौजूद है), जिसे घातीय झुकाव के रूप में भी जाना जाता है, प्रस्ताव वितरण का एक वर्ग प्रदान करता है जो गणना जटिलता को कम कर सकता है, का मान $M$ और संगणनाओं को गति दें (उदाहरण देखें: प्राकृतिक घातीय परिवारों के साथ काम करना)।

उदाहरण: प्राकृतिक घातीय परिवारों के साथ काम करना

एक यादृच्छिक चर दिया $X\sim F(\cdot )$, $F(x)=\mathbb {P} (X\leq x)$ लक्ष्य वितरण है। सादगी के लिए मान लें, घनत्व समारोह स्पष्ट रूप से लिखा जा सकता है $f(x)$. प्रस्ताव को इस रूप में चुनें

$${\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}}$$

कहाँ $\psi (\theta )=\log \left(\mathbb {E} \exp(\theta X)\right)$ और $\Theta =\{\theta :\psi (\theta )<\infty \}$. स्पष्ट रूप से, $\{F_{\theta }(\cdot )\}_{\theta \in \Theta }$, एक प्राकृतिक घातीय परिवार से है। इसके अलावा, संभावना अनुपात है

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

ध्यान दें कि $\psi (\theta )<\infty$ तात्पर्य यह है कि यह वास्तव में एक लॉग क्षण-उत्पन्न करने वाला कार्य है। मोमेंट-जेनरेशन फंक्शन, यानी $\psi (\theta )=\log \mathbb {E} {\exp(tX)}|_{t=\theta }=\log M_{X}(t)|_{t=\theta }$. और प्रस्ताव के लॉग क्षण-सृजन समारोह को प्राप्त करना आसान है और इसलिए प्रस्ताव के क्षण।

$${\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}}$$

एक साधारण उदाहरण के रूप में, मान लीजिए $F(\cdot )$, $X\sim \mathrm {N} (\mu ,\sigma ^{2})$, साथ ${\textstyle \psi (\theta )=\theta \mu +{\frac {\sigma ^{2}\theta ^{2}}{2}}}$. लक्ष्य नमूना लेना है $X|X\in \left[b,\infty \right]$, $b>\mu$. विश्लेषण इस प्रकार है।

• प्रस्ताव वितरण का रूप चुनें $F_{\theta }(\cdot )$, लॉग मोमेंट-जेनरेटिंग फ़ंक्शन के रूप में ${\textstyle \psi _{\theta }(\eta )=\psi (\theta +\eta )-\psi (\eta )=\eta (\mu +\theta \sigma ^{2})+{\frac {\sigma ^{2}\eta ^{2}}{2}}}$, जिसका अर्थ है कि यह एक सामान्य वितरण है $\mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})$.
• अच्छी तरह से चुने गए का फैसला करें $\theta ^{*}$ प्रस्ताव वितरण के लिए इस सेटअप में, चुनने का सहज तरीका $\theta ^{*}$ लगाना है $\mathbb {E} _{\theta }(X)=\mu +\theta \sigma ^{2}=b$, वह है $\theta ^{*}={\frac {b-\mu }{\sigma ^{2}}}$
• स्पष्ट रूप से लक्ष्य, प्रस्ताव और संभावना अनुपात लिखें
  $${\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}}$$
• सीमा प्राप्त करें $M$ संभावना अनुपात के लिए $z(x)$, जो कि एक घटता हुआ कार्य है $x\in [b,\infty ]$, इसलिए
  $$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)}}$$
• अस्वीकृति नमूनाकरण मानदंड: के लिए $U\sim \mathrm {Unif} (0,1)$, अगर
  $$U\leq {\frac {Z(x)}{M}}=e^{-\theta ^{*}(x-b)}\mathbb {I} (x\geq b)$$
  रखता है, का मान स्वीकार करता है $X$; यदि नहीं, तो नया नमूना लेना जारी रखें ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ और नया ${\textstyle U\sim \mathrm {Unif} (0,1)}$ स्वीकृति तक।

उपरोक्त उदाहरण के लिए, दक्षता की माप के रूप में, पुनरावृत्तियों की अपेक्षित संख्या एनईएफ-आधारित अस्वीकृति नमूना पद्धति क्रम बी की है, अर्थात $M(b)=O(b)$, जबकि भोली पद्धति के तहत, पुनरावृत्तियों की अपेक्षित संख्या है ${\textstyle {\frac {1}{\mathbb {P} (X\geq b)}}=O(b\cdot e^{\frac {(b-\mu )^{2}}{2\sigma ^{2}}})}$, जो कहीं अधिक अक्षम है।

सामान्य तौर पर, घातीय झुकाव, प्रस्ताव वितरण का एक पैरामीट्रिक वर्ग, अपने उपयोगी गुणों के साथ अनुकूलन समस्याओं को आसानी से हल करता है जो सीधे प्रस्ताव के वितरण की विशेषता बताते हैं। इस प्रकार की समस्या के लिए अनुकरण करना $X$ सशर्त रूप से $X\in A$, सरल वितरण के वर्ग के बीच, एनईएफ का उपयोग करने की चाल है, जो जटिलता पर कुछ नियंत्रण हासिल करने में मदद करती है और गणना को काफी तेज करती है। दरअसल, एनईएफ का उपयोग करने के गहरे गणितीय कारण हैं।

कमियां

यदि नमूना लिया जा रहा कार्य एक निश्चित क्षेत्र में अत्यधिक केंद्रित है, उदाहरण के लिए एक समारोह जिसमें किसी स्थान पर स्पाइक है, तो अस्वीकृति नमूनाकरण से बहुत सारे अवांछित नमूने लिए जा सकते हैं। कई वितरणों के लिए, इस समस्या को एक अनुकूली विस्तार (देखें # अनुकूली अस्वीकृति नमूनाकरण) का उपयोग करके या वर्दी के अनुपात की विधि के साथ चर के उचित परिवर्तन के साथ हल किया जा सकता है। इसके अलावा, जैसे-जैसे समस्या का आयाम बड़ा होता जाता है, एम्बेडिंग वॉल्यूम के कोनों में एम्बेडेड वॉल्यूम का अनुपात शून्य की ओर बढ़ता जाता है, इस प्रकार एक उपयोगी नमूना उत्पन्न होने से पहले बहुत सारे अस्वीकरण हो सकते हैं, इस प्रकार एल्गोरिथम को अक्षम बना दिया जाता है और अव्यावहारिक। आयामीता का अभिशाप देखें। उच्च आयामों में, एक अलग दृष्टिकोण का उपयोग करना आवश्यक है, सामान्यतः एक मार्कोव श्रृंखला मोंटे कार्लो विधि जैसे मेट्रोपोलिस नमूनाकरण या गिब्स नमूनाकरण। (हालांकि, गिब्स नमूनाकरण, जो एक बहु-आयामी नमूनाकरण समस्या को निम्न-आयामी नमूनों की एक श्रृंखला में विभाजित करता है, इसके एक चरण के रूप में अस्वीकृति नमूनाकरण का उपयोग कर सकता है।)

अनुकूली अस्वीकृति नमूनाकरण

कई वितरणों के लिए, एक ऐसा प्रस्ताव वितरण खोजना मुश्किल है जिसमें बहुत अधिक बर्बाद जगह के बिना दिए गए वितरण को शामिल किया गया हो। अस्वीकृति नमूनाकरण का एक विस्तार जिसका उपयोग इस कठिनाई को दूर करने के लिए किया जा सकता है और विभिन्न प्रकार के वितरणों से कुशलता से नमूना लिया जा सकता है (बशर्ते कि उनके पास लॉगरिदमिक रूप से अवतल कार्य हो। लॉग-अवतल घनत्व कार्य, जो वास्तव में अधिकांश सामान्य वितरणों के मामले में है- यहां तक ​​​​कि जिनके घनत्व कार्य स्वयं अवतल नहीं हैं) को 'अनुकूली अस्वीकृति नमूनाकरण (ARS)' के रूप में जाना जाता है।

1992 में गिल्क्स द्वारा अंततः पेश की गई इस तकनीक के लिए तीन मूल विचार हैं:

1. यदि यह मदद करता है, तो इसके बजाय लॉग स्पेस (जैसे लॉग-प्रायिकता या लॉग-घनत्व) में अपने लिफाफा वितरण को परिभाषित करें। यानी साथ काम करें $h\left(x\right)=\log g\left(x\right)$ के बजाय $g\left(x\right)$ सीधे।
   • अक्सर, जिन वितरणों में बीजगणितीय रूप से गड़बड़ घनत्व कार्य होते हैं, उनके पास यथोचित सरल लॉग घनत्व कार्य होते हैं (अर्थात जब $f\left(x\right)$ गन्दा है, $\log f\left(x\right)$ के साथ काम करना आसान हो सकता है या कम से कम, टुकड़ों में रैखिक के करीब)।
2. एक समान लिफ़ाफ़ा घनत्व फ़ंक्शन के बजाय, अपने लिफाफे के रूप में एक टुकड़ा-वार रैखिक घनत्व फ़ंक्शन का उपयोग करें।
   • हर बार जब आपको किसी नमूने को अस्वीकार करना हो, तो आप के मान का उपयोग कर सकते हैं $f\left(x\right)$ जिसका आपने मूल्यांकन किया है, टुकड़ों के सन्निकटन में सुधार करने के लिए $h\left(x\right)$. इससे आपके अगले प्रयास के अस्वीकृत होने की संभावना कम हो जाती है। असम्बद्ध रूप से, आपके नमूने को अस्वीकार करने की आवश्यकता की संभावना शून्य हो जानी चाहिए, और व्यवहार में, अक्सर बहुत तेज़ी से।
   • जैसा कि प्रस्तावित है, किसी भी समय हम एक ऐसा बिंदु चुनते हैं जिसे अस्वीकार कर दिया जाता है, हम लिफाफे को एक अन्य रेखा खंड के साथ कसते हैं जो उस बिंदु पर स्पर्शरेखा है जो चुने गए बिंदु के समान x-निर्देशांक के साथ है।
   • प्रस्ताव लॉग वितरण का टुकड़ावार रेखीय मॉडल टुकड़ेवार घातीय वितरण के एक सेट में परिणाम देता है (यानी एक या अधिक घातीय वितरण के खंड, अंत से अंत तक संलग्न)। घातीय वितरण अच्छी तरह से व्यवहार किया जाता है और अच्छी तरह से समझा जाता है। एक घातीय वितरण का लघुगणक एक सीधी रेखा है, और इसलिए इस पद्धति में अनिवार्य रूप से रेखा खंडों की एक श्रृंखला में घनत्व के लघुगणक को शामिल करना शामिल है। यह लॉग-अवतल प्रतिबंध का स्रोत है: यदि कोई वितरण लॉग-अवतल है, तो इसका लघुगणक अवतल (उल्टा-नीचे U जैसा आकार) है, जिसका अर्थ है कि वक्र के लिए स्पर्शरेखा रेखा खंड हमेशा वक्र के ऊपर से गुजरेगा।
   • यदि लॉग स्पेस में काम नहीं कर रहा है, तो एक टुकड़े के अनुसार रैखिक घनत्व फ़ंक्शन को त्रिकोण वितरण के माध्यम से भी नमूना लिया जा सकता है
3. मूल्यांकन की लागत से संभावित रूप से बचने के लिए हम (लॉग) समतलता आवश्यकता का और भी लाभ उठा सकते हैं $f\left(x\right)$ जब आपका नमूना स्वीकार किया जाता है।
   • जैसे हम के मानों का उपयोग करके एक टुकड़े की रैखिक ऊपरी सीमा (लिफ़ाफ़ा फ़ंक्शन) का निर्माण कर सकते हैं $h\left(x\right)$ कि हमें अस्वीकृति की वर्तमान श्रृंखला में मूल्यांकन करना था, हम इन मूल्यों का उपयोग करके एक टुकड़े की रैखिक निचली सीमा (निचोड़ने का कार्य) भी बना सकते हैं।
   • मूल्यांकन करने से पहले (संभावित महंगा) $f\left(x\right)$ यह देखने के लिए कि आपका नमूना स्वीकार किया जाएगा या नहीं, हम पहले से ही जान सकते हैं कि यह (आदर्श रूप से सस्ता) के खिलाफ तुलना करके स्वीकार किया जाएगा या नहीं $g_{l}\left(x\right)$ (या $h_{l}\left(x\right)$ इस मामले में) निचोड़ने का कार्य जो उपलब्ध है।
   • गिलक्स द्वारा सुझाए जाने पर भी यह निचोड़ने वाला कदम वैकल्पिक है। सर्वोत्तम रूप से यह आपको आपके (गड़बड़ और/या महंगे) लक्ष्य घनत्व के केवल एक अतिरिक्त मूल्यांकन से बचाता है। हालाँकि, संभवतः विशेष रूप से महंगे घनत्व कार्यों के लिए (और शून्य की ओर अस्वीकृति दर के तेजी से अभिसरण को मानते हुए) यह अंतिम रनटाइम में एक बड़ा अंतर बना सकता है।

इस पद्धति में अनिवार्य रूप से सीधी-रेखा खंडों के एक लिफाफे को क्रमिक रूप से निर्धारित करना शामिल है जो लघुगणक को बेहतर और बेहतर बनाता है, जबकि अभी भी वक्र के ऊपर शेष है, निश्चित संख्या में खंडों (संभवतः केवल एक स्पर्शरेखा रेखा) से शुरू होता है। एक छोटे घातीय यादृच्छिक चर से नमूनाकरण सीधा है। बस एक समान यादृच्छिक चर का लॉग लें (उचित अंतराल और संबंधित ट्रंकेशन के साथ)।

दुर्भाग्य से, एआरएस को केवल लॉग-अवतल लक्ष्य घनत्व से नमूनाकरण से ही लागू किया जा सकता है। इस कारण से, गैर-लॉग-अवतल लक्ष्य वितरण से निपटने के लिए साहित्य में एआरएस के कई विस्तार प्रस्तावित किए गए हैं। इसके अलावा, एआरएस और मेट्रोपोलिस-हेस्टिंग्स पद्धति के विभिन्न संयोजनों को एक सार्वभौमिक सैम्पलर प्राप्त करने के लिए डिज़ाइन किया गया है जो एक स्व-ट्यूनिंग प्रस्ताव घनत्व बनाता है (यानी, एक प्रस्ताव स्वचालित रूप से निर्मित और लक्ष्य के लिए अनुकूलित)। विधियों के इस वर्ग को अक्सर एडेप्टिव रिजेक्शन मेट्रोपोलिस सैंपलिंग (एआरएमएस) एल्गोरिदम कहा जाता है। परिणामी अनुकूली तकनीकों को हमेशा लागू किया जा सकता है लेकिन उत्पन्न नमूने इस मामले में सहसंबद्ध होते हैं (हालांकि पुनरावृत्तियों की संख्या बढ़ने पर सहसंबंध जल्दी से शून्य हो जाता है)।

यह भी देखें

• उलटा नमूना बदलना
• वर्दी का अनुपात
• छद्म यादृच्छिक संख्या नमूनाकरण
• ज़िगगुरैट एल्गोरिथम

अग्रिम पठन

• Robert, C. P.; Casella, G. (2004). Monte Carlo Statistical Methods (Second ed.). New York: Springer-Verlag.