📊 statistics

Partition Tree: Conditional Density Estimation over General Outcome Spaces

यह शोध पत्र 'पार्टीशन ट्री' (Partition Tree) का परिचय देता है, जो एक नवीन नॉनपैरामेट्रिक ढांचा है जो नेगेटिव लॉग-लाइक्लीहुड (negative log-likelihood) को कम करने के लिए डेटा-अनुकूल विभाजनों को सीखकर सामान्य परिणाम स्थानों (general outcome spaces) पर कंडीशनल डेंसिटी का अनुमान लगाता है, साथ ही इसके बैगिंग विस्तार, 'पार्टीशन फॉरेस्ट' (Partition Forest) के साथ, जो मौजूदा ट्री-आधारित और रैंडम फॉरेस्ट विधियों की तुलना में बेहतर संभाव्य भविष्यवाणी प्रदर्शन प्रदर्शित करता है।

मूल लेखक: Felipe Angelim, Alessandro Leite

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

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

CC BY 4.0

मूल लेखक: Felipe Angelim, Alessandro Leite

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

कल्पना कीजिए कि आप मौसम की भविष्यवाणी करने की कोशिश कर रहे हैं, लेकिन केवल यह कहने के बजाय कि "बारिश होगी" या "धूप निकलेगी," आप संभावनाओं की पूरी श्रृंखला का वर्णन करना चाहते हैं। आप जानना चाहते हैं: "हल्की बूंदाबांदी की कितनी संभावना है? भारी मूसलाधार बारिश की? या शायद धूप और बादलों का मिश्रण होगा?"

अधिकांश पारंपरिक कंप्यूटर मॉडल (जैसे मानक निर्णय वृक्ष/standard decision trees) कठोर भविष्यवक्ताओं की तरह होते हैं। वे आपके डेटा को देखते हैं, उसे बक्सों में विभाजित करते हैं, और एक एकल उत्तर या एक सरल प्रायिकता (जैसे, "70% बारिश की संभावना") देते हैं। वे तब संघर्ष करते हैं जब उत्तर केवल एक संख्या या एक साधारण श्रेणी नहीं होता है।

यह शोध पत्र एक नया टूल पेश करता है जिसे पार्टीशन ट्री (Partition Tree) (और इसका टीम-अप संस्करण पार्टीशन फॉरेस्ट - Partition Forest) कहा जाता है, जो एक सुपर-स्मार्ट, लचीले मानचित्रकार (map-maker) की तरह कार्य करता है। यह कैसे काम करता है, इसके लिए सरल उपमाओं का उपयोग यहाँ दिया गया है:

1. "एकल अनुमान" के बजाय "स्मार्ट मैप"

अपने डेटा को लोगों (इनपुट) और उनके मूड (परिणाम) से भरा एक विशाल कमरा मानिए।

पुराना तरीका: एक मानक ट्री पूछता है, "क्या आप लंबे हैं?" यदि हाँ, तो वह आपको एक बॉक्स में डाल देता है और कहता है, "इस बॉक्स में अधिकांश लोग खुश हैं।" यह आपको एक औसत मूड देता है।
पार्टीशन ट्री: यह नया तरीका केवल औसत मूड का अनुमान नहीं लगाता है। यह उस बॉक्स के भीतर एक विस्तृत मानचित्र (detailed map) बनाता है। यह समझ जाता है कि "लंबे" समूह के भीतर, कुछ लोग बहुत खुश हैं, कुछ औसत हैं, और कुछ दुखी हैं। यह एक "डेंसिटी मैप" (घनत्व मानचित्र) बनाता है जो दिखाता है कि उस विशिष्ट समूह के लिए प्रत्येक मूड की कितनी संभावना है।

2. "लेगो ब्लॉक" दृष्टिकोण (Piecewise-Constant)

शोध पत्र इस मॉडल को "पीसवाइज-कॉन्स्टेंट" (piecewise-constant) के रूप में वर्णित करता है। कल्पना कीजिए कि आप लेगो ब्लॉक्स से एक दीवार बना रहे हैं।

