📊 statistics

Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference

यह शोध पत्र एनीटाइम-वैलिड इन्फरेंस (anytime-valid inference) का उपयोग करके ऑनलाइन डिसीजन ट्रीज़ में स्प्लिट सिलेक्शन को सुधारने के लिए एक सिद्धांतपूर्ण विधि प्रस्तुत करता है, जो मौजूदा होफडिंग ट्री (Hoeffding Tree) वेरिएंट्स की सांख्यिकीय अमान्यता को दूर करते हुए गलत स्प्लिट्स के विरुद्ध कठोर गारंटी प्रदान करता है और स्थिर एवं गैर-स्थिर डेटा स्ट्रीम्स दोनों में भविष्य कहनेवाला प्रदर्शन (predictive performance) में सुधार करने के साथ-साथ ट्री के आकार को कम करता है।

मूल लेखक: Salim I. Amoukou, Saumitra Mishra, Manuela Veloso

प्रकाशित 2026-06-01

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

CC BY 4.0

मूल लेखक: Salim I. Amoukou, Saumitra Mishra, Manuela Veloso

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

कल्पना कीजिए कि आप एक माली हैं जो पौधों की एक विशाल, कभी न खत्म होने वाली धारा को छाँटने के लिए एक 'डिसीजन ट्री' (decision tree) उगाने की कोशिश कर रहे हैं। आपका लक्ष्य हर शाखा बिंदु (branch point) पर यह तय करना है कि क्या आप पौधों को दो समूहों में विभाजित करेंगे (जैसे, "पानी की आवश्यकता है" बनाम "धूप की आवश्यकता है") या उन्हें एक साथ रहने देंगे।

डेटा साइंस की दुनिया में, ऑनलाइन डिसीजन ट्री (Online Decision Trees) इसी तरह काम करते हैं। वे डेटा के आने के साथ-साथ सीखते हैं। इसे करने का सबसे लोकप्रिय तरीका होफिंग ट्री (Hoeffding Tree) कहलाता है।

समस्या: "जल्दबाजी करने वाला माली"

पारंपरिक होफिंग ट्री एक ऐसे माली की तरह काम करता है जो बहुत बड़ी जल्दी में है। वह अब तक देखे गए पौधों को देखता है और एक विभाजन (split) करने का निर्णय लेने के लिए एक गणितीय नियम (एक "कंसंट्रेशन इनइक्वालिटी") का उपयोग करता है: "ठीक है, मैं 95% आश्वस्त हूँ कि यह विभाजन अच्छा है। चलो, कट लगाते हैं!"

यह शोध पत्र तर्क देता है कि इस दृष्टिकोण में एक घातक दोष है: यह मान लेता है कि माली पौधों की एक निश्चित संख्या देखने के बाद रुक जाता है।

लेकिन वास्तव में, माली धारा पर नज़र रखता रहता है। यदि पहले 10 पौधे भ्रमित करने वाले लगते हैं, तो माली 10 और पौधों का इंतज़ार करता है। यदि वे अभी भी भ्रमित करने वाले हैं, तो वह 100 और का इंतज़ार करता है। इसे "डेटा-डिपेंडेंट स्टॉपिंग रूल" (data-dependent stopping rule) कहा जाता है।

लेखक समझाते हैं कि जब आप "थोड़े और सबूत" के लिए इंतज़ार करते रहते हैं जबकि डेटा बहता रहता है, तो पुराने गणितीय गारंटी टूट जाते हैं। यह एक सिक्का उछालने जैसा है। यदि आप 10 बार सिक्का उछालते हैं, तो आपको 7 बार 'हेड्स' मिल सकते हैं। लेकिन यदि आप तब तक उछालते रहते हैं जब तक कि आपको लगातार 7 'हेड्स' न मिल जाएं, तो अंततः आपको वे मिल ही जाएंगे, भले ही सिक्का निष्पक्ष हो। पारंपरिक विधि सोचती है कि उसने एक "असली" पैटर्न खोज लिया है, लेकिन वास्तव में वह केवल इसलिए सफल हुई क्योंकि उसने बहुत देर तक इंतज़ार किया और भाग्यशाली रही। इससे गलत विभाजन (false splits) होते हैं—पेड़ को गलत जगह से काटना, जो मॉडल की सटीकता को खराब कर देता है।

