🤖 machine learning

Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks

यह शोध पत्र एक नवीन एल्गोरिदम प्रस्तुत करता है जो सटीक शापली मानों (Shapley values) पर प्रमाणिक, मनचाहे रूप से सटीक सीमाएँ (bounds) कंप्यूट करने के लिए न्यूरल नेटवर्क सत्यापन तकनीकों का लाभ उठाता है, जिससे मौजूदा सटीक विधियों की तुलना में काफी बड़े खोज स्थानों वाले न्यूरल नेटवर्क के लिए स्केलेबल और सटीक SHAP गणना सक्षम होती है।

मूल लेखक: David Boetius, Shahaf Bassan, Guy Katz, Stefan Leue, Tobias Sutter

प्रकाशित 2026-05-26

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

CC BY 4.0

मूल लेखक: David Boetius, Shahaf Bassan, Guy Katz, Stefan Leue, Tobias Sutter

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

कल्पना कीजिए कि आपके पास एक बहुत ही जटिल, ब्लैक-बॉक्स मशीन (एक न्यूरल नेटवर्क) है जो निर्णय लेती है, जैसे कि किसी बीमारी का निदान करना या ऋण (loan) को मंजूरी देना। आप यह जानना चाहते हैं कि ठीक कौन से इनपुट फीचर्स (जैसे आयु, आय, या रक्तचाप) ने उस विशिष्ट निर्णय को लेने के लिए मशीन को प्रेरित किया।

इसका उत्तर देने का मानक तरीका SHAP कहलाता है। SHAP को एक खेल की तरह समझें जहाँ आप यह पता लगाने की कोशिश करते हैं कि प्रत्येक खिलाड़ी (फीचर) ने टीम के अंतिम स्कोर में कितना योगदान दिया। एक पूरी तरह से सटीक उत्तर प्राप्त करने के लिए, सैद्धांतिक रूप से आपको खिलाड़ियों के हर एक संभावित संयोजन (combination) का परीक्षण करने की आवश्यकता होगी।

समस्या:
एक सरल मशीन के लिए, हर संयोजन का परीक्षण करना आसान है। लेकिन एक जटिल न्यूरल नेटवर्क के लिए जिसमें सैकड़ों फीचर्स हो सकते हैं, संयोजनों की संख्या इतनी विशाल है कि यह दुनिया के हर समुद्र तट पर रेत के कणों को गिनने की कोशिश करने जैसा है। इसे करने में इतना समय लगता है कि यह व्यावहारिक रूप से असंभव है। इस कारण से, आज के अधिकांश उपकरण शॉर्टकट का उपयोग करके उत्तर का केवल अनुमान लगाते हैं। ये अनुमान आमतौर पर तेज़ होते हैं, लेकिन वे गलत हो सकते हैं, और हमारे पास यह जानने का कोई तरीका नहीं है कि वे कितने गलत हैं क्योंकि हम वास्तविक उत्तर की तुलना करने के लिए "असली" उत्तर की गणना नहीं कर सकते।

समाधान: वेरीफाइड SHAP (VERISHAP)
इस शोध पत्र के लेखकों ने VERISHAP नामक एक नया टूल बनाया है। उन्होंने "न्यूरल नेटवर्क वेरिफिकेशन" (जो आमतौर पर AI सिस्टम को सुरक्षित और सुदृढ़ बनाने के लिए उपयोग किया जाता है) नामक क्षेत्र से उधार लिया गया एक चतुर तरीका इस्तेमाल किया है।

यह VERISHAP कैसे काम करता है, इसके लिए एक सरल उपमा यहाँ दी गई है:

"कमरा खोजने" की उपमा (The "Room Search" Analogy)

कल्पना कीजिए कि आप लाखों बक्सों से भरे एक विशाल, अंधेरे गोदाम में छिपे एक विशिष्ट खजाने की तलाश कर रहे हैं।

