Analiza wpływu wybranych parametrów na efektywność systemu GCS

• Autorzy: Unold O.
• Języki publikacji: PL

Abstrakty

PL

Przedstawiono nowy model uczącego się systemu klasyfikującego, w którym klasyfikatory reprezentowane są przez produkcję gramatyki bezkontekstowej podane w postaci normaluej Chomsky'ego. System GCS (ang. grammar-based classifier system) odkrywa nowe reguły gramatyki stosując metodę tzw. pokrywania (ang. covering) oraz algorytm genetyczny. Efektywność systemu zależy w znacznej mierze od odpowiedniego ustawienia jego parametrów. W pracy przebadano zależność efektywności od liczności populacji, płodności oraz symbolu dont care.

EN

Grammar-based classifier system (GCS) is a new version of Learning Classifier Systems (LCS) in which classifi-ers arf represented by context-free grammar in Chomsky Normal Form. GCS works basically like all other LCS models but it differs from łbem (i) in the covering, (ii) in the matching, and (iii) in representation. Performance of GCS depends on many parameters. In this paper the influance of size of population, fertility and don't care symbol was tested. The set of experiments was performed on context-free grammar called toy-grammar. The experiments revealed some interesting properties of this faetors and showed that this parameters must be tuned very carefully and knowingly in order to improve performance of the GCS.

Słowa kluczowe

PL

uczenie maszynowe; system klasyfikujący; przetwarzanie ewolucyjne; wnioskowanie gramatyczne; gramatyka bezkontekstowa

EN

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

• Wydawca: Wydawnictwo Politechniki Częstochowskiej
• Czasopismo: Informatyka Teoretyczna i Stosowana
• Rocznik: 2005
• Tom: R. 5, nr 8
• Strony: 177--189
• Opis fizyczny: Bibliogr. 29 poz., rys., tab.

Twórcy

autor

Unold O.

• Instytut Informatyki, Automatyki i Robotyki, Politechnika Wrocławska Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Polska

Bibliografia

• [1] Angluin D., Queries and concept learning. Machine Learning 2(4). 319-342, 1988.
• [2] Arabas J., Wykłady z algorytmów ewolucyjnych. WNT. Warszawa, 2001. 1880.
• [3] Bianchi D., Learning Grammatical Rules from Examples Using a Credit Assignment Algorithm. Proceedings of The First Online Workshop on Soft Computing (WSC1). Nagoya, 1996.
• [4] Charniak E., Statistical Language Learning. MIT Press. Cambridge, MA, 1993.
• [5] Cyre W.R., Learning Grammars with a Modified Classifier System. Proc. 2002 World Congress on Computational Intelligence. Honolulu. Hawaii. 1366-1371, 2002.
• [6] Cyre W.R., Evolutionary Language Acquisition. Proc. 6th IASTED Int. Conf. on Artificial Intelligence and Soft Computing. Banff. Canada. 146-151, 2002.
• [7] Dupont P., Regular Grammatical Inference from Positive and Negative Samples by Genetic Search. Grammatical Inference and Application. 2 International Colloquium ICG-94. Berlin. Springer. 236-245, 1994.
• [8] Gold E., Language identification in the limit. Information Control 10. 447-474, 1967.
• [9] de la Higuera C., Current trends in grammatical inference. Ferri F.J. i in. (red.) Advances in Pattern Recognition. Joint IAPR International Workshops SSPR+SPR”2000. LNCS 1876. 28-31, 2000.
• [10] Holland J., Adaptation. Rosen R., Snell F.M. (red.) Progress in theoretical biology. New York. Plenum, 1976.
• [11] Holland J., Escaping Brittleness: The possibilities of General-Purpose Learning Algorithms Applied to Parallel Rule-Based Systems. Michalski R.S. i in. (red.) Machine Learning, an artificial intelligence approach. vol. II. Morgan Kaufmann. 593-623, 1986.
• [12] Holmes J. H., Lanzi P. L., Stolzmann W., Wilson, S.W., Learning classifier systems: new models, successful applications. Information Processing Letters. 82(1). 23-30, 2002.
• [13] Hopcrofl J.E., UlIman J.D., Wprowadzenie do teorii automatów, języków i obliczeń. PWN. Warszawa, 1994.
• [14] Huijsen W., Genetic Grammatical Inference: Induction of Pushdown Automata and Context-Free Grammars from Examples Using Genetic Algorithms. M.Sc.-thesis. Dept. of Computer Science. University of Twente. Enschede. The Netherlands, 1993.
• [15] Korkmaz E.E., Ucoluk G., Genetic Programming for Grammar Induction. Proc. of the Genetic and Evolutionary Conference GECCO-2001. San Francisco Ca. Morgan Kaufmann Publishers, 2001.
• [16] Lankhorst MM., Breeding grammars: Grammatical inference with a genetic algorithm. Tech. rep., Dept. of CS, U. of Groningen. Box 800. 9700 AV Groningen. The Netherlands, 1994.
• [17] Lankhorst MM., A Genetic Algorithm for the Induction of Nondeterministic Pushdown Automata. Computing Science Reports CS-R 9502. Department of Computing Science. Uniyersity of Groningen, 1995.
• [18] Lanzi P.L., Riolo R.L. A Roadmap to the Last Decade of Learning Classifier System Research. Lanzi P.L., Stolzmazn W., Wilson S.W. (red.) Learning Clasifier Systems. From Foundations to Applications. LNAI 1813. Springer Verlag. Berlin. 33-62, 2000.
• [19] Lee L., Learning of Context-Free Languages: A Survey of the Literature. Report TR-12-96. Harvard University. Cambridge. Massachusetts, 1996.
• [20] Lucas S., Context-Free Grammar Evolution. First International Conference on Evolutionary Computing. 130-135, 1994.
• [21] Piech H., Wykorzystanie narzędzi stochastycznych do realizacji algorytmów genetycznych. Wydawnictwo Politechniki Częstochowskiej. Częstochowa, 2003.
• [22] Smith T.C., Witten, I.H., Learning Language Using Genetic Algorithms. Wermter S., Rilo E., Scheler G. (red.) Connectionist, Statistical, and Symbolic Approaches to Learning for Natural Language Processing, LNAI 1040, 1996.
• [23] Tapanainen P., Jaryinen T., A non-projective dependency parser. Proc. of the Sth Conference on Applied Natural Language Processing. Washington. D.C. Association for Computational Linguistics. 64-71, 1997.
• [24] Unold O., Dąbrowski G., Use of learning classifier system for inferring natural language gram- mar. Abraham A. i in. (red.) Design and application of hybrid intelligent. Amsterdam. IOS Press. 272-278, 2003.
• [25] Unold O., Cielecki L., Grammar-based Classifier System. Kacprzyk J., Koronacki J. (red.) First Warsaw International Seminar on Intelligent Systems. EXIT Publishing House. Warsaw, 2004, (w druku).
• [26] Unoid O., Playing a toy-grammar with GCS. Mira J. „ Alvarez J.R. (red.) IWINAC 2005. LNCS 3562. Springer-Verlag Berlin Heidelberg. 300-309, 2005.
• [27] Unoid O., Learning Context-Free Language using Grammar-based Classifier System. Proc. of the 2nd Language and Technology Conference. Poznań. Poland. 2005, (w druku).
• [28] Unold O., Cielecki L., How to use crowding selection in Grammar-based Classifier System. Proc. of 5th Intemational Conference Intelligent Systems - Design and Applications (ISDA 2005). Wrociaw IEEE (w druku).
• [29] Wilson SW., Classifier Fitness Based on Accuracy. Evolutionary Computation 3 (2). 147-175, (1995).