🤖 machine learning

Decision Tree Learning on Product Spaces

यह शोध पत्र यूनिफॉर्म से लेकर अनिश्चित (arbitrary) प्रोडक्ट डिस्ट्रीब्यूशंस तक टॉप-डाउन ग्रीडी डिसीजन ट्री ह्यूरिस्टिक के सैद्धांतिक विश्लेषण का विस्तार करता है, जो यह सिद्ध करता है कि यह $\exp(\Delta_{\text{opt}} D_{\text{opt}} \log(e/\epsilon))$ द्वारा सीमित आकार वाले एक $\epsilon$ -एप्रोक्सिमेटिंग ट्री का निर्माण करता है और साथ ही एक व्यावहारिक, पैरामीटर-मुक्त एल्गोरिदम प्रदान करता है जो पिछले परिणामों में सुधार करता है।

मूल लेखक: Arshia Soltani Moakahr, Faraz Ghahremani, Kiarash Banihashem, MohammadTaghi Hajiaghayi

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

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

CC BY 4.0

मूल लेखक: Arshia Soltani Moakahr, Faraz Ghahremani, Kiarash Banihashem, MohammadTaghi Hajiaghayi

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

कल्पना कीजिए कि आप एक कंप्यूटर को निर्णय लेना सिखाने की कोशिश कर रहे हैं, जैसे कि डाक के ढेर को "रखें" या "फेंक दें" में छाँटना। इसे करने का सबसे आम तरीका है एक डिसीजन ट्री (Decision Tree) बनाना। इस पेड़ को एक फ्लोचार्ट की तरह समझें: आप ऊपर से शुरू करते हैं, एक सवाल पूछते हैं (जैसे "क्या लिफाफा लाल है?"), और जवाब के आधार पर आप नीचे तक एक लेबल तक बाएँ या दाएँ जाते हैं।

दशकों से, कंप्यूटर वैज्ञानिकों को पता है कि इन पेड़ों को बनाने का सबसे अच्छा तरीका एक "लालची" (greedy) विधि है। यह एक पहाड़ पर चढ़ने जैसा है: हर कदम पर, आप बस उस रास्ते को चुनते हैं जो अभी इसी वक्त सबसे तीव्र ढलान वाला दिखता है, बिना पूरे पहाड़ की चिंता किए। व्यवहार में, यह अविश्वसनीय रूप से अच्छा काम करता है। लेकिन सिद्धांत रूप में, यह साबित करना कि यह इतना अच्छा क्यों काम करता है, एक बड़ी पहेली रही है।

समस्या: "परफेक्ट वर्ल्ड" की धारणा

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

लेकिन वास्तविक दुनिया निष्पक्ष नहीं होती है। कुछ चीजें बहुत अधिक बार होती हैं। शायद आपकी 90% डाक बेकार (junk) है, और केवल 10% महत्वपूर्ण है। इसे बायस्ड (biased) या प्रोडक्ट डिस्ट्रीब्यूशन (product distribution) कहा जाता है। पुराना गणित इसे संभाल नहीं सका; यह एक ऊबड़-खाबड़, बर्फीले पर्वत श्रृंखला में नेविगेट करने के लिए एक सपाट रेगिस्तान के मानचित्र का उपयोग करने जैसा था।

सफलता: वास्तविक दुनिया के लिए एक नया मानचित्र

यह शोध पत्र, सोल्तनी मोआखर और उनके सहयोगियों द्वारा, इस अंतर को पाटता है। उन्होंने उसी "लालची" चढ़ने वाली विधि को लिया जिसका उपयोग वास्तविक जीवन के सॉफ़्टवेयर में किया जाता है और यह सिद्ध किया कि यह इन अस्त-व्यस्त, बायस्ड वास्तविक दुनिया के परिदृश्यों में भी उतना ही अच्छा काम करती है।

उन्होंने इसे कैसे किया, इसके लिए यहाँ कुछ सरल उपमाएँ दी गई हैं:

1. "इन्फ्लुएंस" (Influence) स्कोर
जब एल्गोरिदम तय करता है कि अगला सवाल क्या पूछना है, तो वह केवल अनुमान नहीं लगाता। वह एक "इन्फ्लुएंस स्कोर" की गणना करता है।

उपमा: कल्पना कीजिए कि आप एक गुप्त शब्द का अनुमान लगाने की कोशिश कर रहे हैं। यदि आप पूछते हैं, "क्या शब्द 'A' से शुरू होता है?", तो यह सवाल ज्यादा मदद नहीं कर सकता यदि शब्द आमतौर पर "Zebra" है। लेकिन यदि आप पूछते हैं, "क्या यह एक जानवर है?", तो यह एक बड़ा सुराग है। एल्गोरिदम मापता है कि एक विशिष्ट प्रश्न परिणाम को कितना बदल देता है। यह उस सवाल को चुनता है जो पेड़ को सबसे अधिक हिला देता है।

2. "डेप्थ" (Depth) का जाल
लेखकों ने पाया कि एल्गोरिदम द्वारा बनाए गए पेड़ का आकार दो चीजों पर निर्भर करता है:

अधिकतम गहराई ( $D_{opt}$ ): पेड़ कितना गहरा हो सकता है (सबसे लंबा रास्ता)।
औसत गहराई ( $\Delta_{opt}$ ): रैंडम डेटा के लिए पेड़ आमतौर पर कितना गहरा होता है।

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

उपमा: एक भूलभुलैया की कल्पना करें।
- पुराना गणित: "यदि एक छोटा सा रास्ता 1,000 कदम गहरा है, तो पूरा भूलभुलैया बहुत बड़ा और असंभव है।"
- नया गणित: "ज्यादातर रास्ते केवल 5 कदम लंबे हैं। भले ही एक अजीब 1,000-कदम वाला रास्ता हो, फिर भी भूलभुलैया को हल करना आसान है क्योंकि आप आमतौर पर छोटे रास्तों का ही उपयोग करते हैं।"
  यह एल्गोरिदम को भले ही डेटा अजीब या असंतुलित हो, फिर भी छोटा और कुशल रहने की अनुमति देता है।

3. "नो-प्रिपेरेशन" (No-Preparation) का लाभ
पिछले सिद्धांतों के लिए आवश्यक था कि कंप्यूटर को पेड़ बनाने से पहले ही उसका "परफेक्ट" आकार पता हो। यह ऐसा था जैसे आपको कहा गया हो, "आपको ठीक 10 कमरों वाला घर बनाना है," इससे पहले कि आप हथौड़ा भी उठाएं।
यह पेपर एक ऐसा संस्करण पेश करता है जो पैरामीटर-मुक्त (parameter-free) है। इसे पहले से आकार या गहराई जानने की आवश्यकता नहीं है। यह बस बनाना शुरू करता है, जैसे-जैसे यह सीखता है, आगे बढ़ता है, और जब यह पर्याप्त रूप से अच्छा हो जाता है, तो रुक जाता है। यह इसे वास्तविक दुनिया के उपयोग के लिए बहुत व्यावहारिक बनाता है।

परिणाम

लेखकों ने सिद्ध किया कि किसी भी ऐसे फंक्शन के लिए जिसे एक तार्किक रूप से छोटे पेड़ द्वारा हल किया जा सकता है, यह लालची विधि एक ऐसा पेड़ बनाएगी जो है:

सटीक (Accurate): यह लगभग हर समय सही उत्तर प्राप्त करता है।
कुशल (Efficient): यह बहुत बड़ा नहीं होता है, भले ही डेटा अत्यधिक बायस्ड हो (जैसे कि वह 90% जंक मेल वाला उदाहरण)।
मजबूत (Robust): यह बिना किसी पूर्व जानकारी के काम करता है।

सारांश

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

तकनीकी सारांश: उत्पाद स्थानों (Product Spaces) पर निर्णय वृक्ष शिक्षण (Decision Tree Learning)