पुराने तरीके (अनुमान लगाना): आप मानचित्र पर एक तीर फेंकते हैं और कहते हैं, "खजाना शायद इस सामान्य क्षेत्र में है।" यह तेज़ है, लेकिन आप एक मील दूर भी हो सकते हैं।
पुराने सटीक तरीके (गिनती करना): आप एक-एक करके हर एक बॉक्स खोलने की कोशिश करते हैं। यह गारंटी देता है कि आपको खजाना मिल जाएगा, लेकिन आप इसे पूरा करने से पहले बुढ़ापे की दहलीज पर पहुँच जाएंगे।
VERISHAF (स्मार्ट खोज):
1. विभाजित करो और जीतो (Divide and Conquer): एक-एक करके बॉक्स खोलने के बजाय, आप गोदाम को बड़े कमरों में विभाजित करते हैं।
2. "बाड़" वाला तरीका (The "Fence" Trick): आप एक विशेष गणितीय बाड़ (जिसे बाउंड प्रोपेगेशन कहा जाता है) का उपयोग करते हैं ताकि एक बार में पूरे कमरे की जांच की जा सके। यह बाड़ आपको बताती है: "इस कमरे में खजाना निश्चित रूप से $10 और$ 20 के बीच है।"
3. ज़ूम इन करना: यदि रेंज ( $10 से$ 20) बहुत विस्तृत है, तो आप उस कमरे को छोटे कमरों में विभाजित करते हैं और फिर से जांच करते हैं। अब बाड़ और सटीक हो जाती है: "अब हम जानते हैं कि यह $14 और$ 16 के बीच है।"
4. परिणाम: आप कमरों को तब तक विभाजित करते रहते हैं जब तक कि बाड़ इतनी सटीक न हो जाए कि रेंज प्रभावी रूप से शून्य हो जाए। आपने ठीक खजाना का स्थान ढूंढ लिया है।

यह एक बड़ी बात क्यों है

शोध पत्र तीन मुख्य विजयों का दावा करता है:

यह स्केल अप होता है: पिछले तरीके जो सटीक उत्तर खोजने की कोशिश करते थे, यदि समस्या बहुत बड़ी हो जाए तो क्रैश हो जाते थे या उनकी मेमोरी खत्म हो जाती थी। VERISHAP उन खोज स्थानों को संभाल सकता है जो पिछले तरीकों की तुलना में क्रमशः अधिक (orders of magnitude) बड़े हैं (सोचिए अरबों या ट्रिलियनों गुना बड़े)।
यह आपको जल्दी "पर्याप्त अच्छे" उत्तर देता है: आपको हमेशा 100% समाप्त होने तक प्रतीक्षा करने की आवश्यकता नहीं होती है। यदि "बाड़" पर्याप्त रूप से सटीक हो जाती है (उदाहरण के लिए, "उत्तर 14.9 और 15.1 के बीच है"), तो आप जल्दी रुक सकते हैं और कह सकते हैं, "हम 99.9% आश्वस्त हैं कि उत्तर 15 है।" यह पूर्ण उत्तर की प्रतीक्षा करने की तुलना में बहुत तेज़ी से भरोसेमंद अंतर्दृष्टि प्रदान करता है।
यह परीक्षण के लिए एक "गोल्ड स्टैंडर्ड" बनाता है: क्योंकि VERISHAP बड़े समस्याओं के लिए वास्तविक उत्तर की गणना कर सकता है, इसलिए यह एक "सत्य मशीन" (truth machine) के रूप में कार्य करता है। शोधकर्ता अब इन अनुमान लगाने वाले उपकरणों (जैसे KERNELSHAP) का परीक्षण करने के लिए इसका उपयोग कर सकते हैं कि वे वास्तव में कितने सटीक हैं। इससे पहले, हम केवल छोटे, खिलौने जैसे उदाहरणों पर अनुमान लगाने वाले उपकरणों का परीक्षण कर सकते थे जो वास्तविकता को नहीं दर्शाते थे।

शोध पत्र वास्तव में क्या कहता है (और क्या नहीं कहता)

यह कहता है: उन्होंने टेबुलर डेटा (जैसे स्प्रेडशीट) और इमेज डेटा (जैसे MNIST अंक) पर न्यूरल नेटवर्क के लिए सटीक SHAP मान और टाइट बाउंड्स सफलतापूर्वक कंप्यूट किए हैं। उन्होंने दिखाया है कि यह विभिन्न प्रकार के नेटवर्क आर्किटेक्चर (जैसे ResNets) और विभिन्न एक्टिवेशन फंक्शन (जैसे ReLU, Tanh) पर काम करता है।
यह कहता है: यह वर्तमान में "अनुमान लगाने" वाले तरीकों की तुलना में धीमा है, लेकिन यह बड़े नेटवर्क के लिए गणितीय रूप से प्रमाणित, सटीक उत्तर प्राप्त करने का एकमात्र तरीका है।
यह नहीं कहता है: शोध पत्र यह दावा नहीं करता है कि यह टूल अस्पतालों में तत्काल नैदानिक उपयोग के लिए तैयार है या यह सभी AI पूर्वाग्रह (bias) समस्याओं को हल करता है। यह विशेष रूप से इन मानों को कंप्यूट करने और उन्हें सत्यापित करने की गणितीय क्षमता पर केंद्रित है। यह स्वीकार करता है कि हालांकि यह एक बहुत बड़ा कदम है, लेकिन अंतर्निहित गणित अभी भी बहुत कठिन है, और कुछ बहुत ही विशिष्ट, जटिल नेटवर्कों के लिए, इसमें अभी भी लंबा समय लग सकता है।

