Distributional Learning of Context-Free Languages under Fixed Finite-Monoid Typing

तकनीकी सारांश: निश्चित परिमित-मोनोइड टाइपिंग के तहत संदर्भ-मुक्त भाषाओं का वितरण संबंधी शिक्षण (Distributional Learning)

समस्या विवरण
यह शोध पत्र केवल धनात्मक डेटा (positive data) से संदर्भ-मुक्त भाषाओं (context-free languages - CFLs) के व्याकरणिक अनुमान (grammatical inference) की समस्या को संबोधित करता है। गोल्ड के मौलिक नकारात्मक परिणाम के बाद, जो यह बताता है कि कोई भी वर्ग जिसमें सभी परिमित भाषाएँ और कम से कम एक अनंत भाषा शामिल है, धनात्मक डेटा से सीमा में पहचाना (identifiable in the limit) नहीं जा सकता, इस क्षेत्र ने वितरण संबंधी शिक्षण दृष्टिकोणों पर भरोसा किया है। ये दृष्टिकोण उन शर्तों को प्रतिबंधित करते हैं जिनके तहत सबस्ट्रिंग्स (substrings) को प्रतिस्थापनीय (substitutable) माना जाता है। जबकि क्लासिकल फ्रेमवर्क जैसे क्लार्क-आईरोड (Clark–Eyraud) प्रतिस्थापनीयता और योशिनका की $(k, \ell)$-प्रतिस्थापनीयता ने सकारात्मक शिक्षण परिणाम दिए हैं, वे सीमित संदर्भ खिड़कियों (bounded context windows) पर निर्भर करते हैं। यह शोध पत्र एक अधिक सामान्य ढांचे की जांच करता है: एक निश्चित बोधगम्य सर्वांगसमता (fixed recognizable congruence) $\sim_h$ के तहत सीखना, जो एक स्पष्ट परिमित मोनोइड होमोमोर्फिज्म $h: \Sigma^* \to M$ के कर्नेल द्वारा परिभाषित है। मुख्य समस्या यह निर्धारित करना है कि क्या, एक निश्चित $h$ दिए जाने पर, $\sim_h$-प्रतिस्थापनीय संदर्भ-मुक्त भाषाओं ($C^h_{cf}$) का वर्ग धनात्मक डेटा से सीमा में पहचाना जा सकता है, और यदि ऐसा है, तो क्या इसे बहुपद-समय (polynomial-time) और बहुपद-डेटा (polynomial-data) सीमाओं के साथ प्राप्त किया जा सकता है।

कार्यप्रणाली (Methodology)
लेखक एक परिमित टाइप किया गया पुनर्निर्माण सिद्धांत (finite typed reconstruction theory) विकसित करते हैं जो निश्चित-$h$ सेटिंग के अनुकूल है। कार्यप्रणाली निम्नलिखित चरणों के माध्यम से आगे बढ़ती है:

1. टाइप्ड रिफाइनमेंट (Typed Refinement): स्टार्ट-सेपरेटेड बाइनरी नॉर्मल फॉर्म (SSBNF) में एक न्यूनीकृत संदर्भ-मुक्त व्याकरण $G$ से शुरू करते हुए, लेखक एक टाइप्ड रिफाइनमेंट $\tilde{G}$ का निर्माण करते हैं। इस रिफाइनमेंट में, नॉन-टर्मिनल प्रतीकों को टाइप्ड प्रतियों $A^{m,n}_p$ में विभाजित किया जाता है, जहाँ:

   • $p \in M$ द्वारा उत्पन्न यील्ड (yield) का $h$-प्रकार (type) दर्शाया जाता है।
   • $m, n \in M$ क्रमशः बाएं और दाएं परिवेश के $h$-प्रकारों को दर्शाते हैं।
     यह टाइपिंग एक ही नॉन-टर्मिनल के उन अवयवों को अलग करती है जो विभिन्न बीजगणितीय संदर्भों में दिखाई देते हैं, जिससे यह सुनिश्चित होता है कि व्याकरण निश्चित सर्वांगसमता का सम्मान करता है।

