On Stopping Rules and Spatial Adaptation for CART

मशीन लर्निंग के विशाल परिदृश्य में, जहाँ कंप्यूटर डेटा से भविष्यवाणियाँ करना सीखते हैं, सबसे स्थायी और भरोसेमंद उपकरणों में से एक 'डिसीजन ट्री' (निर्णय वृक्ष) है। एक फ्लोचार्ट की कल्पना करें जो डेटा के एक टुकड़े के बारे में सरल प्रश्नों की एक श्रृंखला पूछता है—जैसे कि "क्या तापमान 70 डिग्री से ऊपर है?" या "क्या आय 50,000 से अधिक है?"—और उत्तर को एक पथ के माध्यम से अंतिम निष्कर्ष तक ले जाता है। ये मॉडल इसलिए लोकप्रिय हैं क्योंकि इन्हें मनुष्यों के लिए पढ़ना और समझना आसान है, फिर भी वे कहीं अधिक जटिल प्रणालियों के साथ प्रतिस्पर्धा करने के लिए पर्याप्त शक्तिशाली बने हुए हैं। इन पेड़ों को बनाने की मानक विधि, जिसे CART कहा जाता है, एक लालची खोजकर्ता (greedy explorer) की तरह काम करती है: प्रत्येक चरण में, यह उस एकल प्रश्न की तलाश करती है जो डेटा के वर्तमान समूह को दो ऐसे भागों में विभाजित करता है जो एक-दूसरे से यथासंभव भिन्न हों। यह इन प्रश्नों को पूछना जारी रखती है, डेटा स्थान को छोटे और छोटे आयताकार बक्सों में काटती रहती है, जब तक कि वह रुकने का निर्णय नहीं लेती।

वह रहस्य जिसने लंबे समय से सांख्यिकीविदों को उलझाया है, यह नहीं है कि पेड़ कैसे बढ़ता है, बल्कि यह है कि वह कब रुकता है। रुकने के नियम महत्वपूर्ण हैं क्योंकि वे अंतिम बक्सों के आकार को निर्धारित करते हैं, जो भविष्यवाणी करने के लिए स्थानीय पड़ोस (local neighborhood) के रूप में कार्य करते हैं। यदि पेड़ बहुत जल्दी रुक जाता है, तो बक्से बहुत बड़े होते हैं, और भविष्यवाणी एक मोटा औसत होती है जो स्थानीय विवरणों को छोड़ देती है। यदि यह बहुत देर से रुकता है, तो बक्से बहुत छोटे हो जाते हैं, जो वास्तविक पैटर्न के बजाय डेटा में रैंडम शोर (random noise) को पकड़ लेते हैं। जबकि विभाजन कहाँ करना है, इसके तरीके का व्यापक अध्ययन किया गया है, लेकिन रुकने के नियम की सांख्यिकीय भूमिका कुछ हद तक अस्पष्ट रही है। शोधकर्ता लंबे समय से यह जानना चाहते थे कि क्या ये लालची पेड़ डेटा की स्थानीय जटिलता के अनुकूल खुद को ढाल सकते हैं—अर्थात, ऊबड़-खाबड़, ऊबड़-खाबड़ क्षेत्रों में सूक्ष्म, विस्तृत भविष्यवाणियाँ करते हुए और समतल, शांत क्षेत्रों में भविष्यवाणियों को सरल और सुचारू रखते हुए—बिना यह बताए कि हर बिंदु पर डेटा कितना जटिल है।

नेशनल यूनिवर्सिटी ऑफ सिंगापुर के शोधकर्ताओं की एक टीम ने अब इस प्रश्न का एक निश्चित उत्तर प्रदान किया है, यह सिद्ध करते हुए कि मानक CART एल्गोरिदम वास्तव में इस स्थानिक अनुकूलन (spatial adaptation) को प्राप्त कर सकता है, लेकिन केवल तभी जब यह एक विशिष्ट प्रकार के रुकने के नियम का उपयोग करता है। उनका कार्य यह प्रदर्शित करता है कि रुकने का निर्णय लेने की सबसे आम विधि—बस यह आवश्यकता कि प्रत्येक अंतिम बॉक्स में डेटा बिंदुओं की एक न्यूनतम संख्या होनी चाहिए—अनुकूलन करने में विफल रहती है। यह कठोर नियम पेड़ को एक सुचारू, अनुमानित क्षेत्र और एक अराजक, शोर वाले क्षेत्र दोनों को विवरण के समान स्तर के साथ उपचार करने के लिए मजबूर करता है, जिससे दोनों क्षेत्रों में खराब प्रदर्शन होता है। इसके विपरीत, शोधकर्ताओं ने सिद्ध किया कि एक अलग नियम, जो पेड़ को तब रोकता है जब विभाजन से प्राप्त सुधार एक विशिष्ट थ्रेशोल्ड (सीमा) से नीचे गिर जाता है, एल्गोरिदम को सही संतुलन खोजने की अनुमति देता है। यह थ्रेशोल्ड-आधारित नियम एक संवेदनशील गेज की तरह कार्य करता है, जो स्वचालित रूप से पता लगा लेता है कि कब आगे का विभाजन नई जानकारी प्रकट करने के बजाय केवल रैंडम उतार-चढ़ाव का पीछा कर रहा है।

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

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

