Pliable rejection sampling

तकनीकी सारांश: प्लायबल रिजेक्शन सैंपलिंग (PRS)

1. समस्या विवरण

रिजेक्शन सैंपलिंग एक मौलिक तकनीक है जिसका उपयोग तब किया जाता है जब लक्ष्य घनत्व (target density) $f$ से सीधे नमूना लेना कठिन हो। यह एक एनवेलप $M_g$ (एक ऊपरी सीमा) का निर्माण करके कार्य करता है, जो एक प्रस्ताव वितरण (proposal distribution) $g$ का उपयोग करता है। हालाँकि, पारंपरिक रिजेक्शन सैंपलिंग (SRS) अत्यंत कम दक्षता प्रदर्शित करती है यदि $g$, $f$ के लिए एक सटीक फिट न हो, जिससे उच्च रिजेक्शन दर और गणना संसाधनों (f के कॉल्स) की बर्बादी होती है।

मौजूदा अनुकूली (adaptive) विधियाँ इसे हल करने का प्रयास करती हैं लेकिन उन्हें महत्वपूर्ण सीमाओं का सामना करना पड़ता है:

• एडेप्टिव रिजेक्शन सैंपलिंग (ARS): इसके लिए लक्ष्य घनत्व का लॉग-कॉन्केव (एकलमोड) होना आवश्यक है, जो कई वास्तविक दुनिया के अनुप्रयोगों के लिए बहुत अधिक प्रतिबंधात्मक है।
• एडेप्टिव रिजेक्शन मेट्रोपोलिस सैंपलिंग: यह आई.आई.डी. (i.i.d.) नमूनों के बजाय सह-संबंधित नमूने (मार्कोव श्रृंखला) उत्पन्न करती है।
• $A^\star$ सैंपलिंग: इसके लिए $f$ के अपघटन (decomposition) के पूर्व ज्ञान की आवश्यकता होती है (इसे एक सुलभ भाग और एक सीमित भाग में विभाजित करना), जो अक्सर उपलब्ध नहीं होता है।

लेखकों द्वारा पहचाना गया मुख्य संघर्ष यह है कि जबकि एडेप्टिव इम्पोर्टेंस सैंपलिंग को केवल $L_2$ जोखिम के संदर्भ में एक अच्छे अनुमानक (estimator) की आवश्यकता होती है, रिजेक्शन सैंपलिंग को दक्षता बनाए रखने के लिए $L_\infty$ जोखिम के संदर्भ में एक सटीक ऊपरी सीमा वाले प्रस्ताव की आवश्यकता होती है।

2. कार्यप्रणाली

लेखक प्लायबल रिजेक्शन सैंपलिंग (PRS) का प्रस्ताव करते हैं, जो एक गैर-पैरामीट्रिक दृष्टिकोण है जो कर्नेल डेंसिटी एस्टीमेशन का उपयोग करके एक समान वितरण को एक सटीक प्रस्ताव में "मोड़ता" (bends) है।

PRS एल्गोरिदम तीन मुख्य चरणों का पालन करता है:

1. प्रारंभिक नमूनाकरण (Initial Sampling): डोमेन $[0, A]^d$ से $N$ बिंदुओं को यादृच्छिक रूप से (uniformly at random) खींचें और इन बिंदुओं पर लक्ष्य फलन $f$ का मूल्यांकन करें।
2. घनत्व अनुमान (Density Estimation): एकत्रित किए गए $N$ नमूनों के आधार पर लक्ष्य घनत्व $\hat{f}$ का अनुमान लगाने के लिए एक कर्नेल रिग्रेशन विधि (विशेष रूप से एक प्रोडक्ट कर्नेल, जैसे कि गौसियन कर्नेल) का उपयोग करें।
3. प्लायबल प्रपोजल निर्माण: एक "प्लायबल" प्रस्ताव $b_{g^\star}$ का निर्माण करें जो एक सटीक ऊपरी सीमा के रूप में कार्य करता है। यह $\hat{f}$ में एक समान त्रुटि सीमा $r_N$ (कर्नेल अनुमानकों के सैद्धांतिक अभिसरण दरों से प्राप्त) जोड़कर किया जाता है। यह सुनिश्चित करता है कि प्रस्ताव $g$ उच्च संभाव्यता के साथ $M_g \geq f$ को संतुष्ट करता है।

मुख्य गणितीय घटक:

• कर्नेल अनुमानक (Kernel Estimator): $f$ को इंटरपोलेट करने के लिए एक कर्नेल $K$ का उपयोग करता है।
• समान सीमा (Uniform Bound): यह विधि घनत्व अनुमान के त्रुटि सीमा पर एक नियंत्रण प्रदान करने के लिए हालिया प्रगति का लाभ उठाती है जो उच्च संभाव्यता ($1-\delta$) के साथ पूरे डोमेन में समान रूप से लागू होती है।
• जटिलता अनुकूलन (Complexity Optimization): अनुमान की लागत और बाद के रिजेक्शन सैंपलिंग चरण की दक्षता के बीच संतुलन बनाने के लिए प्रारंभिक नमूनों की संख्या $N$ को अनुकूलित किया जाता है।

3. मुख्य योगदान

• गैर-पैरामीट्रिक अनुकूलन क्षमता (Non-parametric Adaptivity): ARS के विपरीत, PRS लॉग-कॉन्केविटी या एकलमोडिटी की धारणा नहीं बनाता है; इसे केवल हल्की स्मूथनेस गुणों (Hölder continuity) की आवश्यकता होती है।
• सैद्धांतिक गारंटी: पेपर स्वीकृत नमूनों की संख्या पर एक औपचारिक गारंटी प्रदान करता है। स्पर्शोन्मुखी रूप से (Asymptotically), $n$ कॉल्स के बजट के लिए, प्राप्त किए गए i.i.d. नमूनों की संख्या $n - o(n)$ है, जिसका अर्थ है कि जैसे-जैसे $n$ बढ़ता है, रिजेक्शन दर नगण्य हो जाती है।
• परफेक्ट सैंपलिंग: MCMC-आधारित अनुकूली विधियों के विपरीत, PRS उच्च संभाव्यता के साथ वास्तविक i.i.d. नमूने उत्पन्न करता है।
• उच्च-आयामी विस्तार: लेखक उत्तल अनुकूलन (convex optimization) का उपयोग करके एक स्थानीयकरण रणनीति प्रस्तावित करते हैं। यदि घनत्व अपने उच्च-द्रव्यमान समर्थन (high-mass support) के बाहर उत्तल है, तो वे दिखाते हैं कि "प्रारंभिक नमूनाकरण" चरण को आयाम $d$ के साथ घातीय (exponentially) के बजाय बहुपद (polynomially) के रूप में स्केल किया जा सकता है।

4. परिणाम

लेखकों ने SRS और $A^\star$ सैंपलिंग के विरुद्ध PRS का तुलनात्मक संख्यात्मक प्रयोग किया:

• पीकीनेस स्केलिंग (Peakiness Scaling): जैसे-जैसे लक्ष्य वितरण अधिक "पीकी" (नमूना लेने में कठिन) होता जाता है, PRS दोनों SRS और $A^\star$ सैंपलिंग की तुलना में उच्च स्वीकृति दर बनाए रखता है।
• 2D उदाहरण: एक जटिल 2D त्रिकोणमितीय घनत्व में, PRS ने $A^\star$ सैंपलिंग के समकक्ष स्वीकृति दर प्राप्त की, लेकिन बिना $f(x) \propto \exp(\phi(x))$ अपघटन की आवश्यकता के।
• क्लटर समस्या (Clutter Problem): एक द्वि-मोडल (bimodal), पीकी पोस्टीरियर वितरण (क्लटर समस्या) में, $A^\star$ सैंपलिंग थोड़ा बेहतर प्रदर्शन करती है, लेकिन PRS फिर भी बेसलाइन SRS से काफी बेहतर प्रदर्शन करता है।

5. महत्व

PRS गैर-पैरामीट्रिक घनत्व अनुमान और रिजेक्शन सैंपलिंग के बीच की खाई को पाटकर सैंपलिंग सिद्धांत में एक महत्वपूर्ण प्रगति का प्रतिनिधित्व करता है। इसका प्राथमिक महत्व इसके दक्षता-से-सूचना अनुपात (efficiency-to-information ratio) में निहित है: यह बिना किसी संरचनात्मक धारणा (जैसे लॉग-कॉन्केविटी) या कार्यात्मक अपघटन (जैसे $A^\star$ सैंपलिंग) की आवश्यकता के, लगभग इष्टतम सैंपलिंग दक्षता (एक फलन मूल्यांकन प्रति एक नमूना के करीब) प्रदान करता है। यह इसे जटिल, निम्न-से-मध्यम आयामी घनत्व सैंपलिंग के लिए एक मजबूत, "प्लग-एंड-प्ले" उपकरण बनाता है।