समाधान: "एनीटाइम-वैलिड" (Anytime-Valid) माली

लेखक एक नई विधि प्रस्तावित करते हैं जिसे "एनीटाइम-वैलिड इन्फरेंस" (Anytime-Valid Inference) कहा जाता है। वे "जल्दबाजी वाले" नियम को बेटिंग (betting - दांव लगाने) पर आधारित एक प्रणाली से बदलते हैं।

एक खेल की कल्पना करें जहाँ आप इस विचार के खिलाफ दांव लगा रहे हैं कि "यह विभाजन बेकार है।"

सेटअप: आप "$1 का आत्मविश्वास धन" (confidence money) से शुरुआत करते हैं।
दांव: हर बार जब एक नया पौधा आता है, तो आप जाँचते हैं: क्या नया विभाजन पुराने विभाजन की तुलना में पौधे की बेहतर भविष्यवाणी करता है?
- यदि नया विभाजन जीतता है, तो आप थोड़ा पैसा जीतते हैं (आपका आत्मविश्वास बढ़ता है)।
- यदि नया विभाजन हारता है, तो आप थोड़ा पैसा हारते हैं।
नियम: आप पेड़ को तभी काटते हैं (विभाजन करते हैं) जब आपका "आत्मविश्वास धन" इतना बढ़ जाता है कि यह सांख्यिकीय रूप से असंभव हो कि एक "बेकार विभाजन" शुद्ध भाग्य के दम पर इतना पैसा जीत गया हो।

क्योंकि यह बेटिंग सिस्टम इस आधार पर डिज़ाइन किया गया है कि आप कब भी रुकने का निर्णय लें, यह तब भी वैध रहता है जब आप अनंत काल तक स्ट्रीम देखते रहते हैं। यह "लकी स्ट्रीक" (भाग्यशाली दौर) की समस्या को रोकता है।

व्यवहार में यह कैसे काम करता है

शोध पत्र इस बेटिंग गेम को चलाने के दो तरीके पेश करता है:

बेटिंग मेथड (AVTB): यह "यूनिवर्सल पोर्टफोलियो" रणनीति का उपयोग करता है, जो एक स्मार्ट निवेशक की तरह है जो कई अलग-अलग रणनीतियों पर अपने दांव फैलाता है ताकि वह जीत सके, भले ही उसे यह न पता हो कि कौन सी विशिष्ट रणनीति सबसे अच्छी काम करेगी।
कॉन्फिडेंस मेथड (AVTCS): यह "कॉन्फिडेंस सीक्वेंस" का उपयोग करता है, जो डेटा के चारों ओर एक सुरक्षा जाल (safety net) बनाने जैसा है जो अधिक डेटा आने के साथ-साथ और भी सटीक होता जाता है, यह सुनिश्चित करते हुए कि सत्य हमेशा उस जाल के भीतर रहे।

परिणाम: स्मार्ट और छोटे पेड़

लेखकों ने 12 अलग-अलग वास्तविक दुनिया के डेटा स्ट्रीम (जैसे बाइक रेंटल, उड़ान में देरी और ऊर्जा उपयोग की भविष्यवाणी करना) पर इस नई विधि का परीक्षण किया।

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

मुख्य निष्कर्ष

यह शोध पत्र यह दावा नहीं करता कि यह सीधे जलवायु परिवर्तन को हल करता है या बीमारियों का इलाज करता है। इसके बजाय, यह स्ट्रीमिंग डेटा से सीखने के तरीके में एक मौलिक गणितीय बग को ठीक करता है। "फिक्स्ड-सैंपल" नियमों से "एनीटाइम-वैलिड" बेटिंग नियमों की ओर स्विच करके, उन्होंने ऐसे डिसीजन ट्री बनाने का एक तरीका बनाया जो सांख्यिकीय रूप से ईमानदार, अधिक सटीक और केवल निर्णय लेने में देरी करने के कारण गलतियाँ करने से मुक्त हैं।