संक्षेप में:
VERISHAP एक ऐसे कंपास से अपग्रेड करने जैसा है जो "लगभग उत्तर" की ओर इशारा करता है, एक GPS में जो आपको आपकी सटीक स्थिति बता सकता है, भले ही आप एक विशाल, अनमैप्ड जंगल में हों। यह साबित करता है कि हम जटिल AI निर्णयों के लिए सटीक सत्य प्राप्त कर सकते हैं, और यह हमें एक पैमाना देता है जिससे हम यह माप सकें कि हमारे अन्य, तेज़ उपकरण वास्तव में कितने अच्छे हैं।

तकनीकी सारांश: वेरिफाइड SHAP (VERISHAP)

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

शैपली एडिटिव एक्सप्लेनेशन्स (SHAP) मशीन लर्निंग मॉडल के प्रेडिक्शन को इनपुट फीचर्स के प्रति आबंटित करने के लिए एक मानक पोस्ट-हॉक व्याख्यात्मकता (explainability) विधि है। हालाँकि, न्यूरल नेटवर्क के लिए सटीक SHAP मानों की गणना करना व्यापक रूप से कम्प्यूटेशनल रूप से अव्यवहार्य माना जाता है क्योंकि यह फीचर सबसेट्स के ऊपर एक्सपोनेंशियल सर्च स्पेस ( $2^n$ ) का सामना करता है। जबकि ट्री-आधारित और एडिटिव मॉडल्स के लिए सटीक गणना संभव है, सामान्य न्यूरल नेटवर्क्स के लिए यह #P-हार्ड है। फलस्वरूप, साहित्य सांख्यिकीय एस्टिमेटर्स (जैसे KERNELSHAP, FASTSHAP, LEVERAGESHAP) पर निर्भर करता है। ये एस्टिमेटर्स दो मौलिक सीमाओं का सामना करते हैं:

अशुद्धि (Inaccuracy): वे ऐसे अनुमान प्रदान करते हैं जो अत्यधिक नॉन-लीनियर मॉडल्स या मजबूत फीचर इंटरैक्शन वाले परिदृश्यों में अविश्वसनीय हो सकते हैं।
ग्राउंड ट्रुथ का अभाव (Lack of Ground Truth): चूंकि न्यूरल नेटवर्क्स के लिए सटीक SHAP मानों की गणना करना अत्यधिक महंगा है, इसलिए एस्टिमेटर्स का मूल्यांकन आमतौर पर खिलौने जैसे छोटे मॉडल्स (toy-sized models) पर किया जाता है जहाँ सटीक गणना संभव है। ये सेटिंग्स अक्सर वास्तविक दुनिया के उच्च-आयामी (high-dimensional) न्यूरल नेटवर्क्स पर सामान्यीकृत होने में विफल रहती हैं।

कार्यप्रणाली: वेरिफाइड SHAP (VERISHAP)

यह पेपर VERISHAP को पेश करता है, जो न्यूरल नेटवर्क के लिए सटीक SHAP मान और प्रमाणित बाउंड्स (provable bounds) की गणना करने के लिए हालिया न्यूरल नेटवर्क वेरिफिकेशन प्रगति का लाभ उठाने वाला पहला एल्गोरिदम है। यह दृष्टिकोण SHAP की असतत (discrete), संभाव्य (probabilistic) और समेशन-हैवी प्रकृति के लिए ब्रांच-एंड-बाउंड वेरिफिकेशन तकनीकों को अनुकूलित करता है।

मुख्य एल्गोरिदम (Core Algorithm)

VERISHAP एक वृद्धिशील (incremental) ब्रांच-एंड-बाउंड रणनीति का उपयोग करता है जो फीचर स्पेस (फीचर $i$ के लिए सभी कोलिशन $S_i$ का सेट) को पुनरावर्ती रूप से विभाजित करता है।