2. परिमित टाइप्ड पुनर्निर्माण आधार (Finite Typed Reconstruction Basis): लेखक सिद्ध करते हैं कि सटीक पुनर्निर्माण के लिए प्रासंगिक सिंटैक्टिक जानकारी एक परिमित टाइप्ड पुनर्निर्माण आधार $B(\tilde{G})$ में केंद्रित है। इस आधार में शामिल हैं:

   • पहुंच योग्य (reachable) और उत्पादक (productive) टाइप्ड नॉन-टर्मिनल्स का सेट।
   • वास्तविक टाइप्ड नियम उदाहरणों (rule instances) का सेट।
   • कैनोनिकल टर्मिनल यील्ड और संदर्भ जोड़े (लेक्सिकोग्राफिक रूप से न्यूनतम)।
   • एक परिमित अवलोकन सेट $CS(\tilde{G})$ (विशिष्ट नमूना/characteristic sample) जो इस आधार को "एक्सपोज़" करता है।

3. कैनोनिकल हाइपोथेसिस निर्माण (Canonical Hypothesis Construction): एक परिमित धनात्मक नमूने $K$ को देखते हुए, शिक्षार्थी एक कैनोनिकल हाइपोथेसिस व्याकरण $\hat{G}(K)$ का निर्माण करता है। $\hat{G}(K)$ के नॉन-टर्मिनल्स $[x: u, v]$ के रूप में होते हैं, जो एक गुणनखंड $uxv \in K$ को दर्शाते हैं। नियम स्थानीय गुणनखंडों और निश्चित होमोमोर्फिज्म $h$ से प्राप्त किए जाते हैं:

   • विभाजन (Splitting): यदि $[xy: u, v]$देखा जाता है, तो यह$[x: u, yv]$और$[y: ux, v]$ में विभाजित होता है।
   • परिवहन (Transport): यदि $[x: u, v]$ और $[x: u', v']$ देखे जाते हैं, तो उन्हें जोड़ा जाता है (नॉन-टर्मिनल को संदर्भों के पार ले जाना)।
   • प्रतिस्थापन (Substitution): यदि $[x: u, v]$ और $[x': u, v]$ देखे जाते हैं और $h(x) = h(x')$ है, तो उन्हें जोड़ा जाता है (एक निश्चित संदर्भ के भीतर समान $h$-प्रकार वाली स्ट्रिंग्स को प्रतिस्थापित करना)।

4. सटीक पुनर्निर्माण प्रमाण (Exact Reconstruction Proof): शोध पत्र सिद्ध करता है कि यदि नमूना $K$ अवलोकन सेट $CS(\tilde{G})$ को समाहित करता है, तो $\hat{G}(K)$ लक्ष्य भाषा $L$ को सटीक रूप से उत्पन्न करता है। यह $\sim_h$-प्रतिस्थापनीयता गुण पर निर्भर करता है, जो यह सुनिश्चित करता है कि समान $h$-प्रकार और साझा संदर्भ वाली स्ट्रिंग्स का वितरण समान होता है।

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

1. सटीक पुनर्निर्माण और सीमा में पहचान (Exact Reconstruction and Identification in the Limit):
   प्रत्येक स्पष्ट परिमित मोनोइड होमोमोर्फिज्म $h$ के लिए, $\sim_h$-प्रतिस्थापनीय भाषाओं ($C^h_{cf}$) का वर्ग धनात्मक डेटा से सीमा में पहचाना जा सकता है। शिक्षार्थी $A_h$ एक हाइपोथेसिस $\hat{G}(K)$ का निर्माण करता है जो लक्ष्य भाषा की ओर अभिसरित (converge) होता है जब $K$ में परिमित अवलोकन सेट $CS(\tilde{G})$ शामिल होता है।

2. बहुपद-समय जटिलता (नमूना-आकार सीमा):
   सामान्य संदर्भ-मुक्त वर्ग $C^h_{cf}$ के लिए, हाइपोथेसिस व्याकरण $\hat{G}(K)$ का निर्माण और अपडेट नमूने के आकार के सापेक्ष बहुपद समय (विशेष रूप से, $O(\|K\|^5)$) में किया जा सकता है। जबकि हाइपोथेसिस सटीक लक्ष्य भाषा की ओर अभिसरित होती है, शोध पत्र इस सामान्य मामले के लिए आवश्यक विशिष्ट नमूने (characteristic sample) के आकार पर कोई बहुपद सीमा स्थापित नहीं करता है।

3. लीनियर भाषाओं के लिए पूर्ण बहुपद समय-और-डेटा:
   लीनियर उपवर्ग $C^h_{lin}$ के लिए, लेखक अधिक मजबूत सीमाएं स्थापित करते हैं। वे सिद्ध करते हैं कि विशिष्ट नमूने का आकार और उसके शब्दों की लंबाई लक्ष्य व्याकरण के आकार के बहुपद में सीमित है। फलस्वरूप, शिक्षार्थी लीनियर लक्ष्यों के लिए एक पूर्ण बहुपद समय-और-डेटा परिणाम प्राप्त करता है।

