व्याकरण प्रेरण: Difference between revisions

From Vigyanwiki
(Created page with "{{Machine learning|Problems}} व्याकरण प्रेरण (या व्याकरणिक अनुमान)<ref name="Grammatical Inference">{{cite book|las...")
 
No edit summary
 
(6 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Machine learning|Problems}}
'''व्याकरण प्रेरण''' या व्याकरणिक अनुमान <ref name="Grammatical Inference">{{cite book|last=de la Higuera|first=Colin|title=Grammatical Inference: Learning Automata and Grammars|date=2010|publisher=Cambridge University Press|location=Cambridge|url=http://bootcamp.lif.univ-mrs.fr/de-la-higuera.pdf|access-date=2017-08-16|archive-date=2019-02-14|archive-url=https://web.archive.org/web/20190214170942/http://bootcamp.lif.univ-mrs.fr/de-la-higuera.pdf|url-status=dead}}</ref> [[ यंत्र अधिगम |मशीन लर्निंग]] में अवलोकनों के सेट से [[औपचारिक व्याकरण]] (सामान्यतः फिर से लिखने वाले नियमों या प्रस्तुतियों कंप्यूटर विज्ञान के संग्रह के रूप में या वैकल्पिक रूप से परिमित स्तर मशीन या किसी प्रकार की ऑटोमेटन के रूप में) सीखने की प्रक्रिया है, इस प्रकार मॉडल का निर्माण होता है जो प्रेक्षित वस्तुओं की विशेषताओं का वर्णन करता है। इस प्रकार अधिक सामान्यतः, व्याकरणिक अनुमान मशीन लर्निंग की वह शाखा है जहां इंस्टेंस स्पेस में स्ट्रिंग, ट्री और ग्राफ़ जैसी अलग-अलग संयोजक वस्तुएं होती हैं।
व्याकरण प्रेरण (या व्याकरणिक अनुमान)<ref name="Grammatical Inference">{{cite book|last=de la Higuera|first=Colin|title=Grammatical Inference: Learning Automata and Grammars|date=2010|publisher=Cambridge University Press|location=Cambridge|url=http://bootcamp.lif.univ-mrs.fr/de-la-higuera.pdf|access-date=2017-08-16|archive-date=2019-02-14|archive-url=https://web.archive.org/web/20190214170942/http://bootcamp.lif.univ-mrs.fr/de-la-higuera.pdf|url-status=dead}}</ref> [[ यंत्र अधिगम ]] में अवलोकनों के एक सेट से एक [[औपचारिक व्याकरण]] (आमतौर पर फिर से लिखने वाले नियमों या प्रस्तुतियों (कंप्यूटर विज्ञान) के संग्रह के रूप में या वैकल्पिक रूप से एक परिमित राज्य मशीन या किसी प्रकार की ऑटोमेटन के रूप में) सीखने की प्रक्रिया है, इस प्रकार एक मॉडल का निर्माण होता है जो प्रेक्षित वस्तुओं की विशेषताओं का वर्णन करता है। अधिक आम तौर पर, व्याकरणिक अनुमान मशीन लर्निंग की वह शाखा है जहां इंस्टेंस स्पेस में स्ट्रिंग, पेड़ और ग्राफ़ जैसी अलग-अलग संयोजक वस्तुएं होती हैं।


==व्याकरण कक्षाएं==
==व्याकरण कक्षाएं==


व्याकरणिक अनुमान अक्सर विभिन्न प्रकार की परिमित राज्य मशीनों को सीखने की समस्या पर केंद्रित रहा है (इन दृष्टिकोणों पर विवरण के लिए [[नियमित भाषाओं का प्रेरण]] लेख देखें), क्योंकि 1980 के दशक से इस समस्या के लिए कुशल एल्गोरिदम मौजूद हैं।
व्याकरणिक अनुमान अधिकांशतः विभिन्न प्रकार की परिमित स्तर मशीनों को सीखने की समस्या पर केंद्रित रहा है (इन दृष्टिकोणों पर विवरण के लिए [[नियमित भाषाओं का प्रेरण|नियमित लैंग्वेजेस का प्रेरण]] लेख देखें), क्योंकि 1980 के दशक से इस समस्या के लिए कुशल एल्गोरिदम उपस्थित हैं।


सदी की शुरुआत के बाद से, इन दृष्टिकोणों को [[संदर्भ-मुक्त व्याकरण]] और समृद्ध औपचारिकताओं, जैसे एकाधिक संदर्भ-मुक्त व्याकरण और समानांतर एकाधिक संदर्भ-मुक्त व्याकरण, के अनुमान की समस्या तक विस्तारित किया गया है।
शताब्दी की प्रारंभ के पश्चात्, इन दृष्टिकोणों को [[संदर्भ-मुक्त व्याकरण]] और समृद्ध औपचारिकताओं, जैसे एकाधिक संदर्भ-मुक्त व्याकरण और समानांतर एकाधिक संदर्भ-मुक्त व्याकरण, अनुमान की समस्या तक विस्तारित किया गया है। इस प्रकार व्याकरण के अन्य वर्ग जिनके लिए व्याकरणिक अनुमान का अध्ययन किया गया है, इस प्रकार संयोजनात्मक श्रेणीबद्ध व्याकरण हैं,<ref name="Kwiatkowski"/> [[स्टोकेस्टिक संदर्भ-मुक्त व्याकरण]], <ref>Clark, Alexander. "[https://www.aclweb.org/anthology/W01-0713 Unsupervised induction of stochastic context-free grammars using distributional clustering]." Proceedings of the 2001 workshop on Computational Natural Language Learning-Volume 7. Association for Computational Linguistics, 2001.</ref> प्रासंगिक व्याकरण और क्रम भाषाएँ होती है।
व्याकरण के अन्य वर्ग जिनके लिए व्याकरणिक अनुमान का अध्ययन किया गया है, संयोजनात्मक श्रेणीबद्ध व्याकरण हैं,<ref name="Kwiatkowski"/>[[स्टोकेस्टिक संदर्भ-मुक्त व्याकरण]],<ref>Clark, Alexander. "[https://www.aclweb.org/anthology/W01-0713 Unsupervised induction of stochastic context-free grammars using distributional clustering]." Proceedings of the 2001 workshop on Computational Natural Language Learning-Volume 7. Association for Computational Linguistics, 2001.</ref> प्रासंगिक व्याकरण और पैटर्न भाषाएँ।


==सीखने के मॉडल==
==शिक्षण मॉडल==


सीखने का सबसे सरल रूप वह है जहां सीखने का एल्गोरिदम केवल संबंधित भाषा से लिए गए उदाहरणों का एक सेट प्राप्त करता है: इसका उद्देश्य भाषा को इसके उदाहरणों से सीखना है (और, शायद ही कभी, काउंटर-उदाहरणों से, यानी उदाहरण जो ऐसा करते हैं) भाषा से संबंधित नहीं)
सीखने का सबसे सरल रूप वह है जहां सीखने का एल्गोरिदम केवल संबंधित लैंग्वेज से लिए गए उदाहरणों का सेट प्राप्त करता है: इसका उद्देश्य लैंग्वेज को इसके उदाहरणों से सीखना है (और, संभवतः ही कभी, काउंटर-उदाहरणों से, अर्थात उदाहरण जो ऐसा करते हैं) लैंग्वेज से संबंधित नहीं)
हालाँकि, अन्य शिक्षण मॉडलों का अध्ययन किया गया है। अक्सर अध्ययन किया जाने वाला एक विकल्प वह मामला है जहां शिक्षार्थी सटीक क्वेरी लर्निंग मॉडल या एंग्लुइन द्वारा पेश किए गए न्यूनतम पर्याप्त शिक्षक मॉडल के रूप में सदस्यता प्रश्न पूछ सकता है।<ref>{{cite journal|author=Dana Angluin |title=प्रश्नों और प्रति-उदाहरणों से नियमित सेट सीखना|journal=[[Information and Control]] |year=1987 |volume=75 |issue=2 |pages=87–106 |url=http://www.cse.iitk.ac.in/users/chitti/thesis/references/learningRegSetsFromQueriesAndCounterExamples.pdf |doi=10.1016/0890-5401(87)90052-6 |citeseerx=10.1.1.187.9414 |url-status=dead |archiveurl=https://web.archive.org/web/20131202232143/http://www.cse.iitk.ac.in/users/chitti/thesis/references/learningRegSetsFromQueriesAndCounterExamples.pdf |archivedate=2013-12-02 }}</ref>


चूँकि, अन्य शिक्षण मॉडलों का अध्ययन किया गया है। इस प्रकार अधिकांशतः अध्ययन किया जाने वाला विकल्प वह स्थिति है जहां शिक्षार्थी स्पष्ट क्वेरी लर्निंग मॉडल या एंग्लुइन द्वारा प्रस्तुत किए गए न्यूनतम पर्याप्त शिक्षक मॉडल के रूप में सदस्यता प्रश्न पूछ सकता है।<ref>{{cite journal|author=Dana Angluin |title=प्रश्नों और प्रति-उदाहरणों से नियमित सेट सीखना|journal=[[Information and Control]] |year=1987 |volume=75 |issue=2 |pages=87–106 |url=http://www.cse.iitk.ac.in/users/chitti/thesis/references/learningRegSetsFromQueriesAndCounterExamples.pdf |doi=10.1016/0890-5401(87)90052-6 |citeseerx=10.1.1.187.9414 |url-status=dead |archiveurl=https://web.archive.org/web/20131202232143/http://www.cse.iitk.ac.in/users/chitti/thesis/references/learningRegSetsFromQueriesAndCounterExamples.pdf |archivedate=2013-12-02 }}</ref>


==तरीके==
 
व्याकरणिक अनुमान के लिए अनेक प्रकार की विधियाँ हैं। दो क्लासिक स्रोत हैं {{Harvtxt|Fu|1977}} और {{Harvtxt|Fu|1982}}. {{Harvtxt|Duda|Hart|Stork|2001}} समस्या के लिए एक संक्षिप्त अनुभाग भी समर्पित करें, और कई संदर्भ उद्धृत करें। उनके द्वारा प्रस्तुत बुनियादी परीक्षण-और-त्रुटि विधि की चर्चा नीचे की गई है। विशेष रूप से नियमित भाषाओं के उपवर्गों का अनुमान लगाने के तरीकों के लिए, नियमित भाषाओं का प्रेरण देखें। एक और हालिया पाठ्यपुस्तक डे ला हिगुएरा (2010) है,<ref name = "Grammatical Inference"/>जो नियमित भाषाओं और परिमित राज्य ऑटोमेटा के व्याकरणिक अनुमान के सिद्धांत को शामिल करता है। डी'उलिज़िया, फ़ेरी और ग्रिफ़ोनी<ref>D’Ulizia, A., Ferri, F., Grifoni, P. (2011) "[https://www.academia.edu/download/41900378/A_survey_of_grammatical_inference_method20160202-5760-79hwcu.pdf A Survey of Grammatical Inference Methods for Natural Language Learning]{{dead link|date=July 2022|bot=medic}}{{cbignore|bot=medic}}", ''Artificial Intelligence Review'', Vol. 36, No. 1, pp. 1–27.</ref> एक सर्वेक्षण प्रदान करें जो प्राकृतिक भाषाओं के लिए व्याकरणिक अनुमान विधियों की खोज करता है।
 
==पद्धतियाँ==
व्याकरणिक अनुमान के लिए अनेक प्रकार की विधियाँ हैं। दो क्लासिक स्रोत हैं {{Harvtxt|फु|1977}} और {{Harvtxt|फू|1982}}. {{Harvtxt|डुडा|हार्ट|स्टोर्क|2001}} समस्या के लिए संक्षिप्त अनुभाग भी समर्पित करें, और इस प्रकार अनके संदर्भ उद्धृत करें। इस प्रकार उनके द्वारा प्रस्तुत मूलभूत परीक्षण-और-त्रुटि विधि की चर्चा नीचे की गई है। विशेष रूप से नियमित लैंग्वेजेस के उपवर्गों का अनुमान लगाने के विधियों के लिए, नियमित लैंग्वेजेस का प्रेरण देखें। और वर्तमान पाठ्यपुस्तक डे ला हिगुएरा (2010) है,<ref name = "Grammatical Inference"/> जो नियमित लैंग्वेजेस और परिमित स्तर ऑटोमेटा के व्याकरणिक अनुमान के सिद्धांत को सम्मिलित करता है। इस प्रकार डी'उलिज़िया, फ़ेरी और ग्रिफ़ोनी <ref>D’Ulizia, A., Ferri, F., Grifoni, P. (2011) "[https://www.academia.edu/download/41900378/A_survey_of_grammatical_inference_method20160202-5760-79hwcu.pdf A Survey of Grammatical Inference Methods for Natural Language Learning]{{dead link|date=July 2022|bot=medic}}{{cbignore|bot=medic}}", ''Artificial Intelligence Review'', Vol. 36, No. 1, pp. 1–27.</ref> सर्वेक्षण प्रदान करें जो प्राकृतिक लैंग्वेजेस के लिए व्याकरणिक अनुमान विधियों की खोज करता है।


===परीक्षण-और-त्रुटि द्वारा व्याकरणिक अनुमान===
===परीक्षण-और-त्रुटि द्वारा व्याकरणिक अनुमान===
की धारा 8.7 में प्रस्तावित विधि {{Harvtxt|Duda|Hart|Stork|2001}} व्याकरण के नियमों (प्रस्तुतियों) का क्रमिक रूप से अनुमान लगाने और उन्हें सकारात्मक और नकारात्मक टिप्पणियों के विरुद्ध परीक्षण करने का सुझाव देता है। नियम सेट का विस्तार किया गया है ताकि प्रत्येक सकारात्मक उदाहरण उत्पन्न किया जा सके, लेकिन यदि कोई दिया गया नियम सेट भी नकारात्मक उदाहरण उत्पन्न करता है, तो इसे छोड़ दिया जाना चाहिए। इस विशेष दृष्टिकोण को परिकल्पना परीक्षण के रूप में वर्णित किया जा सकता है और मिशेल के संस्करण अंतरिक्ष एल्गोरिदम में कुछ समानता है। वह {{Harvtxt|Duda|Hart|Stork|2001}} पाठ एक सरल उदाहरण प्रदान करता है जो प्रक्रिया को अच्छी तरह से चित्रित करता है, लेकिन अधिक महत्वपूर्ण समस्याओं के लिए इस तरह के एक अनियंत्रित परीक्षण-और-त्रुटि दृष्टिकोण की व्यवहार्यता संदिग्ध है।
{{Harvtxt|डुडा|हार्ट|स्टोर्क|2001}} की धारा 8.7 में प्रस्तावित विधि व्याकरण के नियमों (प्रस्तुतियों) का क्रमिक रूप से अनुमान लगाने और उन्हें सकारात्मक और नकारात्मक टिप्पणियों के विरुद्ध परीक्षण करने का सुझाव देता है। इस प्रकार नियम सेट का विस्तार किया गया है जिससे प्रत्येक सकारात्मक उदाहरण उत्पन्न किया जा सके, किन्तु यदि कोई दिया गया नियम सेट भी नकारात्मक उदाहरण उत्पन्न करता है, जिससे इसे छोड़ दिया जाना चाहिए। इस विशेष दृष्टिकोण को परिकल्पना परीक्षण के रूप में वर्णित किया जा सकता है और मिशेल के संस्करण अंतरिक्ष एल्गोरिदम में कुछ समानता है। इस प्रकार वह {{Harvtxt|डुडा|हार्ट|स्टोर्क|2001}} टेक्स्ट सरल उदाहरण प्रदान करता है जो प्रक्रिया को अच्छी तरह से चित्रित करता है, किन्तु अधिक महत्वपूर्ण समस्याओं के लिए इस तरह के अनियंत्रित परीक्षण-और-त्रुटि दृष्टिकोण की व्यवहार्यता संदिग्ध है।


=== आनुवंशिक [[कलन विधि]] द्वारा व्याकरणिक अनुमान ===
=== आनुवंशिक [[कलन विधि]] द्वारा व्याकरणिक अनुमान ===
[[विकासवादी एल्गोरिदम]] का उपयोग करके व्याकरणिक प्रेरण कुछ विकासवादी प्रक्रिया के माध्यम से लक्ष्य भाषा के व्याकरण का प्रतिनिधित्व विकसित करने की प्रक्रिया है। औपचारिक व्याकरण को आसानी से उत्पादन नियमों के [[वृक्ष (डेटा संरचना)]] के रूप में दर्शाया जा सकता है जिसे विकासवादी ऑपरेटरों के अधीन किया जा सकता है। इस प्रकार के एल्गोरिदम [[जॉन बकरी]] द्वारा प्रवर्तित [[आनुवंशिक प्रोग्रामिंग]] प्रतिमान से उत्पन्न होते हैं।{{Citation needed|date=August 2007}} सरल औपचारिक भाषाओं पर अन्य प्रारंभिक कार्यों में आनुवंशिक एल्गोरिदम के बाइनरी स्ट्रिंग प्रतिनिधित्व का उपयोग किया गया था, लेकिन विस्तारित बैकस-नौर फॉर्म भाषा में निहित व्याकरणों की अंतर्निहित पदानुक्रमित संरचना ने पेड़ों को अधिक लचीला दृष्टिकोण बना दिया।
[[विकासवादी एल्गोरिदम]] का उपयोग करके व्याकरणिक प्रेरण कुछ विकासवादी प्रक्रिया के माध्यम से लक्ष्य लैंग्वेज के व्याकरण का प्रतिनिधित्व विकसित करने की प्रक्रिया है। औपचारिक व्याकरण को सरलता से उत्पादन नियमों के [[वृक्ष (डेटा संरचना)|ट्री (डेटा संरचना)]] के रूप में दर्शाया जा सकता है इस प्रकार जिसे विकासवादी संचालको के अधीन किया जा सकता है। इस प्रकार के एल्गोरिदम [[जॉन बकरी|जॉन कोज़ा]] द्वारा प्रवर्तित [[आनुवंशिक प्रोग्रामिंग]] प्रतिमान से उत्पन्न होते हैं। इस प्रकार सरल औपचारिक लैंग्वेजेस पर अन्य प्रारंभिक कार्यों में आनुवंशिक एल्गोरिदम के बाइनरी स्ट्रिंग प्रतिनिधित्व का उपयोग किया गया था, किन्तु विस्तारित बैकस-नौर फॉर्म लैंग्वेज में निहित व्याकरणों की अंतर्निहित पदानुक्रमित संरचना ने ट्री को अधिक लचीला दृष्टिकोण बना दिया था।


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


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


===लालची एल्गोरिदम द्वारा व्याकरणिक अनुमान===
===ग्रीडी एल्गोरिदम द्वारा व्याकरणिक अनुमान===
सभी लालची एल्गोरिदम की तरह, लालची व्याकरण अनुमान एल्गोरिदम, पुनरावृत्त तरीके से, ऐसे निर्णय लेते हैं जो उस स्तर पर सबसे अच्छे लगते हैं।
सभी ग्रीडी एल्गोरिदम की तरह, ग्रीडी व्याकरण अनुमान एल्गोरिदम, पुनरावृत्त विधि से, ऐसे निर्णय लेते हैं जो उस स्तर पर सबसे अच्छे लगते हैं। इसके लिए गए निर्णय सामान्यतः नए नियमों के निर्माण, उपस्थिता नियमों को हटाने, प्रयुक्त किए जाने वाले नियम के चुनाव या कुछ उपस्थिता नियमों के विलय जैसी चीजों से संबंधित होते हैं।
लिए गए निर्णय आम तौर पर नए नियमों के निर्माण, मौजूदा नियमों को हटाने, लागू किए जाने वाले नियम के चुनाव या कुछ मौजूदा नियमों के विलय जैसी चीजों से संबंधित होते हैं।
 
चूँकि 'मंच' और 'सर्वश्रेष्ठ' को परिभाषित करने के कई तरीके हैं, इसलिए कई लालची व्याकरण अनुमान एल्गोरिदम भी हैं।
चूँकि 'फोरम' और 'सर्वश्रेष्ठ' को परिभाषित करने के अनके विधि हैं, इसलिए अनके ग्रीडी व्याकरण अनुमान एल्गोरिदम भी हैं।


ये [[संदर्भ-मुक्त व्याकरण]] उत्पन्न करने वाले एल्गोरिदम प्रत्येक पढ़े गए प्रतीक के बाद निर्णय लेते हैं:
ये [[संदर्भ-मुक्त व्याकरण]] उत्पन्न करने वाले एल्गोरिदम प्रत्येक पढ़े गए प्रतीक के बाद निर्णय लेते हैं:
* [[LZW]]|लेम्पेल-ज़िव-वेल्च एल्गोरिथ्म एक नियतात्मक तरीके से एक संदर्भ-मुक्त व्याकरण बनाता है जैसे कि उत्पन्न व्याकरण के केवल प्रारंभ नियम को संग्रहीत करना आवश्यक है।
* [[LZW|एलजेडडब्ल्यू]] या लेम्पेल-ज़िव-वेल्च एल्गोरिथ्म नियतात्मक विधि से संदर्भ-मुक्त व्याकरण बनाता है जैसे कि उत्पन्न व्याकरण के केवल प्रारंभ नियम को संग्रहीत करना आवश्यक है।
* [[एल्गोरिथ्म इस प्रकार है]] और इसके संशोधन।
* सेक्विटुर और इसके संशोधन।


ये संदर्भ-मुक्त व्याकरण उत्पन्न करने वाले एल्गोरिदम पहले दिए गए पूरे प्रतीक-अनुक्रम को पढ़ते हैं और फिर निर्णय लेना शुरू करते हैं:
ये संदर्भ-मुक्त व्याकरण उत्पन्न करने वाले एल्गोरिदम पहले दिए गए पूरे प्रतीक-अनुक्रम को पढ़ते हैं और फिर निर्णय लेना प्रारंभ करते हैं:
* [[बाइट जोड़ी एन्कोडिंग]] और इसके अनुकूलन।
* [[बाइट जोड़ी एन्कोडिंग]] और इसके अनुकूलन।


===वितरणात्मक शिक्षा===
===वितरणात्मक शिक्षा===
एक और हालिया दृष्टिकोण वितरणात्मक शिक्षा पर आधारित है। इन दृष्टिकोणों का उपयोग करने वाले एल्गोरिदम को संदर्भ-मुक्त व्याकरण और हल्के संदर्भ-संवेदनशील भाषाओं को सीखने के लिए लागू किया गया है और इन व्याकरणों के बड़े उपवर्गों के लिए सही और कुशल साबित हुए हैं।<ref>Clark and Eyraud (2007) ''Journal of Machine Learning Research''; Ryo Yoshinaka (2011) ''Theoretical Computer Science''</ref>
एक और वर्तमान दृष्टिकोण वितरणात्मक शिक्षा पर आधारित है। इन दृष्टिकोणों का उपयोग करने वाले एल्गोरिदम को संदर्भ-मुक्त व्याकरण और इस प्रकार हल्के संदर्भ-संवेदनशील लैंग्वेजेस को सीखने के लिए प्रयुक्त किया गया है और इन व्याकरणों के बड़े उपवर्गों के लिए सही और कुशल सिद्ध हुए हैं।<ref>Clark and Eyraud (2007) ''Journal of Machine Learning Research''; Ryo Yoshinaka (2011) ''Theoretical Computer Science''</ref>




===पैटर्न भाषा (औपचारिक भाषाएं) सीखना===
===क्रम लैंग्वेज (औपचारिक भाषाएं) सीखना===


एंग्लुइन एक पैटर्न को Σ से स्थिर प्रतीकों की एक स्ट्रिंग और एक असंयुक्त सेट से 'परिवर्तनीय प्रतीकों' के रूप में परिभाषित करता है।
एंग्लुइन क्रम को Σ से स्थिर प्रतीकों की स्ट्रिंग और असंयुक्त सेट से 'परिवर्तनीय प्रतीकों' के रूप में परिभाषित करता है। इस तरह के क्रम की लैंग्वेज इसके सभी गैर-रिक्त ग्राउंड उदाहरणों का सेट है अर्थात सभी स्ट्रिंग्स जो निरंतर प्रतीकों के गैर-रिक्त स्ट्रिंग्स द्वारा इसके वेरिएबल प्रतीकों के निरंतर प्रतिस्थापन से उत्पन्न होती हैं।
इस तरह के पैटर्न की भाषा इसके सभी गैर-रिक्त ग्राउंड उदाहरणों का सेट है यानी सभी स्ट्रिंग्स जो निरंतर प्रतीकों के गैर-रिक्त स्ट्रिंग्स द्वारा इसके चर प्रतीकों के लगातार प्रतिस्थापन से उत्पन्न होती हैं।<ref group=note>The language of a pattern with at least two occurrences of the same variable is not regular due to the [[Pumping lemma for regular languages|pumping lemma]].</ref>
एक पैटर्न को स्ट्रिंग्स के एक सीमित इनपुट सेट के लिए वर्णनात्मक कहा जाता है यदि इसकी भाषा इनपुट सेट को शामिल करने वाली सभी पैटर्न भाषाओं के बीच न्यूनतम (सेट समावेशन के संबंध में) है।


एंग्लुइन किसी दिए गए इनपुट स्ट्रिंग सेट के लिए, एक चर ''x'' में सभी वर्णनात्मक पैटर्न की गणना करने के लिए एक बहुपद एल्गोरिथ्म देता है।<ref group=note>''x'' may occur several times, but no other variable ''y'' may occur</ref>
एक क्रम को स्ट्रिंग्स के सीमित इनपुट सेट के लिए वर्णनात्मक कहा जाता है इस प्रकार यदि इसकी लैंग्वेज इनपुट सेट को सम्मिलित करने वाली सभी क्रम लैंग्वेजेस के मध्य न्यूनतम (सेट समावेशन के संबंध में) है।
इस प्रयोजन के लिए, वह सभी संभावित प्रासंगिक पैटर्न का प्रतिनिधित्व करने वाला एक ऑटोमेटन बनाती है; शब्द की लंबाई के बारे में परिष्कृत तर्कों का उपयोग करते हुए, जो x के एकमात्र चर होने पर निर्भर करते हैं, राज्य गणना को काफी हद तक कम किया जा सकता है।<ref>{{cite journal| author=Dana Angluin| title=स्ट्रिंग्स के एक सेट के लिए सामान्य पैटर्न ढूँढना| journal=Journal of Computer and System Sciences| year=1980| volume=21| pages=46–62| doi=10.1016/0022-0000(80)90041-0| doi-access=free}}</ref>
एर्लेबैक एट अल. एंग्लुइन के पैटर्न लर्निंग एल्गोरिदम का अधिक कुशल संस्करण, साथ ही एक समानांतर संस्करण भी दें।<ref>{{cite book|author1=T. Erlebach |author2=P. Rossmanith |author3=H. Stadtherr |author4=A. Steger |author4-link=Angelika Steger|author5=T. Zeugmann | chapter=Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries| title=Proc. 8th International Workshop on Algorithmic Learning Theory — ALT'97| year=1997| volume=1316| pages=260–276| publisher=Springer|editor1=M. Li |editor2=A. Maruoka | series=LNAI|chapter-url=https://www.sciencedirect.com/science/article/pii/S0304397500001365/pdf?md5=c9bd770b62e31dcdce6b039a6c392c8f&pid=1-s2.0-S0304397500001365-main.pdf&_valck=1}}</ref>
अरिमुरा एट अल. दिखाएँ कि पैटर्न के सीमित संघों से प्राप्त भाषा वर्ग को बहुपद समय में सीखा जा सकता है।<ref>{{cite book|author1=Hiroki Arimura |author2=Takeshi Shinohara |author3=Setsuko Otsuki | chapter=Finding Minimal Generalizations for Unions of Pattern Languages and Its Application to Inductive Inference from Positive Data| title=प्रोक. स्टैक्स 11| year=1994| volume=775| pages=649–660| publisher=Springer| series=LNCS|chapter-url=http://ai2-s2-pdfs.s3.amazonaws.com/6a4c/0482e0030b0e5791cf75b0edd9f55fdfc10e.pdf}}{{dead link|date=February 2018}}</ref>


एंग्लुइन किसी दिए गए इनपुट स्ट्रिंग सेट के लिए, वेरिएबल ''x'' में सभी वर्णनात्मक क्रम की गणना करने के लिए बहुपद एल्गोरिथ्म देता है। इस प्रयोजन के लिए, वह सभी संभावित प्रासंगिक क्रम का प्रतिनिधित्व करने वाला ऑटोमेटन बनाती है; इस प्रकार शब्द की लंबाई के बारे में परिष्कृत तर्कों का उपयोग करते हुए, जो x के एकमात्र वेरिएबल होने पर निर्भर करते हैं, इस प्रकार स्तर गणना को अधिक सीमा तक कम किया जा सकता है।<ref>{{cite journal| author=Dana Angluin| title=स्ट्रिंग्स के एक सेट के लिए सामान्य पैटर्न ढूँढना| journal=Journal of Computer and System Sciences| year=1980| volume=21| pages=46–62| doi=10.1016/0022-0000(80)90041-0| doi-access=free}}</ref>


===[[पैटर्न सिद्धांत]]===
एर्लेबैक एट अल. एंग्लुइन के क्रम लर्निंग एल्गोरिदम का अधिक कुशल संस्करण, साथ ही समानांतर संस्करण भी दें।<ref>{{cite book|author1=T. Erlebach |author2=P. Rossmanith |author3=H. Stadtherr |author4=A. Steger |author4-link=Angelika Steger|author5=T. Zeugmann | chapter=Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries| title=Proc. 8th International Workshop on Algorithmic Learning Theory — ALT'97| year=1997| volume=1316| pages=260–276| publisher=Springer|editor1=M. Li |editor2=A. Maruoka | series=LNAI|chapter-url=https://www.sciencedirect.com/science/article/pii/S0304397500001365/pdf?md5=c9bd770b62e31dcdce6b039a6c392c8f&pid=1-s2.0-S0304397500001365-main.pdf&_valck=1}}</ref> इस प्रकार अरिमुरा एट अल. दिखाएँ कि क्रम के सीमित संघों से प्राप्त लैंग्वेज वर्ग को बहुपद समय में सीखा जा सकता है।<ref>{{cite book|author1=Hiroki Arimura |author2=Takeshi Shinohara |author3=Setsuko Otsuki | chapter=Finding Minimal Generalizations for Unions of Pattern Languages and Its Application to Inductive Inference from Positive Data| title=प्रोक. स्टैक्स 11| year=1994| volume=775| pages=649–660| publisher=Springer| series=LNCS|chapter-url=http://ai2-s2-pdfs.s3.amazonaws.com/6a4c/0482e0030b0e5791cf75b0edd9f55fdfc10e.pdf}}{{dead link|date=February 2018}}</ref>
[[उल्फ ग्रेनेंडर]] द्वारा प्रतिपादित पैटर्न सिद्धांत,<ref>Grenander, Ulf, and Michael I. Miller. ''[http://www.ulb.tu-darmstadt.de/tocs/185410162.pdf Pattern theory: from representation to inference]''.{{dead link|date=March 2018}} Vol. 1. Oxford: Oxford university press, 2007.</ref> दुनिया के ज्ञान को पैटर्न के रूप में वर्णित करने के लिए एक गणितीय [[औपचारिकता (गणित)]] है। यह कृत्रिम बुद्धिमत्ता के अन्य दृष्टिकोणों से इस मायने में भिन्न है कि यह पैटर्न को पहचानने और वर्गीकृत करने के लिए एल्गोरिदम और मशीनरी निर्धारित करने से शुरू नहीं होता है; बल्कि, यह पैटर्न अवधारणाओं को सटीक भाषा में व्यक्त करने और पुनर्गठित करने के लिए एक शब्दावली निर्धारित करता है।
===[[पैटर्न सिद्धांत|क्रम सिद्धांत]]===
[[उल्फ ग्रेनेंडर]] द्वारा प्रतिपादित क्रम सिद्धांत,<ref>Grenander, Ulf, and Michael I. Miller. ''[http://www.ulb.tu-darmstadt.de/tocs/185410162.pdf Pattern theory: from representation to inference]''.{{dead link|date=March 2018}} Vol. 1. Oxford: Oxford university press, 2007.</ref> संसार के ज्ञान को क्रम के रूप में वर्णित करने के लिए गणितीय [[औपचारिकता (गणित)]] है। इस प्रकार यह कृत्रिम बुद्धिमत्ता के अन्य दृष्टिकोणों से इस तथ्य में भिन्न है कि यह क्रम को पहचानने और वर्गीकृत करने के लिए एल्गोरिदम और मशीनरी निर्धारित करने से प्रारंभ नहीं होता है; किन्तु, यह क्रम अवधारणाओं को स्पष्ट लैंग्वेज में व्यक्त करने और पुनर्गठित करने के लिए शब्दावली निर्धारित करता है।


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


== अनुप्रयोग ==
== अनुप्रयोग ==
व्याकरण प्रेरण के सिद्धांत को [[प्राकृतिक भाषा प्रसंस्करण]] के अन्य पहलुओं पर लागू किया गया है, और इसे (कई अन्य समस्याओं के बीच) [[अर्थपूर्ण विश्लेषण]] पर भी लागू किया गया है,<ref name="Kwiatkowski">Kwiatkowski, Tom, et al. "[http://homes.cs.washington.edu/~lsz/papers/kzgs-emnlp2011.pdf Lexical generalization in CCG grammar induction for semantic parsing]." Proceedings of the conference on empirical methods in natural language processing. [[Association for Computational Linguistics]], 2011.</ref> प्राकृतिक भाषा समझ,<ref>Miller, Scott, et al. "[http://www.aclweb.org/anthology/P94-1004 Hidden understanding models of natural language]." Proceedings of the 32nd annual meeting on Association for Computational Linguistics. Association for Computational Linguistics, 1994.</ref> उदाहरण-आधारित अनुवाद,<ref>Brown, Ralf D. "[https://web.archive.org/web/20180302044726/https://pdfs.semanticscholar.org/c537/ac8bac9d83651e0ce6b37333034a5f572e39.pdf Transfer-rule induction for example-based translation]." Proceedings of the MT Summit VIII Workshop on Example-Based Machine Translation. 2001.</ref> [[भाषा अधिग्रहण के संभाव्य मॉडल]],<ref>Chater, Nick, and Christopher D. Manning. "[https://www.stanford.edu/class/linguist1/Rdgs/chater.pdf Probabilistic models of language processing and acquisition]." Trends in cognitive sciences 10.7 (2006): 335-344.</ref> व्याकरण-आधारित कोड|व्याकरण-आधारित संपीड़न,<ref>Cherniavsky, Neva, and Richard Ladner. "[https://web.archive.org/web/20180206073621/https://pdfs.semanticscholar.org/1be9/0a2f40d10acd17d5910eb21fb3b4a117d08b.pdf Grammar-based compression of DNA sequences]." DIMACS Working Group on The Burrows–Wheeler Transform 21 (2004).</ref> और विसंगति का पता लगाना।<ref>Senin, Pavel, et al. [https://www.researchgate.net/profile/Pavel-Senin/publication/272161935_Time_series_anomaly_discovery_with_grammar-based_compression/links/54dc7ec10cf2a7769d965233/Time-series-anomaly-discovery-with-grammar-based-compression.pdf "Time series anomaly discovery with grammar-based compression."] Edbt. 2015.</ref>
व्याकरण प्रेरण के सिद्धांत को [[प्राकृतिक भाषा प्रसंस्करण|प्राकृतिक लैंग्वेज प्रसंस्करण]] के अन्य तथ्यों पर प्रयुक्त किया गया है, और इसे (अनके अन्य समस्याओं के मध्य) [[अर्थपूर्ण विश्लेषण]] पर भी प्रयुक्त किया गया है,<ref name="Kwiatkowski">Kwiatkowski, Tom, et al. "[http://homes.cs.washington.edu/~lsz/papers/kzgs-emnlp2011.pdf Lexical generalization in CCG grammar induction for semantic parsing]." Proceedings of the conference on empirical methods in natural language processing. [[Association for Computational Linguistics]], 2011.</ref> इस प्रकार प्राकृतिक लैंग्वेज समझ,<ref>Miller, Scott, et al. "[http://www.aclweb.org/anthology/P94-1004 Hidden understanding models of natural language]." Proceedings of the 32nd annual meeting on Association for Computational Linguistics. Association for Computational Linguistics, 1994.</ref> उदाहरण-आधारित अनुवाद,<ref>Brown, Ralf D. "[https://web.archive.org/web/20180302044726/https://pdfs.semanticscholar.org/c537/ac8bac9d83651e0ce6b37333034a5f572e39.pdf Transfer-rule induction for example-based translation]." Proceedings of the MT Summit VIII Workshop on Example-Based Machine Translation. 2001.</ref> लैंग्वेज [[भाषा अधिग्रहण के संभाव्य मॉडल|अधिग्रहण के संभाव्य मॉडल]],<ref>Chater, Nick, and Christopher D. Manning. "[https://www.stanford.edu/class/linguist1/Rdgs/chater.pdf Probabilistic models of language processing and acquisition]." Trends in cognitive sciences 10.7 (2006): 335-344.</ref> व्याकरण-आधारित कोड या व्याकरण-आधारित संपीड़न,<ref>Cherniavsky, Neva, and Richard Ladner. "[https://web.archive.org/web/20180206073621/https://pdfs.semanticscholar.org/1be9/0a2f40d10acd17d5910eb21fb3b4a117d08b.pdf Grammar-based compression of DNA sequences]." DIMACS Working Group on The Burrows–Wheeler Transform 21 (2004).</ref> और विसंगति का पता लगाना है।<ref>Senin, Pavel, et al. [https://www.researchgate.net/profile/Pavel-Senin/publication/272161935_Time_series_anomaly_discovery_with_grammar-based_compression/links/54dc7ec10cf2a7769d965233/Time-series-anomaly-discovery-with-grammar-based-compression.pdf "Time series anomaly discovery with grammar-based compression."] Edbt. 2015.</ref>




==यह भी देखें==
==यह भी देखें==
* कृत्रिम व्याकरण सीखना#कृत्रिम बुद्धिमत्ता
* कृत्रिम व्याकरण सीखना कृत्रिम बुद्धिमत्ता
* [[उदाहरण-आधारित मशीनी अनुवाद]]
* [[उदाहरण-आधारित मशीनी अनुवाद]]
* [[आगमनात्मक प्रोग्रामिंग]]
* [[आगमनात्मक प्रोग्रामिंग]]
* [[कोलमोगोरोव जटिलता]]
* [[कोलमोगोरोव जटिलता]]
* [[सीमा में भाषा की पहचान]]
* [[सीमा में भाषा की पहचान|सीमा में लैंग्वेज की पहचान]]
* [[सीधी-रेखा व्याकरण]]
* [[सीधी-रेखा व्याकरण]]
* [[वाक्यात्मक पैटर्न पहचान]]
* [[वाक्यात्मक पैटर्न पहचान|वाक्यात्मक क्रम पहचान]]


==टिप्पणियाँ==
==टिप्पणियाँ==
Line 84: Line 81:




==संदर्भ==
==संदर्भ                                                                                                                   ==
{{Reflist}}
{{Reflist}}


Line 133: Line 130:
   | publisher=[[Information and Control]] | year=1967}}
   | publisher=[[Information and Control]] | year=1967}}


श्रेणी:आनुवंशिक प्रोग्रामिंग
[[Category:All articles with dead external links]]
श्रेणी:प्राकृतिक भाषा प्रसंस्करण
[[Category:Articles with dead external links from February 2018]]
श्रेणी:कम्प्यूटेशनल भाषाविज्ञान
[[Category:Articles with dead external links from July 2022]]
श्रेणी:व्याकरण
[[Category:Articles with dead external links from March 2018]]
श्रेणी:अनुमान
 
 
[[Category: Machine Translated Page]]
[[Category:Created On 07/07/2023]]
[[Category:Created On 07/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Translated in Hindi]]
[[Category:Templates Vigyan Ready]]

Latest revision as of 16:16, 4 September 2023

व्याकरण प्रेरण या व्याकरणिक अनुमान [1] मशीन लर्निंग में अवलोकनों के सेट से औपचारिक व्याकरण (सामान्यतः फिर से लिखने वाले नियमों या प्रस्तुतियों कंप्यूटर विज्ञान के संग्रह के रूप में या वैकल्पिक रूप से परिमित स्तर मशीन या किसी प्रकार की ऑटोमेटन के रूप में) सीखने की प्रक्रिया है, इस प्रकार मॉडल का निर्माण होता है जो प्रेक्षित वस्तुओं की विशेषताओं का वर्णन करता है। इस प्रकार अधिक सामान्यतः, व्याकरणिक अनुमान मशीन लर्निंग की वह शाखा है जहां इंस्टेंस स्पेस में स्ट्रिंग, ट्री और ग्राफ़ जैसी अलग-अलग संयोजक वस्तुएं होती हैं।

व्याकरण कक्षाएं

व्याकरणिक अनुमान अधिकांशतः विभिन्न प्रकार की परिमित स्तर मशीनों को सीखने की समस्या पर केंद्रित रहा है (इन दृष्टिकोणों पर विवरण के लिए नियमित लैंग्वेजेस का प्रेरण लेख देखें), क्योंकि 1980 के दशक से इस समस्या के लिए कुशल एल्गोरिदम उपस्थित हैं।

शताब्दी की प्रारंभ के पश्चात्, इन दृष्टिकोणों को संदर्भ-मुक्त व्याकरण और समृद्ध औपचारिकताओं, जैसे एकाधिक संदर्भ-मुक्त व्याकरण और समानांतर एकाधिक संदर्भ-मुक्त व्याकरण, अनुमान की समस्या तक विस्तारित किया गया है। इस प्रकार व्याकरण के अन्य वर्ग जिनके लिए व्याकरणिक अनुमान का अध्ययन किया गया है, इस प्रकार संयोजनात्मक श्रेणीबद्ध व्याकरण हैं,[2] स्टोकेस्टिक संदर्भ-मुक्त व्याकरण, [3] प्रासंगिक व्याकरण और क्रम भाषाएँ होती है।

शिक्षण मॉडल

सीखने का सबसे सरल रूप वह है जहां सीखने का एल्गोरिदम केवल संबंधित लैंग्वेज से लिए गए उदाहरणों का सेट प्राप्त करता है: इसका उद्देश्य लैंग्वेज को इसके उदाहरणों से सीखना है (और, संभवतः ही कभी, काउंटर-उदाहरणों से, अर्थात उदाहरण जो ऐसा करते हैं) लैंग्वेज से संबंधित नहीं)

चूँकि, अन्य शिक्षण मॉडलों का अध्ययन किया गया है। इस प्रकार अधिकांशतः अध्ययन किया जाने वाला विकल्प वह स्थिति है जहां शिक्षार्थी स्पष्ट क्वेरी लर्निंग मॉडल या एंग्लुइन द्वारा प्रस्तुत किए गए न्यूनतम पर्याप्त शिक्षक मॉडल के रूप में सदस्यता प्रश्न पूछ सकता है।[4]


पद्धतियाँ

व्याकरणिक अनुमान के लिए अनेक प्रकार की विधियाँ हैं। दो क्लासिक स्रोत हैं फु (1977) और फू (1982). डुडा, हार्ट & स्टोर्क (2001) समस्या के लिए संक्षिप्त अनुभाग भी समर्पित करें, और इस प्रकार अनके संदर्भ उद्धृत करें। इस प्रकार उनके द्वारा प्रस्तुत मूलभूत परीक्षण-और-त्रुटि विधि की चर्चा नीचे की गई है। विशेष रूप से नियमित लैंग्वेजेस के उपवर्गों का अनुमान लगाने के विधियों के लिए, नियमित लैंग्वेजेस का प्रेरण देखें। और वर्तमान पाठ्यपुस्तक डे ला हिगुएरा (2010) है,[1] जो नियमित लैंग्वेजेस और परिमित स्तर ऑटोमेटा के व्याकरणिक अनुमान के सिद्धांत को सम्मिलित करता है। इस प्रकार डी'उलिज़िया, फ़ेरी और ग्रिफ़ोनी [5] सर्वेक्षण प्रदान करें जो प्राकृतिक लैंग्वेजेस के लिए व्याकरणिक अनुमान विधियों की खोज करता है।

परीक्षण-और-त्रुटि द्वारा व्याकरणिक अनुमान

डुडा, हार्ट & स्टोर्क (2001) की धारा 8.7 में प्रस्तावित विधि व्याकरण के नियमों (प्रस्तुतियों) का क्रमिक रूप से अनुमान लगाने और उन्हें सकारात्मक और नकारात्मक टिप्पणियों के विरुद्ध परीक्षण करने का सुझाव देता है। इस प्रकार नियम सेट का विस्तार किया गया है जिससे प्रत्येक सकारात्मक उदाहरण उत्पन्न किया जा सके, किन्तु यदि कोई दिया गया नियम सेट भी नकारात्मक उदाहरण उत्पन्न करता है, जिससे इसे छोड़ दिया जाना चाहिए। इस विशेष दृष्टिकोण को परिकल्पना परीक्षण के रूप में वर्णित किया जा सकता है और मिशेल के संस्करण अंतरिक्ष एल्गोरिदम में कुछ समानता है। इस प्रकार वह डुडा, हार्ट & स्टोर्क (2001) टेक्स्ट सरल उदाहरण प्रदान करता है जो प्रक्रिया को अच्छी तरह से चित्रित करता है, किन्तु अधिक महत्वपूर्ण समस्याओं के लिए इस तरह के अनियंत्रित परीक्षण-और-त्रुटि दृष्टिकोण की व्यवहार्यता संदिग्ध है।

आनुवंशिक कलन विधि द्वारा व्याकरणिक अनुमान

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

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

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

ग्रीडी एल्गोरिदम द्वारा व्याकरणिक अनुमान

सभी ग्रीडी एल्गोरिदम की तरह, ग्रीडी व्याकरण अनुमान एल्गोरिदम, पुनरावृत्त विधि से, ऐसे निर्णय लेते हैं जो उस स्तर पर सबसे अच्छे लगते हैं। इसके लिए गए निर्णय सामान्यतः नए नियमों के निर्माण, उपस्थिता नियमों को हटाने, प्रयुक्त किए जाने वाले नियम के चुनाव या कुछ उपस्थिता नियमों के विलय जैसी चीजों से संबंधित होते हैं।

चूँकि 'फोरम' और 'सर्वश्रेष्ठ' को परिभाषित करने के अनके विधि हैं, इसलिए अनके ग्रीडी व्याकरण अनुमान एल्गोरिदम भी हैं।

ये संदर्भ-मुक्त व्याकरण उत्पन्न करने वाले एल्गोरिदम प्रत्येक पढ़े गए प्रतीक के बाद निर्णय लेते हैं:

  • एलजेडडब्ल्यू या लेम्पेल-ज़िव-वेल्च एल्गोरिथ्म नियतात्मक विधि से संदर्भ-मुक्त व्याकरण बनाता है जैसे कि उत्पन्न व्याकरण के केवल प्रारंभ नियम को संग्रहीत करना आवश्यक है।
  • सेक्विटुर और इसके संशोधन।

ये संदर्भ-मुक्त व्याकरण उत्पन्न करने वाले एल्गोरिदम पहले दिए गए पूरे प्रतीक-अनुक्रम को पढ़ते हैं और फिर निर्णय लेना प्रारंभ करते हैं:

वितरणात्मक शिक्षा

एक और वर्तमान दृष्टिकोण वितरणात्मक शिक्षा पर आधारित है। इन दृष्टिकोणों का उपयोग करने वाले एल्गोरिदम को संदर्भ-मुक्त व्याकरण और इस प्रकार हल्के संदर्भ-संवेदनशील लैंग्वेजेस को सीखने के लिए प्रयुक्त किया गया है और इन व्याकरणों के बड़े उपवर्गों के लिए सही और कुशल सिद्ध हुए हैं।[6]


क्रम लैंग्वेज (औपचारिक भाषाएं) सीखना

एंग्लुइन क्रम को Σ से स्थिर प्रतीकों की स्ट्रिंग और असंयुक्त सेट से 'परिवर्तनीय प्रतीकों' के रूप में परिभाषित करता है। इस तरह के क्रम की लैंग्वेज इसके सभी गैर-रिक्त ग्राउंड उदाहरणों का सेट है अर्थात सभी स्ट्रिंग्स जो निरंतर प्रतीकों के गैर-रिक्त स्ट्रिंग्स द्वारा इसके वेरिएबल प्रतीकों के निरंतर प्रतिस्थापन से उत्पन्न होती हैं।

एक क्रम को स्ट्रिंग्स के सीमित इनपुट सेट के लिए वर्णनात्मक कहा जाता है इस प्रकार यदि इसकी लैंग्वेज इनपुट सेट को सम्मिलित करने वाली सभी क्रम लैंग्वेजेस के मध्य न्यूनतम (सेट समावेशन के संबंध में) है।

एंग्लुइन किसी दिए गए इनपुट स्ट्रिंग सेट के लिए, वेरिएबल x में सभी वर्णनात्मक क्रम की गणना करने के लिए बहुपद एल्गोरिथ्म देता है। इस प्रयोजन के लिए, वह सभी संभावित प्रासंगिक क्रम का प्रतिनिधित्व करने वाला ऑटोमेटन बनाती है; इस प्रकार शब्द की लंबाई के बारे में परिष्कृत तर्कों का उपयोग करते हुए, जो x के एकमात्र वेरिएबल होने पर निर्भर करते हैं, इस प्रकार स्तर गणना को अधिक सीमा तक कम किया जा सकता है।[7]

एर्लेबैक एट अल. एंग्लुइन के क्रम लर्निंग एल्गोरिदम का अधिक कुशल संस्करण, साथ ही समानांतर संस्करण भी दें।[8] इस प्रकार अरिमुरा एट अल. दिखाएँ कि क्रम के सीमित संघों से प्राप्त लैंग्वेज वर्ग को बहुपद समय में सीखा जा सकता है।[9]

क्रम सिद्धांत

उल्फ ग्रेनेंडर द्वारा प्रतिपादित क्रम सिद्धांत,[10] संसार के ज्ञान को क्रम के रूप में वर्णित करने के लिए गणितीय औपचारिकता (गणित) है। इस प्रकार यह कृत्रिम बुद्धिमत्ता के अन्य दृष्टिकोणों से इस तथ्य में भिन्न है कि यह क्रम को पहचानने और वर्गीकृत करने के लिए एल्गोरिदम और मशीनरी निर्धारित करने से प्रारंभ नहीं होता है; किन्तु, यह क्रम अवधारणाओं को स्पष्ट लैंग्वेज में व्यक्त करने और पुनर्गठित करने के लिए शब्दावली निर्धारित करता है।

नई बीजगणितीय शब्दावली के अतिरिक्त, इसका सांख्यिकीय दृष्टिकोण अपने उद्देश्य में नया था:

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

अपने गणितीय कवरेज में व्यापक, क्रम सिद्धांत बीजगणित और सांख्यिकी के साथ-साथ स्थानीय टोपोलॉजिकल और वैश्विक एन्ट्रोपिक गुणों तक फैला हुआ है।

अनुप्रयोग

व्याकरण प्रेरण के सिद्धांत को प्राकृतिक लैंग्वेज प्रसंस्करण के अन्य तथ्यों पर प्रयुक्त किया गया है, और इसे (अनके अन्य समस्याओं के मध्य) अर्थपूर्ण विश्लेषण पर भी प्रयुक्त किया गया है,[2] इस प्रकार प्राकृतिक लैंग्वेज समझ,[11] उदाहरण-आधारित अनुवाद,[12] लैंग्वेज अधिग्रहण के संभाव्य मॉडल,[13] व्याकरण-आधारित कोड या व्याकरण-आधारित संपीड़न,[14] और विसंगति का पता लगाना है।[15]


यह भी देखें

टिप्पणियाँ


संदर्भ

  1. ↑ 1.0 1.1 de la Higuera, Colin (2010). Grammatical Inference: Learning Automata and Grammars (PDF). Cambridge: Cambridge University Press. Archived from the original (PDF) on 2019-02-14. Retrieved 2017-08-16.
  2. ↑ 2.0 2.1 Kwiatkowski, Tom, et al. "Lexical generalization in CCG grammar induction for semantic parsing." Proceedings of the conference on empirical methods in natural language processing. Association for Computational Linguistics, 2011.
  3. ↑ Clark, Alexander. "Unsupervised induction of stochastic context-free grammars using distributional clustering." Proceedings of the 2001 workshop on Computational Natural Language Learning-Volume 7. Association for Computational Linguistics, 2001.
  4. ↑ Dana Angluin (1987). "प्रश्नों और प्रति-उदाहरणों से नियमित सेट सीखना" (PDF). Information and Control. 75 (2): 87–106. CiteSeerX 10.1.1.187.9414. doi:10.1016/0890-5401(87)90052-6. Archived from the original (PDF) on 2013-12-02.
  5. ↑ D’Ulizia, A., Ferri, F., Grifoni, P. (2011) "A Survey of Grammatical Inference Methods for Natural Language Learning[dead link]", Artificial Intelligence Review, Vol. 36, No. 1, pp. 1–27.
  6. ↑ Clark and Eyraud (2007) Journal of Machine Learning Research; Ryo Yoshinaka (2011) Theoretical Computer Science
  7. ↑ Dana Angluin (1980). "स्ट्रिंग्स के एक सेट के लिए सामान्य पैटर्न ढूँढना". Journal of Computer and System Sciences. 21: 46–62. doi:10.1016/0022-0000(80)90041-0.
  8. ↑ T. Erlebach; P. Rossmanith; H. Stadtherr; A. Steger; T. Zeugmann (1997). "Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries". In M. Li; A. Maruoka (eds.). Proc. 8th International Workshop on Algorithmic Learning Theory — ALT'97. LNAI. Vol. 1316. Springer. pp. 260–276.
  9. ↑ Hiroki Arimura; Takeshi Shinohara; Setsuko Otsuki (1994). "Finding Minimal Generalizations for Unions of Pattern Languages and Its Application to Inductive Inference from Positive Data" (PDF). प्रोक. स्टैक्स 11. LNCS. Vol. 775. Springer. pp. 649–660.[dead link]
  10. ↑ Grenander, Ulf, and Michael I. Miller. Pattern theory: from representation to inference.[dead link] Vol. 1. Oxford: Oxford university press, 2007.
  11. ↑ Miller, Scott, et al. "Hidden understanding models of natural language." Proceedings of the 32nd annual meeting on Association for Computational Linguistics. Association for Computational Linguistics, 1994.
  12. ↑ Brown, Ralf D. "Transfer-rule induction for example-based translation." Proceedings of the MT Summit VIII Workshop on Example-Based Machine Translation. 2001.
  13. ↑ Chater, Nick, and Christopher D. Manning. "Probabilistic models of language processing and acquisition." Trends in cognitive sciences 10.7 (2006): 335-344.
  14. ↑ Cherniavsky, Neva, and Richard Ladner. "Grammar-based compression of DNA sequences." DIMACS Working Group on The Burrows–Wheeler Transform 21 (2004).
  15. ↑ Senin, Pavel, et al. "Time series anomaly discovery with grammar-based compression." Edbt. 2015.


स्रोत

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=व्याकरण_प्रेरण&oldid=255445’