विभाजन (Partitioning): एल्गोरिदम शामिल ( $I$ ) और बाहर किए गए ( $E$ ) फीचर्स के सेटों के आधार पर ब्रांचेस $B$ को परिभाषित करता है। एक ब्रांच कोलिशन के उन उपसमुच्चयों का प्रतिनिधित्व करती है जहाँ $I$ के फीचर्स मौजूद हैं और $E$ के फीचर्स अनुपस्थित हैं।
प्रोपैगेशन के माध्यम से बाउंडिंग (Bounding via Propagation): प्रत्येक ब्रांच के लिए, एल्गोरिदम मार्जिनल योगदान $\Delta_i(S) = v(S \cup \{i\}) - v(S)$ $Δ_{i} (S) = v (S \cup {i}) - v (S)$ पर लोअर और अपर बाउंड कंप्यूट करता है।
- असतत (discrete) सेट्स पर कंटीन्यूअस बाउंड प्रोपगेशन (जैसे CROWN, IBP) लागू करने के लिए, एल्गोरिदम बूलियन फीचर मास्क $m \in \{0, 1\}^n$ को कंटीन्यूअस डोमेन $[0, 1]^n$ में रिलैक्स करता है।
- यह रिलैक्स्ड डोमेन पर वैल्यू फंक्शन $v(S)$ पर टाइट बाउंड्स प्राप्त करने के लिए लीनियर बाउंड प्रोपगेशन (LBP) (विशेष रूप से CROWN-IBP) का उपयोग करता है।
एकत्रीकरण (Aggregation): कुल SHAP वैल्यू बाउंड्स को सभी ब्रांचेस के भारित (weighted) बाउंड्स को जोड़कर कंप्यूट किया जाता है:
$\phi_i^{(t)} = \sum_{B \in \mathcal{B}^{(t)}} \Lambda_B \Delta_i^B \leq \phi_i \leq \sum_{B \in \mathcal{B}^{(t)}} \Lambda_B \Delta_i^B = \bar{\phi}_i^{(t)}$
जहाँ $\Lambda_B$ ब्रांच $B$ में कोलिशन के Shapley वेट्स का क्लोज्ड-फॉर्म सम है, जिसे कॉम्बिनेटोरियल रूप से निकाला गया है।
रिफाइनमेंट (Refinement): एल्गोरिदम विभाजित करने के लिए ब्रांचेस (MAXDIAM जैसी रणनीतियों का उपयोग करके) और विभाजित करने के लिए फीचर्स (SMEARS जैसी रणनीतियों का उपयोग करके) को चुनकर बाउंड्स को रिफाइन करता है, जब तक कि वे सटीक मान या वांछित परिशुद्धता (precision) तक न पहुँच जाएँ।

प्रमुख सैद्धांतिक गुण (Key Theoretical Properties)

समाप्ति (Termination): एल्गोरिदम को एक सीमित संख्या में इटरेशन (अधिकतम $2^{n-1}$ ) के बाद सटीक SHAP मानों के साथ समाप्त होने की गारंटी है, क्योंकि विभाजन अंततः सिंगल कोलिशन को आइसोलेट कर देता है।
लीनियर मॉडल्स के लिए अर्ली टर्मिनेशन: लीनियर मॉडल्स के लिए, एल्गोरिदम पहले ही इटरेशन में समाप्त हो जाता है क्योंकि मार्जिनल योगदान स्थिर होता है, और LBP लीनियर कंपोजिशन के लिए कोई अनुमान त्रुटि (approximation error) पेश नहीं करता है।
पीसवाइज-लिनैरिटी (Piecewise-Linearity): ReLU-एक्टिवेटेड नेटवर्क्स के लिए, एल्गोरिदम जल्दी समाप्त हो सकता है यदि विभाजन खोज को उन क्षेत्रों तक सीमित करता है जहाँ नेटवर्क लीनियर व्यवहार करता है।

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

न्यूरल नेटवर्क्स के लिए पहला सटीक SHAP: VERISHAP सामान्य न्यूरल नेटवर्क्स के लिए सटीक SHAP मानों की गणना करने वाला पहला एल्गोरिदम है, जो पिछले सटीक तरीकों की तुलना में बहुत बड़े सर्च स्पेस तक स्केल करता है।
प्रमाणित बाउंड्स (Provable Bounds): यह विधि SHAP मानों के लिए लोअर और अपर बाउंड्स प्रदान करती है, जो पूर्ण अभिसरण (convergence) से पहले भी विश्वसनीय व्याख्यात्मक अंतर्दृष्टि सक्षम बनाती है।
ग्राउंड-ट्रुथ बेसलाइन: यह बड़े और अधिक यथार्थवादी सर्च स्पेस पर सांख्यिकीय SHAP एस्टिमेटर्स का मूल्यांकन करने के लिए एक सिद्धांत आधारित ढांचा स्थापित करता है, जहाँ ग्राउंड ट्रुथ पहले अप्राप्य था।
वेरिफिकेशन के माध्यम से दक्षता: न्यूरल नेटवर्क्स को निकट-लीनियर क्षेत्रों में डीकंपोज करने का लाभ उठाकर, एल्गोरिदम कई व्यावहारिक मामलों में सभी $2^n$ कोलिशन को गिनने से बचता है।

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

