🤖 machine learning

Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactions

यह शोधपत्र Quadrature-TreeSHAP प्रस्तुत करता है, जो एक संख्यात्मक रूप से स्थिर, गहराई-स्वतंत्र विधि है जो कुशलतापूर्वक शापली मानों (Shapley values) और उच्च-क्रम की अंतःक्रियाओं (high-order interactions) की गणना करने के लिए पाथ-डिपेंडेंट ट्री-शापली (Path-Dependent TreeSHAP) को गॉस-लेजेंड्रे क्वाड्रैचर (Gauss-Legendre quadrature) का उपयोग करके पुनर्गठित करता है, जिससे CPU और GPU दोनों पर महत्वपूर्ण गति वृद्धि प्राप्त होती है।

मूल लेखक: Ron Wettenstein, Rory Mitchell, Peng Yu

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

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

CC BY 4.0

मूल लेखक: Ron Wettenstein, Rory Mitchell, Peng Yu

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

कल्पना कीजिए कि आपके पास एक बहुत ही स्मार्ट, लेकिन जटिल निर्णय लेने वाली मशीन है (जैसे कि एक पेड़ जिसकी हजारों शाखाएं विकसित हुई हैं)। आप जानना चाहते हैं कि इसने एक विशिष्ट भविष्यवाणी क्यों की। क्या इसने फीचर A के कारण "हाँ" का निर्णय लिया? या क्या यह फीचर B और फीचर C के बीच एक टीम वर्क था?

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

लंबे समय तक, करने का मानक तरीका (जिसे TreeSHAP कहा जाता था) में तीन मुख्य समस्याएं थीं:

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

लेखकों ने Quadrature-TreeSHAP नामक एक नई विधि पेश की है। यह कैसे काम करती है, इसके सरल उदाहरण यहाँ दिए गए हैं:

1. "स्नैपशॉट" बनाम "मूवी"

पुराने तरीके पेड़ के हर एक पथ (path) पर कदम-दर-कदम चलकर क्रेडिट की गणना करने की कोशिश करते थे। यदि पेड़ गहरा था, तो इसमें बहुत समय लगता था।

Quadrature-TreeSHAP खेल बदल देता है। पूरे पेड़ के हर रास्ते पर चलने के बजाय, यह गणना को एक मूवी की तरह मानता है। यह महसूस करता है कि पेड़ के पीछे का गणित वास्तव में एक सुचारू, अनुमानित वक्र (पॉलीनोमियल) है।

पूरी मूवी को फ्रेम-दर-फ्रेम देखने के बजाय, यह नया तरीका वक्र के 8 विशिष्ट "स्नैपशॉट" (गणितीय रूप से क्वाड्रचर पॉइंट्स कहलाते हैं) लेता है।

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

2. "स्थिर पुल" (Stable Bridge)

पुराना तरीका ऐसा था जैसे अस्थिर और असमान तख्तों से बना एक पुल। जैसे-जैसे पुल लंबा होता गया (गहरे पेड़), तख्ते खिसकने लगे और गणित ढह गया (संख्यात्मक अस्थिरता)।

नया तरीका पुल को चिकने, ठोस कंक्रीट से बनाता है। उन 8 निश्चित बिंदुओं पर उत्तर की गणना करके, यह "डगमगाते तख्तों" से पूरी तरह बच जाता है। परिणाम एक ऐसी गणना है जो सबसे गहरे, सबसे जटिल पेड़ों पर भी पूरी तरह स्थिर रहती है।

3. "टीमवर्क" की सुपरपावर

पुराना तरीका यह समझाने में संघर्ष करता था कि फीचर्स एक साथ मिलकर कैसे काम करते हैं (जैसे, "फीचर A और फीचर B ने मिलकर परिणाम दिया")। यह कमरे में कितने लोग हैं, यह गिनने के लिए लोगों को पहले जोड़ों में, फिर तीन के समूहों में, फिर चार के समूहों में लाइन में खड़ा करने जैसा था—यह तेजी से जटिल होता गया।

Quadrature-TreeSHAP इसे सहजता से संभालता है। क्योंकि यह किसी भी आकार के समूहों के लिए उसी "8 स्नैपशॉट" वाले ट्रिक का उपयोग करता है, यह जटिल टीमवर्क इंटरेक्शन (3-वे, 4-वे या यहाँ तक कि 6-वे) को लगभग तुरंत कैलकुलेट कर सकता है।

गति: अपने परीक्षणों में, यह जटिल इंटरेक्शन की गणना करने में पिछले सबसे अच्छे तरीके की तुलना में 1,200 गुना तेज़ था।

4. "असेंबली लाइन" (Hardware Efficiency)

