An Odd Estimator for Shapley Values

तकनीकी सारांश: शापली मानों के लिए एक विचित्र अनुमानक (An Odd Estimator for Shapley Values)

समस्या विवरण

शापली मान (Shapley value) मशीन लर्निंग में एट्रिब्यूशन के लिए एक मानक ढांचा है, जिसका उपयोग फीचर महत्व (feature importance), डेटा मूल्यांकन और कारण संबंधी अनुमान (causal inference) के लिए किया जाता है। हालाँकि, इसका सटीक गणना करना आम तौर पर कठिन है क्योंकि इसके मूल्यांकन के लिए घातीय संख्या में गठबंधन (coalitions) ($2^d$) की आवश्यकता होती है। जबकि सन्निकटन विधियाँ (approximation methods) मौजूद हैं, सबसे प्रभावी अनुमानक अक्सर "युग्मित नमूनाकरण" (paired sampling) — यानी एक गठबंधन $S$ और उसके पूरक $S^c$ का नमूना लेना — पर निर्भर करते हैं, जो कि एक ह्यूरिस्टिक है जो अनुभवजन्य रूप से सटीकता में सुधार करता है लेकिन इसमें उच्च-क्रम के इंटरैक्शन (higher-order interactions) के संबंध में एक कठोर सैद्धांतिक औचित्य का अभाव है। इसके अलावा, मौजूदा उच्च-क्रम बहुपद प्रतिगमन (higher-order polynomial regression) विधियाँ (जैसे PolySHAP) एक स्केलेबिलिटी बाधा का सामना करती हैं जहाँ कम्प्यूटेशनल लागत बहुपद आधार के आकार के साथ द्विघाती रूप से बढ़ती है, जो उच्च-आयामी सेटिंग्स में उनके अनुप्रयोग को सीमित करती है।

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

लेखक OddSHAP का प्रस्ताव करते हैं, जो एक नवीन अनुमानक है जो शापली मान के एक मौलिक संरचनात्मक गुण का लाभ उठाता है: यह मान फलन (value function) $f$ के विषम घटक (odd component) पर विशेष रूप से निर्भर करता है।

सैद्धांतिक आधार

1. विषम-सम विच्छेदन (Odd-Even Decomposition): किसी भी सेट फलन $f$ को एक विषम घटक ($f_{odd}$) और एक सम घटक ($f_{even}$) में अद्वितीय रूप से विभाजित किया जा सकता है, जहाँ $f_{odd}(S) = -f_{odd}(S^c)$ और $f_{even}(S) = f_{even}(S^c)$।
2. शापली मान गुण: लेखक सिद्ध करते हैं कि सभी खिलाड़ियों $i$ के लिए $\phi_i(f) = \phi_i(f_{odd})$ है। सम घटक शापली मान में शून्य योगदान देता है।
3. युग्मित नमूनाकरण का तंत्र: यह शोध पत्र युग्मित नमूनाकरण के लिए पहला सामान्य सैद्धांतिक औचित्य प्रदान करता है। सममित भारों (symmetric weights) के साथ जोड़ों $(S, S^c)$ का नमूना लेकर, भारित न्यूनतम वर्ग प्रतिगमन (weighted least squares regression) समस्या स्वतंत्र अनुकूलन समस्याओं के लिए ऑर्थोगोनलाइज (विघटित) हो जाती है जो विषम और सम घटकों के लिए हैं। चूंकि सम घटक अप्रासंगिक है, इसलिए युग्मित नमूनाकरण प्रभावी रूप से उस सिग्नल को अलग कर देता है जो शापली मानों के लिए आवश्यक है। यह इस अनुमान को हल करता है कि एक क्रम-$k$ फिट (विषम $k$ के लिए) एक क्रम-$(k+1)$ फिट के बराबर है।

एल्गोरिदम डिज़ाइन: OddSHAP

इस अंतर्दृष्टि का लाभ उठाने और सभी उच्च-क्रम पदों के संयोजन विस्फोट से बचने के लिए, OddSHAP यूनैमिटी बेसिस (unanimity basis) के बजाय फूरियर बेसिस (Fourier basis) में कार्य करता है।

