🔢 mathematics

Optimal training-conditional regret for online conformal prediction

यह शोध पत्र वितरण विचलन (distribution drift) वाले गैर-स्थिर डेटा स्ट्रीम्स के लिए मिनिमैक्स-इष्टतम ऑनलाइन कॉन्फॉर्मल प्रेडिक्शन एल्गोरिदम प्रस्तावित करता है, जो कैलिब्रेशन सेट्स को अनुकूल रूप से अपडेट करने के लिए ड्रिफ्ट डिटेक्शन का उपयोग करता है और इष्टतम प्रशिक्षण-सशर्त संचयी प्रतिफल (training-conditional cumulative regret) प्राप्त करने के लिए मॉडल स्थिरता का लाभ उठाता है।

मूल लेखक: Jiadong Liang, Zhimei Ren, Yuxin Chen

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

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

CC BY 4.0

मूल लेखक: Jiadong Liang, Zhimei Ren, Yuxin Chen

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

कल्पना कीजिए कि आप एक मौसम विज्ञान हैं। आपका काम केवल यह भविष्यवाणी करना नहीं है कि बारिश होगी या नहीं; आपका काम लोगों को एक कॉन्फिडेंस इंटरवल (विश्वास अंतराल) देना है। आप कहते हैं, "बारिश होने की 90% संभावना है, इसलिए छाता साथ रखें।"

मशीन लर्निंग की दुनिया में, इसे कॉन्फिडेन्शियल प्रेडिक्शन (Conformal Prediction) कहा जाता है। यह एक सुरक्षा जाल (सेफ्टी नेट) की तरह है जो हमें बताता है कि कंप्यूटर मॉडल अपने उत्तर के बारे में कितना आश्वस्त है। आमतौर पर, ये सुरक्षा जाल तब बहुत अच्छा काम करते हैं जब मौसम (डेटा) हर दिन एक जैसा रहता है।

लेकिन क्या होता है जब जलवायु बदल जाती है?

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

यहाँ उनके समाधान का विवरण दिया गया है, जिसे रोजमर्रा के उदाहरणों का उपयोग करके समझाया गया है।

1. समस्या: "पुराना नक्शा" (The "Stale Map")

कल्पना कीजिए कि आप जीपीएस (GPS) के साथ गाड़ी चला रहे हैं।

पुराना तरीका: आपका जीपीएस 2010 के नक्शे पर कैलिब्रेट किया गया था। यदि आज एक नया हाईवे खुलता है, तो आपका जीपीएस उसे नहीं जानता। वह आपको पुराने रास्ते पर चलने के लिए कहता रहेगा, जिससे आप भटक सकते हैं।
"रिग्रेट" (Regret) मीट्रिक: लेखक विफलता को मापने का एक नया तरीका पेश करते हैं। केवल यह पूछने के बजाय कि, "क्या आपने 10 वर्षों में औसतन सही उत्तर दिया?" (जो बहुत अस्पष्ट है), वे पूछते हैं: "हर एक क्षण में, आपका आत्मविश्वास (confidence) कितना गलत था?"
- यदि आपका जीपीएस कहता है "90% विश्वास" लेकिन वास्तव में आप 50% समय रास्ता भटक जाते हैं, तो यह उच्च रिग्रेट है।
- वे इस "रिग्रेट" को यथासंभव कम करना चाहते हैं, यह सुनिश्चित करते हुए कि जब आपको अनिश्चित होना चाहिए, तब आप बहुत अधिक आत्मविश्वासी न हों।

2. दो परिदृश्य

लेखक "मौसम परिवर्तन" के दो प्रकारों को संबोधित करते हैं:

अचानक आया तूफान (Change Points): डेटा अचानक बदल जाता है। एक पल धूप है, अगले ही पल तूफान है।
धीमा बदलाव (Smooth Drift): डेटा धीरे-धीरे बदलता है, जैसे मौसम का गर्मियों से शरद ऋतु की ओर बदलना।

3. समाधान: "DriftOCP" (एक स्मार्ट नेविगेटर)

लेखक दो मुख्य एल्गोरिदम प्रस्तावित करते हैं, जो इस बात पर निर्भर करते हैं कि "मौसम मॉडल" कैसे बनाया गया है।

परिदृश्य A: प्री-ट्रेन्ड मॉडल (एक निश्चित नक्शा)

कल्पना कीजिए कि आपके पास एक विशेषज्ञ द्वारा बनाया गया नक्शा है जिसे आप बदल नहीं सकते। आपको बस यह पता लगाना है कि आप उस नक्शे पर कहाँ हैं।

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

परिदृश्य B: लर्निंग मॉडल (एक सेल्फ-ड्राइविंग कार)