अंत में, लेखकों ने इस विधि को आधुनिक कंप्यूटर चिप्स (CPUs और GPUs) के अनुकूल बनाया।

उदाहरण: एक फैक्ट्री असेंबली लाइन की कल्पना करें। पुराना तरीका एक ऐसे कर्मचारी की तरह था जिसे हर आइटम के बारे में अलग से सोचने के लिए रुकना पड़ता था। नया तरीका एक ऐसी मशीन की तरह है जो 8 वस्तुओं को एक ही समय में एक सटीक लय में प्रोसेस करती है।
परिणाम: क्योंकि गणित इतना नियमित है, यह मानक कंप्यूटरों और शक्तिशाली ग्राफिक्स कार्ड (GPUs) दोनों पर बहुत कुशलता से चलता है, जिससे मानक कंप्यूटरों पर 10 गुना और ग्राफिक्स कार्ड पर 7 गुना तक की गति मिलती है।

परिणामों का सारांश

लेखकों ने इसका परीक्षण 12 अलग-अलग वास्तविक दुनिया के डेटासेट्स (जैसे हाउसिंग प्राइस की भविष्यवाणी करना या फोटो में वस्तुओं की पहचान करना) पर किया।

गति: यह पुराने तरीकों की तुलना में लगातार तेज़ है, कभी-कभी 10 के कारक से भी अधिक।
स्थिरता: यह टूटता या गलत नहीं होता है, यहाँ तक कि बहुत गहरे पेड़ों पर भी जहाँ पुराने तरीके विफल हो गए थे।
अपनाने की दर: उन्होंने इसे पहले से ही XGBoost में शामिल कर लिया है, जो दुनिया के सबसे लोकप्रिय मशीन लर्निंग टूल्स में से एक है। यदि आप भविष्य में XGBoost का उपयोग करते हैं, तो आपके मॉडल को समझाने का यह नया, तेज़ और अधिक स्थिर तरीका पहले से ही इसमें मौजूद होगा।

संक्षेप में: Quadrature-TreeSHAP एक धीमी, अस्थिर, मैनुअल कैलकुलेटर से एक हाई-स्पीड, सुपर-स्टेबल डिजिटल कंप्यूटर में अपग्रेड करने जैसा है जो पलक झपकते ही जटिल टीमवर्क पहेलियों को हल कर सकता है।

तकनीकी सारांश: क्वाड्रैचर-ट्री-शैप (Quadrature-TreeSHAP)

समस्या विवरण

ट्री एनसेम्बल मॉडल (जैसे XGBoost, रैंडम फॉरेस्ट) के लिए व्याख्यात्मकता (explainability) काफी हद तक शैप्ली मानों (Shapley values) पर निर्भर करती है। हालांकि पाथ-डिपेंडेंट (Path-Dependent) SHAP अपनी दक्षता के कारण मानक दृष्टिकोण है, मौजूदा विधियाँ गहराई-निर्भर रनटाइम (depth-dependent runtime), संख्यात्मक स्थिरता (numerical stability), और उच्च-क्रम इंटरैक्शन (higher-order interactions) के समर्थन के संबंध में महत्वपूर्ण समझौतों का सामना करती हैं।

वर्तमान अत्याधुनिक विधियाँ विशिष्ट सीमाओं को प्रदर्शित करती हैं:

TreeSHAP और GPUTreeSHAP $O(MTLD^2)$ की समय जटिलता के साथ कार्य करते हैं (जहाँ $M$ नमूने, $T$ पेड़, $L$ पत्तियाँ, $D$ गहराई है)।
FastTreeSHAP v2 और Woodelf जटिलता को $O(MTLD)$ तक कम करते हैं लेकिन गहराई में घातांकीय (exponential) प्रीप्रोसेसिंग चरणों को पेश करते हैं, जो गहरे पेड़ों के लिए अव्यावहारिक बना देते हैं।
Linear TreeSHAP $O(MTND)$ प्राप्त करता है लेकिन मोनॉमियल बेसिस (monomial basis) में ऑपरेशन्स के कारण संख्यात्मक अस्थिरता से ग्रस्त है।
TreeGrad-Shap ग्रेडिएंट फॉर्मुलेशन के माध्यम से स्थिरता में सुधार करता है लेकिन प्रथम-क्रम (first-order) एट्रिब्यूशन तक सीमित है।
TreeSHAP-IQ उच्च-क्रम इंटरैक्शन तक विस्तार करता है, लेकिन इसकी जटिलता $O(MTLD \binom{F-1}{s-1})$ है, जो फीचर्स की संख्या ( $F$ ) और इंटरैक्शन ऑर्डर ( $s$ ) बढ़ने के साथ खराब तरीके से स्केल करती है।

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

