व्याकरण प्रेरण
व्याकरण प्रेरण या व्याकरणिक अनुमान [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.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.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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ Clark and Eyraud (2007) Journal of Machine Learning Research; Ryo Yoshinaka (2011) Theoretical Computer Science
- ↑ Dana Angluin (1980). "स्ट्रिंग्स के एक सेट के लिए सामान्य पैटर्न ढूँढना". Journal of Computer and System Sciences. 21: 46–62. doi:10.1016/0022-0000(80)90041-0.
- ↑ 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.
- ↑ 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]
- ↑ Grenander, Ulf, and Michael I. Miller. Pattern theory: from representation to inference.[dead link] Vol. 1. Oxford: Oxford university press, 2007.
- ↑ 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.
- ↑ Brown, Ralf D. "Transfer-rule induction for example-based translation." Proceedings of the MT Summit VIII Workshop on Example-Based Machine Translation. 2001.
- ↑ Chater, Nick, and Christopher D. Manning. "Probabilistic models of language processing and acquisition." Trends in cognitive sciences 10.7 (2006): 335-344.
- ↑ Cherniavsky, Neva, and Richard Ladner. "Grammar-based compression of DNA sequences." DIMACS Working Group on The Burrows–Wheeler Transform 21 (2004).
- ↑ Senin, Pavel, et al. "Time series anomaly discovery with grammar-based compression." Edbt. 2015.
स्रोत
- Duda, Richard O.; Hart, Peter E.; Stork, David G. (2001), Pattern Classification (2 ed.), New York: John Wiley & Sons
- Fu, King Sun (1982), Syntactic Pattern Recognition and Applications, Englewood Cliffs, NJ: Prentice-Hall
- Fu, King Sun (1977), Syntactic Pattern Recognition, Applications, Berlin: Springer-Verlag
- Horning, James Jay (1969), A Study of Grammatical Inference (Ph.D. Thesis ed.), Stanford: Stanford University Computer Science Department, ProQuest 302483145
- Gold, E. Mark (1967), Language Identification in the Limit, vol. 10, Information and Control, pp. 447–474, archived from the original on 2016-08-28, retrieved 2016-09-04
- Gold, E. Mark (1967), Language Identification in the Limit (PDF), vol. 10, Information and Control, pp. 447–474
