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

समस्या विवरण

शापली मान (Shapley values) मशीन लर्निंग भविष्यवाणियों की व्याख्या करने के लिए एक मौलिक उपकरण हैं, जो सहयोगात्मक गेम थ्योरी (cooperative game theory) पर आधारित फीचर एट्रिब्यूशन प्रदान करते हैं। हालाँकि, सटीक गणना आम तौर पर कठिन (intractable) होती है, क्योंकि इसमें $2^{d-1}$ फीचर कोलिशन का मूल्यांकन करना आवश्यक होता है। जबकि मॉडल-विशिष्ट विधियाँ (जैसे TreeSHAP, RKHS-SHAP) बहुपद समय (polynomial time) प्राप्त करने के लिए संरचनात्मक गुणों का लाभ उठाती हैं, वे अक्सर संख्यात्मक स्थिरता (numerical stability) और गणना दक्षता (computational efficiency) के बीच एक निरंतर समझौते का सामना करती हैं।

विशेष रूप से, बहुपद इंटरपोलेशन (polynomial interpolation) पर निर्भर विधियाँ (जैसे Linear TreeSHAP) वेंडरमोंड इनवर्स (Vandermonde inverses) की खराब स्थिति (ill-conditioning) के कारण बहुपद डिग्री (जो ट्री डेप्थ या फीचर काउंट द्वारा निर्धारित होती है) बढ़ने के साथ तेजी से संख्यात्मक अस्थिरता का शिकार होती हैं। इसके विपरीत, बीजगणितीय पुनरावृत्ति (algebraic recursion) विधियाँ (जैसे प्रोडक्ट-कर्नेल मॉडल्स के लिए) स्थिरता तो प्रदान करती हैं, लेकिन उनमें अंकगणितीय लागत काफी अधिक होती है। यह शोध पत्र एक ऐसी विधि की आवश्यकता को संबोधित करता है जो व्यापक श्रेणी के मॉडलों के लिए, जिनमें मल्टीप्लिकेटिव स्ट्रक्चर (multiplicative structure) होता है, एक साथ सटीक (exact) (या निकट-सटीक), संख्यात्मक रूप से स्थिर और गणना की दृष्टि से कुशल हो।

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

यह शोध पत्र प्रोडक्ट गेम्स (product games) के लिए शापली मानों की गणना करने के लिए QuadraSHAP नामक एक विधि प्रस्तुत करता है—ऐसे सहयोगात्मक खेल जहाँ कोलिशन वैल्यू (coalition value) प्रति-खिलाड़ी पदों के गुणनफल के रूप में विभाजित होती है ($v(S) = \prod_{j \in S} u_j$)। यह संरचना स्वाभाविक रूप से ट्री-आधारित मॉडलों और प्रोडक्ट कर्नेल वाले कर्नेल मेथड्स में दिखाई देती है।

1. इंटीग्रल रिप्रेजेंटेशन (Integral Representation)

मुख्य सैद्धांतिक योगदान $2^{d-1}$ उपसमुच्चयों (subsets) के भारित योग से एक सटीक एक-आयामी इंटीग्रल (one-dimensional integral) में प्रोडक्ट गेम के शापली मान को पुनर्गठित करना है। बीटा-फंक्शन प्रतिनिधित्व का उपयोग करते हुए, लेखक व्युत्पन्न करते हैं:
$$\phi_i(v) = (u_i - 1) \int_0^1 \prod_{j \neq i} \left( (1-t) + t u_j \right) dt$$
यह रूपांतरण उपसमुच्चय गणना (subset enumeration) या इंटरपोलेशन-आधारित गुणांक रिकवरी की आवश्यकता को समाप्त करता है।

2. गॉस-लेजेंड्रे क्वाड्रैचर (Gauss–Legendre Quadrature)

इंटीग्रल का मूल्यांकन गॉस-लेजेंड्रे क्वाड्रैचर का उपयोग करके किया जाता है।

