- author = "Andrew R. McIntyre",
- title = "Novelty Detection + Coevolution = Automatic Problem Decomposition: A Framework for Scalable Genetic Programming Classifiers",
- school = "Dalhousie University",
- year = "2007",
- address = "Halifax, Nova Scotia, Canada",
- month = nov,
- keywords = "genetic algorithms, genetic programming",
-
URL = "
http://projectx25.cs.dal.ca/home/docs/armcintyre_phd_thesis_final.pdf",
- size = "442 pages",
-
abstract = "A novel approach to the classification of large and
unbalanced multi-class data sets is presented where the
widely acknowledged issues of scalability, solution
transparency, and problem decomposition are addressed
simultaneously within the context of the Genetic
Programming (GP) paradigm. A cooperative coevolutionary
training environment that employs multi-objective
evaluation provides the basis for problem decomposition
and reduced solution complexity, while scalability is
achieved through a Pareto competitive coevolutionary
framework, allowing the system to be readily applied to
large data sets (tens or hundreds of thousands of
exemplars) without recourse to hardware-specific
speedups. A key departure from the canonical GP
approach to classification involves expressing the
output of GP in terms of a non-binary, local membership
function (e.g., a Gaussian). Decomposition is achieved
by reformulating the classification problem as one of
cluster consistency, where an appropriate subset of the
training patterns can be associated with each
individual such that problems are solved by several
specialist classifiers as opposed to a singular `super'
individual.
Although multi-objective methods have previously been reported for GP classification domains, we explicitly formulate the objectives for cooperative behavior. Without this the user is left to choose a single individual as the overall solution from a front of solutions. This work is able to use the entire front of solutions without recourse to heuristics for selecting one individual over another or duplicating behaviors between different classifiers.
Extensive benchmarking was performed against alternative frameworks for classification including Genetic Programming, Neural Networks, and deterministic methods. In contrast to classifiers evolved using competitive coevolution alone, we demonstrate the ability of the proposed coevolutionary model to provide a non-overlapping decomposition or association between learners and exemplars, while returning statistically significant improvements in classifier performance. In the case of the Neural Network methods, benchmarking is conducted against the more challenging second order neural learning algorithm of conjugate gradient optimization (previous comparisons limit Neural Networks to first order methods). The proposed evolutionary method was often significantly better than the non-linear Neural Network, whereas the linear model tended to work well or not at all. In effect, the evolutionary paradigm provided a more robust model for searching the space of non-linear models than provided under the neural gradient decent paradigm. With respect to deterministic methods, the problem of benchmarking stochastic versus deterministic algorithms is first addressed, with a new methodology established for making such comparisons. The ensuing comparison demonstrated that the evolutionary algorithms remain competitive with most data sets appearing to benefit from the proposed evolutionary methodology.",
-
notes = "http://projectx25.cs.dal.ca/home/?pg=research
Advisor: Dr. Malcolm I. Heywood (Dalhousie University, Faculty of Computer Science)
External Examiner: Dr. Una-May O'Reilly (MIT Computer Science and Artificial Intelligence Lab)
Graduate Committee: Dr. Evangelos E. Milios and Dr. Syed Sibte Raza Abidi (Dalhousie University, Faculty of Computer Science)",
