Context-free grammar induction with grammar-based classifier system

• Autorzy: Unold O.
• Konferencja: Human Language Technologies as a challenge for Computer Science and Linguistics (2; 21-23.04.2005; Poznań, Poland)
• Języki publikacji: EN

Abstrakty

EN

In the paper we deal with the induction of context-free grammars from sample sentences. We present some extensions to grammar-based classifier system (GCS) that evolves population of classifiers represented by context-free grammar productions rules in Chomsky Normal Form. GCS is a new version of Learning Classifier Systems but it differs from it in the covering, in the matching, and in representation. We modify the discovering component of the GCS and apply system for inferring such context-free languages as toy language, and grammar for large corpora of part-of-speech tagged natural English language. For each task a set of experiments was performed.

Słowa kluczowe

EN

grammar induction; machine learning; learning classifier system; context-free grammar

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2005
• Tom: Vol. 15, no. 4
• Strony: 681--690
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Unold O.

• Institute of Computer Engineering, Control and Robotics, Wrocław University of Technology, Wyb. Wyspianskiego 27, 50-370 Wrocław, Poland,

Bibliografia

• [1] J. Arabas: Wykłady z algorytmów ewolucyjnych. WNT, Warszawa, 2001, (in Polish).
• [2] D. Angluin: Queries and concept learning. Machine Learning, 2(4), (1988), 319-342.
• [3] M. Aycinena, M. J. Kochenderfer and D. C. Mulford: An evolutionary approach lo natural language grammar induction. Final project for CS224N, Natural Language Processing. Stanford University. 2003.
• [4] D. Bianchi: Learning Grammatical Rules from Examples Using a Credit Assignment Algorithm. In Proc 1st Online Workshop on Soft Computing (WSCIi. Nagoya. (1996). 113-118.
• [5] P. Cichosz: Systemy uczące się. WNT. Warszawa. 2000. (in Polish).
• [6] W. R. Cyre: Learning Grammars w uh a Modified Classilicr System. In Proc. World Congress on Computational Intelligence. Honolulu. Hawaii, (2002). 1366-1371.
• [7] W. R. Cyre: Evolutionary language Acquisition. In Proc. 6th IAS TED Int. Conf. on Artificial Intelligence and Soft Computing. Banff. Canada. (2002), 146-151.
• [8] E. Gold: Language identification in the limit. Information Control. 10 (1967), 447-474.
• [9] C. De La Higuera: CurTent trends in grammatical inference. In Ferri F. J. at al (Eds.): Advances in Pattern Recognition. Joint IAPR Int. Workshops SSPR+SPR'2000, LNCS 1876. Springer. (2000), 28-31.
• [10] J. Holland: Adaptation. In Rosen R., Snell FM. (Eds.): Progress in theoretical biology. New York. Plenum, 1976.
• [11] J. Holland: Escaping Brittleness: The possibilities of General-Purpose Learning Algorithms Applied to Parallel Rule-Based Systems. In Michalski R.S. at al. (Eds.): Machine Learning, an artificial intelligence approach. II Morgan Kaufmann, (1986), 593-623.
• [12] J. E. Hopcroft and J. D. Ullman: Wprowadzenie do teorii automatów, języków i obliczeń. PWN, Warszawa, 1994. (in Polish).
• [13] M. M. Lankhorst: Breeding grammars: Grammatical inference with a genetic algorithm. Tech. rep.. Dept. of CS. U. of Groningen. Box 800.9700 AV Groningen, The Netherlands, 1994.
• [14] P. L. Lanzi and R. L. Riolo: A Roadmap to the Last Decade of learning Classifier System Research. In PL Lanzi, W. Stolzmann, S. W. Wilson (Eds.): Learning Classifier Systems. From Foundations to Applications. LNAI 1813. Springer Verlag, Berlin, (2000). 33-62.
• [15] L. Lee: Learning of Context-Free Languages: A Survey of the Literature. Report TR-12-96. Harvard University, Cambridge, Massachusetts, 1996.
• [16] L. Lucas: Structuring chromosomes for context-free grammar evolution. In Proc. 1 st IEEE Conf. on Evolutionary Computation, (1994), 130-135
• [17] P. Tapanainen and T. Jarvinen: A non-projective dependency parser. In Proc. 5th Conf. on Applied Natural Language Processing. Washington, D.C. Association for Computational Linguistocs, (1997), 64-71
• [18] O. Unold and L. Cielecki: Grammar-based Classifier Systems. In O. Hryniewicz at all. (Eds): Issues in Intelligent Systems. Paradigms. Exit Publishing House, Warsaw, (2005), 273-286.
• [19] S. W. Wilson: Classifier Fitness Based on Accouracy. Evolutionary Computation, 3(2), (1995), 147-175
• [20] D. Younger: Recognition and parsing of context-free languages in time n3. University of Hawaii Technical, Report, Department of Computer Science, 1967.