Grammar Inference using Evolutionary-Based Techniques

Grammar, which knows how to control even kings . . .
-Molière, Les Femmes Savantes (1672), Act II, scene VI

Grammar Inference using Evolutionary-Based Techniques

Project Description

We are interested in the development of evolutionary-based techniques for the generation of grammars of different kinds (particularly regular and context-free) from a finite set of positive and negative examples. Some of the main aims of this project is to produce representation schemes, genetic operators, and evolutionary-based techniques in general that are efficient (computationally speaking) and flexible (i.e., easy to generalize). The solution to this problem has multiple applications in speech recognition, pattern recognition, workload modeling, optical character recognition, and robust parsing, among others.

Research Opportunities

Anyone interested in this project may collaborate in one or more of the following activities:

To propose and experiment with several representation schemes and genetic operators suitable for genetic algorithms and genetic programming. These representation schemes should allow the generation of regular and context-free grammars in a compact form as to allow the use of reasonably small strings to represent relatively complex grammars. The proposed genetic operators should preserve (as much as possible) the feasibility of the rules that conform a grammar, as to avoid repair algorithms that can strongly bias the sort of grammars generated. Comparisons should be done with respect to other (evolutionary-based and deterministic) approaches reported in the specialized literature. It is worth mentioning that all aspects of this problem are interesting, because it is difficult to design proper fitness functions that accurately reflect how close is a certain grammar from the target grammar that recognizes a given language. The design of the fitness function normally requires the design of good complexity measures that quantitatively estimate how ``good'' a grammar is with respect to others, but several issues remain open in this research area ( Masters student required )
Development of a platform to experiment with deterministic regular and context-free grammars using genetic programming (or genetic algorithms). This system should facilitate experimentation with new representation schemes and operators, and should serve as a common platform to test existing and new evolutionary-based approaches to grammar inference ( Undergraduate student required )

Interested students, please contact Dr. Carlos A. Coello Coello.

Current Work

Julio César Sandria Reynoso is currently working in the induction of context-free grammars using genetic algorithms, to characterize sequences of symbols. His Masters thesis proposal is available online.

Suggested Readings

John S. Gero; Sushil J. Louis and Sourav Kundu, Evolutionary Learning of novel grammars for design improvement, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, Vol. 8, pp. 83-94, 1994.
Simon Lucas, Structuring Chromosomes for Context-Free Grammar Evolution, Proceedings of first IEEE International Conference on Evolutionary Computation, pp 130-135, June, 1994.
P. A. Whigham, Grammatically-based Genetic Programming, Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, J. Rosca (editor), Morgan Kaufmann Publishers, pp. 33-41, July 1995.
B. Keller and R. Lutz, Learning SCFGs from Corpora by a Genetic Algorithm, in George D. Smith, Nigel C. Steele and Rudolf F. Albrecht (editors), Artificial Neural Nets and Genetic Algorithms, Springer-Verlag, pp. 210-214, 1997.
Marc M. Lankhorst, Breeding Grammars: Grammatical Inference with a Genetic Algorithm, Computing Science Report CS-R 9401. Department of Computing Science, University of Groningen, The Netherlands, 1994.
Marc M. Lankhorst, A Genetic Algorithm for the Induction of Nondeterministic Pushdown Automata, Computing Science Report CS-R 9502, Department of Computing Science, University of Groningen, The Netherlands, 1995.
Willem-Olaf Huijsen, Genetic Grammatical Inference, Proceedings of CLIN'93, Groningen, The Netherlands, pp. 59-72, 1993.
Peter Wyard, Context Free Grammar Induction Using Genetic Algorithms, in Richard K. Belew & Lashon B. Booker (Editors), Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo, California, pp. 512-517, 1991.
Markus Schwehm and Alexander Orst, Inference of Stochastic Regular Grammars by Massively Parallel Genetic Algorithms, in Larry J. Eshelman (Editor), Proceedings of the Sixth International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo, California, 1995.
Helmut Hörner, Helmut, A C++ Class Library for Genetic Programming: The Vienna University of Economics Genetic Programming Kernel, May, 1996.
Hendrik James Antonisse, A Grammar-Based Genetic Algorithm, in Gregory E. Rawlings (Editor), Foundations of Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo California, pp. 193-204, 1991.
Tony C. Smith and Ian H. Witten, A genetic algorithm for the induction of natural language grammars, Proceedings of the IJCAI-95 Workshop on New Approaches to Learning for Natural Language Processing, pp. 17-24, Montreal, Canada, 1995.
Thomas E. Kammeyer and Richard K. Belew, Stochastic Context-Free Grammar Induction with a Genetic Algorithm Using Local Search, in Richard K. Belew and Michael D. Vose (Editors), Foundations of Genetic Algorithms 4, Morgan Kaufmann Publishers, San Francisco, California, pp. 409-436, 1997.
Walter Böhm and Andreas Geyer-Schulz, Exact Uniform Initialization for Genetic Programming, in Richard K. Belew and Michael D. Vose (Editors), Foundations of Genetic Algorithms 4, Morgan Kaufmann Publishers, San Francisco, California, pp. 379-407, 1997.
Ryan, Conor; J. J. Collins & Michael O'Neill, Grammatical Evolution: Evolving Programs for an Arbitrary Language, in W. Banzhaf, R. Poli, M. Schoenauer, and T.C. Fogarty (Editors), Lecture Notes in Computer Science 1391, Proceedings of the First European Workshop on Genetic Programming, pp. 83-95, Paris, France, Springer-Verlag, April, 1998.
Longshaw, Tom, Evolutionary learning of large Grammars, in John R. Koza, Kalyanmoy Deb, Marco Dorigo, David B. Fogel, Max Garzon, Hitoshi Iba and Rick L. Liolo (Editors), Proceedings of the Second Annual Conference on Genetic Programming, July, Stanford University, pp. 445-453, Morgan Kaufmann Publishers, 1997.

Go Back to my Home Page

There have been

Visitors since May 11th 1999.

Send any comments to ccoello@xalapa.lania.mx