• सटीकता (Exactness): यदि क्वाड्रैचर नोड्स की संख्या $m_q \ge \lceil d/2 \rceil$ है, तो विधि सटीक शापली मान प्राप्त करती है।
• अनुमान (Approximation): यदि $m_q < \lceil d/2 \rceil$ है, तो विधि एक निकट-सटीक अनुमान प्रदान करती है। यह सिद्ध किया गया है कि त्रुटि $m_q$ के संबंध में ज्यामितीय रूप से (geometrically) घटती है, विशेष रूप से बर्नस्टीन एलिप्स पैरामीटर $\rho > 1$ के लिए $O(\rho^{-2m_q})$ द्वारा सीमित है। हजारों फीचर्स के साथ उच्च-परिशुद्धता अनुमानों के लिए भी, अनुभवजन्य रूप से कुछ सौ नोड्स पर्याप्त होते हैं, जो सैद्धांतिक सटीकता सीमा से बहुत नीचे है।

3. संख्यात्मक रूप से स्थिर और कुशल कार्यान्वयन

व्यावहारिक कम्प्यूटेशनल चुनौतियों को संबोधित करने के लिए, लेखक विशिष्ट एल्गोरिथम अनुकूलन प्रस्तावित करते हैं:

• लॉग-स्पेस इवैल्यूएशन (Log-Space Evaluation): उच्च आयामों में ओवरफ्लो और अंडरफ्लो को रोकने के लिए, उत्पादों का मूल्यांकन स्पष्ट साइन ट्रैकिंग के साथ लॉग-स्पेस में किया जाता है। एस्टीमेटर को इस प्रकार गणना किया जाता है:
  $$\hat{\phi}_i(v) = (u_i - 1) \sum_{q=1}^{m_q} \omega_q \cdot \text{sgn}(P_q)\text{sgn}(T_{q,i}) \exp\left( \log|P_q| - \log|T_{q,i}| \right)$$
  जहाँ $P_q$ पदों का पूर्ण उत्पाद है और $T_{q,i}$ फीचर $i$ के लिए पद है।
• साझा गणना (Shared Computation): प्रत्येक फीचर के लिए "लीव-वन-आउट" उत्पाद को पुन: गणना करने के बजाय, पूर्ण उत्पाद को एक बार गणना किया जाता है, और फिर फीचर $i$ के विशिष्ट कारक को विभाजित कर दिया जाता है। यह जटिलता को $O(d^2 m_q)$ से घटाकर $O(d m_q)$ कर देता है।
• पैरेललाइजेशन (Parallelization): गणना लॉग-स्पेस रिडक्शन को $O(\log d)$ पैरेलल टाइम में कंप्यूट करने के लिए एसोसिएटिव स्कैन प्रिमिटिव्स (प्रीफिक्स सम्स) का उपयोग करती है।

मुख्य योगदान

1. सटीक इंटीग्रल फॉर्मुलेशन: शोध पत्र स्थापित करता है कि प्रोडक्ट गेम्स के लिए शापली मान एक सटीक इंटीग्रल प्रतिनिधित्व स्वीकार करते हैं, जिससे गॉस-लेजेंड्रे क्वाड्रैचर का उपयोग संभव होता है।
2. स्थिरता और दक्षता: QuadraSHAP स्थिरता-दक्षता के ट्रेड-ऑफ को हल करता है। यह इंटरपोलेशन-आधारित विधियों (जैसे Linear TreeSHAP) की संख्यात्मक अस्थिरता से बचता है और प्रोडक्ट-कर्नेल मॉडल्स के लिए बीजगणितीय पुनरावृत्ति विधियों की तुलना में काफी तेज़ है।
3. सैद्धांतिक गारंटी: विधि $m_q \ge \lceil d/2 \rceil$ के लिए सिद्ध सटीकता और अनुमानित शासन (approximate regimes) के लिए ज्यामितीय अभिसरण सीमाएँ प्रदान करती है।
4. स्केलेबल एल्गोरिदम: लेखक $O(d m_q)$ अनुक्रमिक कार्य और $O(\log d)$ पैरेलल टाइम के साथ एल्गोरिदम विकसित करते हैं, जो इसे उच्च-आयामी समस्याओं (हजारों फीचर्स) के लिए स्केलेबल बनाता है।

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

