Amortized Linear-time Exact Shapley Value for Product-Kernel Methods

तकनीकी सारांश: प्रोडक्ट-कर्नेल विधियों के लिए एमोर्टाइज्ड लीनियर-टाइम सटीक शापली वैल्यू (Amortized Linear-time Exact Shapley Value)

समस्या विवरण
कर्नेल विधियों को उनकी लचीलेपन और अभिव्यंजक शक्ति के लिए व्यापक रूप से मशीन लर्निंग और सांख्यिकी में अपनाया जाता है, फिर भी उनकी "ब्लैक-बॉक्स" प्रकृति उनके उपयोग को कठिन बनाती है। जबकि शापली वैल्यू-आधारित एट्रिब्यूशन विधियाँ (जैसे, SHAP, RKHS-SHAP) व्याख्यात्मकता (explainability) के लिए एक सिद्धांतवादी ढांचा प्रदान करती हैं, सटीक शापली वैल्यू की गणना करना सामान्यतः कठिन है क्योंकि इसमें फीचर्स के उपसमुच्चयों (subsets) की संख्या घातांकीय ($2^d$) होती है। मौजूदा दृष्टिकोण अनुमानों (जैसे, मोंटे कार्लो सैंपलिंग, रिग्रेशन-आधारित एस्टिमेटर्स) पर निर्भर करते हैं जिनमें अपरिहार्य अनुमान त्रुटियां (estimation errors) होती हैं, जो आयामीता (dimensionality) के साथ बढ़ती जाती हैं। इसके अलावा, मानक वैल्यू फंक्शन को अक्सर मार्जिनल या कंडीशनल वितरणों से सैंपलिंग करने या घनत्व अनुमान (density estimation) की आवश्यकता होती है, जो अतिरिक्त कम्प्यूटेशनल बोझ और बैकग्राउंड डेटा पर निर्भरता पैदा करता है।

कार्यप्रणाली (Methodology)
यह शोध पत्र PKeX-Shapley प्रस्तुत करता है, जो एक एल्गोरिदम है जिसे प्रोडक्ट-कर्नेल विधियों (जैसे, सपोर्ट वेक्टर मशीन, कर्नेल रिज रिग्रेशन) के सभी $d$ फीचर्स के लिए सटीक शापली वैल्यू को द्विघातीय समय (quadratic time) में, यानी $O(d^2)$, या प्रति फीचर एमोर्टाइज्ड लीनियर समय में कंप्यूट करने के लिए डिज़ाइन किया गया है।

इसकी कार्यप्रणाली तीन मुख्य घटकों पर आधारित है:

1. डिस्ट्रीब्यूशन-फ्री रिमूवल ऑपरेटर (Distribution-Free Removal Operator): लेखक उन मॉडलों के उपवर्ग (subclass) पर ध्यान केंद्रित करते हैं जो प्रोडक्ट-कर्नेल का उपयोग करते हैं, जहाँ कर्नेल फंक्शन $k(x, x') = \prod_{j=1}^d k_j(x_j, x'_j)$ के रूप में विभाजित होता है। वे इस संरचना के भीतर एक स्वाभाविक 'रिमूवल ऑपरेटर' की पहचान करते हैं: फीचर $j$ को हटाने का अर्थ है उसके कर्नेल फैक्टर $k_j$ को मल्टीप्लिकेटिव आइडेंटिटी ($1$) से बदलना। यह विकल्प उत्पाद संरचना को बनाए रखता है, किसी बैकग्राउंड डिस्ट्रीब्यूशन की आवश्यकता नहीं होती, और एक पैरामीटर-फ्री वैल्यू फंक्शन को प्रेरित करता है।

   • इंटरवेंशनल या ऑब्जर्वेशनल वैल्यू फंक्शन के विपरीत, जिन्हें सैंपलिंग की आवश्यकता होती है, यह वैल्यू फंक्शन कार्यात्मक अपघटन (functional decomposition) के माध्यम से परिभाषित किया गया है।
   • एक कोएलिशन (coalition) $S$ के लिए वैल्यू फंक्शन $v_x(S) = \alpha^\top k_S(X_S, x_S) - f_\emptyset$ द्वारा दिया गया है, जहाँ $f_\emptyset$ एक स्थिरांक (constant) है जो मार्जिनल योगदानों में निरस्त हो जाता है। यह फॉर्मूलेशन बिना किसी सैंपलिंग या घनत्व अनुमान के काम करता है।

