🤖 machine learning

Polynomial-Time Mistake-Bounded Language Generation

यह शोधपत्र मिस्टेक-बाउंडेड लैंग्वेज जनरेशन फ्रेमवर्क के एक बहुपद-समय (polynomial-time) संस्करण को प्रस्तुत करता है, जो यह प्रदर्शित करता है कि पैरिटी (parities), कंजंक्शन (conjunctions) और बहुपद-संख्या में मैक्सटर्म्स वाले मोनोटोन बुलियन फंक्शन (जैसे कि वे जो बहुपद-आकार के डिसीजन ट्री द्वारा गणनीय हैं) सहित परिवार एक नवीन कॉम्बिनेटरियल गेम के माध्यम से कुशलतापूर्वक सीखे जा सकते हैं।

मूल लेखक: Héctor Jimenez, Alexander Kozachinskiy, Vicente Opazo

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

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

CC BY 4.0

मूल लेखक: Héctor Jimenez, Alexander Kozachinskiy, Vicente Opazo

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

कल्पना कीजिए कि आप एक रहस्यमय प्रतिद्वंद्वी के साथ एक अनुमान लगाने वाला खेल (guessing game) खेल रहे हैं। प्रतिद्वंद्वी ने संभव नियमपुस्तिकाओं (rulebooks) के एक विशाल पुस्तकालय में से गुप्त रूप से एक विशिष्ट "नियमपुस्तिका" (भाषा) चुनी है। इस नियमपुस्तिका में वैध शब्दों की एक सूची है। प्रतिद्वंद्वी आपको एक-एक करके, यादृच्छिक क्रम (random order) में ये शब्द दिखाना शुरू करता है।

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

यहाँ एक पेच (catch) है: आपको अपने अनुमान के बाद "हाँ" या "नहीं" नहीं मिलता है। आपको बस चलते रहना है। यदि आप एक ऐसा शब्द चिल्लाते हैं जो गुप्त सूची में नहीं है, तो इसे एक गलती (mistake) माना जाएगा। इस शोध पत्र का लक्ष्य यह पता लगाना है: क्या हम एक ऐसी रणनीति बना सकते हैं जिससे बहुत कम गलतियाँ हों और गणित इतनी तेज़ी से हल हो सके कि वह उपयोगी हो?

लेखक इस खेल का एक नया संस्करण पेश करते हैं जिसे पॉलीनोमियल-टाइम मिस्टेक-बाउंडेड लैंग्वेज जनरेशन (Polynomial-Time Mistake-Bounded Language Generation) कहा जाता है। आइए इसके निष्कर्षों को कुछ रोज़मर्रा के उपमाओं (analogies) का उपयोग करके समझते हैं।

"बस इंतज़ार करने" की समस्या

अतीत में, शोधकर्ता इस समस्या पर विचार करते समय पूछते थे, "हम कितनी देर में गलतियाँ करना बंद कर देंगे?" लेकिन लेखकों ने महसूस किया कि सफलता को मापने का यह एक बुरा तरीका है।

उपमा: कल्पना कीजिए कि दो विशाल पुस्तकालय हैं जिनमें समान पुस्तकों का एक बड़ा हिस्सा साझा है। यदि प्रतिद्वंद्वी उस साझा हिस्से से पुस्तकें दिखाना शुरू करता है, तो आप बहुत लंबे समय तक गलत अनुमान लगा सकते हैं क्योंकि आप अभी तक यह नहीं बता सकते कि असली पुस्तकालय कौन सा है। आप हजारों गलतियाँ कर सकते हैं इससे पहले कि प्रतिद्वंद्वी ऐसी पुस्तक दिखाए जो केवल एक ही पुस्तकालय में मौजूद हो।

लेखक कहते हैं: "आइए यह गिनना बंद करें कि सही होने में कितना समय लगता है। इसके बजाय, हम यह गिनें कि हम कुल मिलाकर कितनी गलतियाँ करते हैं, चाहे खेल कितने भी लंबे समय तक चले।"

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

"जादुई" रणनीतियाँ

यह शोध पत्र सिद्ध करता है कि तीन विशिष्ट प्रकार की नियमपुस्तिकाओं के लिए, आप बहुत कम गलतियों और बहुत तेज़ सोच के साथ यह खेल पूरी तरह से खेल सकते हैं:

1. "AND" का खेल (Conjunctions)