मॉडल आपके डेटा को देखता है और एक ऐसी दीवार बनाता है जहाँ प्रत्येक ब्लॉक वास्तविकता के एक छोटे, विशिष्ट हिस्से का प्रतिनिधित्व करता है।
प्रत्येक ब्लॉक के भीतर, "डेंसिटी" (संभावना) स्थिर और समान होती है, जैसे लेगो ब्रिक का ऊपरी हिस्सा।
इन ब्लॉक्स को स्मार्ट, डेटा-संचालित तरीके से एक साथ जोड़कर, यह एक टेढ़ा-मेढ़ा लेकिन सटीक आकार बनाता है जो डेटा में पूरी तरह फिट बैठता है, बिना यह मान लिए कि इसका आकार एक चिकनी वक्र रेखा (जैसे बेल कर्व) या सीधी रेखा होनी चाहिए।

3. "मिश्रित" सामग्रियों को संभालना

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

नवाचार: पार्टीशन ट्री दोनों प्रकार के डेटा के साथ एक ही एकीकृत भाषा में व्यवहार करता है। यह डेटा को एक संख्या के आधार पर काट सकता है (जैसे "आयु > 30?") या एक श्रेणी के आधार पर (जैसे "रंग नीला है?") और फिर भी परिणाम के लिए उसी तरह का "मूड मैप" बना सकता है। इसे सब कुछ संख्याओं में बदलने की आवश्यकता नहीं है; यह जो कुछ भी आप इसे देते हैं, उसके साथ काम करता है।

4. "बेस्ट-फर्स्ट" बिल्डर

ट्री यह कैसे तय करता है कि डेटा को कहाँ काटना है?

कल्पना कीजिए कि आप मिश्रित फलों के ढेर को छाँटने वाले एक शेफ हैं। आप बेतरतीब ढंग से नहीं काटते। आप ढेर को देखते हैं और पूछते हैं, "यदि मैं यहाँ काटता हूँ, तो क्या मुझे दो ऐसे ढेर मिलेंगे जो उस बड़े अव्यवस्थित ढेर की तुलना में बहुत अधिक समान (uniform) हैं जिससे मैंने शुरुआत की थी?"
एल्गोरिदम एक "ग्रीडी" (greedy) रणनीति का उपयोग करता है (यह हर चरण में सबसे अच्छा स्थानीय विकल्प चुनता है)। यह लगातार उस कट (कटाई) की तलाश करता है जो सबसे अधिक "आश्चर्य" (गणितीय रूप से जिसे नेगेटिव लॉग-लाइक्लीहुड कहा जाता है) को कम करता है। यह डेटा को छोटे और छोटे, अधिक सटीक बक्सों में काटता रहता है जब तक कि मानचित्र सटीक न हो जाए।

5. "फॉरेस्ट" (Bagging)

जिस तरह एक अकेला पेड़ कभी-कभी थोड़ा अस्थिर हो सकता है, लेखकों ने पार्टीशन फॉरेस्ट (Partition Forest) बनाया है।

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

6. प्रयोगों ने क्या दिखाया

लेखकों ने विभिन्न वास्तविक दुनिया के डेटासेट्स (जैसे घर की कीमतों की भविष्यवाणी करना, बीमारियों का निदान करना, या ईमेल को छाँटना) पर इस नए टूल का परीक्षण किया।

सटीकता: यह पुराने मानक पेड़ों की तुलना में संभावनाओं की पूरी श्रृंखला (प्रायिकता भविष्यवाणी) की भविष्यवाणी करने में बेहतर था।
गति: यह आश्चर्यजनक रूप से तेज़ था, अक्सर उन अन्य उन्नत तरीकों की तुलना में बहुत तेज़ी से प्रशिक्षित हुआ जो ऐसा ही काम करने की कोशिश करते हैं।
मजबूती (Robustness): भले ही डेटा में "शोर" (यादृच्छिक त्रुटियां) या अनावश्यक विशेषताएं (बेकार जानकारी) थीं, पार्टीटन ट्री ने अपना आधार मजबूती से बनाए रखा।