• फूरियर बेसिस का लाभ: फूर}}{ier बेसिस में, एक बेसिस फंक्शन $\chi_T$ विषम होता है यदि और केवल यदि कार्डिनैलिटी $|T|$ विषम हो। यह यूनैमिटी बेसिस के विपरीत, विषम और सम पदों के बीच एक स्पष्ट अलगाव की अनुमति देता है।
• दो-चरणीय प्रक्रिया:
  1. इंटरैक्शन स्क्रीनिंग: नमूना लिए गए गठबंधनों पर एक ग्रेडिएंट बूस्टेड ट्री (GBT) प्रॉक्सी मॉडल फिट किया जाता है। ProxySPEX जैसी विधि का उपयोग करके, एल्गोरिदम उच्च-प्रभाव वाले विषम-क्रम (odd-order) फूरियर गुणांकों के एक विरल (sparse) सेट को निकालता है। यह सभी संभावित इंटरैक्शन को फिट करने की आवश्यकता को समाप्त करता है।
  2. विषम प्रतिगमन (Odd Regression): एक भारित न्यूनतम वर्ग प्रतिगमन केवल चयनित विषम-क्रम फूरियर पदों (प्लस रैखिक पदों) पर किया जाता है, जिसे खाली और पूर्ण सेटों पर मान फलन से मेल खाने के लिए प्रतिबंधित किया गया है।
• दक्षता: चुनिते विषम उपस्थान (odd subspace) पर प्रतिगमन को सीमित करके और एक प्रॉक्सी का उपयोग करके पदों को चुनने के माध्यम से, OddSHAP नमूना बजट के सापेक्ष बहुपद समय जटिलता प्राप्त करता है, जिससे यह $O(d^k)$ स्केलिंग को दरकिनार कर देता है जो निश्चित-क्रम बहुपद विधियों की विशेषता है।

मुख्य योगदान

1. युग्मित नमूनाकरण का सैद्धांतिक एकीकरण: यह शोध पत्र सिद्ध करता है कि युग्मित नमूनाकरण आंतरिक रूप से प्रतिगमन उद्देश्य को विषम और सम घटकों में विघटित करता है, जो इसके अनुभवजन्य सफलता के लिए एक कठोर स्पष्टीकरण प्रदान करता है और पिछले निष्कर्षों को सामान्य बनाता है जो निम्न-क्रम इंटरैक्शन तक सीमित थे।
2. OddSHAP अनुमानक: यह एक सुसंगत अनुमानक है जो केवल विषम-क्रम फूरियर बेसिस फंक्शन्स के विरल चयन (प्लस रैखिक टर्म्स) पर बहुपद प्रतिगमन करता है। यह अप्रासंगिक सम घटकों को फ़िल्टर करता है और उच्च-प्रभाव वाले इंटरैक्शन को प्रॉक्सी मॉडल के माध्यम से पहचानता है।
3. स्टेट-ऑफ-द-आर्ट प्रदर्शन: व्यापक बेंचमार्क प्रदर्शित करते हैं कि OddSHAP मौजूदा विधियों (RegressionMSR, LeverageSHAP, और PolySHAP सहित) की तुलना में बड़े नमूना बजट के तहत, विशेष रूप से उच्च-आयामी सेटिंग्स में, बेहतर अनुमान सटीकता प्राप्त करता है।

प्रयोगात्मक परिणाम

लेखकों ने $d=14$ (DistilBERT) से $d=101$ (Crime dataset) तक आठ मान फलनों पर OddSHAP का मूल्यांकन किया, जिसमें डीप लर्निंग (इमेज और टेक्स्ट) और टैबुलर डोमेन शामिल हैं।

• सटीकता: OddSHAP ने लगातार सबसे कम मीन स्क्वेर्ड एरर (MSE) और बेंचमार्क में सर्वश्रेष्ठ औसत रैंक प्राप्त की, विशेष रूप से जब नमूना बजट $m$ इंटरैक्शन का पता लगाने के लिए पर्याप्त था ($m > \eta \cdot d$)।
• FFD के साथ तुलना: OddSHAP ने डीप लर्निंग आर्किटेक्चर (ViT, DistilBERT) पर FFD-RD (Fixed-Budget Fractional Factorial Design) को पछाड़ दिया, जहाँ उच्च-क्रम के इंटरैक्शन महत्वपूर्ण होते हैं। इसके विपरीत, FFD-RD ट्री-आधारित टैबुलर डेटासेट पर थोड़ा बेहतर प्रदर्शन करता है जहाँ उच्च-क्रम के इंटरैक्शन तेजी से घटते हैं, जो डोमेन-विशिष्ट ट्रेड-ऑफ को प्रमाणित करता है।
• एब्लेशन अध्ययन (Ablation Studies):
  • युग्मित बनाम गैर-युग्मित: युग्मित नमूनाकरण ने लगातार गैर-युग्मित नमूनाकरण से बेहतर प्रदर्शन किया।
  • विषम बनाम सभी इंटरैक्शन: युग्मित नमूनाकरण के तहत, सम इंटरैक्शन को शामिल करने से कोई लाभ नहीं हुआ और इसने गणितीय रूप से रद्द होने वाले पदों के साथ इंटरैक्शन बजट को उपभोग करके प्रदर्शन को थोड़ा खराब कर दिया।
  • विरलता (Sparsity): एक मध्यम संख्या में विषम इंटरैक्शन को शामिल करने से (प्रतिगमन वेरिएबल फैक्टर $\eta$ द्वारा नियंत्रित) रैखिक बेसलाइन की तुलना में त्रुटि काफी कम हो गई, हालांकि बहुत अधिक इंटरैक्शन के साथ ओवरफिटिंग भी हुई।

महत्व और दावे

शोध पत्र का दावा है कि OddSHAP एक लचीला-बजट ढांचा (flexible-budget framework) प्रदान करता है जो विविध इंटरैक्शन संरचनाओं में मजबूती से अनुकूलित होता है। इसकी प्राथमिक महत्ता निम्नलिखित में निहित है:

1. एक खुले अनुमान (Open Conjecture) का समाधान: यह युग्मित नमूनाकरण क्यों काम करता है, इसके लिए मौलिक सैद्धांतिक तंत्र प्रदान करता है, जो अनुभवजन्य अवलोकन से आगे बढ़कर संरचनात्मक प्रमाण तक जाता है।
2. स्केलेबिलिटी: यह अपने निषेधात्मक कॉम्बिनेटोरियल खर्चों के बिना उच्च-क्रम सन्निकटन की अभिव्यंजक शक्ति को बनाए रखता है, क्योंकि यह मॉडल को विषम उपस्थान तक सीमित करता है।
3. मजबूती (Robustness): कठोर ट्रंकेशन धारणाओं (जैसे FFD) पर निर्भर विधियों के विपरीत, OddSHAP जटिल डीप लर्निंग डोमेन में प्रभावी रहता है जहाँ उच्च-क्रम इंटरैक्शन नगण्य नहीं हैं, जबकि स्पार्स टैबुलर डोमेन में प्रतिस्पर्धी बना रहता है।

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