तकनीकी सारांश: ऑन्लाइन डिसीजन ट्रीज़ में स्प्लिट सिलेक्शन को 'एनीटाइम-वैलिड इन्फरेंस' के माध्यम से सुधारना

1. समस्या की परिभाषा

यह शोध पत्र होफडिंग ट्रीज़ (HT) में एक मौलिक सांख्यिकीय दोष को संबोधित करता है, जो डेटा स्ट्रीम लर्निंग (जैसे, अडैप्टिव रैंडम फॉरेस्ट) में एन्सेम्बल मेथड्स के लिए एक मानक बेस लर्नर है। जबकि HTs ने होफडिंग या मैकडिर्मिड जैसी एकाग्रता असमानताओं (concentration inequalities) का उपयोग करके यह निर्धारित करने के लिए कि एक स्प्लिट सांख्यिकीय रूप से महत्वपूर्ण है या नहीं, पेड़ों को क्रमिक रूप से विकसित करने में अनुभवजन्य सफलता प्राप्त की है, उनके सैद्धांतिक आश्वासन व्यवहार में अमान्य हैं।

मुख्य मुद्दा ऑप्शनल स्टॉपिंग प्रॉब्लम (optional stopping problem) है। मानक एकाग्रता असमानताएं एक निश्चित नमूना आकार (fixed sample size) मानती हैं। हालाँकि, HTs एक डेटा-निर्भर स्टॉपिंग नियम का उपयोग करते हैं: वे अशुद्धता अनुमानों (impurity estimates) की निरंतर निगरानी करते हैं और जैसे ही एक थ्रेशोल्ड पार होता है, वे एक स्प्लिट के लिए प्रतिबद्ध होते हैं। यह "ऑप्शनल कंटीन्यूएशन" निश्चित-समय वाले बाउंड्स (fixed-time bounds) को अमान्य कर देता है, जिससे गलत स्प्लिट्स की संभावना बढ़कर एक तक बढ़ सकती है। इसके अलावा, मौजूदा सुधार अक्सर स्वतंत्र, स्थिर डेटा की धारणा रखते हैं, जबकि HTs को अक्सर एन्सेम्बल फ्रेमवर्क के भीतर गैर-स्थिर (non-stationary), आश्रित डेटा स्ट्रीम में तैनात किया जाता है।

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

लेखक सेफ, एनीटाइम-वैलिड इन्फरेंस (SAVI) पर आधारित एक सिद्धांतपूर्ण विकल्प प्रस्तावित करते हैं, विशेष रूप से टेस्टिंग बाय बेटिंग (Testing by Betting) और कॉन्फिडेंस सीक्वेंस (CS) का उपयोग करते हुए।