निष्कर्ष

यह शोध पत्र निर्णय वृक्ष (decision trees) बनाने का एक नया तरीका प्रस्तुत करता है जो आपको केवल एक उत्तर नहीं देता है। इसके बजाय, यह किसी भी प्रकार के परिणाम के लिए—चाहे वह संख्या हो, श्रेणी हो, या दोनों का मिश्रण—एक विस्तारित प्रायिकता मानचित्र (detailed probability map) बनाता है। यह एक ऐसे मौसम विज्ञानी से अपग्रेड करने जैसा है जो केवल "बारिश" कहता है, बजाय उसके जो आपको एक 3D मॉडल देता है जो दिखाता है कि गड्ढे ठीक कहाँ बनेंगे, वे कितने गहरे होंगे, और उनके होने की कितनी संभावना है।

तकनीकी सारांश: पार्टीशन ट्री: सामान्य परिणाम स्थानों पर सशर्त घनत्व अनुमान (Conditional Density Estimation)

समस्या विवरण

डिसीजन ट्री (Decision trees) अपने व्याख्यात्मक गुणों और पॉइंट प्रेडिक्शन (वर्गीकरण और रिग्रेशन) में दक्षता के लिए व्यापक रूप से मूल्यवान हैं। हालांकि, सामान्य परिणाम स्थानों (जो निरंतर और श्रेणीबद्ध दोनों चरों को एक साथ सहारा देते हैं) पर सशर्त घनत्व अनुमान (conditional density estimation) के लिए ट्री-आधारित विधियों का विस्तार करना चुनौतीपूर्ण बना हुआ है। मौजूदा दृष्टिकोण विशिष्ट सीमाओं का सामना करते हैं:

पैरामीट्रिक धारणाएं (Parametric Assumptions): CADET जैसी विधियां लीफ नोड्स पर पैरामीट्रिक सशर्त घनत्वों का उपयोग करती हैं, जो जटिल, नॉन-गौसियन वितरणों को पकड़ने में सक्षम नहीं हो सकती हैं।
स्केलेबिलिटी (Scalability): CDTree जैसी विधियां, जो स्प्लिट्स और लीफ-वाइज हिस्टोग्राम को संयुक्त रूप से अनुकूलित करती हैं, अत्यधिक गणनात्मक रूप से मांग वाली हो सकती हैं, जिससे बड़े डेटासेट पर उनकी प्रयोज्यता सीमित हो जाती है।
एकीकृत सूत्रीकरण (Unified Formulation): एक ऐसे एकीकृत ढांचे का अभाव है जो वर्गीकरण (classification) और रिग्रेशन (regression) को बिना किसी पैरामीट्रिक बाधा के सशर्त घनत्व अनुमान के विशिष्ट मामलों के रूप में देख सके।

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

1. सैद्धांतिक ढांचा: माप-सिद्धांत आधारित सूत्रीकरण (Measure-Theoretic Formulation)

लेखक पार्टीशन ट्री (Partition Tree) का प्रस्ताव करते हैं, जो माप सिद्धांत (measure theory) पर आधारित एक ढांचा है।

