Grammatical bias for evolutionary learning

Whigham, Peter Alexander.  University of New South Wales (Australia). ProQuest Dissertations Publishing, 1996. 0597571.

Abstract (summary)

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.

Indexing (details)

Computer science;
Artificial intelligence
0984: Computer science
0800: Artificial intelligence
Identifier / keyword
Applied sciences; artificial intelligence; induction
Grammatical bias for evolutionary learning
Whigham, Peter Alexander
Number of pages
Degree date
School code
DAI-B 57/10, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
University of New South Wales (Australia)
University location
Source type
Dissertation or Thesis
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL