🤖 machine learning

Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Models

यह शोध पत्र ऑनलाइन लर्निंग की उस समस्या की जांच करता है जहाँ उदाहरणों में कई वैध लेबल हो सकते हैं, जो कॉम्बिनेटरियल आयामों (combinatorial dimensions) के माध्यम से इष्टतम मिस्टेक बाउंड्स को अभिलक्षणिक बनाता है और रियलाइजेबल (realizable) एवं एग्नोस्टिक (agnostic) दोनों सेटिंग्स के लिए संगत सैंपल कॉम्प्लेक्सिटी बाउंड्स प्राप्त करने हेतु तीन फीडबैक मॉडलों में रिग्रेट दरों का विश्लेषण करता है।

मूल लेखक: Alireza F. Pour, Farnam Mansouri, Shai Ben-David

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

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

CC BY 4.0

मूल लेखक: Alireza F. Pour, Farnam Mansouri, Shai Ben-David

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

कल्पना कीजिए कि आप एक चालाक प्रतिद्वंद्वी के खिलाफ एक हाई-स्टेक्स अनुमान लगाने वाले खेल (guessing game) खेल रहे हैं। इस खेल में, आपको एक प्रॉम्प्ट (जैसे कोई प्रश्न या वाक्य की शुरुआत) दिया जाता है, और आपको उसका उत्तर देना होता है। मोड़ क्या है? केवल एक सही उत्तर नहीं है। इसके बजाय, स्वीकार्य उत्तरों की एक पूरी सूची है।

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

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

यहाँ उनके निष्कर्षों का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है:

फीडबैक के तीन प्रकार (द "रेफरी")

इस खेल में, आपके द्वारा अनुमान लगाने के बाद, एक रेफरी आपको कुछ बताता है। पेपर तीन अलग-अलग तरीकों की तुलना करता है जिनसे रेफरी बोल सकता है:

"मौन सुधारक" (Silent Corrector - गलती अज्ञात):
- परिदृश्य: आप "कार" का अनुमान लगाते हैं। रेफरी बस एक सही उत्तर फुसफुसाता है, जैसे "सेब।"
- समस्या: आपको यह नहीं पता कि "कार" गलत था या नहीं। आप केवल यह जानते हैं कि "सेब" सही है। शायद "कार" भी सही था, लेकिन रेफरी ने बस आपको बताया नहीं। शायद "कार" गलत था। आप अंधेरे में हाथ-पांव मार रहे हैं।
- परिणाम: पेपर दिखाता है कि इस परिदृश्य में, संभावित उत्तरों की एक छोटी संख्या होने पर भी, लर्नर एक लूप (loop) में फंस सकता है। उनका "रिग्रेट" (regret - वह संख्या जितनी बार वे सबसे अच्छी रणनीति की तुलना में विफल होते हैं) रैखिक (linearly) रूप से बढ़ता है। यह एक ट्रेडमिल पर दौड़ने जैसा है जो लगातार तेज़ होता जा रहा है; चाहे आप कितनी भी मेहनत करें, आप एक स्थिर, निराशाजनक गति से पीछे छूटते जाते हैं।
"ईमानदार रेफरी" (Honest Referee - गलती ज्ञात):
- परिदृश्य: आप "कार" का अनुमान लगाते हैं। रेफरी कहता है, "सेब" (एक सही उत्तर) और साथ ही एक लाल बत्ती जोड़ता है: "आप गलत थे।"
- लाभ: अब आप निश्चित रूप से जानते हैं कि आपने चूक की। आप यह भी जानते हैं कि "सेब" सुरक्षित है।
- परिणाम: यह बहुत बेहतर है। पेपर सिद्ध करता है कि इस फीडबैक के साथ, लर्नर का रिग्रेट बहुत धीमी गति से (sub-linearly) बढ़ता है। यह एक ऐसे कोच की तरह है जो आपको बताता है कि आपने कब गलती की। आप गलतियाँ करते हैं, लेकिन आप उनसे इतनी जल्दी सीखते हैं कि आपका प्रदर्शन समय के साथ सुधरता है।
"सर्वज्ञ ओरेकल" (All-Knowing Oracle - सेट-वैल्यूड):
- परिदृश्य: आप "कार" का अनुमान लगाते हैं। रेफरी सभी सही उत्तरों की पूरी सूची प्रकट करता है: "सही उत्तर {सेब, केला, संतरा} हैं।"
- लाभ: आपके पास पूर्ण पारदर्शिता है। आप देखते हैं कि आपने क्या मिस किया और आप क्या अनुमान लगा सकते थे।
- परिणाम: यह "जादुई" परिदृश्य है। कई प्रकार की समस्याओं के लिए, लर्नर का रिग्रेट स्थिर (constant) हो जाता है। इसका मतलब है कि एक निश्चित बिंदु के बाद, लर्नर सबसे अच्छी रणनीति की तुलना में कोई अतिरिक्त गलतियाँ नहीं करता है। यह एक चीट शीट रखने जैसा है जो अंततः आपको खेल चाहे कितना भी लंबा चले, पूरी तरह से खेलने में सक्षम बनाती है।