लेखकों ने टैबुलर (UCI डेटासेट्स) और विजन (MNIST, FashionMNIST, CIFAR10, GTSRB) बेंचमार्क पर VERISHAP का मूल्यांकन किया।

ExactSHAP के विरुद्ध स्केलेबिलिटी: VERISHAP स्टेट-ऑफ-द-आर्ट सटीक विधि (EXACTSHAP) को काफी पीछे छोड़ देता है। जहाँ EXACTSHAP $2^{20}$ से बड़े सर्च स्पेस के लिए GPU मेमोरी समाप्त कर देता है, वहीं VERISHAP $2^{25}$ ( $\approx 3 \times 10^7$ कोलिशन) तक के इंस्टेंस के लिए सटीक मान कंप्यूट करता है और $2^{60}$ ( $\approx 10^{18}$ कोलिशन) तक के स्पेस के लिए टाइट बाउंड्स प्रदान करता है।
एस्टिमेटर्स के साथ तुलना: सांख्यिकीय एस्टिमेटर्स (KERNELSHAP, TREEMSR, LEVERAGESHAP) के साथ तुलना करने पर, VERISHAP दर्शाता है कि एस्टिमेटर्स अक्सर मेमोरी बाधाओं के भीतर समान सटीकता प्राप्त करने में विफल रहते हैं। इसके अलावा, VERISHAP प्रकट करता है कि एस्टिमेटर का प्रदर्शन विभिन्न डेटासेट्स पर काफी भिन्न होता है (उदाहरण के लिए, ट्री-बेस्ड मॉडल्स की तुलना में न्यूरल नेटवर्क्स पर TREEMSR का प्रदर्शन अस्थिर रहता है)।
आर्किटेक्चर वर्सटाइलिटी: एल्गोरिदम विभिन्न आर्किटेक्चर के लिए सटीक SHAP मान सफलतापूर्वक कंप्यूट करता है, जिसमें ReLU, tanh, और Swish एक्टिवेशन के साथ फुली कनेक्टेड नेटवर्क और ResNets शामिल हैं।
अभिसरण (Convergence): प्रयोगों में (जैसे MNIST), बाउंड्स सटीक मान कंप्यूट होने से बहुत पहले ही सूचनात्मक (attribution पैटर्न प्रकट करना) हो जाते हैं, जो अक्सर कुछ सेकंडों के भीतर होता है, जबकि सटीक गणना में कई सेकंड लग सकते हैं।

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

पेपर VERISHAP को न्यूरल नेटवर्क्स के लिए सटीक SHAP कंप्यूटेशन को स्केल करने की दिशा में एक पहला कदम के रूप में प्रस्तुत करता है। इसका महत्व तीन क्षेत्रों में निहित है:

स्केलेबिलिटी: यह न्यूरल नेटवर्क वेरिफिकेशन का लाभ उठाकर सटीक SHAP कंप्यूटेशन की सैद्धांतिक जटिलता और व्यावहारिक अनुप्रयोग के बीच के अंतर को पाटता है।
विश्वसनीयता (Trustworthiness): यह प्रमाणित गारंटियों के साथ "ग्राउंड-ट्रुथ" स्पष्टीकरण प्राप्त करने का एक तरीका प्रदान करता है, जो सांख्यिकीय अनुमानों में निहित अनिश्चितता को संबोधित करता है।
मूल्यांकन ढांचा: यह बड़े सर्च स्पेस पर SHAP एस्टिमेटर्स का मूल्यांकन करने और उन्हें बेहतर बनाने के लिए एक कठोर बेंचमार्क प्रदान करता है, जो खिलौने वाले मॉडल्स से आगे बढ़ता है।

लेखक स्वीकार करते हैं कि सटीक SHAP कंप्यूट करना अभी भी #P-हार्ड है और कुछ जटिल नेटवर्क्स के लिए VERISHAP अभी भी धीमा हो सकता है। हालाँकि, उनका तर्क है कि प्रमाणित बाउंड्स कंप्यूट करने की क्षमता और न्यूरल नेटवर्क वेरिफिकेशन में निरंतर सुधार की संभावना इसे विश्वसनीय AI व्याख्यात्मकता के लिए एक मौलिक प्रगति बनाती है।