अब, कल्पना कीजिए कि नक्शा स्थिर नहीं है। कार चलते-चलते अपना नक्शा खुद अपडेट कर रही है, यानी वह सीख रही है। यह कठिन है क्योंकि आप उसी समय नक्शा बदलने की कोशिश कर रहे हैं जब आप उसे कैलिब्रेट भी कर रहे हैं।

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

4. यह क्यों महत्वपूर्ण है

पिछले तरीके एक ऐसे थर्मोस्टेट की तरह थे जो साल में केवल एक बार तापमान की जांच करता है। यदि जुलाई में घर गर्म हो जाता, तो थर्मोस्टेट को अगली जनवरी तक पता नहीं चलता।

यह शोध पत्र एक स्मार्ट थर्मोस्टेट बनाता है जो:

परिवर्तन का तुरंत पता लगाता है (Drift Detection)।
सेटिंग्स को तुरंत समायोजित करता है (Adaptive Calibration)।
गारंटी देता है कि आप कभी बहुत गर्म या बहुत ठंडे नहीं होंगे (Minimax Optimality)।

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

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

यह एक ऐसे नेविगेटर के बीच का अंतर है जो जिद्दी होकर पुराने नक्शे का पालन करता है और एक ऐसे नेविगेटर के बीच का अंतर है जो खिड़की से बाहर देखता है, देखता है कि रास्ता बदल गया है, और तुरंत नया मार्ग बना लेता है।

यहाँ लियांग, रेन और चेन के शोध पत्र "Optimal training-conditional regret for online conformal prediction" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या का निरूपण (Problem Formulation)

यह शोध पत्र गैर-स्थिर (non-stationary) वातावरण में ऑनलाइन कॉन्फॉर्मल प्रेडिक्शन (OCP) को संबोधित करता है जहाँ डेटा वितरण समय के साथ बदलता रहता है।

सेटिंग: एक अनुक्रमिक डेटा स्ट्रीम $\{(X_t, Y_t)\}_{t=1}^T$ उत्पन्न की जाती है जो एक गतिशील प्रक्रिया द्वारा संचालित होती है जहाँ $(X_t, Y_t)$ का वितरण $D_t$ समय के साथ बदलता है। एल्गोरिदम को पिछले डेटा और वर्तमान फीचर $X_t$ का उपयोग करके प्रतिक्रिया $Y_t$ के लिए एक प्रेडिक्शन सेट $C_t(X_t)$ का निर्माण करना चाहिए।
लक्ष्य: प्रत्येक समय चरण $t$ पर एक लक्षित मिसकवरेज स्तर $\alpha$ (अर्थात $P(Y_t \in C_t(X_t)) \approx 1-\alpha$ ) प्राप्त करना।
पूर्व कार्य में अंतराल (The Gap in Prior Work): मौजूदा OCP साहित्य मुख्य रूप से निम्नलिखित पर केंद्रित है:
1. एडवर्सरियल सेटिंग्स (Adversarial settings): जहाँ $D_t$ पर कोई संरचना नहीं मानी जाती।
2. दीर्घकालिक मार्जिनल कवरेज (Long-term marginal coverage): यह सुनिश्चित करना कि समय-औसत कवरेज $1-\alpha$ के अभिसरण (converge) होता है।
- आलोचना: दीर्घकालिक कवरेज "रिक्त" (vacuous) समाधानों की अनुमति देता है (उदाहरण के लिए, पूरे स्पेस $\mathbb{R}$ को प्रायिकता $1-\alpha$ के साथ प्रेडिक्ट करना और प्रायिकता $\alpha$ के साथ खाली सेट $\emptyset$ प्रेडिक्ट करना) जो विशिष्ट समय चरणों पर सूचनात्मक अंतराल प्रदान करने में विफल रहते हैं। इसके अलावा, एडवर्सरियल रिग्रेट मेट्रिक्स में अक्सर सांख्यिकीय वैधता के साथ सीधा संबंध नहीं होता है।
प्रस्तावित मीट्रिक: लेखक ट्रेनिंग-कंडीशनल क्युमुलेटिव रिग्रेट (Training-Conditional Cumulative Regret) पेश करते हैं:
$\text{regret}_T = \sum_{t=1}^T \mathbb{E} \left[ \left| P(Y_t \in C_t(X_t) \mid \text{past data}, \text{internal randomness}) - (1-\alpha) \right| \right]$
यह मीट्रिक प्रत्येक चरण पर लक्षित कवरेज से कंडीशनल कवरेज प्रायिकता के विचलन को मापता है, जिसे समय के साथ एकत्रित किया जाता है। यह सुनिश्चित करता है कि एल्गोरिदम अब तक देखे गए विशिष्ट डेटा के लिए कैलिब्रेटेड है, न कि केवल औसत पर।

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