संयुक्त स्थान विभाजन (Joint Space Partitioning): पारंपरिक पेड़ों के विपरीत, जो केवल कोवेरिएट स्पेस $X$ को विभाजित करते हैं, पार्टीशन ट्री संयुक्त कोवेरिएट-आउटकम स्पेस $Z = X \times Y$ का एक डेटा-अनुकूलित विभाजन $\pi_N$ बनाता है।
पीसवाइज़-कांस्टेंट अनुमान (Piecewise-Constant Estimation): सशर्त घनत्व $f(y|x)$ को इन विभाजनों पर एक पीसवाइज़-कांस्टेंट फंक्शन के रूप में मॉडल किया जाता है।
राडॉन-निकोडिम डेरिवेटिव (Radon–Nikodym Derivative): यह विधि सशर्त घनत्व को एक प्रोडक्ट मेजर $\nu = P_X \otimes \mu_Y$ के सापेक्ष राडॉन-निकोडिम डेरिवेटिव के माध्यम से परिभाषित करती है, जहाँ $\mu_Y$ एक संदर्भ मेजर (डिस्क्रीट आउटकम के लिए काउंटिंग मेजर, निरंतर के लिए लेबेग मेजर) है।
अनुमानकर्ता (Estimator): विभाजन के एक सेल $A = A_X \times A_Y$ के लिए, घनत्व अनुमान है:
$\hat{f}_\pi(z) = \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)}$
जहाँ $n_{XY}$ और $n_X$ एम्पिरिकल काउंट्स हैं। यह सूत्रीकरण स्वाभाविक रूप से मिश्रित-प्रकार के परिणामों को संभालता है और वर्गीकरण एवं रिग्रेशन को विशेष मामलों के रूप में उभरने की अनुमति देता है।

2. ट्री निर्माण एल्गोरिथ्म

पेड़ को एक ग्रीडी, बेस्ट-फर्स्ट रणनीति (greedy, best-first strategy) का उपयोग करके विकसित किया जाता है जो सीधे सशर्त नेगेटिव लॉग-लाइक्लीहुड (conditional negative log-likelihood) को कम करता है।

उद्देश्य: स्प्लिटिंग मानदंड लॉग-लॉस में एम्पिरिकल गेन को अधिकतम करता है:
$\hat{G}(\pi', \pi) = \sum_{A' \in \{A_l, A_r\}} \frac{n_{XY}(A')}{N} \log \left( \frac{n_{XY}(A')}{n_X(A') \mu_Y(A'_Y)} \right) - \frac{n_{XY}(A)}{N} \log \left( \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)} \right)$
स्प्लिट प्रकार:
- कोवेरिएट स्प्लिट्स ( $X$ ): कोवेरिएट स्पेस को परिष्कृत करते हैं (मानक ट्री स्प्लिट्स)।
- आउटकम स्प्लिट्स ( $Y$ ): एक निश्चित कोवेरिएट क्षेत्र के भीतर आउटकम बिन्स को परिष्कृत करते हैं। यह ट्री को आउटकम वितरण के लिए अनुकूल रूप से हिस्टोग्राम बनाने की अनुमति देता है।
दक्षता: एल्गोरिथ्म $O(d_Z N \log N)$ समय में (या संतुलित पेड़ों के लिए $O(d_Z N \log^2 N)$ ) संभावित स्प्लिट्स का मूल्यांकन करने के लिए कुशल सॉर्टिंग और प्रीफिक्स-सम तकनीकों का उपयोग करता है, जो मानक CART की स्केलेबिलिटी से मेल खाता है।
ट्रंकेशन (Truncation): अनबाउंडेड निरंतर परिणामों के लिए, विधि एक डेटा-डिपेंडेंट ट्रंकेशन (min-max box) का उपयोग करती है ताकि परिमित मेजर सुनिश्चित किया जा सके, जिसमें यह सैद्धांतिक गारंटी है कि ट्रंकेशन एसिम्प्टोटिक रूप से सारा प्रोबेबिलिटी मास कैप्चर करता है।

3. पार्टीशन फॉरेस्ट (Partition Forest)

स्थिरता और भविष्य कहनेवाला प्रदर्शन (predictive performance) में सुधार के लिए, लेखक पार्टीशन फॉरेस्ट नामक एक एन्सेम्बल विधि पेश करते हैं। यह बूटस्ट्रैप नमूनों पर प्रशिक्षित कई पार्टीशन ट्री के सशर्त घनत्व अनुमानों का औसत निकालता है (बैगिंग), और वैकल्पिक रूप से रैंडम फीचर सबसैंपलिंग का उपयोग करता है।

