व्याकरण प्रेरण
| Part of a series on |
| Machine learning and data mining |
|---|
 |
व्याकरण प्रेरण (या व्याकरणिक अनुमान)[1] यंत्र अधिगम में अवलोकनों के एक सेट से एक औपचारिक व्याकरण (आमतौर पर फिर से लिखने वाले नियमों या प्रस्तुतियों (कंप्यूटर विज्ञान) के संग्रह के रूप में या वैकल्पिक रूप से एक परिमित राज्य मशीन या किसी प्रकार की ऑटोमेटन के रूप में) सीखने की प्रक्रिया है, इस प्रकार एक मॉडल का निर्माण होता है जो प्रेक्षित वस्तुओं की विशेषताओं का वर्णन करता है। अधिक आम तौर पर, व्याकरणिक अनुमान मशीन लर्निंग की वह शाखा है जहां इंस्टेंस स्पेस में स्ट्रिंग, पेड़ और ग्राफ़ जैसी अलग-अलग संयोजक वस्तुएं होती हैं।
व्याकरण कक्षाएं
व्याकरणिक अनुमान अक्सर विभिन्न प्रकार की परिमित राज्य मशीनों को सीखने की समस्या पर केंद्रित रहा है (इन दृष्टिकोणों पर विवरण के लिए नियमित भाषाओं का प्रेरण लेख देखें), क्योंकि 1980 के दशक से इस समस्या के लिए कुशल एल्गोरिदम मौजूद हैं।
सदी की शुरुआत के बाद से, इन दृष्टिकोणों को संदर्भ-मुक्त व्याकरण और समृद्ध औपचारिकताओं, जैसे एकाधिक संदर्भ-मुक्त व्याकरण और समानांतर एकाधिक संदर्भ-मुक्त व्याकरण, के अनुमान की समस्या तक विस्तारित किया गया है। व्याकरण के अन्य वर्ग जिनके लिए व्याकरणिक अनुमान का अध्ययन किया गया है, संयोजनात्मक श्रेणीबद्ध व्याकरण हैं,[2]स्टोकेस्टिक संदर्भ-मुक्त व्याकरण,[3] प्रासंगिक व्याकरण और पैटर्न भाषाएँ।
सीखने के मॉडल
सीखने का सबसे सरल रूप वह है जहां सीखने का एल्गोरिदम केवल संबंधित भाषा से लिए गए उदाहरणों का एक सेट प्राप्त करता है: इसका उद्देश्य भाषा को इसके उदाहरणों से सीखना है (और, शायद ही कभी, काउंटर-उदाहरणों से, यानी उदाहरण जो ऐसा करते हैं) भाषा से संबंधित नहीं) हालाँकि, अन्य शिक्षण मॉडलों का अध्ययन किया गया है। अक्सर अध्ययन किया जाने वाला एक विकल्प वह मामला है जहां शिक्षार्थी सटीक क्वेरी लर्निंग मॉडल या एंग्लुइन द्वारा पेश किए गए न्यूनतम पर्याप्त शिक्षक मॉडल के रूप में सदस्यता प्रश्न पूछ सकता है।[4]
तरीके
व्याकरणिक अनुमान के लिए अनेक प्रकार की विधियाँ हैं। दो क्लासिक स्रोत हैं Fu (1977) और Fu (1982). Duda, Hart & Stork (2001) समस्या के लिए एक संक्षिप्त अनुभाग भी समर्पित करें, और कई संदर्भ उद्धृत करें। उनके द्वारा प्रस्तुत बुनियादी परीक्षण-और-त्रुटि विधि की चर्चा नीचे की गई है। विशेष रूप से नियमित भाषाओं के उपवर्गों का अनुमान लगाने के तरीकों के लिए, नियमित भाषाओं का प्रेरण देखें। एक और हालिया पाठ्यपुस्तक डे ला हिगुएरा (2010) है,[1]जो नियमित भाषाओं और परिमित राज्य ऑटोमेटा के व्याकरणिक अनुमान के सिद्धांत को शामिल करता है। डी'उलिज़िया, फ़ेरी और ग्रिफ़ोनी[5] एक सर्वेक्षण प्रदान करें जो प्राकृतिक भाषाओं के लिए व्याकरणिक अनुमान विधियों की खोज करता है।
परीक्षण-और-त्रुटि द्वारा व्याकरणिक अनुमान
की धारा 8.7 में प्रस्तावित विधि Duda, Hart & Stork (2001) व्याकरण के नियमों (प्रस्तुतियों) का क्रमिक रूप से अनुमान लगाने और उन्हें सकारात्मक और नकारात्मक टिप्पणियों के विरुद्ध परीक्षण करने का सुझाव देता है। नियम सेट का विस्तार किया गया है ताकि प्रत्येक सकारात्मक उदाहरण उत्पन्न किया जा सके, लेकिन यदि कोई दिया गया नियम सेट भी नकारात्मक उदाहरण उत्पन्न करता है, तो इसे छोड़ दिया जाना चाहिए। इस विशेष दृष्टिकोण को परिकल्पना परीक्षण के रूप में वर्णित किया जा सकता है और मिशेल के संस्करण अंतरिक्ष एल्गोरिदम में कुछ समानता है। वह Duda, Hart & Stork (2001) पाठ एक सरल उदाहरण प्रदान करता है जो प्रक्रिया को अच्छी तरह से चित्रित करता है, लेकिन अधिक महत्वपूर्ण समस्याओं के लिए इस तरह के एक अनियंत्रित परीक्षण-और-त्रुटि दृष्टिकोण की व्यवहार्यता संदिग्ध है।
आनुवंशिक कलन विधि द्वारा व्याकरणिक अनुमान
विकासवादी एल्गोरिदम का उपयोग करके व्याकरणिक प्रेरण कुछ विकासवादी प्रक्रिया के माध्यम से लक्ष्य भाषा के व्याकरण का प्रतिनिधित्व विकसित करने की प्रक्रिया है। औपचारिक व्याकरण को आसानी से उत्पादन नियमों के वृक्ष (डेटा संरचना) के रूप में दर्शाया जा सकता है जिसे विकासवादी ऑपरेटरों के अधीन किया जा सकता है। इस प्रकार के एल्गोरिदम जॉन बकरी द्वारा प्रवर्तित आनुवंशिक प्रोग्रामिंग प्रतिमान से उत्पन्न होते हैं।[citation needed] सरल औपचारिक भाषाओं पर अन्य प्रारंभिक कार्यों में आनुवंशिक एल्गोरिदम के बाइनरी स्ट्रिंग प्रतिनिधित्व का उपयोग किया गया था, लेकिन विस्तारित बैकस-नौर फॉर्म भाषा में निहित व्याकरणों की अंतर्निहित पदानुक्रमित संरचना ने पेड़ों को अधिक लचीला दृष्टिकोण बना दिया।
कोज़ा ने लिस्प (प्रोग्रामिंग भाषा) कार्यक्रमों को पेड़ों के रूप में दर्शाया। वह वृक्ष संचालकों के मानक सेट के भीतर आनुवंशिक संचालकों के अनुरूप खोजने में सक्षम थे। उदाहरण के लिए, उप-वृक्षों की अदला-बदली आनुवंशिक क्रॉसओवर की संबंधित प्रक्रिया के बराबर है, जहां आनुवंशिक कोड के उप-स्ट्रिंग्स को अगली पीढ़ी के एक व्यक्ति में प्रत्यारोपित किया जाता है। फिटनेस को लिस्प कोड के व्याकरणिक फ़ंक्शन से आउटपुट स्कोर करके मापा जाता है। वृक्ष संरचित लिस्प प्रतिनिधित्व और वृक्षों के रूप में व्याकरण के प्रतिनिधित्व के बीच समान अनुरूपता ने व्याकरण प्रेरण के लिए आनुवंशिक प्रोग्रामिंग तकनीकों के अनुप्रयोग को संभव बना दिया।
व्याकरण प्रेरण के मामले में, उप-वृक्षों का प्रत्यारोपण उत्पादन नियमों की अदला-बदली से मेल खाता है जो कुछ भाषा से वाक्यांशों के विश्लेषण को सक्षम बनाता है। व्याकरण के लिए फिटनेस ऑपरेटर कुछ माप पर आधारित है कि लक्ष्य भाषा से वाक्यों के कुछ समूह को पार्स करने में उसने कितना अच्छा प्रदर्शन किया है। व्याकरण के वृक्ष प्रतिनिधित्व में, उत्पादन नियम का एक टर्मिनल प्रतीक पेड़ के एक पत्ती नोड से मेल खाता है। इसके मूल नोड्स नियम सेट में एक गैर-टर्मिनल प्रतीक (उदाहरण के लिए एक संज्ञा वाक्यांश या एक क्रिया वाक्यांश) से मेल खाते हैं। अंततः, रूट नोड एक वाक्य गैर-टर्मिनल के अनुरूप हो सकता है।
लालची एल्गोरिदम द्वारा व्याकरणिक अनुमान
सभी लालची एल्गोरिदम की तरह, लालची व्याकरण अनुमान एल्गोरिदम, पुनरावृत्त तरीके से, ऐसे निर्णय लेते हैं जो उस स्तर पर सबसे अच्छे लगते हैं। लिए गए निर्णय आम तौर पर नए नियमों के निर्माण, मौजूदा नियमों को हटाने, लागू किए जाने वाले नियम के चुनाव या कुछ मौजूदा नियमों के विलय जैसी चीजों से संबंधित होते हैं। चूँकि 'मंच' और 'सर्वश्रेष्ठ' को परिभाषित करने के कई तरीके हैं, इसलिए कई लालची व्याकरण अनुमान एल्गोरिदम भी हैं।
ये संदर्भ-मुक्त व्याकरण उत्पन्न करने वाले एल्गोरिदम प्रत्येक पढ़े गए प्रतीक के बाद निर्णय लेते हैं:
- LZW|लेम्पेल-ज़िव-वेल्च एल्गोरिथ्म एक नियतात्मक तरीके से एक संदर्भ-मुक्त व्याकरण बनाता है जैसे कि उत्पन्न व्याकरण के केवल प्रारंभ नियम को संग्रहीत करना आवश्यक है।
- एल्गोरिथ्म इस प्रकार है और इसके संशोधन।
ये संदर्भ-मुक्त व्याकरण उत्पन्न करने वाले एल्गोरिदम पहले दिए गए पूरे प्रतीक-अनुक्रम को पढ़ते हैं और फिर निर्णय लेना शुरू करते हैं:
- बाइट जोड़ी एन्कोडिंग और इसके अनुकूलन।
वितरणात्मक शिक्षा
एक और हालिया दृष्टिकोण वितरणात्मक शिक्षा पर आधारित है। इन दृष्टिकोणों का उपयोग करने वाले एल्गोरिदम को संदर्भ-मुक्त व्याकरण और हल्के संदर्भ-संवेदनशील भाषाओं को सीखने के लिए लागू किया गया है और इन व्याकरणों के बड़े उपवर्गों के लिए सही और कुशल साबित हुए हैं।[6]
पैटर्न भाषा (औपचारिक भाषाएं) सीखना
एंग्लुइन एक पैटर्न को Σ से स्थिर प्रतीकों की एक स्ट्रिंग और एक असंयुक्त सेट से 'परिवर्तनीय प्रतीकों' के रूप में परिभाषित करता है। इस तरह के पैटर्न की भाषा इसके सभी गैर-रिक्त ग्राउंड उदाहरणों का सेट है यानी सभी स्ट्रिंग्स जो निरंतर प्रतीकों के गैर-रिक्त स्ट्रिंग्स द्वारा इसके चर प्रतीकों के लगातार प्रतिस्थापन से उत्पन्न होती हैं।[note 1] एक पैटर्न को स्ट्रिंग्स के एक सीमित इनपुट सेट के लिए वर्णनात्मक कहा जाता है यदि इसकी भाषा इनपुट सेट को शामिल करने वाली सभी पैटर्न भाषाओं के बीच न्यूनतम (सेट समावेशन के संबंध में) है।
एंग्लुइन किसी दिए गए इनपुट स्ट्रिंग सेट के लिए, एक चर x में सभी वर्णनात्मक पैटर्न की गणना करने के लिए एक बहुपद एल्गोरिथ्म देता है।[note 2] इस प्रयोजन के लिए, वह सभी संभावित प्रासंगिक पैटर्न का प्रतिनिधित्व करने वाला एक ऑटोमेटन बनाती है; शब्द की लंबाई के बारे में परिष्कृत तर्कों का उपयोग करते हुए, जो x के एकमात्र चर होने पर निर्भर करते हैं, राज्य गणना को काफी हद तक कम किया जा सकता है।[7] एर्लेबैक एट अल. एंग्लुइन के पैटर्न लर्निंग एल्गोरिदम का अधिक कुशल संस्करण, साथ ही एक समानांतर संस्करण भी दें।[8] अरिमुरा एट अल. दिखाएँ कि पैटर्न के सीमित संघों से प्राप्त भाषा वर्ग को बहुपद समय में सीखा जा सकता है।[9]
पैटर्न सिद्धांत
उल्फ ग्रेनेंडर द्वारा प्रतिपादित पैटर्न सिद्धांत,[10] दुनिया के ज्ञान को पैटर्न के रूप में वर्णित करने के लिए एक गणितीय औपचारिकता (गणित) है। यह कृत्रिम बुद्धिमत्ता के अन्य दृष्टिकोणों से इस मायने में भिन्न है कि यह पैटर्न को पहचानने और वर्गीकृत करने के लिए एल्गोरिदम और मशीनरी निर्धारित करने से शुरू नहीं होता है; बल्कि, यह पैटर्न अवधारणाओं को सटीक भाषा में व्यक्त करने और पुनर्गठित करने के लिए एक शब्दावली निर्धारित करता है।
नई बीजगणितीय शब्दावली के अलावा, इसका सांख्यिकीय दृष्टिकोण अपने उद्देश्य में नया था:
- कृत्रिम उत्तेजनाओं के बजाय वास्तविक दुनिया डेटा का उपयोग करके डेटा सेट के अव्यक्त चर की पहचान करें, जो उस समय आम बात थी।
- छिपे हुए चरों के लिए पूर्व वितरण तैयार करें और देखे गए चरों के लिए मॉडल बनाएं जो गिब्स-जैसे ग्राफ के शीर्ष बनाते हैं।
- इन ग्राफ़ों की यादृच्छिकता और परिवर्तनशीलता का अध्ययन करें।
- पैटर्न की विकृतियों को सूचीबद्ध करके लागू स्टोकेस्टिक मॉडल की बुनियादी कक्षाएं बनाएं।
- मॉडलों से संश्लेषण (नमूना) करें, न कि केवल इसके साथ संकेतों का विश्लेषण करें।
अपने गणितीय कवरेज में व्यापक, पैटर्न सिद्धांत बीजगणित और सांख्यिकी के साथ-साथ स्थानीय टोपोलॉजिकल और वैश्विक एन्ट्रोपिक गुणों तक फैला हुआ है।
अनुप्रयोग
व्याकरण प्रेरण के सिद्धांत को प्राकृतिक भाषा प्रसंस्करण के अन्य पहलुओं पर लागू किया गया है, और इसे (कई अन्य समस्याओं के बीच) अर्थपूर्ण विश्लेषण पर भी लागू किया गया है,[2] प्राकृतिक भाषा समझ,[11] उदाहरण-आधारित अनुवाद,[12] भाषा अधिग्रहण के संभाव्य मॉडल,[13] व्याकरण-आधारित कोड|व्याकरण-आधारित संपीड़न,[14] और विसंगति का पता लगाना।[15]
यह भी देखें
- कृत्रिम व्याकरण सीखना#कृत्रिम बुद्धिमत्ता
- उदाहरण-आधारित मशीनी अनुवाद
- आगमनात्मक प्रोग्रामिंग
- कोलमोगोरोव जटिलता
- सीमा में भाषा की पहचान
- सीधी-रेखा व्याकरण
- वाक्यात्मक पैटर्न पहचान
टिप्पणियाँ
- ↑ The language of a pattern with at least two occurrences of the same variable is not regular due to the pumping lemma.
- ↑ x may occur several times, but no other variable y may occur
संदर्भ
- ↑ 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
श्रेणी:आनुवंशिक प्रोग्रामिंग श्रेणी:प्राकृतिक भाषा प्रसंस्करण श्रेणी:कम्प्यूटेशनल भाषाविज्ञान श्रेणी:व्याकरण श्रेणी:अनुमान