समस्या विवरण
डिसीजन ट्री लर्निंग मशीन लर्निंग का एक आधार स्तंभ है, जो अपनी व्याख्यात्मकता (interpretability) और अनुभवजन्य सफलता के लिए सराहा जाता है। मानक व्यावहारिक दृष्टिकोण शीर्ष-डाउन ग्रीडी ह्यूरिस्टिक (top-down greedy heuristic) है, जो सबसे "प्रभावशाली" चर के आधार पर पुनरावर्ती रूप से नोड्स को विभाजित करता है (अक्सर एंट्रॉपी या गिनी इंडेक्स जैसी अशुद्धता कमी के माध्यम से मापा जाता है)। हालांकि यह अनुभवजन्य रूप से प्रभावी है, इसका सैद्धांतिक बोध सीमित रहा है। पूर्ववर्ती कठोर गारंटी, जैसे कि ब्लैंक एट अल. (ITCS, 2020) द्वारा दी गई थी, यूनिफॉर्म डिस्ट्रीब्यूशन (Boolean hypercube पर) तक ही सीमित थी। यह धारणा वास्तविक दुनिया के डेटा को पकड़ने में विफल रहती है, जहाँ विशेषताएँ अक्सर विषम, गैर-यूनिफॉर्म उत्पाद वितरण (product distributions) का पालन करती हैं। इसके अलावा, कई सैद्धांतिक कार्य जटिल, गैर-ग्रीडी एल्गोरिदम (जैसे बॉटम-अप या ब्रूट-फोर्स सर्च) प्रस्तावित करते हैं, जो व्यावहारिक कार्यान्वयन से भिन्न होते हैं, जिससे सिद्धांत और व्यवहार के बीच एक अंतर रह जाता है।

कार्यप्रणाली
लेखक अनिश्चित उत्पाद वितरणों (arbitrary product distributions) के लिए शीर्ष-डाउन ग्रीडी ह्यूरिस्टिक के सैद्धांतिक विश्लेषण का विस्तार करते हैं। सेटिंग एक बूलियन फलन $f: \{0, 1\}^n \to \{\pm 1\}$ को एक उत्पाद वितरण $\mu = \mu_1 \times \dots \times \mu_n$ के तहत सीखने की है, जहाँ प्रत्येक बिट $p_i$ प्रायिकता के साथ 1 है।

विश्लेषित मुख्य एल्गोरिदम BuildTopDownDT है, जो मानक ग्रीडी दृष्टिकोण का एक औपचारिक रूप है:

आरंभीकरण (Initialization): एक एकल लीफ (leaf) से शुरू करें।
स्कोरिंग (Scoring): प्रत्येक चरण में, वर्तमान वृक्ष के प्रत्येक लीफ $l$ को स्कोर दें। स्कोर को लीफ तक पहुँचने वाली प्रायिकता द्रव्यमान ( $p_l$ ) और उस लीफ पर उप-फलन (subfunction) के किसी भी चर के अधिकतम प्रभाव ( $\max_i \text{Inf}_i(f_l)$ ) के गुणनफल के रूप में परिभाषित किया गया है।
विभाजन (Splitting): उच्चतम स्कोर वाले लीफ का चयन करें और इसे अपने सबसे प्रभावशाली चर पर विभाजित करें।
समाप्ति (Termination): तब तक दोहराएं जब तक कि वृक्ष का $f$ -पूर्णता (लीव्स को बहुमत लेबल सौंपना) $f$ का $\epsilon$ -अनुमान न बन जाए।