नियम: एक शब्द तभी वैध है यदि उसमें विशिष्ट स्थानों पर विशिष्ट अक्षर हों (उदाहरण के लिए, "तीसरा अक्षर A होना चाहिए AND पाँचवाँ अक्षर B होना चाहिए")।
रणनीति: आप प्रतिद्वंद्वी द्वारा दिखाए गए अब तक के सभी शब्दों को देखते हैं। आप उन स्थानों को खोजते हैं जहाँ वे सभी सहमत हैं। आप एक नया शब्द चिल्लाते हैं जो उन सहमतियों से मेल खाता है।
यह क्यों काम करता है: यदि आप गलत अनुमान लगाते हैं, तो इसका अर्थ है कि प्रतिद्वंद्वी का अगला शब्द आपको अपने "सहमति वाले स्थानों" को बदलने के लिए मजबूर करेगा। चूंकि सहमति के स्थान सीमित हैं (अक्षर), इसलिए आप केवल एक सीमित संख्या में ही अपना विचार बदलने के लिए मजबूर हो सकते हैं। यह एक खोज क्षेत्र को कम करने जैसा है; आप खोज क्षेत्र को अनंत काल तक छोटा नहीं कर सकते।

2. "XOR" का खेल (Parities)

नियम: एक शब्द तब वैध होता है जब कुछ अक्षरों का योग (संख्याओं के रूप में माने जाने पर) सम (even) या विषम (odd) हो।
रणनीति: आप शब्दों को अंतरिक्ष में तीरों (arrows) की तरह मानते हैं। आप प्रतिद्वंद्वी द्वारा दिखाए गए तीरों को मिलाकर नए तीर बनाते हैं।
यह क्यों काम करता है: हर बार जब आप गलत अनुमान लगाते हैं, तो प्रतिद्वंद्वी वास्तव में आपको एक नया "दिशा" दे रहा होता है जिसे आप पहले से नहीं जानते थे। लेकिन निश्चित आयामों (letters/dimensions) वाली दुनिया में, आप पूरी जगह का मानचित्र बनाने से पहले केवल सीमित संख्या में ही नई दिशाओं की खोज कर सकते हैं।

3. "अपवर्ड" (ऊर्ध्वगामी) खेल (Monotone Functions)
यह इस शोध पत्र की सबसे बड़ी खोज है।

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

इसका क्या अर्थ है

लेखक दिखाते हैं कि यदि कोई नियमपुस्तिका एक विशिष्ट गणितीय तरीके से "सरल" है (जैसे कि एक निर्णय वृक्ष/decision tree जिसमें सीमित "ऑफ" स्विच हैं), तो एक कंप्यूटर बहुत तेज़ी से और बहुत कम त्रुटियों के साथ उससे नए वैध शब्द बनाना सीख सकता है।

वे यह भी बताते हैं कि वे अभी तक क्या नहीं जानते हैं:

क्या यह उन नियमपुस्तिकाओं के लिए काम करता है जो "मोनोटोन" (monotone) नहीं हैं?
क्या यह जटिल निर्णय वृक्षों (decision trees) के लिए काम करता है जो मोनोटोन नहीं हैं?
यदि आप दो वैध नियमपुस्तिकाओं को मिलाते हैं, तो क्या परिणाम भी आसानी से सीखा जा सकता है?

सारांश

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

तकनीकी सारांश: बहुपद-समय त्रुटि-सीमित भाषा पीढ़ी (Polynomial-Time Mistake-Bounded Language Generation)

समस्या परिभाषा

यह शोध पत्र बहुपद-समय मिस्टेक-बाउंडेड लैंग्वेज जनरेशन (MBLG) ढांचे का एक बहुपद-समय संस्करण प्रस्तुत करता है, जिसे मूल रूप से क्लाइनबर्ग, पील और रींगोल्ड (2026) द्वारा प्रस्तावित किया गया था। यह कार्य बड़े भाषा मॉडलों (LLMs) की वास्तविकता के अनुकूल सैद्धांतिक मशीन लर्निंग मॉडलों को ढालने के व्यापक संदर्भ में स्थित है।

समस्या को इस प्रकार परिभाषित किया गया है:

सेटिंग: एक प्रतिपक्षी (adversary) गुप्त रूप से $n$ लंबाई की बाइनरी भाषाओं के एक परिवार $\mathcal{F} = \{L_1, \dots, L_s\}$ में से एक भाषा $L$ का चयन करता है, जहाँ $s = 2^{\text{poly}(n)}$ है।
प्रक्रिया: प्रतिपक्षी एक विशिष्ट क्रम में $L$ के शब्दों को एक-एक करके प्रिंट करता है।
कार्य: पहले $i$ शब्दों ( $x_1, \dots, x_i$ ) को देखने के बाद, शिक्षार्थी (learner) को एक नया शब्द $y_i \in L \setminus \{x_1, \dots, x_i\}$ आउटपुट करना चाहिए।
प्रतिबंध:
1. त्रुटि सीमा (Mistake Bound): शिक्षार्थी को अधिकतम $\text{poly}(n)$ गलतियाँ (ऐसा शब्द आउटपुट करना जो $L$ में नहीं है) करने की अनुमति है।
2. समय जटिलता (Time Complexity): इतिहास $x_1, \dots, x_i$ से $y_i$ की गणना करने के लिए लगने वाला समय $\text{poly}(n^i)$ होना चाहिए।
अंतर: ऑनलाइन लर्निंग के विपरीत, यहाँ इस बारे में कोई फीडबैक नहीं है कि शिक्षार्थी का अनुमान सही था या नहीं। मानक 'लिमिट इन द लिमिट' भाषा पहचान के विपरीत, लक्ष्य भाषा की पहचान करना नहीं है, बल्कि लगातार नए वैध उदाहरण उत्पन्न करना है।

