🤖 machine learning

Online Prediction of Stochastic Sequences with High Probability Regret Bounds

यह शोध पत्र ज्ञात परिमित समय क्षितिज (finite time horizon) वाले स्टोकेस्टिक अनुक्रमों के सार्वभौमिक पूर्वानुमान (universal prediction) के लिए उच्च-संभाव्यता लुप्त होने वाले रिग्रेट बाउंड्स (high-probability vanishing regret bounds) स्थापित करता है, जो $\mathcal{O}(T^{-1/2} \delta^{-1/2})$ की अभिसरण दर (convergence rate) प्रदर्शित करता है और यह सिद्ध करता है कि अतिरिक्त धारणाओं के बिना आत्मविश्वास पैरामीटर (confidence parameter) $\delta$ पर निर्भरता में सुधार नहीं किया जा सकता है।

मूल लेखक: Matthias Frey, Jonathan H. Manton, Jingge Zhu

प्रकाशित 2026-02-19

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

CC BY 4.0

मूल लेखक: Matthias Frey, Jonathan H. Manton, Jingge Zhu

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

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

कंप्यूटर विज्ञान और गणित की दुनिया में, इसे ऑनलाइन प्रेडिक्शन (Online Prediction) कहा जाता है। आप "लर्नर" (सीखने वाले) हैं, मौसम एक "स्टोकेस्टिक सीक्वेंस" (एक यादृच्छिक प्रक्रिया) है, और आपका लक्ष्य अपने "रिग्रेट" (पछतावे/त्रुटि) को कम करना है।

रिग्रेट (Regret) सरल शब्दोंत: यह अंतर है कि आपने कैसा प्रदर्शन किया और आप कितना अच्छा कर सकते थे यदि आपके पास एक जादुई क्रिस्टल बॉल होती जो शुरुआत से ही मौसम के सटीक नियमों को जानती।

समस्या: अपेक्षा बनाम वास्तविकता

दशकों से, गणितज्ञों ने इस समस्या का अध्ययन किया है। वे सिद्ध कर सके कि, औसत रूप से, यदि आप इस खेल को पर्याप्त लंबे समय तक खेलते हैं, तो आपका रिग्रेट लगभग शून्य हो जाएगा। वे कह सकते थे, "यदि आप इस खेल को 1,000 बार खेलते हैं, तो आपके द्वारा की जाने वाली औसत गलती बहुत मामूली होगी।"

लेकिन वास्तविक जीवन में, "औसत रूप से" हमेशा पर्याप्त नहीं होता।

उपमा: एक पुल इंजीनियर की कल्पना करें जो कहता है, "औसत रूप से, यह पुल ठीक रहता है।" यह बहुत अच्छा है, लेकिन यदि किसी विशेष दिन पुल के गिरने की 1% संभावना है, तो यह एक आपदा है। आप एक "औसत" गारंटी नहीं चाहते; आप एक उच्च-संभाव्यता गारंटी (high-probability guarantee) चाहते हैं। आप चाहते हैं कि लगभग निश्चित रूप से, आप बड़ी गलती न करें।

यह शोध पत्र पूछता है: क्या हम यह सिद्ध कर सकते हैं कि हमारी भविष्यवाणी रणनीति उच्च संभाव्यता के साथ अच्छी तरह से काम करेगी, न कि केवल औसत रूप से?

समाधान: एक नया सुरक्षा जाल

लेखक (मैथियास फ्रे, जोनाथन मैंटन और जिंगगे झू) कहते हैं कि हाँ, लेकिन एक शर्त के साथ।

उन्होंने एक नया गणितीय "सुरक्षा जाल" विकसित किया है। उन्होंने सिद्ध किया कि आप वास्तव में यह गारंटी दे सकते हैं कि बहुत उच्च संभाव्यता (मान लीजिए 99% या 99.9%) के साथ आपका रिग्रेट कम रहेगा।

हालाँकि, इस उच्च स्तर की निश्चितता प्राप्त करने के लिए, गलत होने का "दंड" औसत मामले की तुलना में थोड़ा अधिक है।

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

यह शोध पत्र दिखाता है कि यह नया सुरक्षा जाल सबसे अच्छा है जिसे आप मौसम के बारे में अतिरिक्त, अवास्तविक धारणाएं बनाए बिना बना सकते हैं।

"मिसमैच्ड" (Mismatched) प्रेडिक्शन ट्रिक

इसे हल करने के लिए, लेखकों ने मिसमैच्ड प्रेडिक्शन (Mismatched Prediction) नामक एक चतुर ट्रिक का उपयोग किया।

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

पुराना तरीका: शोधकर्ताओं ने गणना की कि आपका अनुमान मॉडल सत्य की तुलना में औसतन कितना खराब है।
नया तरीका: लेखकों ने गणना की कि आपका अनुमान मॉडल सत्य की तुलना में, उन सबसे खराब परिदृश्यों में कितना खराब है जो वास्तव में घटित होते हैं।

उन्होंने सिद्ध किया कि भले ही आपका अनुमान मॉडल पूर्ण न हो, जब तक कि वह सत्य के "काफी करीब" है, आपकी गलतियाँ उच्च संभाव्यता के साथ छोटी रहेंगी।

यह क्यों मायने रखता है?

यह केवल अमूर्त गणित नहीं है। यह जीवन-मरण की स्थितियों में लागू होता है जहाँ विश्वसनीयता महत्वपूर्ण है:

एयर ट्रैफिक कंट्रोल: यह भविष्यवाणी करना कि क्या दो विमान आपस में टकरा सकते हैं। आपको केवल "औसत" सुरक्षा रिकॉर्ड नहीं चाहिए; आपको एक गारंटी चाहिए कि टक्कर होने की संभावना अत्यंत कम है।
सेल्फ-ड्राइविंग कारें: यह भविष्यवाणी करना कि पैदल यात्री कहाँ कदम रखेगा। यदि कार की भविष्यवाणी "आमतौर पर सही" है, तो वह पर्याप्त नहीं है। उसे लगभग हमेशा सही होने की आवश्यकता है।
स्वास्थ्य सेवा: यह भविष्यवाणी करना कि क्या कोई रोगी सेप्सिस (sepsis) की स्थिति में जा सकता है। एक गलत नकारात्मक (false negative) घातक हो सकता है।

"असंभवता" का परिणाम

लेखकों ने यह भी सिद्ध किया कि: आप इससे बेहतर नहीं कर सकते।

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

सारांश

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

यहाँ फ्रे, मैंटन और झू द्वारा लिखित शोध पत्र "Online Prediction of Stochastic Sequences with High Probability Reget Bounds" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र एक परिमित, नियत समय क्षितिज (deterministic time horizon) $T$ के साथ स्टोकेस्टिक अनुक्रमों के सार्वभौमिक पूर्वानुमान (universal prediction of stochastic sequences) की शास्त्रीय समस्या को संबोधित करता है।

सेटअप: एक शिक्षार्थी (learner) एक अज्ञात संयुक्त संभाव्यता वितरण $P$ से प्राप्त अनुक्रम $Z_1, \dots, Z_T$ को देखता है। प्रत्येक समय चरण $t$ पर, शिक्षार्थी पिछले अवलोकनों $Z_{1}, \dots, Z_{t-1}$ के आधार पर $B_t$ की भविष्यवाणी करता है और एक हानि (loss) $\ell(B_t, Z_t)$ उठाता है।
लक्ष्य: शिक्षार्थी एक ऐसी रणनीति चाहता है जो "सार्वभौमिक" (universal) हो, जिसका अर्थ है कि यह विशिष्ट अज्ञात वितरण $P$ पर निर्भर नहीं करती है, फिर भी वह रिग्रेट (regret) (शिक्षार्थी की संचयी हानि और $P$ को जानने वाली एक इष्टतम रणनीति की संचयी हानि के बीच का अंतर) प्राप्त करती है जो $T \to \infty$ होने पर शून्य हो जाता है।
साहित्य में अंतराल: मौजूदा साहित्य (जैसे, मेरहव और फेडर, 1998; हटर, 2003) अपेक्षित रिग्रेट (expected regret) ( $\mathbb{E}[\Delta]$ ) पर सीमाएँ प्रदान करता है। हालाँकि, ये गारंटी नहीं देते हैं कि रिग्रेट उच्च प्रायिकता (high probability) के साथ कम होगा, जो सुरक्षा-महत्वपूर्ण अनुप्रयोगों (जैसे, स्वायत्त ड्राइविंग, एयर ट्रैफिक कंट्रोल) के लिए महत्वपूर्ण है। यह शोध पत्र जांच करता है कि क्या इस परिदृश्य के लिए उच्च-प्रायिकता रिग्रेट बाउंड्स (अर्थात, $\mathbb{P}(\Delta > \epsilon) \leq \delta$ ) प्राप्त किए जा सकते हैं।

2. कार्यप्रणाली

लेखक एक दो-चरणीय दृष्टिकोण अपनाते हैं, जो एक सरलीकृत तकनीकी समस्या से सामान्य सार्वभौमिक सेटिंग की ओर बढ़ता है।

A. मिसमैच्ड प्रेडिक्शन समस्या (The Mismatched Prediction Problem)

बाउंड्स निकालने के लिए, लेखक पहले एक "मिसमैच्ड" परिदृश्य का विश्लेषण करते हैं जहाँ शिक्षार्थी यह मान लेता है कि डेटा एक ज्ञात वितरण $Q$ (जो वास्तविक $P$ से भिन्न हो सकता है) का अनुसरण करता है और $Q$ के संबंध में इष्टतम रूप से कार्य करता है।

रिग्रेट की परिभाषा: रिग्रेट $\Delta$ को शिक्षार्थी (जो $Q$ का उपयोग कर रहा है) द्वारा झेली गई हानि और एक ओरेकल (जो $P$ का उपयोग कर रहा है) द्वारा झेली गई हानि के औसत अंतर के रूप में परिभाषित किया गया है।
समानता माप (Similarity Measures): विश्लेषण $P$ $P$ और $Q$ $Q$ के बीच विचलन को मापने पर आधारित है:
- वैरिएशनल डिस्टेंस ( $V_T$ ): $P$ और $Q$ के कंडीशनल डिस्ट्रीब्यूशन के बीच अपेक्षित औसत टोटल वेरिएशन डिस्टेंस।
- कुलबैक-लीलर (KL) डाइवर्जेंस ( $D(P||Q)$ ): अपेक्षित औसत KL डाइवर्जेंस।
मुख्य तकनीकी उपकरण: लेखक रिग्रेट प्रक्रिया में एक सुपरमार्टिंगेल (supermartingale) संरचना की पहचान करते हैं। अज़ुमा-होफडिंग असमानता (Azuma-Hoeffding inequality) को लागू करके, वे मिसमैच्ड मामले के लिए एक उच्च-प्रायिकता बाउंड प्राप्त करते हैं।

B. सार्वभौमिक पूर्वानुमान के लिए अनुप्रयोग

मिसमैच्ड समस्या के परिणामों को एक सार्वभौमिक माप $Q_N$ का निर्माण करके सार्वभौमिक पूर्वानुमान सेटिंग में लागू किया जाता है।

सार्वभौमिक माप: $Q_N$ को आमतौर पर एक वेट $w$ द्वारा भारित एक पैरामेट्रिक फैमिली ऑफ डिस्ट्रीब्यूशन्स $\{P_\theta\}_{\theta \in \Theta}$ के मिश्रण के रूप में बनाया जाता है:
$Q_N = \int_{\Theta} P_\theta w(d\theta)$
अभिसरण तर्क (Convergence Logic): यदि वास्तविक वितरण $P$ उस फैमिली का हिस्सा है (अर्थात, $w$ के सपोर्ट में किसी $\theta_0$ के लिए $P = P_{\theta_0}$ ), तो KL डाइवर्जेंस $D(P||Q_N)$ , $T$ के साथ उप-रैखिक (sublinearly) रूप से बढ़ता है (अक्सर लॉगरिदमिक)। यह सुनिश्चित करता है कि रिग्रेट शून्य हो जाता है।

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

उच्च-प्रायिकता रिग्रेट बाउंड्स: यह शोध पत्र बिना एक्सपर्ट एडवाइस के गैर-i.i.d. स्टोकेस्टिक अनुक्रमों के सार्वभौमिक पूर्वानुमान के लिए पहले उच्च-प्रायिकता रिग्रेट बाउंड्स प्रदान करता है।
असंभवता परिणाम (Impossibility Result): लेखक सिद्ध करते हैं कि उनके बाउंड्स में विफलता की प्रायिकता $\delta$ पर निर्भरता इष्टतम है। विशेष रूप से, वे दिखाते हैं कि बिना अतिरिक्त धारणाओं के, $\delta \to 0$ होने पर $1/\delta$ (या $1/\sqrt{\delta}$ ) कारक को काफी धीमी गति से बढ़ने वाले पद (जैसे, लॉगरिदमिक) से बदला नहीं जा सकता है।
शिथिल धारणाएँ (Relaxed Assumptions): पिछले कार्यों के विपरीत, जिन्हें अक्सर परिमित अल्फाबेट की आवश्यकता होती थी, यह कार्य हल्के तकनीकी अनुमानों के साथ गणनीय (countable) और सामान्य मापने योग्य स्थानों (measurable spaces) को संभालता है।

4. मुख्य परिणाम

सैद्धांतिक बाउंड्स (Theoretical Bounds)

मुख्य परिणाम (थ्योरम 4) बताता है कि किसी भी $\delta \in (0, 1]$ के लिए, कम से कम $1-\delta$ प्रायिकता के साथ:
$\Delta < 2L \sqrt{\frac{D(P||Q)}{T}} \cdot \frac{1}{\sqrt{\delta}} + \frac{2\sqrt{2}L}{\sqrt{T}} \sqrt{\log \frac{2}{\delta}}$
जहाँ $L$ लॉस फंक्शन की ऊपरी सीमा है।

अभिसरण दर (Convergence Rate): एक गणनीय अल्फाबेट के लिए जहाँ $D(P||Q)$ सीमित है (जैसे, यूनिवर्सल कोडिंग सेटिंग में), रिग्रेट $O(T^{-1/2} \delta^{-1/2})$ की दर से अभिसरित होता है।
अपेक्षा से तुलना: यह ज्ञात अपेक्षित बाउंड $O(T^{-1/2})$ का पूरक है। उच्च-प्रायिकता बाउंड एक दंड कारक (penalty factor) $\delta^{-1/2}$ पेश करता है, जो यह गारंटी देने के लिए आवश्यक है कि बाउंड उच्च विश्वास के साथ बना रहे।

असंभवता प्रमेय (Theorem 5)

लेखक एक काउंटर-एग्जांपल का निर्माण करते हैं जो दिखाता है कि किसी भी प्रेडिक्शन समस्या के लिए, एक ऐसा वितरण मौजूद है जहाँ रिग्रेट उच्च प्रायिकता के साथ 0 है लेकिन $\delta$ प्रायिकता के साथ अधिकतम हानि के करीब है। यह सिद्ध करता है कि लॉस के टेल व्यवहार (tail behavior) पर अतिरिक्त धारणाओं के बिना $\delta^{-1/2}$ (या $\delta^{-1}$ ) स्केलिंग अपरिहार्य है।