इसका विश्लेषण करने के लिए, लेखक एक 'बेयर ट्री' (बिना लेबल वाला) के लागत (cost) के लिए एक पोटेंशियल फंक्शन पेश करते हैं, जिसे प्रत्येक लीफ पर उप-फन्क्शन्स के कुल प्रभाव के योग के रूप में परिभाषित किया गया है, जिसे उस लीफ तक पहुँचने वाली प्रायिकता द्वारा भारित (weighted) किया गया है। वे इस लागत, अनुमान त्रुटि (approximation error), और इष्टतम वृक्ष के संरचनात्मक गुणों (अधिकतम गहराई $D_{\text{opt}}$ और औसत गहराई $\Delta_{\text{opt}}$ ) के बीच एक संबंध स्थापित करते हैं।

मुख्य योगदान

उत्पाद वितरणों के लिए सामान्यीकरण: यह शोध पत्र अनिश्चित उत्पाद वितरणों के तहत शीर्ष-डाउन ग्रीडी ह्यूरिस्टिक के लिए पहली कठोर प्रदर्शन गारंटी प्रदान करता है, जो पूर्ववर्ती कार्यों की प्रतिबंधात्मक यूनिफॉर्म डिस्ट्रीब्यूशन धारणा को हटा देता है।
बेहतर आकार सीमाएँ (Improved Size Bounds): मुख्य सैद्धांतिक परिणाम (थ्योरम 1.1) बताता है कि किसी भी फलन के लिए जो $s$ $s$ आकार, अधिकतम गहराई $D_{\text{opt}}$ $D_{opt}$ , और औसत गहराई $\Delta_{\text{opt}}$ $Δ_{opt}$ वाले इष्टतम वृक्ष द्वारा गणनीय है, ग्रीडी ह्यूरिस्टिक अधिकतम $\left( \left( \frac{e \cdot \Delta_{\text{opt}}}{\epsilon D_{\text{opt}}} \right)^{\Delta_{\text{opt}} D_{\text{opt}}}, e^{\Delta_{\text{opt}} D_{\text{opt}}} \right)$ $((\frac{e \cdot Δ _{opt}}{ϵ D _{opt}})^{Δ_{opt} D_{opt}}, e^{Δ_{opt} D_{opt}})$ तक के आकार का $\epsilon$ $ϵ$ -अनुमानित वृक्ष बनाता है:
- संतुलित शासन (Balanced Regime): पूर्ण बाइनरी ट्री के लिए जहाँ $D_{\text{opt}} = \Delta_{\text{opt}} = \log s$ , सीमा सरल होकर $s^{O(\log s \cdot \log(e/\epsilon))}$ हो जाती है। यह एक क्वासी-पॉलीनोमियल (quasi-polynomial) सीमा है जो ब्लैंक एट अल. (2020) द्वारा स्थापित सीमा में सुधार करती है और वितरणों के एक व्यापक वर्ग के लिए मान्य है।
- पथ-समान शासन (Path-Like Regime): अत्यधिक असंतुलित वृक्षों (जैसे पथ वृक्ष) के लिए, $D_{\text{opt}}$ $O(n)$ हो सकता है जबकि $\Delta_{\text{opt}}$ एक छोटा स्थिरांक बना रहता है। $\Delta_{\text{opt}}$ और $D_{\text{opt}}$ पर मिश्रित निर्भरता $e^{O(n)}$ की तुलना में $e^{O(n^2)}$ से काफी अधिक सटीक सीमा प्रदान करती है।
पैरामीटर-मुक्त व्यावहारिक कार्यान्वयन: लेखक अपने पैरामीटर-मुक्त एल्गोरिदम का व्यावहारिक कार्यान्वयन प्रस्तुत करते हैं, जो पूरी तरह से पैरामीटर-मुक्त है। पिछले सैद्धांतिक विश्लेषणों के विपरीत, जो इष्टतम वृक्ष के आकार ( $s$ ) या गहराई के ज्ञान को मानते हैं, यह एल्गोरिदम स्कोर और त्रुटियों के नमूना-आधारित अनुमान (sample-based estimation) पर निर्भर करता है। यह सांख्यिकीय विश्वास बनाए रखने के लिए लक्ष्य फलन की जटिलता के पूर्व ज्ञान के बिना अनुकूल रूप से नमूना आकार बढ़ाता है।
अनुमान के प्रति मजबूती (Robustness to Estimation): यह दिखाया गया है कि गारंटी तब भी बनी रहती है जब एल्गोरिदम एक ऐसे लीफ का चयन करता है जिसका स्कोर अधिकतम संभव स्कोर का केवल एक स्थिर अंश (जैसे, $1/4$ ) है, जो नमूना-आधारित अनुमान में निहित शोर (noise) को समायोजित करता है।