2. कार्यात्मक अपघटन (Functional Decomposition): रिमूवल ऑपरेटर का लाभ उठाते हुए, मॉडल $f(x)$ को फीचर उपसमुच्चयों द्वारा इंडेक्स किए गए घटकों के योग में अद्वितीय रूप से विघटित किया जा सकता है: $f(x) = \sum_{S \subseteq D} f_S(x_S)$। इन घटकों को सबसेट लैटिस पर मोबियस इनवर्जन (Möbius inversion) के माध्यम से प्राप्त किया जाता है, जिससे एक क्लोज्ड फॉर्म मिलता है: $f_S(x_S) = \sum_{i=1}^n \alpha_i \prod_{j \in S} (k_j(x_j, x^{(i)}_j) - 1)$।

3. एलिमेंट्री सिमेट्रिक पॉलिनोमिअल्स (ESPs) के माध्यम से रिकर्सिव गणना:

   • एकल फीचर के लिए शापली वैल्यू को मार्जिनल योगदानों के भारित योग (weighted sum) के रूप में व्यक्त किया जाता है, जो कर्नेल इवैल्यूएशन के एलिमेंट्री सिमेट्रिक पॉलिनोमिअल्स (ESPs) वाले पदों में विभाजित होता है।
   • प्रत्येक फीचर के लिए सीधे ESPs की गणना करना अक्षम हो सकता है। लेखक न्यूटन की आइडेंटिटीज (Newton's identities) पर आधारित एक रिकर्सिव फॉर्मूलेशन विकसित करते हैं।
   • सभी $d$ शापली वैल्यू को संयुक्त रूप से कंप्यूट करने के लिए, वे एक प्रीफिक्स-सफिक्स कंस्ट्रक्शन (prefix–suffix construction) का उपयोग करते हैं। वे प्रीफिक्स (फीचर $j$ से पहले के फीचर्स) और सफिक्स (फीचर $j$ के बाद के फीचर्स) के लिए जनरेटिंग पॉलिनोमिअल्स को परिभाषित करते हैं। इन पॉलिनोमिअल्स को गुणा करके, वे 'लीव-वन-आउट' सेट $Z_{-j}$ के लिए ESPs को पुनः प्राप्त करते हैं।
   • यह $O(d^2 n)$ समय में सभी शापली वैल्यू की गणना करने की अनुमति देता है, जहाँ $n$ नमूनों (samples) की संख्या है। एल्गोरिदम संख्यात्मक रूप से स्थिर (numerically stable) है, जो केवल एलिमेंट-वाइज जोड़ और गुणा पर निर्भर करता है, जिससे अन्य सटीक विधियों (जैसे TreeSHAP में उपयोग किए जाने वाले चेबीशेव या फूरियर इंटरपोलेशन) से जुड़ी संख्यात्मक अस्थिरता से बचा जा सकता है।

सांख्यिकीय विसंगतियों (Statistical Discrepancies) तक विस्तार
इस ढांचे को प्रेडिक्टिव मॉडलिंग से परे सांख्यिकीय विसंगतियों, विशेष रूप से निम्नलिखित तक विस्तारित किया गया है:

• मैक्सिमम मीन डिसक्रेपेंसी (MMD): वितरण संबंधी निकटता को मापने के लिए। रिमूवल ऑपरेटर एक ऐसा वैल्यू फंक्शन देता है जो दो वितरणों के बीच समग्र विसंगति को व्यक्तिगत चरों (variables) के बीच आवंटित करता है।
• हिल्बर्ट-श्मिट इंडिपेंडेंस क्राइटेरियन (HSIC): रैंडम वेरिएबल्स के बीच निर्भरता को मापने के लिए। यह विधि HSIC का कार्यात्मक अपघटन प्रदान करती है, जिससे विशिष्ट फीचर्स को निर्भरता का श्रेय (attribution) दिया जा सकता है।

परिणाम
शोध पत्र सिंथेटिक और वास्तविक दुनिया के डेटासेट्स पर PKeX-Shapley का सत्यापन करता है:

• सटीकता बनाम सन्निकटन (Accuracy vs. Approximation): लोकल एक्सप्लेनेशन में, PKeX-Shapley (सटीक) सैंपलिंग-आधारित सन्निकटन (जैसे, Kernel SHAP, RKHS-SHAP) से काफी बेहतर प्रदर्शन करता है। जैसे-जैसे आयामीता बढ़ती है (जैसे, $d=50$), सैंपलिंग-आधारित विधियों को कम त्रुटि प्राप्त करने के लिए अत्यधिक बड़े कोएलिशन साइज की आवश्यकता होती है, जबकि PKeX-Shapley आयामीता की परवाह किए बिना सटीक परिणाम प्रदान करता है।
• फीचर चयन (Feature Selection): पॉलीनोमियल और एक्सपोनेंशियल टारगेट फंक्शन वाले सिंथेटिक रिग्रेशन कार्यों में ग्लोबल सेंसिटिविटी एनालिसिस के लिए HSIC का उपयोग करते हुए, PKeX-Shapley प्रभावी रूप से सक्रिय फीचर्स की पहचान करता है, जो RKHS-SHAP, GEMFIX, और BiSHAP जैसे बेसलाइन्स को मात देता है या उनके बराबर प्रदर्शन करता है।
• कम्प्यूटेशनल दक्षता (Computational Efficiency): एल्गोरिदम 1,000 फीचर्स को सेकंडों में स्केल कर सकता है, जबकि ब्रूट-फोर्स गणना ~20 फीचर्स तक ही सीमित है। यह उन सैंपलिंग-आधारित विधियों की तुलना में लगातार तेज़ है, भले ही वे विधियाँ कम कोएलिशन सैंपल्स का उपयोग कर रही हों।
• संख्यात्मक स्थिरता (Numerical Stability): विभिन्न ESP एग्रीगेशन रणनीतियों (क्वाड्रेटिक रिकर्सन बनाम FFT/चेबीशेव इंटरपोलेशन) की तुलना करने वाले प्रयोगों से पता चलता है कि जबकि इंटरपोलेशन विधियाँ तेज़ हैं, वे मध्यम आयामों ($d \approx 50$) पर विनाशकारी संख्यात्मक अस्थिरता से ग्रस्त होती हैं। प्रस्तावित क्वाड्रेटिक रिकर्सन $d=1000$ तक स्थिर रहता है।

महत्व और दावे
शोध पत्र का दावा है कि PKeX-Shapley कर्नेल विधियों के लिए शापली वैल्यू गणना की दो प्राथमिक चुनौतियों का समाधान करता है:

1. सन्निकटन के बिना सटीकता (Exactness without Approximation): यह एक क्लोज्ड-फॉर्म, पैरामीटर-फ्री वैल्यू फंक्शन प्रदान करता है जो सैंपलिंग और घनत्व अनुमान की आवश्यकता को समाप्त करता है, जिससे अनुमान त्रुटि (estimation error) दूर हो जाती है।
2. स्केलेबिलिटी (Scalability): यह सटीक गणना के लिए एमोर्टाइज्ड लीनियर टाइम ($O(dn)$ प्राप्त करता है, जो ब्रूट-फोर्स की घातांकीय लागत या उच्च-आयामी सेटिंग्स में सैंपलिंग विधियों की उच्च वेरिएंस की तुलना में एक महत्वपूर्ण सुधार है।

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