4. संरचनात्मक सीमा परिणाम (Structural Boundary Results):
   यह शोध पत्र वितरण संबंधी शिक्षण के व्यापक परिदृश्य में निश्चित-$h$ ढांचे को स्थापित करता है:

   • नियमित स्तर पर सख्त समावेशन (Strict Inclusion at Regular Level): सीमित प्रीफिक्स-सफिक्स संदर्भों ($K_L$, योशिनका के $(k, \ell)$-प्रतिस्थापनीय वर्गों का संघ) द्वारा पहचानने योग्य भाषाओं का वर्ग, $\sim_h$-प्रतिस्थापनीय भाषाओं ($RS$) के वर्ग में सख्ती से समाहित है। इसे **कैप्ड-काउंटर फैमिली**$CCL_p$(जहाँ$p \ge 2$) का उपयोग करके प्रदर्शित किया गया है, जो नियमित है और$RS$में है, लेकिन किसी भी$(k, \ell)$ वर्ग में नहीं है।
   • **$RS$की सीमाएं:** सभी डिटरमिनिस्टिक संदर्भ-मुक्त भाषाएँ$RS$में नहीं आती हैं। शोध पत्र दिखाता है कि अनकैप्ड काउंटर भाषा ($CCL$), वन-ब्रैकेट डिक भाषा ($D_1$), और योशिनका की क्लासिकल भाषा ($L(S \to aSS \mid b)$)$RS$ के बाहर हैं।
   • गैर-नियमित विस्तार (Non-Regular Extension): महत्वपूर्ण रूप से, यह शोध पत्र एक खुले प्रश्न को हल करता है, यह दिखाते हुए कि सख्त समावेशन $K_L \subsetneq RS$ नियमित भाषाओं से परे भी विस्तृत है। भाषा $L^* = \{a^n b^n : n \ge 0\}^*$ को एक गैर-नियमित डिटरमिनिस्टिक संदर्भ-मुक्त भाषा के रूप में सिद्ध किया गया है जो $RS \setminus K_L$ में है।

महत्व और दावे
शोध पत्र का दावा है कि यह वितरण संबंधी संदर्भ-मुक्त शिक्षण के भीतर एक "गणितीय रूप से सुदृढ़ और संरचनात्मक रूप से पारदर्शी उप-सिद्धांत" को तराशता है। इसका प्राथमिक महत्व निम्नलिखित में निहित है:

• प्रतिस्थापनीयता का सामान्यीकरण: सीमित संदर्भ खिड़कियों के स्थान पर मनमाने बोधगम्य सर्वांगमताओं को प्रतिस्थापित करना, जिससे पिछले परिणामों (क्लार्क-आईरोड और $(k, \ell)$-प्रतिस्थापनीयता) को एक विशेष मामले के रूप में एकीकृत और विस्तारित किया जा सके।
• समस्याओं का पृथक्करण: सर्वांगसमता के अनुमान (inferring the congruence) की समस्या को एक निश्चित सर्वांगसमता के तहत सीखने (learning under a fixed congruence) की समस्या से स्पष्ट रूप से अलग करना। यह शोध पत्र दूसरे पर ध्यान केंद्रित करता है, जो निश्चित-$h$ व्यवस्था के लिए एक पूर्ण समाधान प्रदान करता है।
• लीनियर लक्ष्यों के लिए पूर्णता: एक सामान्य वितरण संबंधी प्रतिबंध के तहत गैर-तुच्छ संदर्भ-मुक्त उपवर्ग (लीनियर उपवर्ग $C^h_{lin}$) के लिए पहला पूर्ण बहुपद समय-और-डेटा प्रमेय प्रदान करना।

लेखक विनम्रतापूर्वक नोट करते हैं कि हालांकि वे निश्चित-$h$ सेटिंग के लिए एक संरचनात्मक लक्षण वर्णन प्रदान करते हैं, लेकिन $RS \cap CFL$ के पूर्ण लक्षण वर्णन का मुद्दा अभी भी खुला है। उन्होंने "अनजान-$h$" सेटिंग (डेटा से सर्वांगसमता का अनुमान लगाना) और समृद्ध औपचारिकताओं (जैसे MCFGs) तक विस्तार को भविष्य के कार्यों के लिए स्वाभाविक दिशा के रूप में भी पहचाना है।