4. सैद्धांतिक गारंटी

पेपर अनुमानकर्ता की $L^1(\nu)$ -निरंतरता ( $L^1(\nu)$ -consistency) के लिए पर्याप्त स्थितियाँ स्थापित करता है। निरंतरता तब गारंटीकृत होती है यदि विभाजन अनुक्रम निम्नलिखित को संतुष्ट करता है:

सेल्स की संख्या $N$ के सापेक्ष सबलीनियर रूप से बढ़ती है।
विभाजन परिवार का ग्रोथ फंक्शन विशिष्ट VC-डायमेंशन बाउंड्स को संतुष्ट करता है।
सेल्स का व्यास (diameter) शून्य तक घटता है।
अलग-अलग कोवेरिएट प्रोजेक्शन की संख्या $\sqrt{\log N / N}$ के सापेक्ष धीरे-धीरे बढ़ती है।

मुख्य योगदान

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

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

लेखकों ने विविध वर्गीकरण और रिग्रेशन बेंचमार्क पर पार्टीशन ट्री और पार्टीशन फॉरेस्ट का मूल्यांकन किया, और उनकी तुलना CART, रैंडम फॉरेस्ट, CADET और CDTree से की।

वर्गीकरण (Classification):
- सिंगल ट्री: पार्टीशन ट्री ने लॉग-लॉस के मामले में अधिकांश डेटासेट्स (9 में से 8) पर CART को पछाड़ दिया।
- एन्सेम्बल्स: पार्टीशन फॉरेस्ट ने अधिकांश डेटासेट्स पर रैंडम फॉरेस्ट की तुलना में कम लॉग-लॉस प्राप्त किया, जो बेहतर प्रोबेबिलिस्टिक कैलिब्रेशन प्रदर्शित करता है।
रिग्रेशन (Regression):
- सिंगल ट्री: पार्टीशन ट्री ने प्रतिस्पर्धी पॉइंट प्रेडिक्शन और मजबूत प्रोबेबिलिस्टिक प्रदर्शन प्रदान किया। विशेष रूप से, इसने बड़े डेटासेट्स (जैसे Air, Power, California, Protein) पर पैरामीट्रिक CADET को पछाड़ दिया, जो बेहतर स्केलेबिलिटी और सैंपल साइज के प्रति अनुकूलन क्षमता का सुझाव देता है।
- एन्सेम्बल्स: पार्टीशन फॉरेस्ट ने लॉग-लॉस के संबंध में अधिकांश रिग्रेशन बेंचमार्क (10 में से 8) पर रैंडम फॉरेस्ट को लगातार पछाड़ दिया।
मजबूती (Robustness):
- शोर (Noise): विधि ने होमोसेडास्टिक और हेटरोसेडास्टिक शोर दोनों के प्रति मजबूती दिखाई, जिसमें CDTree की तुलना में प्रदर्शन गिरावट समान थी और CADET की तुलना में बेहतर स्थिरता देखी गई।
- अनावश्यक फीचर्स (Redundant Features): जबकि CDTree ने सह-संबंधित फीचर डुप्लीकेशन के खिलाफ थोड़ी बेहतर स्थिरता दिखाई, पार्टीशन ट्री ने फीचर करप्शन के तहत CADET की तुलना में अधिक सुसंगत भविष्यवाणियां (कम वेरिएंस) दीं।
दक्षता (Efficiency): Physicochemical Protein डेटासेट पर रनटाइम तुलना दर्शाती है कि $N=10,000$ पर पार्टीशन ट्री, CADET की तुलना में लगभग 5 $\times$ तेज़ और CDTree की तुलना में 25 $\times$ तेज़ है।

महत्व और दावे

पेपर का दावा है कि पार्टीशन ट्री मौजूदा संभाव्य ट्री विधियों के लिए एक स्केलेबल, नॉन-पैरामीट्रिक विकल्प प्रदान करता है। इसका प्राथमिक महत्व निम्नलिखित में निहित है:

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

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