Grammatical bias for evolutionary learning

A framework for declarative bias, based on the genetic programming paradigm (GP), is presented. The system, CFG-GP, encapsulates background knowledge, inductive bias and program structure. A context-free grammar is used to create a population of programs, represented by their corresponding derivation trees. These computer programs evolve using the principle of Darwinian selection. The grammar biases the form of language that is expressible and the inductive hypotheses that are generated. Using a formal grammar to define the space of legal statements allows a declarative language bias to be stated. The defined language may express knowledge in the form of program structure and incorporate explicit beliefs about the structure of possible solutions. Additionally, the form of the initial population of programs may be explicitly biased using a merit selection operation. This probabilistically biases particular statements generated from the grammar.

The program induction system, CFG-GP, represents search bias with three operators, namely selective crossover, selective mutation and directed mutation. Each of these operators allows a bias to be explicitly defined in terms of how programs are modified and how the search for a solution proceeds. Hence, both a search and language bias are declaratively represented in an evolutionary framework.

The use of a grammar to define language bias explicitly separates this bias from the learning system. Hence, the opportunity exists for the learning system to modify this bias as an additional strategy for learning. A general technique is described to modify the initial grammar while the evolution for a solution proceeds. Feedback between the evolving grammar and the population of programs is shown to improve the convergence of the learning system. The generalising properties of the learnt grammar are demonstrated by incrementally adapting a grammar for a class of problems.

A theoretical framework, based on the schema theorem for Genetic Algorithms (GA), is presented for CFG-GP. The formal structure of a grammar allows a clear and concise definition of a building block for a general program. The result is shown to be a generalisation of both fixed-length (GA) and variable-length (GP) representations within the one framework.