Evolving stochastic grammars
Thomas E. Kammeyer, Richard K. Belew · 1998
Evolutionary algorithms (EAs) are a class of machine learning algorithms which, along with neural networks and simulated annealing, reflect a theme that has become popular in machine learning: the pursuit of algorithms that work because they mimic natural processes. In the case of EAs, a population of individual solutions evolves to solve a machine learning problem. Here, the simulated evolution of a population of stochastic phrase-structure grammars and how derivations from those grammars play a role analogous to biological ontogenesis are explored. An overview of evolutionary algorithms is presented and a simple EA is discussed in detail, taking note of some extensions important for the purposes of this thesis. The problem of representing definitions of functions on EA genotypes, and representing grammars as a special case of this problem, are discussed. A review of grammar induction provides background and context. Two EAs to evolve grammars are described, using distinct methods to evaluate grammars' fitnesses. The first EA evolves grammars which derive descriptions of merging networks, and tests these simple merging algorithms for correctness in order to evaluate grammar fitness. The second EA, EvoGrams, evaluates a grammar by parsing each string in a training set and evaluating the probability of the data given the grammar using these parses. A mechanism to give partial credit to grammars is important in assigning fitness when no complete parses are possible, and a local search method plays an important role in evaluation as well. The best evolved merging networks from the first EA are tested for the property of being log-sequential sorting networks. A previously unknown sorting network is discovered that combines parts of the recursive definitions from two known networks. EvoGrams is successfully applied to induce grammars for several formal languages, compared with other algorithms, and experiments are presented which address important issues related to performing grammar induction with it. Finally, an attempt to use EvoGrams to perform grammar induction on data from the primary sequences of proteins is presented and analyzed, and further work and improvements suggested by the results are discussed.