- author = "Man Leung Wong",
- title = "Evolutionary Program Induction Directed by Logic Grammars",
- 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 general.
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 induced.
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",
