Evolutionary Program Induction Directed by Logic Grammars

Created by W.Langdon from gp-bibliography.bib Revision:1.4420

  author =       "Man Leung Wong",
  title =        "Evolutionary Program Induction Directed by Logic
  school =       "Department of Computer Science and Engineering, The
                 Chinese University of Hong Kong",
  year =         "1995",
  address =      "Hong Kong",
  month =        jun,
  keywords =     "genetic algorithms, genetic programming, Logic
                 programming, ILP, LOGENPRO, FOIL, Uncle predicate",
  URL =          "http://etheses.lib.cuhk.edu.hk/pdf/000743570.pdf",
  size =         "253 pages",
  abstract =     "Program induction generates a computer program with
                 the desired behaviour for a given set of situations.
                 Genetic Programming (GP) and Inductive Logic
                 Programming (ILP) are two of the approaches for program
                 induction. GP is a method of automatically inducing
                 S-expressions in Lisp to perform specified tasks while
                 ILP involves the construction of logic programs from
                 examples and background knowledge.

                 Since their formalisms are very different, these two
                 approaches cannot be integrated easily although their
                 properties and goals are similar. If they can be
                 combined in a common framework, then their techniques
                 and theories can be shared and their problem solving
                 power can be enhanced.

                 This thesis describes a framework that integrates GP
                 and ILP based on a formalism of logic grammars. A
                 system called LOGENPRO (the LOgic grammar based GENetic
                 PROgramming system) is developed. This system has been
                 tested on many problems in program induction, knowledge
                 discovery from databases, and meta-level learning.
                 These experiments demonstrate that the proposed
                 framework is powerful, flexible, and

                 Experiments are performed to illustrate that programs
                 in different programming languages can be induced by
                 LOGENPRO. The problem of inducing programs can be
                 formulated as a search for a highly fit program in the
                 space of all possible programs. This thesis shows that
                 the search space can be specified declaratively by the
                 user in the framework. Moreover, the formalism is
                 powerful enough to represent context-sensitive
                 information and domain-dependent knowledge. This
                 knowledge can be used to accelerate the learning speed
                 and/or improve the quality of the programs

                 Knowledge discovery systems induce knowledge from
                 datasets which are huge, noisy (incorrect), incomplete,
                 inconsistent, imprecise (fuzzy), and uncertain. The
                 problem is that existing systems use a limiting
                 attribute-value language for representing the training
                 examples and induced knowledge. Furthermore, some
                 important patterns are ignored because they are
                 statistically insignificant. LOGENPRO is employed to
                 induce knowledge from noisy training examples. The
                 knowledge is represented in first-order logic program.
                 The performance of LOGENPRO is evaluated on the chess
                 endgame domain. Detailed comparisons with other ILP
                 systems are performed. It is found that LOGENPRO
                 outperforms these ILP systems significantly at most
                 noise levels. This experiment indicates that the
                 Darwinian principle of natural selection is a plausible
                 noise handling method which can avoid over fitting and
                 identify important patterns at the same time.

                 An Adaptive Inductive Logic Programming (Adaptive ILP)
                 system is implemented using LOGENPRO as the meta-level
                 learner. The system performs better than FOIL in
                 inducing logic programs from perfect and noisy training
                 examples. The result is very encouraging as it suggests
                 that LOGENPRO can successfully evolve a high
                 performance ILP system.",
  notes =        "Supervisor: K.S. Leung",

Genetic Programming entries for Man Leung Wong