स्प्लिट सिलेक्शन का पुनर्गठन: उम्मीदवारों वाले स्प्लिट्स की तुलना एक-दूसरे से करके वैश्विक इष्टतम (global optimum) खोजने के बजाय (जो गैर-स्थिर सेटिंग्स में अपरिभाषित हो सकता है), यह विधि स्प्लिट सिलेक्शन को एक ऑनलाइन मॉडल तुलना के रूप में फ्रेम करती है। यह परीक्षण करता है कि क्या एक "चैलेंजर" मॉडल (एक उम्मीदवार के अनुसार लीफ स्प्लिट) प्रेक्षित डेटा के आधार पर "इन्कंबेंट" मॉडल (अविभाजित लीफ) से स्पष्ट रूप से बेहतर प्रदर्शन करता है।
लॉस फंक्शन्स (Loss Functions): भविष्य कहनेवाला प्रदर्शन (predictive performance) बाउंडेड लॉस फंक्शन्स (जैसे, लॉग लॉस या ब्रियर स्कोर) का उपयोग करके मूल्यांकित किया जाता है, जो एंट्रॉपी और गिनी इम्प्योरिटी के एनालॉग के रूप में कार्य करते हैं।
हाइपोथीसिस टेस्टिंग:
- स्ट्रॉन्ग नल ( $H_0$ ): चैलेंजर किसी भी समय इन्कंबेंट से बेहतर प्रदर्शन नहीं करता है ( $\delta_t \le 0$ )।
- वीक नल ( $H_{w,0}$ ): चैलेंजर समय के साथ औसतन इन्कंबेंट से बेहतर प्रदर्शन नहीं करता है।
- यह पेपर मुख्य रूप से स्ट्रॉन्ग नल को अपनाता है, जो एक ही डेटा स्ट्रीम पर निकट रूप से संबंधित एल्गोरिदम की तुलना करने के लिए सिफारिशों के अनुरूप है।
टेस्टिंग तंत्र:
1. बेटिंग-आधारित टेस्ट (AVTB): यह हाइपोथीसिस टेस्टिंग को एक बेटिंग गेम के रूप में व्याख्यायित करता है। एक बेट्टर लॉस डिफरेंस ( $\Delta_t$ ) के साइन पर दांव लगाता है। नल के तहत, कोई भी रणनीति सकारात्मक अपेक्षित वृद्धि (positive expected growth) नहीं दे सकती। विधि जेफ्रीज़ प्रायर (Jeffreys prior) के साथ एक यूनिवर्सल पोर्टफोलियो (UP) रणनीति का उपयोग करती है ताकि वेल्थ ( $W_t$ ) को अपडेट किया जा सके। यदि $W_t > 1/\alpha$ हो जाता है, तो नल को खारिज कर दिया जाता है, और स्प्लिट को कमिट कर दिया जाता है। यह प्रक्रिया एक नॉन-नेगेटिव सुपरमार्टिंगेल (nonnegative supermartingale) है, जो विले के असमानता (Ville's inequality) के माध्यम से मनमाने स्टॉपिंग टाइम के तहत वैधता सुनिश्चित करती है।
2. कॉन्फिडेंस सीक्वेंस टेस्ट (AVTCS): औसत लाभ के लिए एम्पिरिकल बर्नस्टीन कॉन्फिडेंस सीक्वेंस के लिए औसत लाभ के निचले स्तर (lower bound) के शून्य से ऊपर जाने पर स्टॉपिंग टाइम को परिभाषित करता है।
ग्लोबल एरर कंट्रोल: समय के साथ उत्पन्न होने वाले संभावित अनंत कैंडिडेट स्प्लिट्स को संभालने के लिए, लेखक सभी परीक्षणों में महत्व स्तरों ( $\alpha_{v,c}$ ) को इस प्रकार आवंटित करते हैं कि उनका योग एक वैश्विक $\alpha$ द्वारा सीमित हो। यह सुनिश्चित करता है कि पेड़ के जीवनकाल में किसी भी गलत स्प्लिट के होने की संभावना अधिकतम $\alpha$ है।

3. प्रमुख योगदान

वैध स्प्लिट मानदंड: एक ऐसा स्प्लिट मानदंड जो मनमाने डेटा-निर्भर स्टॉपिंग नियमों के तहत सांख्यिकीय रूप से वैध रहता है, जो गैर-स्थिर और आश्रित दोनों डेटा स्ट्रीम पर लागू होता है।
फाइनाइट कमिटमेंट: प्रमाण कि यदि कोई उम्मीदवार स्प्लिट निरंतर भविष्य कहनेवाला लाभ प्रदर्शित करता है, तो प्रक्रिया $\tilde{O}(\log(1/\alpha)/\Delta^2)$ की दर से परिमित समय में स्प्लिट को कमिट करती है।
मोनोटोनिक रिस्क रिडक्शन: स्थिर i.i.d. डेटा के तहत, तैनात किए गए पेड़ के अपेक्षित प्रेडिक्टिव लॉस को समय के साथ गैर-बढ़ता हुआ दिखाया गया है और प्रत्येक स्प्लिट कमिट पर यह स्पष्ट रूप से सुधरता है।
ड्रॉप-इन रिप्लेसमेंट: यह विधि अडैप्टिव रैंडम फॉरेस्ट जैसे मौजूदा एन्सेम्बल फ्रेमवर्क के भीतर होफडिंग ट्रीज़ के लिए एक प्रत्यक्ष प्रतिस्थापन के रूप में कार्य करती है, जिससे एक "एनीटाइम-वैलिड फॉरेस्ट" (AVF) बनता है।

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

लेखकों ने अपने मेथड (AVT) और उनके एन्सेम्बल वेरिएंट (AVF) का 12 वास्तविक दुनिया की डेटा स्ट्रीम (6 रिग्रेशन, 6 क्लासिफिकेशन) और सिंथेटिक बेंचमार्क पर मूल्यांकन किया।

प्रदर्शन:
- स्थिरता (Stability): मानक होफडिंग ट्रीज़ के विपरीत, जो स्थिर डेटा पर भी बार-बार सामान्यीकरण प्रदर्शन (generalization performance) में अचानक गिरावट दिखाते हैं, एनीटाइम-वैलिड मेथड्स ने स्थिर, मोनोटोन सुधार दिखाया।
- सटीकता (Accuracy): AVTB (बेटिंग-आधारित) आम तौर पर मानक HT से बेहतर रहा और कई स्ट्रीम्स पर ARF बेसलाइन के बराबर या उससे बेहतर प्रदर्शन किया। एन्सेम्बल AVF ने लगभग सभी डेटासेट्स पर मानक ARF को लगातार पछाड़ दिया।
- मॉडल का आकार: प्रस्तावित विधियों ने HT और ARF की तुलना में काफी छोटे पेड़ (कम नोड्स/लीव्स) बनाए जबकि उच्च या तुलनीय प्रेडिक्टिव प्रदर्शन प्राप्त किया।
कंप्यूटेशनल लागत:
- इन्फरेंस समय HT के समान बना रहा।
- अपडेट समय शैडो चैलेंजर स्टैटिस्टिक्स और वेल्थ कैलकुलेशन के रखरखाव के कारण अधिक था लेकिन व्यावहारिक सीमाओं (मिलीसेकंड प्रति इंस्टेंस) के भीतर रहा।
- लेखक नोट करते हैं कि AVF अक्सर उथले पेड़ (shallower trees) सीखता है, जिससे अपडेट के लिए आवश्यक नोड्स की संख्या कम हो जाती है, जो कंप्यूटेशनल ओवरहेड को कम करता है।

5. महत्व और दावे

यह पेपर मौजूदा ऑनलाइन डिसीजन ट्री मेथड्स की एक "मौलिक सीमा" को हल करने का दावा करता है। फिक्स्ड-सैंपल-साइज़ असमानताओं के बजाय एनीटाइम-वैलिड इन्फरेंस को अपनाकर, लेखक सांख्यिकीय गारंटी प्रदान करते हैं जो उन स्थितियों (डेटा-डिपेंडेंट स्टॉपिंग, नॉन-स्टेशनैरिटी) में भी मान्य हैं जहाँ पिछले तरीके विफल हो जाते हैं।

महत्व निम्नलिखित में निहित है:

सैद्धांतिक कठोरता (Theoretical Rigor): ऑप्शनल स्टॉपिंग के तहत ऑनलाइन ट्रीज़ में स्प्लिट सिलेक्शन के लिए पहला वैध सांख्यिकीय आश्वासन प्रदान करना।
व्यावहारिक मजबूती (Practical Robustness): यह प्रदर्शित करना कि सांख्यिकीय वैधता, अनुभवजन्य स्थिरता में अनुवादित होती है, जिससे मानक HTs में देखी गई प्रदर्शन की "कोलेप्स" (collapse) को रोका जा सकता है।
दक्षता (Efficiency): बेहतर प्रेडिक्टिव प्रदर्शन के साथ छोटे, अधिक संक्षिप्त मॉडल प्राप्त करना, जो यह सुझाव देता है कि मानक HTs में गलत स्प्लिट निर्णयों द्वारा पेश किया गया "शोर" अनावश्यक पेड़ विकास की ओर ले जाता है।

लेखक निष्कर्ष निकालते हैं कि उनका फ्रेमवर्क होफडिंग ट्रीज़ के लिए एक मजबूत, ड्रॉप-इन रिप्लेसमेंट के रूप में कार्य करता है, जो प्रभावी रूप से डेटा स्ट्रीम माइनिंग के सबसे व्यापक रूप से उपयोग किए जाने वाले एल्गोरिदम में से एक की सांख्यिकीय नींव को ठीक करता है।