लेखक सिंथेटिक और वास्तविक दुनिया के डेटासेट्स पर स्टेट-ऑफ-द-आर्ट बेसलाइन्स (TreeSHAP, Linear TreeSHAP, FastTreeSHAP, shapiq, और PKeX-Shapley) के विरुद्ध QuadraSHAP का मूल्यांकन करते हैं।

• ट्री एन्सेम्बल्स (Tree Ensembles):
  • गति (Speed): QuadraSHAP सभी परीक्षण किए गए कॉन्फ़िगरेशन में सबसे तेज़ संख्यात्मक रूप से स्थिर विधि है। बड़े एन्सेम्बल्स ($10^5$ लीव्स) पर, यह TreeSHAP से 3–5$\times$ और FastTreeSHHAP से 2–2.7$\times$ बेहतर प्रदर्शन करता है।
  • स्थिरता (Stability): गहरे ट्री शासन (100 की गहराई तक) में, प्रतिस्पर्धी विधियाँ जैसे Linear TreeSHAP और TreeSHAP शापली एफिशिएंसी एक्सिओम (efficiency axiom) का विनाशकारी उल्लंघन प्रदर्शित करती हैं (त्रुटियाँ $10^{186}$ या उससे अधिक तक पहुँच जाती हैं)। QuadraSHाह फ्लोटिंग-पॉइंट सीमाओं ($\sim 10^{-13}$) के स्तर पर सटीकता बनाए रखता है।
• प्रोडक्ट-कर्नेल मेथड्स (Product-Kernel Methods):
  • स्केलेबिलिटी (Scalability): प्रोडक्ट कर्नेल्स के साथ कर्नल रिज रिग्रेशन के लिए, QuadraSHAP वर्तमान सटीक बेसलाइन (PKeX-Shapley) की तुलना में एक क्रम अधिक (order of magnitude) तेज़ है।
  • उच्च आयाम (High Dimensions): जहाँ PKeX-Shapley फीचर आयाम $d \ge 2000$ के लिए टाइम-आउट हो जाता है (300s सीमा), वहीं QuadraSHAP सेकंडों में स्पष्टीकरण पूरा कर लेता है (उदाहरण के लिए, $d=5000$ के लिए 7.6s)।
• अनुमान की गुणवत्ता (Approximation Quality): प्रयोग पुष्टि करते हैं कि अनुमान त्रुटि $m_q$ नोड्स के साथ ज्यामितीय रूप से घटती है। $d=5000$ के लिए, केवल 400 नोड्स का उपयोग करने पर (सटीकता सीमा 2500 से बहुत नीचे) भी मशीन-प्रिसिजन के करीब सटीकता प्राप्त होती है।

महत्व और दावे

शोध पत्र का दावा है कि QuadraSHAP मल्टीप्लिकेटिव स्ट्रक्चर वाले मॉडलों के लिए एक एकीकृत, सुदृढ़ ढांचा प्रदान करता है। इंटीग्रल प्रतिनिधित्व और गॉस-लेजेंड्रे क्वाड्रैचर का लाभ उठाकर, यह प्राप्त करता है:

• संख्यात्मक मजबूती (Numerical Robustness): यह उच्च-आयामी और गहरे-ट्री सेटिंग्स में स्थिर रहता है जहाँ इंटरपोलेशन-आधारित विधियाँ विफल हो जाती हैं।
• गणना संबंधी श्रेष्ठता (Computational Superiority): यह अपनी सटीकता या नियंत्रित अनुमान बनाए रखते हुए सबसे तेज़ मौजूदा विधियों की बराबरी करता है या उनसे बेहतर प्रदर्शन करता है।
• सामान्यीकरण (Generality): यह ट्री एन्सेम्बल्स और प्रोडक्ट-कर्नेल मेथड्स को एक ही कम्प्यूटेशनल प्रतिमान (paradigm) के तहत एकीकृत करता है।

लेखक QuadraSHAP को इन विशिष्ट मॉडलों के लिए सबसे तेज़ संख्यात्मक रूप से स्थिर विधि के रूप में प्रस्तुत करते हैं, जो जटिल, उच्च-आयामी मशीन लर्निंग सिस्टम के लिए एक व्यावहारिक समाधान प्रदान करता है।