📊 statistics

ShaplEIG: Bayesian Experimental Design for Shapley Value Estimation

यह शोध पत्र ShaplEIG को प्रस्तुत करता है, जो एक बेयसियन प्रायोगिक डिजाइन पद्धति है जो गठबंधन (coalitions) को अनुकूल रूप से चुनने के लिए गॉसियन प्रोसेस सरोगेट्स और क्लोज्ड-फॉर्म अपेक्षित सूचना लाभ (expected information gain) का लाभ उठाती है, जिससे महंगी, कम-बजट वाली स्थितियों में शापली वैल्यू (Shapley value) अनुमान की नमूना दक्षता (sample efficiency) में महत्वपूर्ण सुधार होता है।

मूल लेखक: David Rundel, Fabian Fumagalli, Maximilian Muschalik, Bernd Bischl, Matthias Feurer

प्रकाशित 2026-06-02

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: David Rundel, Fabian Fumagalli, Maximilian Muschalik, Bernd Bischl, Matthias Feurer

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

बड़ी समस्या: "बहुत अधिक विकल्प" की दुविधा

कल्पना कीजिए कि आप यह पता लगाने की कोशिश कर रहे हैं कि एक टीम की जीत में प्रत्येक खिलाड़ी का कितना योगदान था। मशीन लर्निंग की दुनिया में, ये "खिलाड़ी" फीचर्स (जैसे किसी मरीज की उम्र या घर का क्षेत्रफल) या डेटा पॉइंट्स होते हैं। इस योगदान को मापने के लिए उपयोग किए जाने वाले गणितीय उपकरण को Shapley Value कहा जाता है।

सटीक Shapley Value की गणना करने के लिए, आपको खिलाड़ियों के हर संभावित संयोजन (combination) का परीक्षण करना होगा।

यदि आपके पास 10 खिलाड़ी हैं, तो 1,024 संयोजन हैं।
यदि आपके 20 खिलाड़ी हैं, तो 10 लाख से अधिक संयोजन हैं।
यदि आपके पास 50 खिलाड़ी हैं, तो संख्या इतनी विशाल है कि यह ब्रह्मांड के परमाणुओं की संख्या से भी अधिक है।

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

वर्तमान समाधान: अनुमान लगाना और जांचना

चूंकि हम सब कुछ टेस्ट नहीं कर सकते, इसलिए वर्तमान तरीके आमतौर पर या तो रैंडम तरीके से संयोजनों को चुनते हैं या एक निश्चित पैटर्न का पालन करते हैं (जैसे "हमेशा पहले छोटे समूहों का परीक्षण करें")।

उपमा: कल्पना कीजिए कि आप संदिग्धों का इंटरव्यू लेकर अपराध सुलझाने की कोशिश कर रहे हैं। वर्तमान तरीके उन संदिग्धों का इंटरव्यू लेने जैसे हैं जो वर्णमाला के क्रम (alphabetical order) में हैं या टोपी से नाम निकालकर चुने गए हैं। आप गलत लोगों का इंटरव्यू ले सकते हैं जबकि उस महत्वपूर्ण सुराग को मिस कर सकते हैं जो उस एक व्यक्ति के पास है जिससे आपने अभी तक बात नहीं की है।

नया समाधान: ShaplEIG (स्मार्ट डिटेक्टिव)

लेखकों ने ShaplEIG नामक एक नई विधि प्रस्तावित की है। रैंडम अनुमान लगाने के बजाय, यह विधि Bayesian Experimental Design पर आधारित "स्मार्ट डिटेक्टिव" दृष्टिकोण का उपयोग करती है।

यह कैसे काम करता है, चरण-दर-चरण यहाँ दिया गया है:

1. "सरोगेट" मैप (क्रिस्टल बॉल)

चूंकि हर संयोजन का परीक्षण करना बहुत महंगा है, इसलिए ShaplEIG खेल का एक surrogate model (एक सरलीकृत, तेज़ सन्निकटन/approximation) बनाता है।