अभिसरण दरों का सारांश (तालिका 1)

शोध पत्र विभिन्न परिदृश्यों के लिए अभिसरण दरों को सारांशित करता है:

गणनीय $Z$ (Universal): $O(T^{-1/2})$ (अपेक्षा) $\to$ $O(T^{-1/2}\delta^{-1/2})$ (उच्च प्रायिकता)।
i.i.d. $P_N$ : $O((T/\log T)^{-1/2})$ (अपेक्षा) $\to$ $O((T/\log T)^{-1/2}\delta^{-1/2})$ (उच्च प्रायिकता)।
मार्कोव चेन (Markov Chains): अपेक्षित बाउंड्स की तुलना में समान सुधार।

5. संख्यात्मक प्रयोग (Numerical Experiments)

लेखकों ने $m=3$ मेमोरी और $S=2$ स्टेट्स वाले मार्कोव चेन का उपयोग करके अपने सिद्धांत को सत्यापित किया।

सेटअप: शिक्षार्थी ने सभी संभावित ट्रांजिशन पैरामीटर्स पर एक मिश्रण वितरण $Q_N$ का उपयोग किया।
निष्कर्ष:
- अनुक्रम की लंबाई बढ़ने के साथ औसत रिग्रेट 0 की ओर अभिसरित हुआ।
- देखे गए क्वांटाइल्स (जो उच्च-प्रायिकता व्यवहार का प्रतिनिधित्व करते हैं) भी 0 की ओर अभिसरित हुए, हालांकि औसत की तुलना में धीमे, जो सैद्धांतिक $\delta^{-1/2}$ कारक के अनुरूप है।
- प्रयोगों ने प्रदर्शित किया कि मध्यम स्टेट स्पेस और मेमोरी ऑर्डर के लिए यह ढांचा गणनात्मक रूप से व्यवहार्य है।

6. महत्व और निहितार्थ

व्यावहारिक विश्वसनीयता: ये परिणाम उन सुरक्षा-महत्वपूर्ण प्रणालियों के लिए महत्वपूर्ण हैं जहाँ "औसत" प्रदर्शन पर्याप्त नहीं है। यह जानना कि रिग्रेट $1-\delta$ प्रायिकता के साथ सीमित है, चिकित्सा निदान (सेप्सिस भविष्यवाणी) और स्वायत्त नेविगेशन जैसे अनुप्रयोगों में कठोर जोखिम प्रबंधन की अनुमति देता है।
सैद्धांतिक कठोरता: यह शोध पत्र ऑनलाइन लर्निंग थ्योरी के एक अंतराल को भरता है, यह स्थापित करते हुए कि सार्वभौमिक पूर्वानुमान के लिए उच्च-प्रायिकता बाउंड्स संभव हैं, लेकिन स्वाभाविक रूप से विश्वास पैरामीटर $\delta$ के संबंध में एक विशिष्ट लागत आती है।
इष्टतमता (Optimality): असंभवता परिणाम शोधकर्ताओं को इस सामान्य सेटिंग के लिए "लॉगरिदमिक इन $\delta$ " बाउंड्स के पीछे भागने से रोकता है, जिससे ध्यान उन विशिष्ट संरचनात्मक धारणाओं को खोजने की ओर केंद्रित होता है जो अधिक कड़े बाउंड्स की अनुमति दे सकती हैं।

संक्षेप में, यह शोध पत्र स्थापित करता है कि जबकि सार्वभौमिक पूर्वानुमान उच्च प्रायिकता के साथ शून्य रिग्रेट प्राप्त कर सकता है, विश्वास स्तर $\delta$ बाउंड में एक बहुपद लागत (polynomial cost) के साथ आता है, जो कि समस्या की संरचना के प्रति मौलिक रूप से अनिवार्य है।