बड़ी खोज: "रियल" बनाम "एग्नोस्टिक"

पेपर दो प्रकार के खिलाड़ियों के बीच एक महत्वपूर्ण अंतर बनाता है:

रियलइज़ेबल प्लेयर (Realizable Player): खेल निष्पक्ष है। नियमों में निश्चित रूप से एक "परफेक्ट" रणनीति छिपी हुई है जो 100% उत्तर सही दे सकती है।
एग्नोस्टिक प्लेयर (Agnostic Player): खेल पक्षपाती या अव्यवset हो सकता है। ऐसा नहीं हो सकता कि हर राउंड के लिए एक ही परफेक्ट रणनीति मौजूद हो। लक्ष्य बस उपलब्ध सबसे अच्छी रणनीति के जितना संभव हो सके उतना अच्छा करना है, भले ही वह रणनीति परफेक्ट न हो।

चौंकाने वाली खोज:
कई लर्निंग समस्याओं में, यदि आप "रियल" संस्करण को हल कर सकते हैं, तो आप आमतौर पर "मेसी" (messy) संस्करण को भी हल कर सकते हैं। यहाँ ऐसा नहीं है।

मौन सुधारक (Silent Corrector) खेल में, भले ही नियम सरल हों, "मेसी" संस्करण एक आपदा है। लर्नर लगातार विफल होता है।
ऑल-नोइंग ओरेकल (All-Knowing Oracle) खेल में, "मेसी" संस्करण बहुत आसान है। लर्नर एक स्थिर, लगभग पूर्ण स्कोर प्राप्त कर सकता है।

यह हमें बताता है कि "कई सही उत्तरों" वाली दुनिया में, थोड़ी अधिक जानकारी होना (जैसे यह जानना कि आपने गलती की, या पूरी सूची देखना) खेल की कठिनाई को "असंभव" से "आसान" में बदल देता है।

"पेड़" की उपमा (The "Tree" Analogy)

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

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

सारांश

यह पेपर लैंग्वेज जनरेशन (जैसे AI टेक्स्ट लिखना) के बारे में है। यह तर्क देता है कि क्योंकि AI के पास अक्सर वाक्य पूरा करने के कई वैध तरीके होते हैं, इसलिए हमें इसे प्रशिक्षित करने के तरीके पर पुनर्विचार करने की आवश्यकता है।

यदि हम AI को केवल एक सही उत्तर का उदाहरण दिखाते हैं (Silent Corrector), तो यह सीखने में संघर्ष कर सकता है, भले ही कार्य सरल लगे।
यदि हम AI को बताते हैं कि "आप गलत थे" (Honest Referee), तो यह काफी हद तक सीख लेता है।
यदि हम AI को स्वीकार्य उत्तरों की पूरी रेंज दिखाते हैं (All-Knowing Oracle), तो यह लगभग तुरंत महारत हासिल कर सकता है, यहाँ तक कि अव्यवस्थित और अप्रत्याशित स्थितियों में भी।

मुख्य संदेश यह है: "कई सही उत्तरों वाली दुनिया में, आपको मिलने वाले फीडबैक की गुणवत्ता उतनी ही महत्वपूर्ण है जितनी कि लर्नर की बुद्धिमत्ता।

तकनीकी सारांश: कई सही उत्तरों के साथ सीखना – विभिन्न फीडबैक मॉडलों के तहत रिग्रेट बाउंड्स (Reget Bounds)

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

यह कार्य कई सही उत्तरों के साथ ऑनलाइन लर्निंग की समस्या को संबोधित करता है, जो एक ऐसी सेटिंग है जहाँ एक एकल इनपुट इंस्टेंस $x$ के लिए एक ही लक्ष्य लेबल के बजाय वैध लेबल्स का एक सेट $S \subseteq \mathcal{Y}$ मौजूद होता है। यह फॉर्मूलेशन आधुनिक कार्यों जैसे कि भाषा पीढ़ी (जहाँ एक प्रॉम्प्ट के कई स्वीकार्य पूर्ण रूप हो सकते हैं), ओपन-एंडेड प्रश्न उत्तर, संवाद पीढ़ी और अनुशंसा प्रणाली (recommendation systems) से प्रेरित है।

यह अध्ययन ऑनलाइन लर्निंग प्रतिमान (paradigm) पर केंद्रित है, जो राउंड $t \in [T]$ में आगे बढ़ता है। प्रत्येक राउंड में, एक एडवर्सरी (adversary) एक इंस्टेंस $x_t$ और स्वीकार्य लेबल्स का एक सेट $S_t$ प्रस्तुत करता है। शिक्षार्थी (learner) एक लेबल $\hat{y}_t$ का अनुमान लगाता है और यदि $\hat{y}_t \notin S_t$ है, तो 1 का नुकसान (loss) उठाता है। यह पेपर तीन अलग-अलग फीडबैक मॉडलों के तहत इस समस्या का विश्लेषण करता है:

मिस्टेक-अननोन (Mistake-unknown): शिक्षार्थी को केवल एक वैध लेबल $y_t \in S_t$ प्राप्त होता है (जो एडवर्सरी द्वारा चुना गया है), लेकिन उसे यह पता नहीं चलता कि उसका अनुमान सही था या नहीं।
मिस्टेक-नोन (Mistake-known): शिक्षार्थी को एक एकल वैध लेबल $y_t \in S_t$ और एक बाइनरी इंडिकेटर प्राप्त होता है जो यह प्रकट करता है कि क्या उनका अनुमान $\hat{y}_t$ एक गलती थी।
सेट-वैल्यूड (Set-valued): शिक्षार्थी को वैध लेबल्स के संपूर्ण सेट $S_t$ का खुलासा किया जाता है।

विश्लेषण रियलाइजेबल सेटिंग (जहाँ एक परिकल्पना $h^* \in \mathcal{H}$ मौजूद है ताकि सभी $t$ के लिए $h^*(x_t) = S_t$ हो) और एग्नोस्टिक सेटिंग (जहाँ शिक्षार्थी $\mathcal{H}$ में सर्वश्रेष्ठ परिकल्पना के विरुद्ध संचयी हानि को कम करने के लिए प्रतिस्पर्धा करता है) दोनों को कवर करता है।

2. कार्यप्रणाली और कॉम्बिनेटोरियल लक्षण वर्णन

लेखक प्रत्येक फीडबैक मॉडल के तहत मल्टी-लेबल परिकल्पना वर्गों (hypothesis classes) $\mathcal{H}$ की सीखने की क्षमता को लक्षणबद्ध करने के लिए नवीन कॉम्बिनेटोरियल आयाम (combinatorial dimensions) पेश करते हैं। ये आयाम विशिष्ट मॉडल में उपलब्ध जानकारी के अनुकूल रूपांतरित किए गए ट्री-शैटिंग (tree-shattering) तर्कों के माध्यम से परिभाषित किए जाते हैं।

कॉम्बिनेटोरियल आयाम (Combinatorial Dimensions)

सेट-वैल्यूड लिटलेस्टोन डायमेंशन ( $LD_{set}$ ): एक सेट-वैल्यूड ट्री पर परिभाषित, जहाँ नोड्स को $\mathcal{Y}$ के उपसमुच्चयों (subsets) के साथ लेबल किया जाता है। एक ट्री तब शैटर्ड (shattered) होता है जब प्रत्येक प्रेडिक्शन पाथ के लिए, प्रकट किए गए सेटों $S_t$ के साथ सुसंगत (consistent) एक परिकल्पना मौजूद होती है लेकिन अनुमानित लेबल पर गलती करती है।
मिस्टेक-नोन लिटलेस्टोन डायमेंशन ( $LD_{known}$ ): एक मल्टी-लेबल ट्री पर परिभाषित जहाँ नोड्स को एकल लेबल्स के साथ लेबल किया जाता है। शैटरिंग के लिए प्रकट एकल लेबल $y_t$ के साथ सुसंगत होना और प्रेडिक्शन पर गलती करना आवश्यक है।
मिस्टेक-अननोन लिटलेस्टोन डायमेंशन ( $LD_{unknown}$ ): एक "मिस्टेक ऑफसेट" फंक्शन का उपयोग करके परिभाषित। एक ट्री $d$ -शैटर्ड है यदि किसी भी पाथ के साथ संचयी गलतियों की संख्या, प्लस एक परिकल्पना के लिए ऑफसेट, $d$ से अधिक है। यह शुद्धता पर तत्काल फीडबैक की कमी को ध्यान में रखता है।

एल्गोरिदम (Algorithms)

रियलाइजेबल सेटिंग के लिए, लेखक प्रत्येक फीडबैक मॉडल के लिए स्टैंडर्ड ऑप्टिमल एल्गोरिदम (SOA) प्रस्तावित करते हैं। ये एल्गोरिदम सुसंगत परिकल्पनाओं के वर्ज़न स्पेस (version space) को बनाए रखते हैं और उन प्रेडिक्शन को चुनते हैं जो शेष वर्ज़न स्पेस के वर्स्ट-केस डायमेंशन को कम करते हैं।

मिस्टेक-अनोन के लिए SOA: एक वर्ज़न स्पेस और एक ऑफसेट फंक्शन बनाए रखता है, और उस लेबल का अनुमान लगाता है जो परिणामी उप-वर्गों (sub-classes) के अधिकतम $LD_{unknown}$ को कम करता है।
मिस्टेक-नोन के लिए SOA: संभावित मिस्टेक बिट द्वारा बनाए गए उप-वर्गों के अधिकतम $LD_{known}$ को कम करने के लिए प्रेडिक्ट करता है।
सेट-वैल्यूड के लिए SOA: प्रकट किए गए सेट $S_t$ द्वारा बनाए गए उप-वर्गों के अधिकतम $LD_{set}$ को कम करने के लिए प्रेडिक्ट करता है।

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

रियलाइजेबल ऑनलाइन लर्निंग

यह पेपर किसी भी मल्टी-लेबल क्लास $\mathcal{H}$ के लिए रियलाइजेबल सेटिंग में इष्टतम मिस्टेक बाउंड का पूर्ण लक्षण वर्णन प्रदान करता है:

मिस्टेक-अनोन: इष्टतम मिस्टेक बाउंड $\min(LD_{unknown}(\mathcal{H}), T)$ है।
मिस्टेक-नोन: इष्टतम मिस्टेक बाउंड $\min(LD_{known}(\mathcal{H}), T)$ है।
सेट-वैल्यूड: इष्टतम मिस्टेक बाउंड $\min(LD_{set}(\mathcal{H}), T)$ है।