लेखक नोट करते हैं कि जबकि मूल MBLG ढांचा परिमित परिवारों के लिए लघुगणकीय त्रुटि सीमा ( $\lceil \log_2 s \rceil$ ) की गारंटी देता है, ज्ञात एल्गोरिदम को परिवार के सभी भाषाओं के माध्यम से पुनरावृत्ति (iterating) करने की आवश्यकता होती है, जिससे वे बहुपद समय में अव्यवहार्य हो जाते हैं। यह शोध पत्र उन परिवारों की पहचान करने का प्रयास करता है जहाँ यह कार्य बहुपद समय बाधाओं के भीतर संभव है।

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

लेखक वैलिएंट के PAC लर्निंग और लिटलस्टोन के ऑनलाइन मिस्टेक-बाउंड लर्निंग के शैलीगत समानांतरों को खींचते हुए पॉलीनोमियल-टाइम MBLG मॉडल को औपचारिक रूप देते हैं। मुख्य कार्यप्रणाली में शामिल हैं:

रचनात्मक एल्गोरिदम (Constructive Algorithms): विभिन्न भाषा परिवारों के लिए विशिष्ट पीढ़ी रणनीतियों को डिजाइन करना जो पूरे परिकल्पना स्थान (hypothesis space) को सूचीबद्ध करने के बजाय आंतरिक अवस्था (internal state) (जैसे कि सुसंगत चरों या रैखिक विस्तार के सेट) को बनाए रखने पर निर्भर करती हैं।
संयोजन गेम थ्योरी (Combinatorial Game Theory): मोनोटोन फंक्शन्स के संबंध में मुख्य परिणाम के लिए, लेखक शिक्षार्थी की अवस्था के विकास को बोर्ड पर लिखे गए नंबरों वाले एक संयोजन खेल (combinatorial game) में कम करते हैं। यह खेल "अधिकतम गैर-चिह्नित तत्वों" के उम्मीदवार सेट को बनाए रखने की "लागत" को मॉडल करता है।
पोटेंशियल फंक्शन विश्लेषण (Potential Function Analysis): अपने मुख्य प्रमेय के प्रमाण में, लेखक एक पोटेंशियल फंक्शन तर्क का उपयोग करते हैं (नंबरों को घातीय लागत वाले सिक्कों के स्टैक के रूप में दर्शाते हुए) ताकि एक विशिष्ट अवस्था तक पहुँचने के लिए आवश्यक चरणों की संख्या को सीमित किया जा सके, जिससे गलतियों की संख्या सीमित हो जाती है।

मुख्य योगदान और परिणाम

1. बहुपद-समय MBLG का औपचारिकीकरण

पेपर बहुपद-समय MBLG परिवारों को परिभाषित करता है। एक परिवार इस वर्ग में है यदि एक जनरेटर फंक्शन मौजूद है जो प्रतिपक्षी के क्रम की परवाह किए बिना, अधिकतम एक बहुपद संख्या में गलतियाँ करते हुए बहुपद समय में चलता है।

2. सुलभ परिवार: पैरिटीज़ और कंजंक्शन्स (Parities and Conjunctions)

लेखक प्रदर्शित करते हैं कि दो मौलिक परिवार बहुपद-समय MBLG हैं:

कंजंक्शन्स ऑफ लिटरल (Conjunctions of Literals): चरों के कंजंक्शन्स (जैसे, $x_{i_1}^{\alpha_1} \land \dots \land x_{i_k}^{\alpha_k} = 1$ $x_{i_{1}}^{α_{1}} \land \dots \land x_{i_{k}}^{α_{k}} = 1$ ) द्वारा परिभाषित भाषाओं का परिवार।
- रणनीति: शिक्षार्थी उन स्थितियों का सेट बनाए रखता है जहाँ देखे गए सभी शब्द मेल खाते हैं। यह इन स्थितियों के साथ सुसंगत एक नया शब्द उत्पन्न करने का प्रयास करता है। एक गलती तभी होती है जब प्रतिपक्षी ऐसे सभी शब्दों को समाप्त कर देता है, जो कि $n$ बार हो सकता है (सुसंगत सेट से एक स्थिति हटने पर एक बार)।
पैरिटीज़ (Parities): 2 के मॉड्यूलो रैखिक समीकरणों (जैसे, $x_{i_1} \oplus \dots \oplus x_{i_k} = 0$ $x_{i_{1}} \oplus \dots \oplus x_{i_{k}} = 0$ ) द्वारा परिभाषित भाषाओं का परिवार।
- रणनीति: शिक्षार्थी देखे गए वेक्टर्स का कोई भी रैखिक संयोजन आउटपुट करता है। एक गलती तभी होती है जब देखा गया सेट लक्षित भाषा के संपूर्ण स्थान (space) को स्पैन करता है, जो $n$ बार होता है क्योंकि स्पैन का आयाम (dimension) बढ़ता है।

3. मुख्य परिणाम: सीमित मैक्सटर्म्स वाले मोनोटोन बुलियन फंक्शन्स

केंद्रीय योगदान यह प्रमाण है कि अधिकतम $p(n)$ मैक्सटर्म्स वाले मोनोटोन बुलियन फंक्शन्स का परिवार किसी भी बहुपद $p(n)$ के लिए बहुपद-समय MBLG है।

परिभाषाएँ: एक मोनोटोन भाषा $L$ का मैक्सटर्म (maxterm) एक अधिकतम इनपुट (समावेशन क्रम में) है जहाँ फलन 0 का मूल्यांकन करता है।
निहितार्थ: यह परिणाम इसमें शामिल है:
- चरों के डिसजंक्शन्स (जिनमें ठीक एक मैक्सटर्म होता है)।
- सभी मोनोटोन बुलियन फंक्शन्स जो बहुपद-आकार के निर्णय वृक्षों (decision trees) द्वारा गणनीय हैं। लेखक तर्क देते हैं कि ऐसे फंक्शन्स में अधिकतम एक बहुपद संख्या में 0-लीव्स होते हैं, और इस प्रकार एक बहुपद संख्या में मैक्सटर्म होते हैं।
एल्गोरिदम: एल्गोरिदम "मैक्सिमल नॉन-मार्क्ड" तत्वों का एक सेट $M$ बनाए रखता है। "महत्वपूर्ण क्षणों" पर (जब चिह्नित शब्दों का सेट अपवर्ड-क्लोज्ड होता है), शिक्षार्थी $M$ से एक ऐसा तत्व आउटपुट करता है जिसे सबसे कम बार चुना गया है।
विश्लेषण: लेखक सिद्ध करते हैं कि $M$ के प्रत्येक तत्व को महत्वपूर्ण क्षणों पर अधिकतम $O(n)$ बार आउटपुट किया जा सकता है। वे चयन गणनाओं के विकास को एक ऐसे खेल में मैप करते हैं जहाँ $n$ मान वाली अवस्था तक पहुँचने के लिए आवश्यक चरणों की संख्या कम से कम $2^{n-1}$ है, यह सुनिश्चित करते हुए कि कुल गलतियाँ बहुपद बनी रहें।

महत्व और दावे

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

सिद्धांत और व्यवहार को जोड़ना: यह MBLG मॉडल की व्यवहार्यता को संबोधित करता है, जो पहले सामान्य परिवारों के लिए गैर-बहुपद समय आवश्यकताओं तक सीमित था।
सीखने की क्षमता का दायरा: लेखक विनम्रतापूर्वक "सीखने योग्य परिवारों के कुछ शुरुआती उदाहरण" प्रदान करने का दावा करते हैं। वे स्पष्ट रूप से कहते हैं कि वर्तमान में यह स्पष्ट नहीं है कि क्या उनका मुख्य परिणाम गैर-मोनोटोन फंक्शन्स (जैसे, लिटरल के डिसजंक्शन्स) तक विस्तृत है या क्या बहुपद-समय MBLG परिवार यूनियन के तहत बंद (closed under union) हैं।
अन्य मॉडलों के साथ संबंध: पेपर नोट करता है कि जबकि प्रत्येक बहुपद-समय ऑनलाइन सीखने योग्य परिवार बहुपद-समय PAC सीखने योग्य होता है, इसके विपरीत हमेशा सत्य नहीं होता है। बहुपद-समय MBLG और इन अन्य मॉडलों के बीच के संबंध को एक खुले प्रश्न के रूप में छोड़ दिया गया है।

कार्य इन परिवारों के क्लोजर गुणों और गैर-मोनोटोन निर्णय वृक्षों और अन्य लर्निंग प्रतिमानों के साथ उनके संबंध के संबंध में खुले प्रश्नों की पहचान करके समाप्त होता है।