उपमा: कल्पना कीजिए कि आप एक विशाल, धुंधले पर्वत श्रृंखला का मानचित्र बनाने की कोशिश कर रहे हैं। हर इंच पैदल चलने के बजाय, आप कुछ शुरुआती यात्राओं के आधार पर इलाके का एक छोटा, तेज़ 3D मॉडल बनाते हैं। यह मॉडल एकदम सटीक नहीं है, लेकिन यह आपको चोटियों और घाटियों का एक अच्छा अंदाजा देता है।

2. "एक्सपेक्टेड इंफॉर्मेशन गेन" (कंपास)

यही इस पेपर का मुख्य जादू है। यह विधि पूछती है: "अगला कौन सा एकल संयोजन (combination) मुझे अंतिम उत्तर के बारे में सबसे अधिक जानकारी देगा?"

उपमा: एक सामान्य जासूस पूछेगा, "कौन संदिग्ध लग रहा है?" (Uncertainty Sampling)। ShaplEIG पूछता है, "यदि मैं इस विशिष्ट व्यक्ति का इंटरव्यू लेता हूँ, तो इससे बाकी सभी के लिए पूरे रहस्य में कितनी स्पष्टता आएगी?"
यह Expected Information Gain (EIG) की गणना करता है। यह अपने द्वारा बनाए गए 3D मैप को देखता है और कहता है, "इस विशिष्ट गठबंधन (coalition) का परीक्षण करने से सभी खिलाड़ियों के अंतिम स्कोर के बारे में हमारी अनिश्चितता सबसे अधिक कम हो जाएगी।"

3. "क्लोज्ड-फॉर्म" शॉर्टकट (सुपरपावर)

आमतौर पर, "हमें कितनी जानकारी मिलेगी" यह गणना करना अविश्वसनीय रूप से कठिन और धीमा होता है (जैसे कि हिलते हुए टुकड़ों के साथ पहेली सुलझाने की कोशिश करना)।

पेपर का ब्रेकथ्रू: लेखकों ने खोजा कि चूंकि Shapley Values एक विशिष्ट रैखिक (linear) तरीके से गणना किए जाते हैं, इसलिए वे सूचना लाभ (information gain) की गणना करने के लिए एक गणितीय शॉर्टकट ("closed-form expression") लिख सकते हैं।
उपमा: आमतौर पर, यह जानने के लिए कि एक नया सुराग कितना मदद करता है, आपको पूरी जांच को फिर से सिम्युलेट करना होगा। ShaplEIG ने एक ऐसा फॉर्मूला खोजा जो आपको पलक झपकते ही उत्तर दे देता है, जैसे एक GPS जो पूरी दुनिया का दोबारा नक्शा बनाए बिना तुरंत सबसे अच्छा रास्ता बता देता है।

4. "पॉलीनोमियल" स्पीड-अप (एलिवेटर)

इस शॉर्टकट के बावजूद, लाखों संयोजनों के लिए इसकी गणना करना अभी भी बहुत धीमा होगा।

पेपर का ब्रेकथ्रू: उन्होंने Elementary Symmetric Polynomials (एक प्रकार का गणितीय पैटर्न) का उपयोग करते हुए एक चतुर गणितीय ट्रिक का उपयोग किया, जिसने एक ऐसी गणना को जो तेजी से (exponentially: 1, 10, 100, 1000...) बढ़ती है, उसे पॉलीनोमियल (polynomially: 1, 10, 100, 1000... लेकिन बहुत धीमी गति से) में बदल दिया।
उपमा: पहाड़ पर एक-एक कदम चढ़ने (exponential) के बजाय, उन्होंने एक लिफ्ट (polynomial) बनाई जो आपको बहुत बड़े पहाड़ों पर भी जल्दी पहुँचा देती है।

परिणाम: बेहतर उत्तर, कम काम

लेखकों ने विभिन्न कठिन कार्यों पर ShaplEIG का परीक्षण किया, जैसे कि:

यह पता लगाना कि मेडिकल डायग्नोसिस मॉडल के लिए कौन से फीचर्स सबसे महत्वपूर्ण हैं।
एक डेटासेट में विशिष्ट डेटा पॉइंट्स का मूल्य निर्धारित करना।
यह समझना कि कौन सी सेटिंग्स (hyperparameters) एक AI मॉडल को सबसे अच्छा काम करने में मदद करती हैं।

परिणाम:
लगभग हर परीक्षण में, ShaplEIG ने मौजूदा सर्वोत्तम तरीकों की तुलना में तेजी से और कम महंगे परीक्षणों के साथ सही उत्तर दिए।

उपमा: यदि अन्य तरीकों को 90% सटीकता के साथ मामला सुलझाने के लिए 400 संदिग्धों का इंटरव्यू लेने की आवश्यकता थी, तो ShapleIG अक्सर केवल 200 इंटरव्यू के साथ, और उच्च सटीकता के साथ मामले को सुलझा लेता है।

सारांश

ShaplEIG एक स्मार्ट तरीका है यह अनुमान लगाने का कि एक AI मॉडल के निर्णयों में प्रत्येक भाग का कितना योगदान है। रैंडम संयोजनों का अंधाधुंध परीक्षण करने के बजाय, यह सबसे अधिक जानकारी देने वाले अगले परीक्षण को चुनने के लिए एक गणितीय "कंपास" का उपयोग करता है। एक चतुर गणितीय शॉर्टकट का उपयोग करके, यह बहुत तेज़ी से काम करता है, जिससे महंगे AI मॉडल के साथ काम करते समय समय और पैसे की बचत होती है।

तकनीकी सारांश: ShaplEIG

समस्या विवरण (Problem Statement)

शापली मान (Shapley values - SVs) व्याख्यात्मक मशीन लर्निंग में एक सिद्धांतवादी एट्रिब्यूशन माप के रूप में कार्य करते हैं, फिर भी उनकी सटीक गणना अक्सर कठिन (intractable) होती है। गणना का बोझ दो कारकों से उत्पन्न होता है: खिलाड़ियों की संख्या $p$ के साथ गठबंधन (coalitions) की घातांकीय वृद्धि ( $2^p$ ), और प्रत्येक गठबंधन के लिए वैल्यू फंक्शन $\nu$ के मूल्यांकन की उच्च लागत। रिट्रेनिंग-आधारित फीचर इम्पोर्टेंस, डेटा वैल्यूएशन और हाइपरपैटरमीटर इम्पोर्टेंस जैसे अनुप्रयोगों में, वैल्यू फंक्शन मूल्यांकन में पूर्ण मॉडल रिट्रेनिंग या महंगी इंफरेंस शामिल हो सकती है, जो मूल्यांकन बजट को गंभीर रूप से सीमित करती है।

मौजूदा सन्निकटन (approximation) विधियाँ, जिनमें मोंटे कार्लो सैंपलिंग और सरोगेट-आधारित दृष्टिकोण (जैसे, Kernel SHAP, Regression MSR) शामिल हैं, आमतौर पर निश्चित, गैर-अनुकूली (non-adaptive) सैंपलिंग वितरणों पर निर्भर करती हैं। यह प्रश्न उठता है कि क्या पिछले अवलोकनों के आधार पर मूल्यांकन के लिए गठबंधनों को अनुकूल रूप से (adaptively) चुनकर सन्निकटन सटीकता में सुधार किया जा सकता है, विशेष रूप से कम-बजट वाले परिदृश्यों में। हालांकि बेयसियन एक्सपेरिमेंटल डिजाइन (BED) अपेक्षित सूचना लाभ (Expected Information Gain - EIG) का उपयोग करके अनुक्रमिक डिजाइन के लिए एक ढांचा प्रदान करता है, लेकिन क्लोज्ड-फॉर्म EIG अभिव्यक्तियों की कमी और उच्च-आयामी डिस्क्रीट स्पेस के लिए EIG का अनुमान लगाने की कम्प्यूटेशनल जटिलता के कारण SV अनुमान में इसकी स्वीकार्यता सीमित रही है।