शोध पत्र स्कोर फंक्शन ट्रेनिंग के विभिन्न परिदृश्यों के लिए दो अलग-अलग एल्गोरिदम प्रस्तावित करता है, जो कैलिब्रेशन सेट्स को अनुकूल रूप से अपडेट करने के लिए ड्रिफ्ट डिटेक्शन (drift detection) का लाभ उठाते हैं।

A. परिदृश्य 1: प्रीट्रेन्ड स्कोर्स (Pretrained Scores - DriftOCP)

संदर्भ: नॉन-कन्फॉर्मिटी स्कोर $s_t(\cdot, \cdot)$ एक स्वतंत्र डेटासेट पर प्री-ट्रेन किए गए हैं और ऑनलाइन स्ट्रीम से स्वतंत्र रहते हैं या विकसित होते हैं। यह स्प्लिट कॉन्फॉर्मल (Split Conformal) विधियों की नकल करता है।
एल्गोरिदम (DriftOCP):
1. ड्रिफ्ट डिटेक्शन: एक सबरूटीन DriftDetect का उपयोग करता है जो सांख्यिकीय रूप से महत्वपूर्ण विचलन की जांच के लिए एक टाइम विंडो $[t_0, t]$ को स्कैन करता है। यह जाँचता है कि क्या सामान्यीकृत संचयी विचलन थ्रेशोल्ड $\sigma$ से अधिक है।
2. स्टेज-राउंड डिकम्पोजिशन: टाइमलाइन को "स्टेज" (ड्रिफ्ट डिटेक्शन द्वारा ट्रिगर) और "राउंड" (ज्यामितीय रूप से बढ़ती लंबाई, $3^r$ ) में विभाजित किया गया है।
3. अनुकूली कैलिब्रेशन (Adaptive Calibration): एक स्टेज के भीतर, एल्गोरिदम स्टेशनैरिटी (stationarity) मानता है। यह पिछले राउंड के डेटा का उपयोग करके क्वांटाइल थ्रेसहोल्ड $q$ को अपडेट करता है। यदि ड्रिफ्ट का पता चलता है, तो एक नया स्टेज शुरू होता है और कैलिब्रेशन सेट को रीसेट कर दिया जाता है।
हैंडल किए गए ड्रिफ्ट प्रकार:
- चेंज-पॉइंट (Change-point): वितरण में अचानक बदलाव।
- स्मूथ ड्रिफ्ट (Smooth Drift): वितरण का निरंतर विकास (संचयी भिन्नता द्वारा सीमित)।

B. परिदृश्य 2: एडेप्टिवली ट्रेन किए गए स्कोर्स (Adaptively Trained Scores - DriftOCP-full)

संदर्भ: प्रेडिक्टिव मॉडल और नॉन-कन्फॉर्मिटी स्कोर दोनों को पिछले अवलोकनों का उपयोग करके ऑनलाइन प्रशिक्षित किया जाता है। इसके लिए डेटा स्प्लिटिंग की अक्षमताओं से बचने के लिए फुल कॉन्फॉर्मल (Full Conformal) विधियों की आवश्यकता होती है।
चुनौती: ऑनलाइन लर्निंग एल्गोरिदम (जैसे SGD) अक्सर शास्त्रीय फुल कॉन्फॉर्मल वैधता के लिए आवश्यक परम्यूटेशन सिमेट्री (permutation symmetry) का उल्लंघन करते हैं।
एल्गोरिदम (DriftOCP-full):
1. स्टेबिलिटी धारणा (Stability Assumption): परम्यूटेशन सिमेट्री के बजाय, लेखक यह मानते हैं कि लर्निंग एल्गोरिदम स्टेबल है (ट्रेनिंग डेटा में छोटे बदलाव भविष्यवाणियों में छोटे बदलाव लाते हैं) और कंडीशनल रिस्पॉन्स डिस्ट्रीब्यूशन लिप्सचिट्ज निरंतर (Lipschitz continuous) है।
2. ड्रिफ्ट डिटेक्शन: DriftDetect+ का उपयोग करता है, जो गैर-स्थिरता का पता लगाने के लिए सीधे प्रेडिक्शन सेट्स के कवरेज की निगरानी करता है।
3. फुल कॉन्फॉर्मल निर्माण: प्रत्येक राउंड में, मॉडल को वर्तमान राउंड से पहले के सभी डेटा पर प्रशिक्षित किया जाता है, और कैलिब्रेशन सेट में ठीक पिछला राउंड शामिल होता है।
मुख्य नवाचार: यह सिद्ध करता है कि स्टेबिलिटी धारणाओं के तहत, फुल कॉन्फॉर्मल विधियाँ परम्यूटेशन सिमेट्री के बिना भी ट्रेनिंग-कंडीशनल वैधता प्राप्त कर सकती हैं।