परिणाम

सैद्धांतिक: शोध पत्र सिद्ध करता है कि ग्रीडी ह्यूरिस्टिक संतुलित शासन में क्वासी-पॉनोमियल आकार की सीमा प्राप्त करता है और असंतुलित शासन में केवल अधिकतम गहराई पर निर्भर सीमाओं की तुलना में काफी बेहतर सीमा प्राप्त करता है। विश्लेषण वृक्ष की लागत और इसकी त्रुटि के बीच नए लेम्मा (lemmas) स्थापित करने और वर्तमान त्रुटि एवं वृक्ष गहराई के संदर्भ में चयनित लीफ के स्कोर पर निचली सीमा स्थापित करने पर आधारित है।
अनुभवजन्य: लेखक विभिन्न उत्पाद वितरणों (यूनिफॉर्म, मध्यम बायस, हेवी बायस) के तहत संतुलित और असंतुलित दोनों प्रकार के डिसीजन ट्री लक्ष्यों पर अपने पैरामीटर-मुक्त एल्गोरिदम (एल्गोरिदम 2) का अनुभवजन्य मूल्यांकन प्रदान करते हैं। परिणाम पुष्टि करते हैं कि रिकवर किए गए वृक्ष के आकार ग्राउंड-ट्रुथ लक्ष्यों के करीब रहते हैं और सैद्धांतिक सीमाओं के भीतर होते हैं, जिसमें नमूना जटिलता (sample complexity) आयाम और $1/\epsilon$ में बहुपद (polynomial) रूप से बढ़ती है।

महत्व और दावे
यह शोध पत्र डिसीजन ट्री लर्निंग के सैद्धांतिक विश्लेषण और इसके व्यावहारिक अनुप्रयोग के बीच के अंतर को पाटने का दावा करता है। जटिल, गैर-ग्रीडी वेरिएंट के बजाय क्लासिक, सरल ग्रीडी ह्यूरिस्टिक (जो ID3, C4.5, CART में उपयोग किया जाता है) का विश्लेषण करके, लेखक इन व्यापक रूप से उपयोग किए जाने वाले एल्गोरिदम के मजबूत अनुभवजन्य प्रदर्शन के लिए कठोर औचित्य प्रदान करते हैं।

इसका महत्व निम्नलिखित में निहित है:

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

लेखक अपनी सीमाओं को स्वीकार करते हैं, यह नोट करते हुए कि उनका विश्लेषण अनप्रून्ड (unpruned) वृक्षों पर केंद्रित है (क्योंकि कठोर प्रूनिंग विश्लेषण कम है) और वर्तमान प्रमाण असतत (discrete) उत्पाद स्थानों पर निर्भर है। वे निरंतर विशेषताओं (continuous features) और थ्रेशोल्ड-आधारित स्प्लिट्स के विश्लेषण को भविष्य की दिशा के रूप में पहचानते हैं। वे यह भी उल्लेख करते हैं कि हालांकि उनकी सीमा क्वासी-पॉलीनोमियल है, डिसीजन ट्री लर्निंग के लिए सुपर-पॉलीनोमियल निचली सीमाएँ मौजूद हैं, जो सुझाव देती हैं कि इष्टतम आकार $s$ पर कुछ निर्भरता अपरिहार्य है।

समस्या: "परफेक्ट वर्ल्ड" की धारणा

सफलता: वास्तविक दुनिया के लिए एक नया मानचित्र

परिणाम

सारांश

इसी तरह के और पेपर