तकनीकी सारांश: बिना प्रतिस्थापन के नमूनाकरण (Sampling Without Replacement) और नए बूटस्ट्रैप विचरण अनुमानकों (Bootstrap Variance Estimators) का उपयोग करके अनुमानित शापली मान (Shapley Value) अनुमान

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

शास्त्रीय कर्नेल-SHAP (KernelSHAP) ढांचा (लुंडबर्ग और ली, 2017) सभी $2^p$ संभावित उपसमुच्चयों के लिए योगदान फलन (contribution function) का मूल्यांकन करने के बजाय, गठबंधनों (coalitions) के एक उपसमूह का नमूना लेकर शापली मान अनुमान की कम्प्यूटेशनल लागत को कम करने का लक्ष्य रखता है। हालाँकि, मौजूदा कार्यान्वयन आमतौर पर प्रतिस्थापन के साथ (with replacement) गठबंधनों का नमूना लेते हैं। यह दृष्टिकोण विशिष्ट सांख्यिकीय चुनौतियाँ पेश करता है:

1. नमूनाकरण अक्षमता (Sampling Inefficiency): प्रतिस्थापन के साथ नमूना लेने से 'कूपन कलेक्टर की समस्या' (Coupon Collector's Problem) का एक भारित संस्करण उत्पन्न होता है, जहाँ जैसे-जैसे नमूने का आकार बढ़ता है, अद्वितीय गठबंधनों को प्राप्त करना कठिन होता जाता है, विशेष रूप से कम-भार वाले गठबंधनों के लिए।
2. विचरण अनुमान सीमाएँ (Variance Estimation Limitations): पारंपरिक बूटस्ट्रैप विधियाँ स्वतंत्र और समान रूप से वितरित (i.i.d.) नमूनों को मानती हैं। जब एक सीमित जनसंख्या (सभी गठबंधनों का सेट) से बिना प्रतिस्थापन के नमूना लिया जाता है, तो इस धारणा का उल्लंघन होता है। फलस्वरूप, मानक बूटस्ट्रैप तकनीकें शापली मानों के लिए गलत विचरण अनुमान दे सकती हैं, क्योंकि वे उस परिमित जनसंख्या बाधा (finite population constraint) को ध्यान में रखने में विफल रहती हैं जहाँ सैद्धांतिक रूप से विचरण शून्य हो जाना चाहिए यदि सभी गठबंधनों का मूल्यांकन किया जाए।

यह शोध पत्र इन मुद्दों को संबोधित करने के लिए एक ढांचा प्रस्तावित करता है जो बिना प्रतिस्थापन के नमूनाकरण (sampling without replacement) का उपयोग करता है और सटीक शापली मानों के विचरण का अनुमान लगाने के लिए परिमित जनसंख्या सिद्धांत (finite population theory) के अनुकूल नई बूटस्ट्रैप पद्धतियों को पेश करता है।

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

2.1 वालेनियस के वितरण (Wallenius' Distribution) के माध्यम से बिना प्रतिस्थापन के नमूनाकरण

प्रस्तावित एल्गोरिदम वालेनियस के गैर-केंद्रीय हाइपरजियोमेट्रिक वितरण (Wallenius' noncentral hypergeometric distribution) का उपयोग करके कर्नेल-SHAP प्रक्रिया को संशोधित करता है ताकि बिना प्रतिस्थापन के गठबंधनों का नमूना लिया जा सके। इस प्रक्रिया में दो मुख्य चरण शामिल हैं:

1. स्तरीकरण (Stratification): गठबंधनों को उनके द्वारा समाहित किए गए विशेषताओं (features) की संख्या (आकार) के आधार पर समूहों में विभाजित किया जाता है।
2. नमूना आकार का निर्धारण: गठबंधनों को स्टोकेस्टिक रूप से एक-एक करके नमूना लेने के बजाय, एल्गोरिदम वालेनियस के गैर-केंद्रीय हाइपरजियोमेट्रिक वितरण का उपयोग करके प्रत्येक समूह से निकाले जाने वाले अपेक्षित गठबंधनों की संख्या की गणना करता है। यह वितरण उन विषम नमूनों को मॉडल करता है जहाँ वस्तुओं का भार अलग-अलग होता है।
   • एल्गोरिदम प्रत्येक स्तर (stratum) से नमूना लेने के लिए समूहों की संख्या निर्धारित करने हेतु इस वितरण के अपेक्षित मानों का उपयोग करता है, जिन्हें निकटतम पूर्णांक तक राउंड किया जाता है।
   • एक बार संख्याएँ निर्धारित हो जाने के बाद, प्रत्येक समूह के भीतर बिना प्रतिस्थापन के गठबंधनों का नमूना लिया जाता है।
   • पेयरिंग रणनीति (Pairing Strategy): विचरण को और कम करने के लिए, यह विधि एक पेयरिंग रणनीति (क्रोसे एट अल., 2013) का उपयोग करती है। यदि एक गठबंधन $S$ का नमूना लिया जाता है, तो उसका पूरक $S^c$ भी गणना में शामिल किया जाता है, जिससे यह सुनिश्चित होता है कि युग्मित समूहों में विशेषताओं का योग स्थिर रहता है।

2.1 विचरण अनुमान के लिए बूटस्ट्रैप विधियाँ

यह शोध पत्र नए नमूनाकरण डिजाइन के तहत शापली मानों के मानक विचलन का अनुमान लगाने के लिए तीन दृष्टिकोणों का मूल्यांकन करता है:

1. अमान्य सहज विधि (Invalid Intuitive Method): सीधे भारित न्यूनतम वर्ग (weighted least squares) समस्या पर लागू एक मानक होरविट्ज़-थॉमसन (Horvitz-Thompson) विचरण अनुमानक। लेखक प्रदर्शित करते हैं कि यह अमान्य है क्योंकि यह पेयरिंग रणनीति द्वारा उत्पन्न विशिष्ट निर्भरताओं और कर्नेल-SHAP संदर्भ में $Z^T W Z$ मैट्रिक्स की संरचना को ध्यान में रखने में विफल रहता है।
2. डबलड हाफ बूटस्ट्रैप (Antal and Tillé, 2014): सीमित जनसंख्या के लिए एक ज्ञात विधि जहाँ इकाइयों को बरनौली (Bernoulli) नमूनाकरण के माध्यम से चुना जाता है, और न-चुनी इकाइयों को यादृच्छिक रूप से दो बार चुना जाता है। तुलना के लिए इस विधि को लागू किया गया है।
3. सिमेट्रिक बूटस्ट्रैप (नया योगदान): इस संदर्भ के लिए विशेष रूप से विकसित एक नवीन बूटस्ट्रैप विधि।
   • तंत्र: प्रत्येक बूटस्ट्रैप नमूने में, मूल नमूने की प्रत्येक इकाई 0, 1, या 2 बार दिखाई दे सकती है।
   • समरूपता (Symmetry): यह विधि सुनिश्चित करती है कि 0 बार दिखाई देने वाली इकाइयों की कुल संख्या 2 बार दिखाई देने वाली इकाइयों की कुल संख्या के बराबर हो।
   • प्रायिकताएँ: एक इकाई $k$ के $S_k$ बार दिखाई देने की प्रायिकताएँ इस प्रकार हैं:
     • $Pr(S_k = 0) = Pr(S_k = 2) = \frac{1}{2}(1 - \frac{n}{N})$
     • $Pr(S_k = 1) = \frac{n}{N}$
   • गुण: यह निर्माण सुनिश्चित करता है कि अपेक्षित मान $E(S_k) = 1$ और विचरण $Var(S_k) = 1 - \frac{n}{N}$ है, जो वैध विचरण अनुमान के लिए आवश्यक शर्तों (होरविट्ज़-थॉमसन निरंतरता) को पूरा करता है।
   • गैर-पूर्णांकों का प्रबंधन: जब "0" या "2" बार होने की अपेक्षित संख्या पूर्णांक नहीं होती है, तो एक बरनौली यादृच्छिक चर (Bernoulli random variable) पेश किया जाता है ताकि आसन्न पूर्णांक मानों के बीच बारी-बारी से परिवर्तन हो सके, जिससे यह सुनिश्चित होता है कि प्रक्रिया पूरी तरह से स्वचालित बनी रहे।

2.3 कम्प्यूटेशनल कार्यान्वयन

योगदान फलन $v(S)$ का अनुमान नमूने लिए गए गठबंधनों पर रिग्रेशन (regression) का उपयोग करके लगाया जाता है। कार्यान्वयन रैखिक मॉडल को कुशलतापूर्वक संभालने के लिए स्पार्स मैट्रिसेस (sparse matrices) और चोलेस्की अपघटन (Cholesky decomposition - Matrix पैकेज) का लाभ उठाता है, जो एक सिंगल कोर पर कुछ ही मिनटों के भीतर 65,000 से अधिक रैखिक मॉडल के माध्य का अनुमान लगाने में सक्षम है (एनेस, 2025)।

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

1. नमूनाकरण ढांचा: कुशल बिना प्रतिस्थापन के नमूनाकरण को सक्षम करने के लिए वालेनियस के गैर-केंद्रीय हाइपरजियोमेट्रिक वितरण को कर्नेल-SHAP ढांचे में एकीकृत करना, जो प्रतिस्थापन के साथ नमूना लेने में निहित 'कूपन कलेक्टर की समस्या' की अक्षमताओं से बचता है।
2. सिमेट्रिक बूटस्ट्रैप: बिना प्रतिस्थापन के परिमित जनसंख्या नमूनाकरण के लिए विशेष रूप से तैयार की गई एक नई, कम्प्यूटेशनल रूप से कुशल बूटस्ट्रैप विधि। यह इस संदर्भ में अनबायस्ड (unbiased) विचरण अनुमान के लिए आवश्यक मोमेंट स्थितियों (mean and variance) को पूरा करती है।
3. विचरण अनुमान विश्लेषण: एक कठोर तुलना, जो दर्शाती है कि मानक बूटस्ट्रैपिंग इस विशिष्ट डिज़ाइन के लिए अमान्य है और नई सिमेट्रिक बूटस्ट्रैप विधि मौजूदा डबल्ड हाफ बूटस्ट्रैप (Antal and Tillé, 2014) के बराबर या उससे बेहतर प्रदर्शन करती है।

4. परिणाम

"लाइफ एक्सपेक्टेंसी" (Life Expectancy) डेटासेट (कागल से) का उपयोग करके दो सिमुलेशन अध्ययन किए गए, जिसमें नई विधि की तुलना अत्याधुनिक shapr R-पैकेज (संस्करण 1.0.7) से की गई, जो प्रतिस्थापन के साथ नमूना लेता है।

• लघु सिमुलेशन अध्ययन (5 फीचर्स, 16 गठबंधन):
  • नए नमूनाकरण पद्धति ने shapr के तुलनीय मानक विचलन के साथ शापली मान अनुमान प्रस्तुत किए।
  • Antal-Tillé बूटस्ट्रैप का प्रदर्शन खराब रहा, जो अक्सर नॉन-फुल-रैंक मैट्रिसेस ($Z^T W Z$) और गलत विचरण अनुमान उत्पन्न करता है।
  • सिमेट्रिक बूटस्ट्रैप ने Antal-Tillé की तुलना में काफी बेहतर प्रदर्शन किया, हालांकि इसने कभी-कभी थोड़े "उदार" (liberal/छोटे) मानक विचलन उत्पन्न किए (ग्राउंड ट्रुथ/सभी गठबंधनों के पुन: नमूनाकरण की तुलना में)।
• लघु सिमुलेशन अध्ययन (16 फीचर्स, 402 गठबंधन):
  • सिमेट्रिक बूटस्ट्रैप और Antal-Tillé विधियों ने मानक विचलन के अविभेद्य (indistinguishable) अनुमान उत्पन्न किए।
  • दोनों नई बूटस्ट्रैप विधियों ने shapr में अंतर्निहित बूटस्ट्रैप प्रक्रिया की तुलना में थोड़ा बेहतर प्रदर्शन किया, जो कई चरों के लिए मानक विचलन को कम आंकने की प्रवृत्ति रखती थी।
  • नया नमूनाकरण एल्गोरिदम (बिना प्रतिस्थापन के) शापली मान अनुमानों की सटीकता के मामले में shapr पद्धति (प्रतिस्थापन के साथ) के समान प्रदर्शन करता है।

5. महत्व और निष्कर्ष

शोध पत्र यह निष्कर्ष निकालता है कि प्रस्तावित एल्गोरिदम, जो वालेनियस के वितरण के माध्यम से बिना प्रतिस्थापन के नमूनाकरण को नए सिमेट्रिक बूटस्ट्रैप के साथ जोड़ता है, मौजूदा कर्नेल-SHAP कार्यान्वयनों के लिए एक मजबूत विकल्प प्रदान करता है।

• प्रदर्शन: नया तरीका बिंदु अनुमानों (point estimates) के संबंध में shapr पैकेज के उन्नत कर्नेल-SHAP पद्धति के "समान" प्रदर्शन करता है।
• विचरण अनुमान: सिमेट्रिक बूटस्ट्रैप को एक "बहुत तेज़, समझने में आसान" विधि के रूप में रेखांकित किया गया है जो अच्छा प्रदर्शन करती है, विशेष रूप से बड़े सिमुलेशन अध्ययनों में। यह बिना प्रतिस्थापन के यादृच्छिक नमूनाकरण के लिए एक "गो-टू" (go-to) बूटस्ट्रैप विधि के रूप में साहित्य के अंतर को भरता है।
• सीमाएँ: लेखक विनम्रता से नोट करते हैं कि सबसे छोटे अध्ययन में, सिमेट्रिक बूटस्ट्रैप ने कभी-कभी कुछ चरों के लिए थोड़े बहुत छोटे (liberal) मानक विचलन उत्पन्न किए, हालांकि इसने लगातार सबसे बड़े मानक विचलन को कैप्चर किया।
• उपयोगिता: यह विधि उन परिदृश्यों के लिए डिज़ाइन की गई है जहाँ योगदान फलन का अनुमान रैखिक या सामान्यीकृत रैखिक मॉडल (GLM) के माध्यम से लगाया जाता है (जहाँ भविष्यवाणियाँ रूपांतरित पैमाने पर रैखिक होती हैं), जो तेज़ गणना तकनीकों का लाभ उठाती है।

यह कार्य स्थापित करता है कि शापली मान अनुमान में नमूनाकरण दक्षता में सुधार करने और वैध विचरण अनुमान प्रदान करने के लिए परिमित जनसंख्या सिद्धांत को सफलतापूर्वक लागू किया जा सकता है, जो पारंपरिक i.i.d. बूटस्ट्रैप धारणाओं की सैद्धांतिक सीमाओं को दूर करता है।