Genetic programming for multiclass object classification

Abstract

This thesis investigates the use of Genetic Programming (GP) in solving object classification tasks of three or more classes (multiclass). Methods are developed to improve the performance of the GP system at four multiclass object classification tasks of varying difficulty, by investigating two aspects of GP The first aspect of GP is the classification strategy, or the method used to translate a real program output into a class label for classification. Previous classification strategies typically arrange the program output space into class regions, which in some methods can change position or class during evolution. We have developed a new classification strategy that does not deal with the regions directly, but instead models the output of a program using normal distributions. Advantages of the new approach include the use of improved fitness measures, and the possibility of multiple programs being used together to predict the class of a test example. In experiments, this method performs significantly better than the three other classification strategies it was tested against, especially on difficult tasks. We have also developed a method which decomposes the multiclass classification task into many binary subtasks. Unlike previous approaches, this method solves all binary subtasks in one evolution using a modified, multi-objective fitness function. The multiclass task is solved by combining expert programs, each able to solve one subtask. In experiments, this method outperforms the basic approach, and a previous 'divide-and-conquer' approach, especially on difficult problems. The second aspect of GP investigated is the use of hybrid searches, involving both evolutionary search and gradient-descent search. By adding weights to the links of genetic programs, we have enabled a similar search to that of neural networks, within each generation of a GP search. The weights control the effect of each subtree in a program, and may be efficiently optimized using gradient-descent. The use of weights was found to improve accuracy over the basic approach, and slightly improve on the gradient-descent search of numeric terminals alone. We have also developed a novel hybrid search in which changes to each program's fitness occur only through gradient-descent, though the evolutionary search still modifies program structure. This is possible through modified genetic operators and inclusion factors which allow certain sub-trees in a program to be 'mapped-out' of the program's calculations. Unfortunately, the new search is found to decrease accuracy and increase time per run for the GP system. The aim of this thesis, to improve the performance of GP at multiclass object classification tasks, has been achieved. This thesis contains methods that significantly improve the performance of a GP system for these problems, over the basic approach. The work of this thesis serves to improve GP as a competitive method on multiclass object classification tasks.