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

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Machine learning|Problems}}
{{Machine learning|समस्याएँ}}
व्याकरण प्रेरण (या व्याकरणिक अनुमान)<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}} टेक्स्ट सरल उदाहरण प्रदान करता है जो प्रक्रिया को अच्छी तरह से चित्रित करता है, किन्तु अधिक महत्वपूर्ण समस्याओं के लिए इस तरह के अनियंत्रित परीक्षण-और-त्रुटि दृष्टिकोण की व्यवहार्यता संदिग्ध है।


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


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


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


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


ये [[संदर्भ-मुक्त व्याकरण]] उत्पन्न करने वाले एल्गोरिदम प्रत्येक पढ़े गए प्रतीक के बाद निर्णय लेते हैं:
ये [[संदर्भ-मुक्त व्याकरण]] उत्पन्न करने वाले एल्गोरिदम प्रत्येक पढ़े गए प्रतीक के बाद निर्णय लेते हैं:
* [[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>
 
 
===क्रम भाषा (औपचारिक भाषाएं) सीखना===
 
एंग्लुइन क्रम को Σ से स्थिर प्रतीकों की स्ट्रिंग और असंयुक्त सेट से 'परिवर्तनीय प्रतीकों' के रूप में परिभाषित करता है। इस तरह के क्रम की भाषा इसके सभी गैर-रिक्त ग्राउंड उदाहरणों का सेट है अर्थात सभी स्ट्रिंग्स जो निरंतर प्रतीकों के गैर-रिक्त स्ट्रिंग्स द्वारा इसके चर प्रतीकों के निरंतर प्रतिस्थापन से उत्पन्न होती हैं।


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


===पैटर्न भाषा (औपचारिक भाषाएं) सीखना===
एंग्लुइन किसी दिए गए इनपुट स्ट्रिंग सेट के लिए, चर ''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 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>




===[[पैटर्न सिद्धांत]]===
===[[पैटर्न सिद्धांत|क्रम सिद्धांत]]===
[[उल्फ ग्रेनेंडर]] द्वारा प्रतिपादित पैटर्न सिद्धांत,<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 78: Line 80:
* [[सीमा में भाषा की पहचान]]
* [[सीमा में भाषा की पहचान]]
* [[सीधी-रेखा व्याकरण]]
* [[सीधी-रेखा व्याकरण]]
* [[वाक्यात्मक पैटर्न पहचान]]
* [[वाक्यात्मक पैटर्न पहचान|वाक्यात्मक क्रम पहचान]]


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




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


Revision as of 14:25, 12 July 2023

Part of a series on
Machine learning
and data mining
Scatterplot featuring a linear support vector machine's decision boundary (dashed line)
Problems
Clustering
Dimensionality reduction
Structured prediction
Anomaly detection
Artificial neural network
Reinforcement learning
Learning with humans
Model diagnostics
Theory
Machine-learning venues
Related articles

व्याकरण प्रेरण या व्याकरणिक अनुमान [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=216511’