कार्यप्रणाली (Methodology)

लेखक ShaplEIG प्रस्तावित करते हैं, जो एक बेयसियन एक्सपेरिमेंटल डिजाइन दृष्टिकोण है जो शापली मानों के संबंध में सूचना लाभ को अधिकतम करने के लिए गठबंधनों को अनुकूल रूप से चुनता है।

1. हैमिंग कर्नेल के साथ गॉसियन प्रोसेस सरोगेट (Gaussian Process Surrogate with Hamming Kernel)

ShaplEIG, वैल्यू फंक्शन $\nu$ को एक गॉसियन प्रोसेस (GP) सरोगेट का उपयोग करके मॉडल करता है। गठबंधनों के बाइनरी इनपुट स्पेस (जो इंडिकेटर वेक्टर्स $z \in \{0, 1\}^p$ के रूप में दर्शाए जाते हैं) को संभालने के लिए, यह विधि एक हैमिंग डिस्टेंस कर्नेल का उपयोग करती है। यह कर्नेल भारित हैमिंग दूरियों के आधार पर गठबंधनों के बीच समानता को मापता है, जिसमें सीखने योग्य लेंथस्केल हाइपरपैरामीटर $\xi$ होते हैं। GP, देखे गए मूल्यांकनों के डेटासेट $D_t$ के आधार पर, सभी $2^p$ गठबंधनों में वैल्यू फंक्शन पर एक पोस्टीरियर वितरण प्रदान करता है।

2. रैखिकता के माध्यम से सुसंगत SV अनुमान (Consistent SV Estimation via Linearity)

एक प्रमुख सैद्धांतिक अंतर्दृष्टि वैल्यू फंक्शन के सापेक्ष शापली मानों की रैखिकता है। SVs $\phi$ को वैल्यू फंक्शन वेक्टर $\nu$ के एक रैखिक रूपांतरण के रूप में व्यक्त किया जा सकता है: $\phi = A\nu$ , जहाँ $A$ शापली फॉर्मूला से प्राप्त एक ज्ञात मैट्रिक्स है। फलस्वरूप, GP सरोगेट के तहत, SVs पर पोस्टीरियर वितरण भी गॉसियन होता है और क्लोज्ड-फॉर्म में उपलब्ध होता है:
$\phi | D_t \sim \mathcal{N}_p(A\mu_{\nu|D_t}, A\Sigma_{\nu|D_t}A^\top)$
लेखक पोस्टीरियर मीन, $\hat{\phi} = A\mu_{\nu|D_t}$ से SV अनुमान निकालते हैं। महत्वपूर्ण रूप से, नॉइलेस (या लगभग नॉइलेस) GPs के लिए, यह एस्टिमेटर सुसंगत (consistent) है: यदि सभी $2^p$ गठबंधनों का मूल्यांकन किया जाता है, तो अनुमान सटीक शापली मानों की ओर अभिसरित (converge) होते हैं।

3. क्लोज्ड-फॉर्म अपेक्षित सूचना लाभ (Closed-Form Expected Information Gain - EIG)

