The week's pick
Reseach Article
Sequential Structuring Element for CFG Induction Using Genetic Algorithm
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 1 - Number 1 |
| Year of Publication: 2010 |
| Authors: N. S. Choubey,M. U. Kharat |
10.5120/29-137
|
N. S. Choubey,M. U. Kharat . Sequential Structuring Element for CFG Induction Using Genetic Algorithm. International Journal of Computer Applications. 1, 1 ( February 2010), 7-11. DOI=10.5120/29-137
Abstract
This paper investigates the induction of Context free Grammar with genetic algorithm. The genetic algorithm is not very effective at this [1]. To overcome this problem we investigate combined effect of two methods for structuring the chromosomes. The first is to bias the distribution of Non-terminals in the chromosome at the time of chromosome generation as well as updating. The latter approach is sequential structural mapping from chromosome to grammar. It is shown that biasing the chromosome in this fashion produces extremely fast convergence as shown in the result section. Grammars are an extremely general and useful tool with many applications. These include the higher levels of signal processing, such as pattern recognition. However, the application of grammars is limited by the algorithms we can apply to infer them from samples of data. The main contribution of this paper is the effective decoding of the context free grammar from chromosomes with the distinct approaches mentioned.
References
- Simon Lucas, IEEE, 2000, A. Structuring Chromosomes for Context-Free Grammar Evolution
- Wyard P.,1994, Representational Issues for Context-Free Grammar Induction Using Genetic Algorithm in Proceedings of the 2nd International Colloquim on Grammatical Inference and Applications, Lecture Notes in Artificial Intelligence, Vol 862, pp. 222-235,
- De la Higuera, 2005, “A Bibliographical Study of Grammatical Inference”, Pattern Recognition, v. 38, no. 9, 2005, pp. 1332-1348.
- Ernesto Rodrigues and Heitor Silvério Lopes, Genetic Programming with Incremental Learning for Grammatical Inference, Graduate Program in Electrical Engineering and Computer Science, Federal University of Technology – Paraná, Av. 7 de setembro, 3165 80230-901, Curitiba, Brazil.
- Guy De Pauw, 2003, Evolutionary Computing as a Tool for Grammar Development, CNTS – Language Technology Group, UIA – University of Antwerp, Antwerp – Belgium, E. Cant´u-Paz et al. (Eds.): GECCO 2003, LNCS 2723, pp. 549–560, 2003.,c_Springer-Verlag Berlin Heidelberg 2003.
- Marcus, M.P., Santorini, B., Marcinkiewicz, M., 1994, Building a large annotated corpus of english: the penn treebank. Computational linguistics 19 (1993) 313–330 Reprinted in Susan Armstrong, ed., Using large corpora, Cambridge, MA: MIT Press, 273–290.
- Daelemans,W., van den Bosch, A., Zavrel J, 1999, Forgetting exceptions is harmful in language learning. Machine Learning, Special issue on Natural Language Learning 34 (1999) 11–41.
- F. Javed, B. R. Bryant, M.Crepinek, Mernik, Sprague,2004, “Context-free Grammar Induction using GeneticProgramming”, ACMSE, Huntzville.
- Marc Lankhorst, “A Genetic Algorithm for the Induction of Nondeterministic Pushdown Automata”, University of Groningen, The Netherlands, May 1995.
Index Terms
Keywords