इसके विपरीत, थ्रेशोल्ड-आधारित नियम एक विभाजन से प्राप्त वास्तविक मूल्य को मापकर काम करता है। जैसे-जैसे पेड़ डेटा को छोटे टुकड़ों में काटता है, प्रत्येक नए कट से प्राप्त लाभ अंततः कम होता जाता है। एक सुचारू क्षेत्र में, लाभ तेजी से गिरता है, जो पेड़ को जल्दी रुकने का संकेत देता है और एक बड़ा बॉक्स छोड़ देता है। एक ऊबड़-खाबड़ क्षेत्र में, लाभ लंबे समय तक उच्च रहता है, जो पेड़ को बारीक विवरणों तक पहुँचने के लिए कटिंग जारी रखने के लिए प्रोत्साहित करता है। शोधकर्ताओं ने सिद्ध किया कि यह रुकने का बिंदु ठीक उसी स्थान पर सटीक भविष्यवाणी करने के लिए इष्टतम आकार के साथ मेल खाता है। उन्होंने दिखाया कि पेड़ ठीक तब विभाजित होना बंद कर देता है जब डेटा से प्राप्त सिग्नल बैकग्राउंड नॉइज़ से अविभाज्य हो जाता है, यह सुनिश्चित करते हुए कि अंतिम बॉक्स न तो बहुत बड़ा हो और न ही बहुत छोटा।

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

हालाँकि यह शोध पत्र एल्गोरिदम के सैद्धांतिक गारंटियों पर ध्यान केंद्रित करता है, लेकिन वास्तविक दुनिया के डेटा विश्लेषण के लिए इसके निहितार्थ स्पष्ट हैं। यह सुझाव देता है कि निर्णय वृक्षों की सफलता आकस्मिक नहीं है बल्कि एक गहरे सांख्यिकीय गुण में निहित है: सही रुकने के नियम द्वारा पेड़ की संरचना को डेटा की स्थानीय ज्यामिति के साथ संरेखित करने की क्षमता। यह सिद्ध करके कि 'मिनिमम इम्प्योरिटी डिक्रीज' (न्यूनतम अशुद्धि कमी) नियम स्थानीय भविष्यवाणी के लिए सटीकता की सर्वोत्तम दर प्राप्त करता है, शोधकर्ताओं ने इन मॉडलों की अनुभवजन्य सफलता के लिए एक ठोस सैद्धांतिक आधार प्रदान किया है। उनका कार्य उन सरल, अधिक कठोर रुकने के नियमों के उपयोग के विरुद्ध एक चेतावनी के रूप में भी कार्य करता है जो लागू करने में आसान लग सकते हैं लेकिन अंततः मॉडल को समस्या की वास्तविक जटिलता के अनुकूल होने से रोकते हैं।

शोधकर्ता केवल यह सिद्ध करने तक नहीं रुके कि सही नियम क्यों काम करता है; उन्होंने यह भी दिखाया कि गलत नियम क्यों विफल होता है। एक विस्तृत गणितीय तर्क के माध्यम से, उन्होंने प्रदर्शित किया कि रुकने के लिए एक एकल वैश्विक पैरामीटर (global parameter) दो अलग-अलग स्मूथनेस स्तरों वाले दो अलग-अलग बिंदुओं के बीच बायस (bias) और वेरिएंस (variance) के बीच के ट्रेड-ऑफ को एक साथ अनुकूलित नहीं कर सकता है। यह न्यूनतम लीफ साइज दृष्टिकोण की एक मौलिक सीमा है। प्रमाण एक विशिष्ट उदाहरणों का निर्माण करके आधारित है जहाँ एक ऊबड़-खाबड़ बिंदु के लिए इष्टतम बॉक्स का आकार एक सुचारू बिंदु के लिए इष्टतम बॉक्स के आकार से बहुत भिन्न होता है, जिससे यह असंभव हो जाता है कि एक ही वैश्विक बाधा दोनों को सही कर सके।

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

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