लेखक गॉस-लेजेंड्रे क्वाड्रैचर (Gauss–Legendre quadrature) और एक वेटेड-बैनज़ाफ इंटरैक्शन पॉलीनोमियल (weighted-Banzhaf interaction polynomial) पर आधारित पाथ-डिपेंडेंट ट्री-शैप का पुनर्गठन प्रस्तावित करते हैं।

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

यह विधि शैप्ली मानों और वेटेड बैनज़ाफ मानों के बीच संबंध का लाभ उठाती है।

वेटेड बैनज़ाफ पॉलीनोमियल: एक निर्णय वृक्ष की पत्ती $v$ के लिए, समावेश प्रायिकता $p$ पर फीचर सबसेट $S$ के लिए पाथ-डिपेंडेंट वेटेड बैनज़ाफ इंटरैक्शन मान एक पॉलीनोमियल $B^{(S)}_{p,v}$ के रूप में व्यक्त किया जाता है। यह पॉलीनोमियल पत्ती की पथ संरचना और एज वेट्स से व्युत्पन्न होता है।
इंटीग्रल रिकवरी (Integral Recovery): शैप्ली इंटरैक्शन मानों को भागीदारी प्रायिकता $p \in [0, 1]$ पर इन बैनज़ाफ पॉलीनोमियल्स के इंटीग्रेशन द्वारा प्राप्त किया जाता है:
$SII^{(S)}(f_v) = \int_0^1 B^{(S)}_p(f_v) \, dp$
क्वाड्रैचर सन्निकटन (Quadrature Approximation): प्रतीकात्मक एकीकरण (symbolic integration) के बजाय, लेखक इस इंटीग्रल को गॉस-लेजेंड्रे क्वाड्रैचर का उपयोग करके मूल्यांकित करते हैं। इंटीग्रल को निश्चित नोड्स $t_m$ पर मूल्यांकित किए गए पॉलीनोमियल के भारित योग के रूप में अनुमानित किया जाता है:
$SII^{(S)}_v \approx \sum_{m=1}^n w_m B^{(S)}_{t_m, v}$

2. एल्गोरिदम कार्यान्वयन

फिक्स्ड-पॉइंट फॉर्मुलेशन: एल्गोरिदम ट्री का एक एकल डेप्थ-फर्स्ट ट्रावर्सल (DFS) करता है। ट्रावर्सल के दौरान, यह एक निश्चित सेट के गॉस-लेजेंड्रे नोड्स (आमतौर पर 8) पर पथ पॉलीनोमियल के मानों को प्रसारित करता है, न कि प्रतीकात्मक रूप से पॉलीनोमियल्स का विस्तार करता है।
जटिलता में कमी:
- सैद्धांतिक रूप से, इंटीग्रेंड (integrand) की डिग्री ऑर्डर- $s$ इंटरैक्शन के लिए अधिकतम $d-s$ है (जहाँ $d$ एक पथ पर अधिकतम अद्वितीय फीचर्स है)।
- व्यावहारिक रूप से, लेखक प्रदर्शित करते हैं कि बहुत गहरे पेड़ों के लिए भी मशीन प्रिसिजन (float32) तक पहुँचने के लिए 8 निश्चित क्वाड्रैचर पॉइंट्स पर्याप्त हैं।
- यह आंतरिक गणना से पेड़ की गहराई $d$ पर निर्भरता को हटा देता है, जिससे प्रभावी जटिलता प्रथम-क्रम के लिए $O(MTN \lceil d/2 \rceil)$ से घटकर $O(MTN) $और ऑर्डर-$ s $इंटरैक्शन के लिए$ O(MTN d^s) $से$ O(MTN d^{s-1})$ हो जाती है।
हार्डवेयर त्वरण (Hardware Acceleration): क्योंकि गणना हर पथ के लिए समान बिंदुओं के एक निश्चित सेट का मूल्यांकन करती है, इसलिए अंकगणित नियमित (regular) है। यह CPU पर कुशल SIMD (Single Instruction, Multiple Data) और GPU पर SIMT (Single Instruction, Multiple Threads) निष्पादन की अनुमति देता है, जिससे GPUTreeSHAP द्वारा आवश्यक बिन-पैकिंग और शेड्यूलिंग ओवरहेड समाप्त हो जाता है।

मुख्य योगदान