3. मुख्य योगदान (Key Contributions)

नया प्रदर्शन मीट्रिक: ड्रिफ्ट के तहत OCP के मूल्यांकन के लिए ट्रेनिंग-कंडीशनल क्युमुलेटिव रिग्रेट को एक मानक के रूप में औपचारिक रूप दिया, और तर्क दिया कि यह दीर्घकालिक मार्जिनल कवरेज या एडवर्सरियल रिग्रेट से बेहतर है।
मिनिमैक्स-ऑप्टिमल एल्गोरिदम:
- Pretrained Scores के लिए: DriftOCP चेंज-पॉइंट्स के लिए $\tilde{O}(\sqrt{(N_{cp}+1)T})$ और स्मूथ ड्रिफ्ट के लिए $\tilde{O}(\sqrt{T} + K_{ST}^{1/3}T^{2/3})$ का रिग्रेट बाउंड प्राप्त करता है (जहाँ $K_{ST}$ संचयी KS डिस्टेंस है)।
- Adaptively Trained Scores के लिए: DriftOCP-full स्टेबिलिटी धारणाओं के तहत समान बाउंड प्राप्त करता है (KS डिस्टेंस के स्थान पर टोटल वेरिएशन डिस्टेंस का उपयोग करता है)।
मिनिमैक्स लोअर बाउंड्स (Minimax Lower Bounds): लेखक दोनों सेटिंग्स के लिए मिलान करने वाले लोअर बाउंड्स निकालते हैं।
- महत्वपूर्ण रूप से, वे $K$ -इंटरवल प्रेडिक्शन सेट्स तक सीमित फुल कॉन्फॉर्मल सेटिंग के लिए एक लोअर बाउंड स्थापित करते हैं, जो दर्शाता है कि प्रस्तावित एल्गोरिदम लॉगरिदमिक कारकों तक इष्टतम (optimal) हैं।
फुल कॉन्फॉर्मल के लिए सैद्धांतिक गारंटी: स्टेबल लर्नर्स का उपयोग करने वाले बैच फुल कॉन्फॉर्मल विधियों के लिए एक नई ट्रेनिंग-कंडीशनल कवरेज गारंटी सिद्ध करता है (प्रपोजिशन 4.1), जो एक्सचेंजैबिलिटी और परम्यूटेशन सिमेट्री से आगे बढ़ता है।
क्षितिज-मुक्त और कुशल (Horizon-Free & Efficient): इन एल्गोरिदमों को समय क्षितिज $T$ या ड्रिफ्ट पॉइंट्स की संख्या के पूर्व ज्ञान की आवश्यकता नहीं होती है, और वे गणनात्मक रूप से हल्के (विंडो साइज के रैखिक) हैं।

4. परिणाम (Results)

सैद्धांतिक (Theoretical):
- रिग्रेट बाउंड्स मिनिमैक्स लोअर बाउंड्स से मेल खाते हैं, जो यह सिद्ध करते हैं कि एल्गोरिदम मिनिमैक्स अर्थ में इष्टतम हैं।
- बाउंड्स स्पष्ट रूप से समय क्षितिज $T$ , ड्रिफ्ट की मात्रा (चेंज पॉइंट्स की संख्या या संचयी भिन्नता), और प्रेडिक्शन सेट्स की जटिलता के बीच ट्रेड-ऑफ को मात्रात्मक रूप से दर्शाते हैं।
अनुभवजन्य (Empirical):
- Pretrained Scores: अचानक वेरिएंस शिफ्ट और स्मूथ बायस ड्रिफ्ट के प्रयोगों में, DriftOCP एडैप्टिव कॉन्फॉर्मल इन्फरेंस (ACI) से काफी बेहतर प्रदर्शन करता है। ACI स्टेप-साइज़ के ट्रेड-ऑफ (तेजी से अनुकूलन बनाम स्थिरता) के साथ संघर्ष करता है, जबकि DriftOCM स्टेशनरी अवधि के दौरान स्थिरता बनाए रखते हुए शिफ्ट्स के प्रति तेजी से अनुकूलित होता है।
- Adaptively Trained Scores: मॉडल अपडेट के लिए ऑनलाइन SGD का उपयोग करते समय, DriftOCP-full फिक्स्ड प्रीट्रेन्ड मॉडल्स या मॉडल-फ्री अप्रोच की तुलना में स्थिर कवरेज के साथ संकीर्ण प्रेडिक्शन इंटरवल बनाता है। यह मीन और वेरिएंस शिफ्ट के तहत वेल-स्पेसिफाइड और मिसस्पेसिफाइड लीनियर मॉडल्स दोनों को सफलतापूर्वक संभालता है।

5. महत्व (Significance)

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