ये परिणाम परिमित (finite) वर्गों के पिछले कार्यों का सामान्यीकरण करते हैं। लेखक सिद्ध करते हैं कि $LD_{set}(\mathcal{H}) = 0 \iff LD_{known}(\mathcal{H}) = 0 \iff LD_{unknown}(\mathcal{H}) = 0$ , जो तभी होता है जब किसी भी इंस्टेंस के लिए सभी परिकल्पनाओं के लेबल सेट्स का इंटरसेक्शन (intersection) गैर-रिक्त (non-empty) हो।

एग्नोस्टिक ऑनलाइन लर्निंग (रिग्रेट बाउंड्स)

एक महत्वपूर्ण योगदान यह दिखाना है कि एग्नोस्टिक सेटिंग में रिग्रेट दर दर फीडबैक मॉडल के आधार पर नाटकीय रूप से भिन्न होती है, जो सिंगल-लेबल लर्निंग के विपरीत है जहाँ रिग्रेट आमतौर पर $\tilde{\Theta}(\sqrt{T})$ होता है।

मिस्टेक-अनोन: लेखक दिखाते हैं कि रिग्रेट $T$ में रैखिक (linearly) रूप से बढ़ सकता है ( $\Omega(T)$ ), यहाँ तक कि सरल परिकल्पना वर्गों के लिए भी जहाँ $LD_{unknown}=1$ है। इसका तात्पर्य है कि $LD_{unknown}$ द्वारा लक्षणबद्ध रियलाइजेबल लर्नबिलिटी, इस फीडबैक मॉडल के लिए एग्नोस्टिक सेटिंग में सबलीनियर रिग्रेट की गारंटी नहीं देती है।
मिस्टेक-नोन: पेपर एक सबलीनियर रिग्रेट अपर बाउंड $O(\sqrt{LD_{known}(\mathcal{H}) |\mathcal{Y}| T \log T})$ स्थापित करता है। यह SOA-आधारित विशेषज्ञों (experts) के एक सेट का उपयोग करके, नॉन-स्टोकेस्टिक बैंडिट्स विद एक्सपर्ट एडवाइस के रूप में समस्या को कम करके प्राप्त किया गया है।
सेट-वैल्यूड:
- विशिष्ट वर्गों के लिए (जैसे, उदाहरण क्लास $H_3$ ), रिग्रेट स्थिर (constant) ( $O(1)$ ) है।
- सामान्य वर्गों के लिए, रिग्रेट $O(\sqrt{LD_{set}(\mathcal{H}) T \log T})$ द्वारा सीमित है। उल्लेखनीय रूप से, यह बाउंड लेबल स्पेस के आकार $|\mathcal{Y}|$ से स्वतंत्र है, जिससे यह अनंत लेबल स्पेस के लिए भी लागू हो सकता है।

बैच लर्निंग निहितार्थ

व्युत्पन्न कॉम्बिनेटोरियल डायमेंशन और ऑनलाइन बाउंड्स संबंधित बैच लर्निंग समस्याओं के लिए सैंपल कॉम्प्लेक्सिटी बाउंड्स को दर्शाते हैं। लेखक फुल-सेट फीडबैक मॉडल के तहत बैच लर्निंग के लिए पहले ज्ञात अपर बाउंड प्रदान करते हैं और परिमित से अनंत वर्गों तक सिंगल-करेक्ट-आंसर केस के मौजूदा बाउंड्स में सुधार करते हैं।

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

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

इसके अलावा, यह कार्य एग्नोस्टिक मल्टी-लेबल लर्निंग में एक समृद्ध संरचना को उजागर करता है:

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

लेखक स्पष्ट रूप से उल्लेख करते हैं कि उनके रिग्रेट डेफिनिशन पूर्ववर्ती कार्यों (जैसे, जोशी इ.ए. [JLB+25] और रमन इ.ए. [RST24]) से भिन्न हैं ताकि वे केवल एक प्रकट किए गए लेबल के विरुद्ध प्रतिस्पर्धा करने के बजाय, वास्तविक स्वीकार्य लेबल्स के विरुद्ध त्रुटि को कम करने के अंतर्निहित प्रेडिक्शन टास्क के साथ बेहतर ढंग से संरेखित हो सकें।