मुख्य योगदान एक उम्मीदवार गठबंधन $z^{(i)}$ के संबंध में SVs के लिए EIG की एक क्लोज्ड-फॉर्म अभिव्यक्ति को व्युत्पन्न करना है। अनुक्रमिक चयन को एक बेयसियन लीनियर इनवर्स प्रॉब्लम के रूप में फ्रेम करके, यह दिखाया गया है कि EIG केवल SVs के पोस्टीरियर कोवेरिएंस पर निर्भर करता है:
$\text{EIG}^{(t)}_{\phi}(z^{(i)}) \propto -\log \det \left( A \Sigma_{\nu|\nu'(z^{(i)}), D_t} A^\top \right) + C$
यह उन नेस्टेड अपेक्षाओं (nested expectations) से बचता है जो आमतौर पर BED में आवश्यक होते हैं, क्योंकि EIG केवल प्रयोगात्मक डिजाइन (चुने गए गठबंधन) पर निर्भर करता है न कि विशिष्ट परिणाम $y(x)$ पर।

4. एलिमेंट्री सिमेट्रिक पॉलिनोमिअल्स के माध्यम से कुशल गणना (Efficient Computation via Elementary Symmetric Polynomials)

EIG की प्रत्यक्ष गणना $2^p \times 2^p$ आकार के मैट्रिसेस पर ऑपरेशन्स शामिल करती है, जिससे घातांकीय जटिलता (exponential complexity) आती है। लेखक एक कुशल गणना योजना प्रस्तावित करते हैं जो हैमिंग कर्नेल की मल्टीप्लिकेटिव संरचना का लाभ उठाकर जटिलता को पॉलीनोमियल समय ( $O(p^4 + t^3)$ ) तक कम कर देती है।

EIG के लिए आवश्यक पद (विशेष रूप से $A\Sigma_{\nu|D_t}e_i$ और $A\Sigma_{\nu|D_t}A^\top$ ) कर्नेल मूल्यांकनों के भारित योग के रूप में पुनर्गठित किए जाते हैं।
इन योगों को स्केल्ड एलिमेंट्री सिमेट्रिक पॉलिनोमिअल्स (ESPs) के रूप में पहचाना गया है।
डायनेमिक प्रोग्रामिंग और प्रीफिक्स/सफिक्स टेबल्स का कुशलतापूर्वक उपयोग करके इन पॉलिनोमिअल्स की गणना करके, यह विधि सभी गठबंधनों की स्पष्ट गणना (explicit enumeration) से बचती है।

5. एल्गोरिदम (Algorithm)

एल्गोरिदम लालची (greedily) तरीके से आगे बढ़ता है:

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

मुख्य योगदान (Key Contributions)

ShaplEIG फ्रेमवर्क: SV अनुमान के लिए एक अभिनव, BED-आधारित पद्धति का परिचय जो हैमिंग कर्नेल के साथ GP सरोगेट का उपयोग करती है और EIG के आधार पर गठबंधनों को अनुकूल रूप से चुनती है।
क्लोज्ड-फॉर्म EIG: यह प्रदर्शन कि एक GP सरोगेट के तहत, शापली मानों के लिए EIG एक क्लोज्ड-फॉर्म अभिव्यक्ति स्वीकार करता है, जो वैल्यू फंक्शन में SVs की रैखिकता का लाभ उठाता है।
पॉलीनोमियल जटिलता: एक कुशल गणना योजना का प्रस्ताव जो एलिमेंट्री सिमेट्रिक पॉलिनोमिअल्स के माध्यम से EIG की जटिलता को खिलाड़ियों की संख्या ( $p$ ) में घातांकीय से पॉलीनोमियल में बदल देता है।
सुसंगत अनुमान (Consistent Estimation): एक सुसंगत SV एस्टिमेटर प्रदान करना जो सभी गठबंधनों के मूल्यांकन होने पर सटीक मानों की ओर अभिसरित होता है, जो कुछ ट्री-आधारित सरोगेट विधियों के विपरीत है जिन्हें अतिरिक्त समायोजन चरणों की आवश्यकता होती है।

प्रयोगात्मक परिणाम (Experimental Results)

लेखक विविध, महंगी अनुप्रयोगों में ShaplEIG का मूल्यांकन करते हैं जिनमें छोटे से मध्यम आकार के गेम्स ( $8 \le p \le 101$ ) शामिल हैं:

कार्य (Tasks): ग्लोबल फीचर इम्पोर्टेंस (TabPFN), डेटा वैल्यूएशन (Random Forest, Gradient Boosting), हाइपरपैरामीटर इम्पोर्टेंस (XGBoost, LCBench), और लोकल एक्सप्लेनेशन (ResNet, ViT, Random Forest)।
बेसलाइन्स (Baselines): Kernel SHAP, Leverage SHAP, Permutation Sampling, और स्टेट-ऑफ-द-आर्ट रिग्रेशन MSR (XGBoost के साथ युग्मित) के विरुद्ध तुलना।
एब्लेशन (Ablations): समान GP सरोगेट लेकिन विभिन्न चयन रणनीतियों (Random, Uncertainty Sampling, Leverage Score Sampling) का उपयोग करने वाले वेरिएंट्स के विरुद्ध तुलना।

निष्कर्ष:

सैंपल दक्षता (Sample Efficiency): ShaplEIG अधिकांश कार्यों में लो-बजट रिजीम में लगातार सबसे अच्छी समग्र सटीकता (न्यूनतम मीन स्क्वेर्ड एरर) प्राप्त करता है। यह अक्सर प्रतिस्पर्धियों पर पूरी तरह से हावी रहता है, विशेष रूप से एसिमेट्रिक गेम्स में जहाँ प्लेयर इंटरैक्शन नॉन-यूनिफॉर्म होते हैं।
एब्लेशन अंतर्दृष्टि: मजबूत प्रदर्शन मुख्य रूप से EIG-आधारित चयन रणनीति के कारण है, न कि केवल GP सरोगेट के उपयोग के कारण। अनसर्टेनिटी सैंपलिंग (US) अक्सर रैंडम सैंपलिंग से भी खराब प्रदर्शन करती है, जो यह दर्शाता है कि मार्जिनल वेरिएंस को अधिकतम करना अनिवार्य रूप से रैखिक रूप से रूपांतरित SVs के बारे में सूचना को अधिकतम करने के बराबर नहीं है।
स्केलेबिलिटी (Scalability): बड़े गेम्स ( $p > 16$ ) के लिए, यह विधि प्रभावी रहती है भले ही हाइपरपैरामीटर रिफिटिंग को हर इटरेशन के बजाय एक शेड्यूल पर किया जाए।
कम्प्यूटेशनल लागत: जबकि EIG गणना कुशल है (सेकंड में), $p \approx 100$ के लिए $p$ तक हाइपरपैरामीटर फिटिंग एक बाधा बन सकती है (प्रति इटरेशन 25 मिनट तक)। लेखक नोट करते हैं कि ShaplEIG वास्तव में महंगी वैल्यू फंक्शन वाली स्थितियों के लिए सबसे उपयुक्त है, जो इस ओवरहेड को उचित ठहराता है।

महत्व और दावे (Significance and Claims)

पेपर का दावा है कि ShaplEIG, महंगी गेम्स के लिए SV अनुमान में सैंपल दक्षता में सुधार के लिए एक सिद्धांतवादी ढांचा प्रदान करता है। एक क्लोज्ड-फॉर्म EIG और एक कुशल पॉलीनोमियल-टाइम गणना योजना को व्युत्पन्न करके, लेखक इस डोमेन में बेयसियन एक्सपेरिमेंटल डिजाइन को लागू करने की प्राथमिक बाधाओं को दूर करते हैं।

लेखक विनम्रतापूर्वक कहते हैं कि हालांकि इसमें बार-बार GP ऑप्टिमाइजेशन से कम्प्यूटेशनल ओवरहेड होता है, लेकिन यह कम बजट वाले परिदृश्यों में अनुमान सटीकता में पर्याप्त लाभ प्रदान करता है। वे स्वीकार करते हैं कि बहुत बड़े गेम्स या कम महंगी वैल्यू फंक्शन के लिए, यह ओवरहेड निषेधात्मक हो सकता है, जो भविष्य के काम के लिए और अधिक कम्प्यूटेशनल सुधारों पर ध्यान केंद्रित करने का सुझाव देता है ताकि इसकी प्रयोज्यता को बढ़ाया जा सके। यह कार्य सभी परिदृश्यों के लिए SV अनुमान को हल करने का दावा नहीं करता है, बल्कि विशेष रूप से महंगी वैल्यू फंक्शन वाले रिजीम को लक्षित करता है जहाँ अनुकूल चयन महत्वपूर्ण है।