Any-Order Interaction Algorithm: पेपर किसी भी-क्रम के शैप्ली इंटरैक्शन मानों की गणना करने के लिए एक एल्गोरिदम प्रस्तुत करता है जो TreeSHAP-IQ की $O(MTLD \binom{F-1}{s-1})$ जटिलता को $O(MTN d^s)$ में सुधारता है। यह तब पर्याप्त लाभ देता है जब फीचर्स की संख्या पेड़ की गहराई से अधिक होती ( $F > D \ge d$ )।
क्वाड्रैचर-आधारित पुनर्गठन: लेखक एक सैद्धांतिक और अनुभवजन्य विश्लेषण प्रदान करते हैं जो दिखाता है कि शैप्ली मानों और इंटरैक्शन के लिए मशीन प्रिसिजन तक पहुँचने के लिए 8 गॉस-लेजेंड्रे पॉइंट्स पर्याप्त हैं, जो व्यवहार में पेड़ की गहराई से रनटाइम को प्रभावी रूप से अलग (decouple) कर देता है।
संख्यात्मक स्थिरता: मोनॉमियल बेसिस में गुणांकों का विस्तार करने के बजाय, बाउंडेड, पॉजिटिव नोड्स पर समरी पॉलीनोमियल का मूल्यांकन करके, यह विधि विनाशकारी कैंसिलेशन (catastrophic cancellation) से बचती है। लेखक दावा करते हैं कि Quadrature-TreeSHAP, विशेष रूप से गहरे एनसेम्बल्स के लिए, TreeSHAP की तुलना में अधिक संख्यात्मक रूप से स्थिर है।
हार्डवेयर-कुशल कार्यान्वयन: इस विधि को CPU के लिए C++ में लागू किया गया है और GPU के लिए XGBoost में एकीकृत किया गया है। यह वेक्टरकरण (CPU पर 4 पॉइंट, GPU पर 32) का लाभ उठाता है ताकि मौजूदा कार्यान्वयनों की तुलना में महत्वपूर्ण गति प्राप्त की जा सके।
ओपन सोर्स एकीकरण: इसका कार्यान्वयन ओपन-सोर्स है और XGBoost लाइब्रेरी में एकीकृत है (TreeSHAP बैकएंड को रिप्लेस करते हुए), जो मानक API कॉल्स (pred_contribs=True और pred_interactions=True) के माध्यम से सुलभ है।

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

लेखकों ने 12 XGBoost बेंचमार्क एनसेम्बल्स (Adult, CalHousing, CovType, Fashion-MNIST) पर छोटे, बड़े और स्पार्स (sparse) परिदृश्यों में Quadrature-TreeSHAP का मूल्यांकन किया।

प्रथम-क्रम (Shapley Values):
- CPU: TreeSHAP से 1.06× से 10.59× तेज़ (औसत 3.84×)।
- GPU: GPUTreeSHAP से 1.84× से 6.95× तेज़।
द्वितीय-क्रम (Pairwise Interactions):
- CPU: TreeSHAP से 3.80× से 58.11× तेज़ (औसत 12.86×)।
- GPU: GPUTreeSHAP से 6.65× तक तेज़ (हालांकि GPUTreeSHAP विशिष्ट कम-गहराई वाले वर्कलोड पर प्रतिस्पर्धी बना रहा)।
उच्च-क्रम इंटरैक्शन (Python Benchmarks):
- तीसरे-क्रम के इंटरैक्शन पर TreeSHAP-IQ की तुलना में, Quadrature-TreeSHP 18.73× से 26.49× तेज़ था।
- CovType-sparse डेटासेट पर, TreeSHAP-IQ पर स्पीडअप इंटरैक्शन ऑर्डर के साथ बढ़ता गया, जो ऑर्डर 6 पर 1209.37× तक पहुँच गया।
संख्यात्मक स्थिरता:
- बढ़ती पेड़ की गहराई के साथ Fashion-MNIST-sparse बेंचमार्क पर, TreeSHAP गहराई 32 के बाद अस्थिर हो गया। Quadrature-TreeSHAP स्थिर रहा, जिसमें 6-8 पॉइंट्स ने उच्च सटीकता प्राप्त की।

महत्व

पेपर का दावा है कि Quadrature-TreeSHAP, पाथ-डिपेंडेंट SHAP का एक संख्यात्मक रूप से स्थिर, हार्डवेयर-कुशल और इंटरैक्शन-जागरूक पुनर्गठन प्रदान करता है। प्रतीकात्मक पॉलीनोमियल अंकगणित से फिक्स्ड-पॉइंट क्वाड्रैचर की ओर शिफ्ट होकर, यह विधि गहराई निर्भरता और संख्यात्मक स्थिरता के बीच के समझौते को हल करता है। यह गहरे पेड़ों पर उच्च-क्रम इंटरैक्शन की कुशल गणना को सक्षम बनाता है, जो पहले की विधियों की घातांकीय जटिलता या अस्थिरता के कारण बाधित था। XGBoost में इसका एकीकरण इस लाइब्रेरी और व्यापक shap पैकेज के उपयोगकर्ताओं के लिए तत्काल व्यावहारिक उपयोगिता सुनिश्चित करता है।