% TODO: Need Results for hereditary repulsion
% TODO: Discuss false negative vs. false positives with Adrian
% TODO: Results for even class allocation

\chapter{Validating the Evolved Learning System}
\label{ch:gpcomparison}

\begin{quotation}
\noindent ``Name the greatest of all inventors. Accidents.''\\
\em Mark Twain
\end{quotation}

% The power of accidents
\noindent Rubber in its natural form is not particularly useful. In cold conditions it is brittle and cracks, yet in hotter climates it readily melts. It was the accidental spillage of sulphur onto raw rubber by Charles Goodyear in 1839 that led to the discovery of vulcanisation, the process by which rubber can be rendered into a stable consistency\footnote{Goodyear was unable to patent his invention and died penniless.}. Similarly, the recipe for Coca Cola was formulated inadvertently by John Pemberton while he tried to concoct a pain relief remedy\footnote{Pemberton later sold the recipe for \$900 and died penniless.}. In 1897, Ernest Duchesne submitted his thesis describing his discovery, again by accident, that certain moulds would kill bacteria. Although his research went largely unnoticed at the time, it was the first documented discovery of antibiotics\footnote{Duchesne later died penniless, ironically from Tuberculosis, which his own discovery could have treated.}. While science certainly does not progress through accidental discovery alone, chance happenings like these can suggest avenues of exploration that had not previously been considered. The inherent randomness and abstract nature of Genetic Programming (GP) would appear to make it quite good at simulating creativity, but is this enough for it to compete with the best of human-written pattern recognition algorithms? The goal of this chapter is to make several empirical comparisons in order to answer this question. 

GP has already been recognised as an automatic innovator in fields outside of pattern recognition. According to John Koza \cite{koza-web-site}, whose seminal books on GP continue to dominate the literature, there are at least thirty six recorded instances where GP has produced human competitive solutions, mainly within the domain of evolved electronics. Twenty one of these instances either infringe or duplicate functionality of previously patented 20th/21st Century inventions, and two are sufficiently novel as to be patentable in their own right.

 In the latter part of this chapter, the author's GP toolkit will be compared to a standard GP implementation, then to other results reported by GP researchers in general, and finally to the results of a range of other popular classification techniques. This chapter begins, however, with a more thorough description of the author's GP system, an enumeration of its novel features, and a discussion of how a genetic learning system, often plagued by the need to discover problem-specific parameters, can be adapted into a ``black-box'' generic problem solver.

\section{Building a GP System}
\label{sxgp}
\label{ecj}
Although the author's initial experiments made use of ECJ \cite{ECJ}, a popular but cumbersome open-source GP toolkit, it became apparent that in order to experiment with changes to the GP system itself, it would be worthwhile to develop the GP system from scratch\footnote{Of course, it is also more satisfying than to use other peoples' code!}. This toolkit (named SXGP, after its \foreign{alma mater}) is specifically designed for evolving solutions to problems involving vision. 

Being practically minded, the author also sought to develop a toolkit whose evolved solutions could easily be put to work within applications. Since the objective is to develop vision systems using two or more evolved components, it is crucial that each component be easily deployed since the system cannot be evaluated purely within the confines of the GP environment. ECJ is rather difficult to integrate into other software (since each run is usually defined by a configuration file, rather than programmatically) and does not readily output individuals as for use in other programs\footnote{ECJ outputs individuals using LISP syntax. The author has written an extension to output ECJ individuals in Java \cite{oechsle:ecj2java}.}. The author's toolkit, SXGP, can be instantiated though a straightforward programming interface, and can deploy programs in various different ways so that they may be put to work within applications.

The various components that make up a Genetic Programming toolkit were described in detail in Chapter \ref{ch:gpsurvey}. There are numerous choices that one can make for each component, so two Genetic Programming implementations can actually differ quite significantly. Thus, before the comparisons commence, it is necessary to describe SXGP in more detail.

\subsection{Specification}
The main components of the author's system are specified in Table \ref{tab:gp-spec}.

% TODO: Ensure all pages are referenced here
\begin {table}[ht]
\centering 
\begin {tabular}{ llr }
Component 		& Method			& Where Described				\\ \toprule
Representation	 	& Tree				& Page \pageref{tree-representation}		\\ \midrule
Population Builder	 	& Ramped Half and Half		& Page \pageref{ramped-half-and-half}		\\ \midrule
Selection Method 	& Tournament Selection		& Page \pageref{tournament-selection}		\\ \midrule
Generation Gap	 	& Generational			& Page \pageref{generation-gap}			\\ \midrule
Fitness Function 	& Variable			& Page \pageref{fitness-function}		\\ \midrule
Elitism			& Enabled			& Page \pageref{elitism}			\\ \midrule
Genetic Operators 	& Crossover and Mutation	& Pages \pageref{crossover}, \pageref{mutation}	\\ \midrule
Population Size 	& Variable			& Page \pageref{pop-size}			\\ \midrule
Generations		& Variable			& Page \pageref{pop-size}			\\ \midrule
Function Nodes	 	& Task Dependent		& Page \pageref{functionset}	\\ \midrule
Terminal Nodes	 	& Problem Dependent		& 						\\ \midrule
Learning Paradigm 	& Supervised			&  						\\ \midrule
Island Selection 	& Utilised			& Page \pageref{island-selection}		\\ \midrule
\end {tabular}
\caption{Specification of SXGP, the author's Genetic Programming Toolkit}
\label{tab:gp-spec}
\end {table}

\subsection{Implementation Notes}
SXGP is implemented in Java, a language well suited to the development of abstract tools. Java also offers excellent libraries for image acquisition,  networking and multi-threading. The cross platform nature of Java makes it particularly suitable for distributing the Genetic Programming process over a number of CPUs, a feature also implemented in SXGP.

Results by a performance profiler reveal a significant amount of computational time expended by the Genetic Programming process is actually devoted to the copying of individuals, which is necessary to ensure that offspring are separate instances from their parents\footnote{Otherwise the later actions of genetic operators on parents would also affect the offspring.}. Although the author originally used a flexible copying operator which serialises an object into a stream and then re-instantiates it as a new instance, this was found to be a significant bottleneck. Instead, each object implements its own cloning method which permits the process to proceed much more quickly, while maintaining the requirement to perform ``deep cloning''\footnote{Deep cloning refers to copying both an instance and all of its class members; shallow cloning will clone the instance, but will not copy class members. In GP, individuals must be completely separate instances, otherwise the genetic operators may affect more than one individual at a time.}.

We shall look at other means of enhancing performance throughout the course of this thesis.

\subsection{Novel Features}
SXGP comprises a number of features that are novel. Each is discussed briefly below.

\paragraph{Strong-er Typing}
\label{stronger-typing}
Depending on the set of functions used and the maximum tree size permitted, the program search space can be very large. While the essential purpose of any genetic learning system is to discover good solutions to a problem without resorting to an exhaustive evaluation of the search space, it is nonetheless desirable to ensure the search space itself is as small as possible.

One way of reducing the program space is through the use of \emph{strong typing}, where the tree builder, which is responsible for constructing the programs (and new mutations), is constrained to connect only nodes which make semantic sense. For instance, the \emph{LessThan} operator, which returns a boolean value, should not be supplied as an argument to the \emph{division} operator -- execution could lead to divide-by-zero errors and a rather inconsistent logic. As was mentioned in Chapter \ref{ch:cvsurvey}, Montana\cite{EvoVision:Montana:1993} implemented a means of strong typing for GP systems by introducing the notion of a \emph{return type}, which would have to be matched with each node's argument types, as is the case in the strongly-typed programming languages. As an example the \emph{add} operator should insist that both its arguments have a \emph{numeric} return type; the operator itself will also return a \emph{numeric} value.

However, as Montana pointed out, types such as \emph{numeric} or \emph{boolean} have the disadvantage of being rather \emph{too} generic. If one is looking for a count for a loop, for instance, a floating point number is not necessarily appropriate -- it is better to involve an integer. However, if one defines ``integer'' as a new type to accommodate this requirement, then the arithmetic operators would no longer accept it, since it cannot be both ``numeric'' and an ``integer''. Of course this shouldn't be the case. Essentially a node should be able to return more than one type, for instance to say that it returns a number that is also an integer: indicating a hierarchy of inheritance among different types. SXGP includes this flexibility, where each node may implement \emph{multiple} return types. The overall return type of a node is instead defined as an \emph{array} of different individual types. If any of these match the required, specific argument of a node, then it is deemed acceptable for addition to the tree by the tree builder. This permits the system to make use of more complex structures while producing fewer trees that don't make semantic sense.

\paragraph{Tree Checking}
Here the author's stronger-typing framework extends beyond Montana's work. Although GP is capable of evolving many means of procrastination, the stronger-typing approach still permits the creation of ``useless'' code that performs no function. Code may be considered useless if it is never executed, or if it always returns the same value regardless of input. The former is usually to be found in branches of if-statements whose condition is accidentally constant. 

The tree builder in the author's GP toolkit attempts to avoid  creating such code by following additional criteria, which may be created for specific nodes. For instance comparative nodes (\emph{lessThan, moreThan, between, equals}) additionally insist that at least one of the child nodes in the sub-tree beneath each be some kind of image feature (a separate sub-type, based on the numeric type). This helps ensure that every sub-tree has the potential to perform some useful processing\footnote{Although it is still not perfect: the lessThan function could compare a feature whose return values are in the range 0-255 to a value of 1000, which would again always return the same value. However, SXGP's automatic optimisation mechanism will remove this kind of code.}. This restriction also reduces the size of the program search space.

The system also discards those programs that do not make use of features at all. GP programs, if left unchecked, may take advantage of the \emph{a priori} probabilities of solutions and simply return the most popular!

\paragraph{Automatic Optimisation}

%TODO: This could be expanded a bit, perhaps with results (also instant deployment)
The author's GP system automatically optimises the best individual at the end of evolution, in order to make it more suitable for deployment in the computer vision task for which efficiency is always a criterion. After running the individual again on the training data, the system collects statistics about each node, then removes nodes that are never used and replaces nodes that always return the same value with constants.

%TODO: Also mention ERC optimisation, results etc.

\paragraph{Instant Deployment}
Solutions evolved by SXGP can be deployed for use in other applications immediately, in two modes:

\begin{description}
 \item[GP Tree] The GP tree is used as-is, so the program can be used immediately. The SXGP tree class itself is \emph{serializable}, which means it can take advantage of the Java mechanism to be readily saved to disk and reinstantiated later, or on different machines. All important information, including the status of the individual's program classification map, are saved. Wrapper classes permit different GP trees to be applied to different tasks in vision, such as feature detection or object classification. However, since the program is executed in an interpreted manner, the program will not run as efficiently as possible.
\item[Compiled Java] The GP tree is first converted into Java source code, then compiled automatically. This kind of program will run significantly faster (see page \pageref{deployment}), but requires the right libraries to be linked, and for the user to have a Java Development Kit installed on their computer for compilation to proceed. The process of deploying individuals for use in vision systems is discussed in greater depth in Chapter \ref{ch:low-level}.
 \end{description}

\paragraph{Live Evaluation}
%TODO: Screenshot here?
As well as providing a graphical interface to display the status of the evolutionary system, the effect of the current best GP program on images is displayed live by the user during evolution. This enables the user to assess how well the evolved solution is working and generalising, and provides an insight into how difficult a feat of image processing is: the user may subsequently tailor the training set to incorporate characteristics that apparently were not emphasised sufficiently in initial training data.

\subsection{Parameter Choices for a Generic System}
One can think of a Genetic Programming system as a whole ``world'' in which the birth, life and death of thousands of individuals are simulated by a series of sub-components. As such, one of the problems of developing solutions with GP is the sheer number of parameters required by each component: there are parameters for the minimum and maximum initial depth of individuals, the kind of tree builder to use, the population size, the number of generations, choice of fitness function, and so on.  Moreover, it is difficult to assess the true effect of any parameter since all these components are rather inter-related. The work published by other researchers indicates that parameter tuning and experimentation is often called for, which doesn't bode well for a supposedly generic problem solver. In order to maintain the aspiration of a generic system, it is worthwhile to consider the research and theory behind different parameter choices in order to establish a set of parameters that work well on a wide range of problems. Some of these are discussed below.

\paragraph{Genetic Operators}
A standard breeding pipeline involving crossover, mutation and reproduction (copying) operators is used in SXGP: each new individual in the new population is produced from one or more ``parents'' using one of the above operators. The number of individuals generated by each operator is usually determined by allocating a given percentage to each. The optimal ``blend'' of the learning operators crossover and mutation is something not all researchers agree on. Koza himself used no mutation, preferring a 100\% crossover pipeline\footnote{Koza was keen to prove that GP learning was not random search.}. Other researchers \cite{Chellapilla:1998} have shown that Genetic Programming can proceed without using crossover at all, by using 100\% mutation. In fact, provided that there is a suitable means of selection, and that there is some genetic search proceeding, the GP process is remarkably robust\footnote{The author's own toolkit, SXGP, for several months featured a silent bug in which crossover-generated individuals were not added to the new population. The problem was only noticed later --- the bug had had little apparent effect on the results by GP, much to the embarrassment of the author.}.

Work by Luke and Spector \cite{luke:1997:ccmGP} aimed to establish a way forward through systematic comparisons of evolution using different proportions of crossover and mutation. They found that, in general, evolution using only crossover was slightly more successful than evolution using only mutation, but that the difference was not particularly substantial. Mutation was shown to be slightly advantageous in certain situations where the population size was small. In general the authors could not find an ideal blend of crossover and mutation that would yield better results consistently. From the author's point of view this is a good thing -- it isn't necessary to tune the operator rates to different problems.

Given these observations, the author used a reasonably ``standard'' set of values for all tasks, making use of both operators, in which crossover produces about 75\% of the new population; mutation 20\%; the remainder obtained simply by copying. Making use of both operators is desirable, at least from a practical point of view, since each has its own specific advantages. Crossover helps to exchange useful building blocks between good parents, while mutation can help maintain diversity by re-introducing sub-trees that might otherwise fall out of the population.

% TODO: Graph of GP learning with 100% crossover, and 100% mutation - is there any significant difference?

\paragraph{Tournament Size}
Genetic Programming is distinguished from random search by its bias toward more successful individuals, which is achieved through the evaluation of individuals' performance (see Section \ref{fitness-function}) and subsequent selection of ``good'' individuals to produce next generation. The most widely used selection technique, tournament selection, picks $t$ individuals at random from the population to form a ``tournament'', from which the individual with the best fitness score is selected. Larger tournament sizes $t$ will increase the selective pressure, albeit at the expense of variability in the subsequent generation. Other selection methods were discussed, starting from page \pageref{selection}.

During their comprehensive analysis of a series of selection methods, Blickle and Thiele \cite{blickle95mathematical} concluded that Tournament Selection produced the smallest loss in diversity and the highest selection variance in comparison to Fitness-Proportional and Ranking selection. For this reason, and the reasons presented above, Tournament Selection was chosen as the \foreign{de facto} selection method in the author's Genetic Programming environment.

Motoki \cite{motoki2002} calculated that, given a population of size $N$, and tournament size $t$, the expected loss of diversity $D_T$ in tournament selection would be:

\[
D_{T}=\frac{1}{N}\sum_{k=1}^{N}\left(1-\frac{k^{t}-(k-1)^{t}}{N^{t}}\right)
^{N}\]
%t, D_T
%2, 0.4320084907775432
%3, 0.5040767165463467
%4, 0.5609853315004579
%5, 0.6056699380001629
%6, 0.6414158083907268
%7, 0.6706096031935803
%8, 0.6949075022501697
%9, 0.7154660366616032
%10, 0.7331081339211165
%11, 0.7484320883677308
%12, 0.7618821762885557
%13, 0.7737948652692138
%14, 0.7844295829781405
%15, 0.7939896134099429
%16, 0.8026365742968069
%17, 0.8105006418145717
%18, 0.8176879032260399
%19, 0.8242857334340232

\noindent Interestingly, this formula predicts that the loss of diversity initially grows rapidly but becomes relatively static in populations with more than 8 individuals. This means that we can select a value of $t$ which should not require specific tuning for each individual experiment, especially if using a fixed population size. When $t=20$, the formula predicts that around 82\% of the diversity of the population is lost in any given generation, which may significantly affect the ability of the evolutionary algorithm to explore the search space. At the lowest practical value, when $t=2$, the loss is about 43\% per generation. Low selection pressures are generally suggested in GP practice and successful results have been achieved using low values \cite{poli:2005:foga}. 

But how low should the selection pressure be? Although the Genetic Algorithm community has traditionally used a tournament size $t=2$ which preserves as much diversity as possible within the population while maintaining some degree of selective pressure, GP researchers generally use $t=7$ as this is thought to instill higher selective pressure on the population, tending to improve the learning rate during the limited time of a GP run\footnote{Genetic Algorithms are potentially faster to run than GP, so can be indulged in evaluating more generations.}. However, higher values of $t$ will cause the same parents to be selected more often, which reduces the variability within the population and increases the redundancy. An experiment measuring the population redundancy\footnote{Redundancy is measured by calculating the number of individuals that are duplicates of another member in the population.} is shown in Figure \ref{fig:population-redundancy-tournament-size}, which shows a substantial difference in population redundancy between $t=2$ selection and $t=7$ selection.

\begin{figure}
\begin{centering}
\includegraphics[width=0.9\textwidth]{images/population-redundancy-tournament-size}
\caption[Tournament Size and Population Redundancy]{The average redundancy of a population over the course of 50 generations, for different tournament sizes.}
\label{fig:population-redundancy-tournament-size}
\end{centering}
\end{figure}  

The author has conducted a number of comparative experiments using the range of  tournament sizes described above, the result of which is that no significant difference could be detected in training accuracy, evolution time or average population size. Neither was it observed that the performance of runs with different tournament sizes was any more variable for different values of $t$. As it is difficult to decide exactly which is the best parameter, one of the author's classification schemes errs on the safe side by using different sizes for different runs, and in general SXGP uses the more obvious compromise: a tournament size of $t=5$.

\paragraph{Population Size}
\label{pop-size}
The computational expense of an evolutionary run is usually proportional to the product of two parameters which specify the breadth and length of the search: namely the population size and generation count. Populations are used by evolutionary learning algorithms to store a diverse base of knowledge that can be built upon. Although the degree of selectivity employed has a significant effect on the variability within a population, such variability can only be stored within a population of solutions of sufficient size. While there is clearly a lower bound for the population size, there is no practical upper bound, since the search space is potentially enormous.

An impression of the size of the search space can be gleaned through a brief example. If one imagines a GP system which uses $n$ functions each of arity (number of arguments taken by the function) $2$, and maximum tree depth $D$, whose individuals are generated by a FULL tree builder (see page \pageref{full-builder}), the search space, or number of potential programs is:

%\[
%size = n^{\left(\displaystyle\sum_{i=0}^{D-1}{2^i}\right)}
%\]

\[
size = T + \displaystyle\sum_{i=1}^{D-1}\left(F^{2^i}-1\right) \times T^{2^i}
\]


From the exponential nature of this calculation, it can be seen that modest increases in the number of functions or the tree depth will quickly yield spectacularly large search spaces. The addition of continuous random constants can increase the size of the search space to even more gigantic proportions, which in any case is such that the GP system will never be able to explore it comprehensively. Given that the population size can only ever be a tiny fraction of the size of the search space, its choice might be considered relatively arbitrary: it doesn't appear necessary to tune for individual problems. Many GP researchers settle on a population size of 500, although higher values are used in more modern research. Nonetheless, the use of the ramped-half-and-half tree builder (see page \pageref{ramped-half-and-half}) introduces a significant level of duplication into the population (for reasons explained later), which is alleviated in SXGP using fitness caching (see page \pageref{fitness-caching}).

Aside from problems of duplication, genetic populations have a tendency to become dominated by a particular solution, a phenomenon described as premature convergence. Various ``convergence manipulation'' protocols exist to avoid the homogenisation of a population, including island selection, discussed on page \pageref{island-selection}, but each introduces extra parameters to the system. Murphy and Ryan \cite{hereditaryRepulsion} suggested the use of a different tournament selection algorithm which would repel individuals which shared a similar ancestry. The algorithm starts by selecting an individual at random\footnote{This is the protocol by Murphy and Ryan\cite{hereditaryRepulsion}, in SXGP it starts by selecting an individual using tournament selection as normal, which seems to be rather more sensible.}, then searching for an appropriate partner to participate in crossover in a ``repulsion tournament''\footnote{This author feels the chosen term for this technique, ``hereditary repulsion'', is something of a missed opportunity; ``incest police'' is rather more enjoyable terminology.}. The partner chosen is the one with the fewest shared ancestors with the first individual. Thus the crossover operator is forced to continue exploring previously uncharted areas of the search space, while ensuring the population maintains a higher degree of diversity. Hereditary repulsion was implemented on the author's toolkit; comparative results are shown in Figure \ref{fig:hereditary-repulsion}, which shows that the technique can both decrease and increase the average error. 

\begin{figure}
\begin{centering}
\includegraphics[width=0.9\textwidth]{images/hereditary-repulsion}
\caption[Hereditary Repulsion]{The effect of Murphy and Ryan's Hereditary Repulsion technique on average classifier accuracy.} 
\label{fig:hereditary-repulsion}
\end{centering}
\end{figure}  

% TODO: Need Results for hereditary repulsion.

% We now turn our attention to the choice of generations, which determine how many attempts at recombination and selection should be made. An understandable response would be to permit the GP program to learn for as long as possible, however this will not necessarily lead to the best possible classifier. While Genetic Programming offers a flexible approach to classification, in common with other non-parametric methods, it is also prone to overfitting on training data, which does not necessarily lead to a corresponding accuracy on test data. The 1-nearest-neighbour method, for instance, will always achieve 100\% on training data, but will not always perform so well on test data. Indeed, the number of generations to run for should perhaps be rephrased as ``how long to allow before genetic programming should be stopped''. Again, a relatively straightforward solution is to compare the performance of the classifier on both training and testing data, and stop the evolutionary process when improvements in training fitness no longer translate into improvements in test fitness\footnote{Although this may be considered something of a grey-area, the author does not consider this to be equivalent to training on the test data itself, As the algorithm is looking simply for the relative differences in fitness between runs, without reference to absolute fitness. Training on test data would compromise any assessment of a classifers generalisation ability.}

\subsection{Tree Builder Parameter Choices}
As we saw in Chapter \ref{ch:gpsurvey}, there are two means of producing trees in Genetic Programming, the \emph{FULL} builder, which generates ``full'' trees, in which every branch extends to the maximum depth $D$, and the \emph{GROW} builder, which extends branches until the point where a leaf node terminates it. Because the \emph{FULL} builder limits the number of tree structures that can be used, and the \emph{GROW} builder will not always produce trees of the full size, most GP practitioners use the ramped-half-and-half  algorithm to generate the population, which uses each technique half the time, usually for each of a range of depths ${1,2,...,D}$. The author identifies two problems with this technique, which are dealt with in this section.

The first problem relates to redundancy, or the presence of identical individuals within a population. Redundancy reduces the variability within the population, which may affect the rate of learning, and prevents the search space from being explored as thoroughly as possible.

Here is a simple calculation. Suppose the \emph{FULL} tree builder is called upon to construct a tree of depth $D$, using $F$ different function nodes and $T$ different terminal nodes. We can calculate how many leaves (terminals) the tree will use easily (assuming that each node has arity 2):

\[
terminals = 2^D
\]

\noindent The total number of non-leaf (function) nodes in a binary tree will be:

\[
functions = \displaystyle\sum_{d=0}^{D-1} 2^d
\]

\noindent The number of ``parent'' functions at depth $D-1$, who each have two terminals as children:

\[
parentfunctions = 2^{D-1}
\]

\noindent The number of unique combinations for a function with two \emph{function} nodes as children is\footnote{It is assumed that the arguments to each function are commutative, so certain combinations can be removed}:

% Total combinations - non unique ones.
\[
c_f = F^2 - \displaystyle\sum_{i=1}^{F-1} i
\]

\noindent And the number of unique combinations for a function with two \emph{terminal} nodes is:

\[
c_t = T^2 - \displaystyle\sum_{i=1}^{T-1} i
\] 

\noindent Thus, a simple estimate for the number of possible trees is:

\[
numtrees = F\left(\displaystyle\prod_{d=0}^{D-2}2^d c_f\right)\left(2^{D-1}c_t\right)
\]

\noindent Given a set of 6 features (as is the case for the BUPA dataset), and 4 functions, often used by GP programs, the number of possible trees is:

\begin{center}
\begin{tabular}{p{1.5cm}p{1.5cm}p{1.5cm}p{1.5cm}p{1.5cm}p{1.5cm}l}
D & 0 & 1 & 2 & 3 & 4 & 5 \\ \toprule
Trees & 4 & 84 & 1,680 & 67,200 & 5,376,000 & 860,160,000 \\ \bottomrule
\end{tabular}
\end{center}

\noindent Of interest is the relatively small number of trees for low values of $D$ which gives rise to a particular observation. The ramped-half-and-half technique makes an even allocation of depths, such that each depth is used $1/D$ times. To generate a population of size 500, with six depth levels, would mean that roughly 83 individuals are produced at each level. If we assume for a moment that all individuals are produced using the FULL builder, then based on the table above, it is clear that there are many more individuals allocated to depth 0 than are needed. Such a strategy would guarantee the initial population was at least 15.8\% redundant. In fact, the redundancy will often climb higher than this early on in evolution. The reader may be thinking that it is rather implausible that the minimum tree depth would ever be set to 0, creating individuals composed of just a single node -- but both ECJ and Lil-GP, another popular open source toolkit, do so; single terminals, in combination with DRS classifiers can be useful, not least when forming replacements for sub-trees during mutation.

The author's adaptation for the tree builder is to ensure that it does not allocate any more trees to a particular depth than are calculated by the above formula. ``Spare'' individuals are allocated to other depths. This helps to ensure that the population will be less redundant. The results comparing the ``standard'' tree builder, which allocates each depth the same number of individuals, and the author's ``weighted'' tree builder, which allocates depths more reasonably, are shown in Figure  \ref{fig:population-redundancy-treebuilder}. Results shown are the average over 25 runs on the BUPA classification problem and show the average population redundancy at each generation. They show a marked difference in population redundancy: the author's tree builder significantly reduces it. The reader may recall that the tree builder is used to generate the initial population and then to generate sub-trees for mutation. Although mutation is only used for 20\% of reproduction events, and not all mutation involves sub-tree mutation, the choice of tree builder nonetheless has a significant effect on the redundancy of the population. 

\begin{figure}
\begin{centering}
\includegraphics[width=0.9\textwidth]{images/population-redundancy-treebuilder}
\caption[Less Redundant Tree Builders]{A comparison between the author's weighted tree builder, and the standard tree builder. The authors builder yields populations with substantially less redundancy over the course of 50 generations.}
\label{fig:population-redundancy-treebuilder}
\end{centering}
\end{figure}  

%A second consideration relates to the \emph{GROW} builder, which does not insist upon building FULL trees. However, the deeper the tree, the less likely it becomes that a tree that extends all the way to the maximum depth $D$ can be built. Given a probability $p(t)$ of picking a terminal node, as opposed to a function node, the probability of a branch reaching D is:

%\[
%p(branch) = 1 - p(t) ^{D-1}
%\]

%\noindent The probability of the any branch in the tree reaching D is:

%\[
%p(tree) = \displaystyle \prod_{d=1}^D 1 - p(t) ^{d-1}
%\]

%\begin{figure}
%\begin{centering}
%\includegraphics[width=0.9\textwidth]{images/full-tree-probability-graph}
%\caption[Comparing ECJ Program Sizes]{The probability of developing a tree of depth $D$ for different terminal:function ratios}
%\label{fig:full-tree-probability-graph}
%\end{centering}
%\end{figure}  

%Figure \ref{fig:full-tree-probability-graph} shows the output of this function plotted for different values of the max depth $D$ and different values of $p(t)$. Although the probability of a single branch reaching depth $D$ will decrease as $D$ increases, so too does the number of possible branches, so the probability of the tree having at least one branch at depth $D$ approaches equilibrium for higher values of $D$, since the most important determinants of whether a tree can have branches at depth $D$ are the choices made nearest to the root of the tree. As is shown in the graph, the equilibrium point is chiefly determined by the value of $p(t)$. Later in this chapter, we shall study the classification of a variety of different datasets, which use between 4 and 36 features. Given a fixed number of functions, the choice of dataset will therefore affect $p(t)$. In turn, this will bias the tree builder in favour of producing smaller trees for certain datasets, which may increase the amount of redundancy, and cause the system to behave differently for different tasks.

%The author's second adaptation is to introduce a probabilistic selection method to the tree builder in order to ensure that $p(t)$ is constant for all datasets. This is similar to a technique implemented by Luke \cite{luke-tree-creation}, but here we are able to catch a glimpse of what appropriate parameter choices may be. Figure \ref{fig:full-tree-probability-graph} shows the consequences of different values of $p(t)$ A straight 50:50 split would only result in about 30\% of trees at $D=5$ to reach the maximum depth, which may result in more duplicates. Setting $p(t)$ to 0.3 means that trees reach the maximum depth over 60\% of the time, which may allow the system to explore the search space more thoroughly. This is the default parameter in the author's toolkit. It ensures that every dataset can be treated in a similar fashion, which makes comparisons more valid, and the system more applicable to different datasets. Further experiments have confirmed that this has no negative effect on the eventual accuracy on any of the datasets.

% Further experiments - from Terminal Probability.xls

\subsection{Performance Considerations}
The nature of many evolutionary learning systems is to produce a lot of solutions then throw the majority of them away. Although this process is key to learning by simulated natural selection, it is also inherently wasteful. As a stochastic process, it is usually wise to run the genetic learning system several times in order to estimate the true performance, which introduces further computational expense. Although the programs evolved can be very concise, the computational demands of GP learning, especially on computer vision problems, is always a concern -- and possibly one of the reasons members of the computer vision community do not often use GP! By contrast, techniques such as XCS \cite{Wilson1995a} aim to evolve and improve a single system through less blunt reinforcement and thus may converge upon a solution more quickly. The nature of the genetic operators themselves is also of concern. The process of crossover and mutation, which drive the search through the program space, can become more destructive than constructive.

Although GP will often be more processor intensive than other techniques, there are ways in which one can preserve the learning capabilities of GP while significantly reducing the time required to evaluate a given number of individuals. In this section we shall provide a  brief performance comparison between SXGP and ECJ, an established evolutionary computation system.

A common issue in GP which has significant impact on performance is the presence of useless code segments within individuals, known as ``code bloat'', that reduce the efficiency of the learning process. As the amount of useless code increases, so it becomes increasingly less likely that the GP operators will have a noticeable effect, since they end up swapping one unused code fragment for another. Left unchecked, the process of learning can effectively cease.

Various techniques are used to reduce bloat, including parsimony pressure and dynamic maximum tree depth \cite{silva:2003:gecco}, which penalise or remove large individuals respectively.  However, for a generic system, it is difficult to quantify what is ``large'', so an alternative solution was employed.  

Elitism, a commonly-used technique which copies the $n$ best individuals in the population directly into the next generation, is used instead. Studies have shown that evolution with elitism enabled yields smaller average population sizes \cite{Poli:2008:geccoe}. One can argue that individuals that are padded out with unused, and thus expendable, pieces of code are more likely to survive the processes of crossover and mutation intact: so there is a selective pressure which encourages the proliferation of code bloat. The direct copying into the next generation removes some of this selective pressure that encourages individuals to protect themselves with unused code.

%However, the tendency to embellish programs with useless code reduces the efficiency of the evolutionary process,  In the author's experience, limiting the size of programs will often increase the rate of learning. 

SXGP's tournament selection mechanism will also choose smaller individuals in the case that two equally-fit programs are competing for the same tournament. This is a form of multi-objective optimisation analagous to lexicographic ordering, described in Chapter \ref{ch:gpsurvey}. The tree checking and strong-er typing functions in SXGP also prevent bloat code from becoming prevalent. Since SXGP can automatically remove many forms of inactive code, additional trees that have a negative effect on the individual's ability are quickly eliminated. 

The combined effect of these additions is presented in Figure \ref{fig:ecj-program-size}, which compares the average size of best-of-run programs for both SXGP and ECJ following evolutionary runs of 50 generations. Although the \emph{max-tree-depth} parameter was set to the same value in both toolkits (all other parameters were similarly matched), ECJ tends to produce significantly larger individuals than does SXGP\footnote{In addition, the SXGP equivalent is generally slightly fitter.}, whose best-of-run programs are typically a third of the size of ECJ programs. Consequentially, evaluating 500 individuals over the course of 50 generations takes about three times longer in ECJ. 

% This is the average over 20 runs, from sxgp-vs-ecj.xls
\begin{figure}
\begin{centering}
\includegraphics[width=0.8\textwidth]{images/ecj-program-size-comparison}
\caption[Comparing ECJ Program Sizes]{Comparison between best-of-run program sizes (in terms of number of nodes) following 50 generations of evolution for SXGP and ECJ.}
\label{fig:ecj-program-size}
\end{centering}
\end{figure}

\subsection{Function Set}
\label{functionset}
Thus far we have not discussed in much detail the \emph{function set} to be used by defined for the GP system. The function set is a pool of nodes that the tree builder can use when generating problems. Functions, be they mathematical, logical or boolean in nature, are essential for combining terminals together in order to produce a one-dimensional output. It is typical for GP researchers to include their chosen function set in their published work, and indeed there are variations, although many restrict the function set quite tightly to purely mathematical operators. The author suggests that this limits the system to evolving linear operations. The most common non-linear function in use is the $IF()$ function (example on p \pageref{fig:if-node}), which in turn requires boolean operators such as ${{AND},{OR},{LESSTHAN},{MORETHAN}}$ to form its condition. 

One can embellish the function set with any number of additional functions, including trigonometric functions, statistical functions, and other non-linear operators. An interesting question is whether the use of such functions yield better individuals. An experiment was conducted to assess the average accuracy of individuals produced from two different function sets. The first ``limited'' set used only the four arithmetic operators ${+,-,\times,\div}$, and the $IF()$ and boolean operators mentioned above; the second ``extended'' dataset added a variety of additional operators, including trigonometric functions ${\sin,\cos,\tan}$, non-linear functions ${max,min}$ and  additional mathematical functions ${exp, ln, squared, cubed}$. GP classifiers were evolved using each function set 50 times apiece; the results are shown in Figure \ref{fig:function-set}.

% From function-set-2.xls
\begin{figure}
\begin{centering}
\includegraphics[width=0.8\textwidth]{images/function-set}
\caption[The Effect of Function Sets]{Average errors for individuals evolved by GP systems with ``limited'' and ``extended'' function sets.}
\label{fig:function-set}
\end{centering}
\end{figure}

The figure shows the average error for two different function sets. For the eleven datasets, the difference in error was insignificant on eight occasions, indicating once again that GP is able to select appropriate functions automatically in most situations. For the three datasets for which there was a significant difference (BUPA, Pima, WDBC) however, the extended dataset was found to perform worse on each occasion. In each case the fitness on training data was also affected, indicating that the additional functions do not hamper the classifier's ability to generalise, but rather the system's learning rate. On the basis of this experiment, it would appear that any advantage offered by these more complex operators is offset by an increase in the size of the search space. The author's generic system therefore makes use of the limited function set, which appears to yield better results in most situations.

\subsection{Terminal Set}
\label{terminalset}
The terminal set includes all the attributes within the feature vector that describes a particular object. In the case of the public datasets used throughout this chapter, the features are predefined, ranging in number from 4 -- 36. The generation of the features themselves from images is discussed in the following two chapters. In any case, feature vectors are provided to the GP system through a common dataset interface, which permits samples loaded from files or databases to be loaded, or those taken directly from images. Each feature is packaged up as a terminal node type, and becomess a member of the terminal set. 

In addition, the terminal set includes a number of so-called ephemeral random constants (ERCs), constants whose values are set at the time of tree-creation and subsequently remain fixed. These terminals give GP the opportunity to perform scaling, other arithmetic operations, or comparisons. To ensure that comparisons are meaningful, the constants are matched using the author's stronger-typing technique (see page \pageref{stronger-typing}): features which return, say, values between 0 and 1 are only compared with constants which return values within a similar range.

\section{The Evaluation of Fitness}
\label{fitness-function}

We shall move our discussion of parameters onto the evaluation of fitness (discussed in Chapter \ref{ch:gpsurvey}, page \pageref{fitness}), which merits its own section. The computation of fitness is the primary means by which the selection algorithms can differentiate between different programs, and is therefore very important.

%There are various aspects of performance that one may wish to take into account during the calculation of fitness, in order that each be maximised as far as possible. Examples include the efficiency of the individual, its ability to generalise, or its simplicity. It may also be the case that some of these requirements are based on context, or even change dynamically during the course of the evolutionary process.

%We covered a number of different fitness functions, ranging from the simplest (a percentage of the number of mistakes made by a program on a training set) to more complex ones which allocate different weights to different types of error. 

The appropriate fitness function to use in computer vision is often task dependent. For general classification tasks, it is usually the case that each error is equally costly, so a straightforward fitness function that measures simply the number of mistakes made by a given program on a training set can yield good results. It is sometimes the case that certain classes are more prevalent in training data than others, and therefore receive more attention than others. This is not necessarily a problem provided the training data is a true representation of the world. If not, one strategy is to calculate fitness per-class, and choose the average or indeed lowest fitness. The former gives each class an equal weighting and the latter encourages ``generalists''.

Binary detection tasks, by contrast, may be considered as multi-objective optimisation problems: ideal solutions must both be able to detect as many of the objects of interest as possible (be sensitive), and not detect erroneously other objects (be specific). In face detection, for instance, there are many more non-face objects than there are face objects, so it is beneficial to take the relative occurrence of each class into account in the fitness function. 

The two criteria can be aggregated into a single fitness function using some form of weighted sum. One example is that used by Roberts \& Howard \cite{roberts:1999:evdIRLI}, who incorporated two coefficients $\alpha$ and $\beta$ to weight the system's sensitivity to the different types of error:

\[
error_2=\frac{\alpha TP}{\alpha N_t+\beta FP}
\]

\noindent Where $TP$ is the number of correctly classified samples (true positives), $FP$ is the number of incorrectly classified samples (false positives), and $N_t$ is the number of ``true'' samples in the training set. Oddly, this formula calculates $\alpha{TP}/{N}$ as a percentage, but also adds $FP$ to the denominator, meaning that the effect of $\alpha$ relative to $\beta$ is dependent on the total number of ``false'' samples. It occurs to the author that the following calculation makes more sense:

\[
fitness_3 = \alpha\frac{{FN}}{{totalN}}+\beta\frac{{FP}}{{totalP}}
\]

\noindent Where $totalN$ is the total number of negative samples, and $totalP$ is the total number of positive samples. In $fitness_3$ the fitness is composed of two parts, the first relating to the total weight of false negatives and the second relating to the total weight of false positives. The relative importance of each kind of mistake is encoded using an appropriate $\alpha:\beta$ ratio. The allocation of weights, however, introduces additional parameters to the evolutionary system; often the approach is to try different combinations of each such that the classifier's performance can be plotted using an ROC curve. This is one means of finding solutions distributed along or nearby the Pareto front. 

From a more practical point of view, however, we are really interested in just a single solution to detect objects in images. The approach taken by researchers is usually to develop a rough detector, which is highly sensitive but yields quite a few false positives, whose output is then passed to a finer detector, which makes the final decision. During the course of this study, the author experimented with various other fitness approaches, admittedly not always with much degree of success. Some of which are briefly mentioned below.

%The author believes a proportional approach is more appropriate in order to make the fitness landscape as smooth as possible. Therefore, an approach in which each class is given equal weight appears to be a sensible suggestion.

%\[
%f=\sum_{c=1}^{c=C}\left(\frac{mistakes_c}{N_c}\right)
%{}^{N}\]

%For this reason some fitness functions have a degree of \emph{parsimony} pressure built in, which penalises larger individuals. However this introduces another parameter: how big is too big? As the answer to this question is hard to answer for a single problem, let alone multiple ones, we have avoided the use of parsimony pressure in our work.

%\subsection{Even Class Allocation}
%A consequence of evaluating performance entirely using a fitness value is that the GP system will become prone to falling into fitness minima. These minima can be most pronounced in situations where some classes are more prevalent than others. In these cases high fitness values do not necesarrily correspond to effective classifiers. For instance, faces account for only 2\% of the CBCL face training set \cite{cbcl}, reflecting that there are many more non faces in the world than faces. Nonetheless, the classifier could evolve a solution with accuracy exceeding 98\% simply by returning false for everything. One way to approach this problem is either to allocate the same number of samples to each class, or to weight each sample such that each class has the same total influence. 

% TODO: I need an even class allocation experiment to go here.

\subsection{Sample Weighting}
Having considered the relative importances of different kinds of mistake, and whether one may wish to weight samples collectively, it is also worth considering whether individual samples should be allocated different weights according to their \emph{individual} difficulty, since some samples will be easier to  classify than others. By weighting the samples that appear more difficult (that are misclassified most often), it may be possible to improve performance of the classifier, or at least ensure that the system does not become mired in local minima. 

A useful benchmark when considering this sort of approach is AdaBoost, by Freund and Shapire \cite{EvoVision:Freund-Shapire:1996}. Adaboost is a meta learning algorithm which develops classifier ensembles over the course of several learning sessions. The weights associated with different training data samples are adjusted to influence the learning system to solve more difficult training data. Weights are adjusted only following the complete learning of one classifier, which makes it quite slow to generate accurate classifier ensembles.

The author investigated a technique whereby the weights of different samples could be adjusted \emph{during} a single evolutionary run. As usual, the fitness of any individual is calculated by adding the weights of all incorrectly classified samples. After each generation, the weights of each sample is adjusted, such that unsolved samples increase their weight while solved samples have their weight reduced in proportion to how well the classifier solved the sample set as a whole. By implementing a dynamic fitness function, it is hypothesised that the individual would be less susceptible to becoming stuck in local minima. However, experiments revealed that this approach did not yield an improved rate of learning; classifiers were typically less accurate than those developed using a standard fitness function.

%This process is repeated $T$ times or until a further useful classifier cannot be found. After training is complete, a strong classifier is constructed from the set of weak classifiers using their associated error values which give some indication of the confidence in the classifier. Every time a weak classifier returns a label, a value associated with that label is incremented by the confidence factor, with the label with the highest overall confidence level being returned.

%The author considered a different method, by which the difficulty of each item of training data be assessed at the end of every generation with its weight adjusted accordingly. Regretfully this strategy failed miserably.

\subsection{Encouraging Generalisation Ability}
The fitness functions mentioned thus far have concentrated on the classifier's error on a given training set. However, a common problem in non-parametric classification is over-fitting, where a classifier learns the behaviour of a specific set of data set so well that its ability to work on novel data is compromised. It is desirable, therefore, to evolve classifiers that can learn to \emph{generalise}. As has been observed elsewhere in this thesis (see page \pageref{entropy-drs}), different techniques may produce a lower fitness score on training data but nonetheless outperform the fitter classifier on test data. Given a set of individuals evolved by a learning function, choosing the best of them according to training data error alone is therefore somewhat insufficient. 

The usual solution is to reserve a portion of the training set for the purpose of validating the classifier; the performance on the validation set gives a better indication of the classifier's ability to generalise. Of course, once the validation set has been used for this purpose it is no longer an unbiased estimator of performance, so a completely unseen test set is also employed to make the final assessment of a classifier's capability.

\paragraph{Training Set Splitting}
Of course, the use of a validation set takes away a proportion of samples from the training set that would otherwise be used for training, which itself may have an effect on the generalisation ability of the classifier. 

The author devised an alternative method, intended to gain information about the classifier's generalisation ability without sacrificing any data, and without resorting to computationally costly methods such as cross-validation or jack-knifing.

The technique involved splitting the training data into two sets, which are evaluated separately. The classifier was evaluated on each set, with the sum of errors yielding the training fitness as before. To this error, the \emph{difference} between errors on the two sets is also added, thus imposing a fitness pressure toward \emph{consistency}. However, it was not possible to detect a significant improvement; indeed this algorithm sometimes worsened the performance of the classifier both on training and test datasets, perhaps reflecting that the two sub-datasets could not be assumed to be directly comparable. This experiment reveals once more the perils of tinkering with fitness functions!

\paragraph{The Validation Dataset}
Discarding the author's penchant for experimentation for one moment, the conventional way to use validation sets is to leave them untouched until the evolution process has completed, then to use them as estimators of the classifier's performance on unseen data. This allows the generalisation capability of the classifier to be assessed without affecting the delicate fitness function. As GP evolution sessions typically involve producing a number of individuals during the course of many runs\footnote{This is done to avoid the effects of initial populations. The GP environment should always converge on an equally fit solution given enough time, but undertaking multiple runs is the most reliable way to ensure that a particular result is representative.}, their performance on validation data, as opposed to their training fitness, can be used to select the most promising individual. A similar process can be used when trying out classifiers produced by classifier fusion.

One significant advantage of using validation data in this way is that the GP evolution time is shortened, since the training set is reduced in size. The proportion of data to use for validation sets poses a dilemma: choosing too high a proportion may make the training set too small, while choosing too low a proportion may make the validation set unreliable. However, results from the author's experiments with validation results did not reveal any significant advantage of using validation sets.

%TODO: Results showing results from Experiment 31.

% Talking about margin maximisation?
%\paragraph{Margin Maximisation}

\section{Comparisons}
Having discussed the GP toolkit in more detail, we now move onto some empirical comparisons, using a set of binary and multi-class benchmark datasets (summarised on page \pageref{datasets}).

\subsection{Dataset Interface}
Of the selection of eleven datasets used throughout this thesis, four include their own separate test set permitting validation on unseen data, which provides an indication of a given classifier's ability to generalise. The rest are validated using 10-fold cross validation, a standard technique for estimating performance on unseen data. Cross validation is usually performed by splitting the dataset into 10 sub-sets, from which one is chosen as a test set, with the rest used for training. The learning process is invoked for every test/training combination, so the overall training error can be averaged, and the test error estimated. The author's implementation of k-fold cross validation uses a \emph{stratified} selection policy to generate the folds, which ensures that the relative class distributions within each sub-set are kept as similar to that of the main set as possible. Some benchmarks, such as the Vehicle dataset, include pre-defined folds; this is also accommodated. The author's software interface permits each type of dataset to be presented to the classification system, whether it be one of the public training datasets, or a dataset generated from images.

\subsection{Comparing with ECJ}

%The dangers of making your own toolkit - crossover wasn't working on SXGP for months before I noticed it: 15% mutation was doing all the work. Also the DeepCopy code, that I'd used for years was hopelessly inefficient, and sped up the GP process no end. Finally saving the PCM for every evaluated individual, cached output or not, slowed down the learning process by about HALF!

Before going on to evaluate SXGP in a more general sense, it is necessary to compare it to a benchmark GP implementation. For this comparison, the popular ECJ toolkit \cite{ECJ} was chosen, which at time of writing was available in its 18th version. Like the author's own toolkit, ECJ is implemented in Java, so comparisons of performance are meaningful. ECJ's default implementation is, where appropriate, based on Koza's original specification, making it a suitable benchmark. Finally, and despite a rather complex architecture, ECJ is surprisingly efficient when it comes to evaluating programs -- so much so that this author had to expend some considerable time on optimising his own toolkit first!

In the experiments each toolkit was run on the same datasets. In order to make the comparison as meaningful as possible, most of the novel features in SXGP were deactivated such that the two toolkits could compete on an equal footing. As far as possible, equivalent problem definitions were coded using each toolkit, including identical  node functionality, identical parameters and an identical fitness-function. The representation in each case was a multi-class DRS classifier.

%\begin {table}[tp]
%\centering 
%\begin {tabular}{ rccll }
%\toprule
%Dataset 	& ECJ			& SXGP			& Better  		&	Significance \\ \toprule
%BUPA		& 0.394 $\pm$ 0.024	& 0.376 $\pm$ 0.026	& SXGP, 4.5\%		&	Very Significant \\ \midrule
%GLASS		& 0.429 $\pm$ 0.023	& 0.417 $\pm$ 0.031	& --			&	Not Significant \\ \midrule 
%HEART		& 0.241 $\pm$ 0.019	& 0.223 $\pm$ 0.018	& SXGP, 7.5\%		&	Very Significant \\ \midrule
%IONOSPHERE	& 0.120 $\pm$ 0.015	& 0.101 $\pm$ 0.014	& SXGP, 15.8\%		&	Extremely Significant \\ \midrule
%IRIS		& 0.109 $\pm$ 0.030	& 0.054 $\pm$ 0.013	& SXGP, 50.5\%		&	Extremely Significant \\ \midrule
%PENDIG		& 0.408 $\pm$ 0.032	& 0.405 $\pm$ 0.026	& --			&	Not Significant \\ \midrule
%PIMA		& 0.257 $\pm$ 0.008	& 0.247 $\pm$ 0.008	& SXGP, 3.9\%		&	Very Significant \\ \midrule
%SATIMAGE	& 0.245 $\pm$ 0.027	& 0.252 $\pm$ 0.023	& --			&	Not Significant \\ \midrule
%THYROID		& 0.029 $\pm$ 0.008	& 0.023 $\pm$ 0.003	& SXGP, 14.8\%		&	Very Significant \\ \midrule
%VEHICLE		& 0.394 $\pm$ 0.014	& 0.395 $\pm$ 0.017	& --			&	Not Significant \\ \midrule 
%WDBC		& 0.057 $\pm$ 0.008	& 0.041 $\pm$ 0.005	& SXGP, 50.5\%		&	Extremely Significant \\ \bottomrule
%\end {tabular}
%\caption[Comparing SXGP and ECJ Toolkits]{ Toolkit Comparison: SXGP Vs ECJ v18 on various datasets. Averages from 25 runs, $\pm$ value indicates the standard deviation}
%\label {toolkit-comparison-test-data} 
%\end {table}

\begin {table}[tp]
\centering 
\begin {tabular}{ rccll }
\toprule
Dataset 	& ECJ Accuracy		& SXGP Accuracy 		\\ \toprule
BUPA		& 60.6 $\pm$ 2.4	& \textbf{62.4} $\pm$ 2.6 	\\ \midrule
Glass		& 57.1 $\pm$ 2.3	& 58.3 $\pm$ 3.1 		\\ \midrule 
Heart		& 75.9 $\pm$ 1.9	& \textbf{77.7} $\pm$ 1.8 	\\ \midrule
Ionosphere	& 88.0 $\pm$ 1.5	& \textbf{89.9} $\pm$ 1.4 	\\ \midrule
Iris		& 89.1 $\pm$ 3.0	& \textbf{94.6} $\pm$ 1.3 	\\ \midrule
PenDigits	& 59.2 $\pm$ 3.2	& 59.5 $\pm$ 2.6 		\\ \midrule
Pima		& 74.3 $\pm$ 0.8	& \textbf{74.7} $\pm$ 0.8 	\\ \midrule
SatImage	& 75.5 $\pm$ 2.7	& 74.8 $\pm$ 2.3 		\\ \midrule
Thyroid		& 97.1 $\pm$ 0.8	& \textbf{97.7} $\pm$ 0.3 	\\ \midrule
Vehicle		& 60.6 $\pm$ 1.4	& 60.5 $\pm$1.7	 		\\ \midrule 
WDBC		& 94.3 $\pm$ 0.8	& \textbf{95.9} $\pm$ 0.5 	\\ \bottomrule
\end {tabular}
\caption[Comparing SXGP and ECJ Toolkits]{ Toolkit Comparison: Average accuracy of DRS2 classifiers developed by SXGP and ECJ v18 on various datasets. Averages from 25 runs, $\pm$ value indicates the standard deviation. \textbf{Bold} text indicates a statistically significant better result.}
\label {toolkit-comparison-test-data} 
\end {table}

%Independent samples t test- when each member of the sample has no particular relationship with a particular member in the other sample.

Twenty five classifiers were evolved by each toolkit over the course of 25 runs, each lasting for fifty generations. The average test fitness of these classifiers on a series of datasets is presented in Table \ref{toolkit-comparison-test-data}, and graphically in Figure \ref{fig:ecj-program-accuracy}. The difference between classifiers, and the results of an independent samples T-Test are also shown. The results show that SXGP is able to compete effectively with ECJ: SXGP produces the better classifiers on every occasion where the difference between classifiers' average fitness is significant.

\begin{figure}
\begin{centering}
\includegraphics[width=0.9\textwidth]{images/ecj-program-accuracy-comparison}
\caption[Comparing SXGP and ECJ on Public Datasets]{Comparison between best-of-run program test errors after 50 generations between SXGP and ECJ.}
\label{fig:ecj-program-accuracy}
\end{centering}
\end{figure}

It is interesting to question why ECJ's performance is not more equivalent with SXGP, given the similarity of the problem implementations and otherwise identical parameters. One answer may be found in the average program size of individuals evolved by ECJ and SXGP respectively, already presented in Figure \ref{fig:ecj-program-size}, which shows that ECJ produces substantially larger individuals most of the time. Since SXGP can achieve equivalent or better solutions with substantially smaller individuals, it is fair to say that the additional size is a result of bloat, as opposed to useful code. As well as reducing the efficiency of GP learning, bloat can prevent learning from taking place, by turning the GP system into an automatic means of swapping useless code fragments. 

These results suggest that the author's toolkit is comparable to a standard and widely used Genetic Programming toolkit, which has been under continuous development for the best part of a decade\footnote{This particular comparison is valid only for problems of this type, using GP: ECJ does support considerably more evolutionary learning paradigms than does SXGP.}. This experiment justifies the author's decision to use SXGP exclusively as the GP toolkit in this thesis.

\subsection{Comparing to Other GP Results}
In the second process of validation, the author's GP Toolkit was compared to published results obtained by other GP researchers in order to establish whether the author's ICS classifier is competitive with the state of the art in Genetic Programming in a more general sense. SXGP was put to work on certain public datasets, for which figures had already been published by other GP researchers. The results of the experiments are presented in Table \ref{compare-to-other-gp}.

\begin {table}[ht]
\centering 
\begin {tabular}{lcccccc}
\toprule
Data Set 	& SXGP(ICS) & Loveard\cite{EvoVision:Loveard-Ciesielski:2001} & Chien \cite{chien:2003} & Bot\cite{bot:2000:GPilct} & Muni\cite{muni:2004} & Folino \cite{folino2006} \\ \toprule
BUPA			& \textbf{71.3} $\pm$ 1.6	& 69.2 $\pm$ 1.6	& 						& 						& -		&  	\\ \midrule
Heart			& \textbf{84.8} $\pm$ 1.7	& 						& 						& 						& -		&	\\ \midrule
Glass			& \textbf{67.3} $\pm$ 2.0	& 						& 						& 64.1 $\pm$ 9.1	& -		&	\\ \midrule
Ionosphere	& \textbf{95.7} $\pm$ 0.8	& 						& 92.8 $\pm$ 2.3	& 90.2 $\pm$ 5.5	& -		&	\\ \midrule
Iris			& \textbf{98.7} $\pm$ 0.1	& 						& 95.3 $\pm$ 1.0	&						& \textbf{98.7} $\pm$ 0.0&	\\ \midrule
PenDigits	& \textbf{92.0} $\pm$ 2.3	& 						& 						& 						& -		& 83.1	\\ \midrule
Pima			& \textbf{76.5} $\pm$ 0.8	& 75.8 $\pm$ 0.8	& 						& 71.7 $\pm$ 5.0	& -		&	\\ \midrule
SatImage		& \textbf{87.8} $\pm$ 0.5	& 80.7 $\pm$ 1.3	& 						& 						& -		& 81.4	\\ \midrule
Thyroid		& \textbf{98.9} $\pm$ 0.3	& 97.6 $\pm$ 0.2	& 						& 						& -		&	\\ \midrule
Vehicle		& 73.0 $\pm$ 3.1				& 62.4 $\pm$ 2.9	& \textbf{75.3} $\pm$ 2.4				&			& 61.8 $\pm$ 0.1&	\\ \midrule
WDBC  		& 97.1 $\pm$ 0.1				& 96.4 $\pm$ 0.2	& -					&						& \textbf{97.2} $\pm$ 0.0&	\\ \midrule
\end {tabular}
\caption [Comparisons to Other Published GP Results]{Results compared to those published by other GP researchers. Results in \textbf{bold} are the most accurate.}
\label {compare-to-other-gp} 
\end {table}

%TODO: Add these results too:
%``Genetic Programming for Data Classification: Partitioning the Search Space''
%Eggermont, Kok, Kosters
%PIMA: 75.8 +- 0.8
%Heart: 84.4
%Ionosphere: 92.9
%IRIS: 98.0

The results in Table \ref{compare-to-other-gp} show that the author's Genetic Programming toolkit consistently produces classifiers that are competitive with other published results, although as usual there is no single best technique for every dataset. The author's work is based most closely upon the work by Loveard and Ciesielski \cite{EvoVision:Loveard-Ciesielski:2001}; it can be seen that the author's toolkit delivers significantly improved results over those published by Loveard.

\subsection{Comparing to Other Classification Techniques}

In this final comparison, the author's toolkit is compared to other techniques from \emph{outside} the Genetic Programming community in order to establish the extent to which evolved classifiers are competitive with the results of human-written learning algorithms. The comparisons are performed once again using publicly available datasets. This has already been done in the past: a previous study by Lim \cite{Lim97anempirical} compared 33 different classification algorithms on a series of public datasets. Equivalent results using Genetic Programming were later added \cite{EvoVision:Loveard-Ciesielski:2001}. With the algorithms compared in rank order, one particular GP representation (DRS, discussed in Chapter \ref{ch:gp-classification}) was found to be reasonably competitive with the 33 other techniques at solving binary problems (ranking as high as fourth), but in general the GP programs' rankings were mediocre.

The study by Lim was dominated by a number of decision tree algorithms; the results here also include comparisons to other, more recent classifiers. The algorithms compared here include Support Vector Machines (SVM), Multi layer Perceptron Neural Networks (MLP), the C4.5 Decision Tree Algorithm, and various implementations of k-Nearest-Neighbour algorithm (k-NN). The best results found by the author for each dataset, which come from a variety of different sources, are presented in Table \ref{classification-comparison}.

\begin {table}[ht]
\centering 
\begin {tabular*}{0.6\textwidth}{ lcccccc }
\toprule
Data Set 	& SXGP(ICS) 	& SVM	& MLP	& C4.5	& k-NN	\\ \toprule
BUPA 		& 71.3 	& 76.1	& 73.1	& 68.1	& 64.9	\\ \midrule
Heart 		& 84.8 	& 87.4	& 82.0	& 78.9	& 83.8	\\ \midrule
Glass 		& 67.3 	& 68.6	& 75.2	& 68.2	& 72.0	\\ \midrule
Ionosphere	& 95.7 	& 93.2	& 96.0	& 94.9	& 98.7	\\ \midrule
Iris 		& 98.7 	& 98.0	& 96.0	& 95.3	& 95.7	\\ \midrule
PenDigits	& 92.0 	& 97.5	& 93.4	& 96.6	& -	\\ \midrule
Pima		& 76.5 	& 77.2	& 76.4	& 73.0	& 76.7	\\ \midrule
SatImage	& 87.8 	& 88.4	& 91.0	& 86.3	& 90.9	\\ \midrule
Thyroid		& 98.9 	& 96.1	& 99.3	& 92.6	& 97.9	\\ \midrule
Vehicle		& 73.0 	& 79.0	& 79.3	& 73.4	& 72.8	\\ \midrule
WDBC		& 97.1 	& 97.2	& 96.7	& 94.7	& 97.1	\\ \toprule
Average		& 85.7	& 87.1	& 87.1	& 83.8	& 85.5	\\ \midrule
\end {tabular*}
\caption { SXGP versus Other Techniques on 11 Public Datasets.}
\label {classification-comparison} 
\end {table}

% Direct discussion of results
As well as confirming the phenomenon that there is no such thing as a \emph{best} classifier that consistently outperforms other algorithms, the results show that SXGP is competitive with a range of other techniques from outside the realm of evolutionary computation on a series of different problems. It should be noted that the same GP implementation with identical parameters was used to derive all of the SXGP results.

% Need for better features
The Vehicle dataset, in which silhouettes of four different vehicle types must be established, is difficult to solve. This is not to say that the problem itself is intractable -- our brains can differentiate all kinds of silhouettes accurately. Rather, it is the limitations in the attributes chosen to describe each silhouette that make the problem difficult since a certain amount of important information is lost. Many of the UCI datasets were constructed from a finite set of measurements taken during the course of manual experimentation. However a computer can take literally thousands of measurements from a given image with  little effort, leaving one spoiled for choice. It is difficult to decide which attributes would aid accurate classification and which would be irrelevant. In fact, irrelevant attributes may actually decrease the performance of some classification algorithms, such as k-NN. Different feature sets which may facilitate classification will be investigated in Chapter \ref{ch:low-level}.

\section{A Discussion}
\label{lda}
Before moving onto the vision aspects of this thesis, the author shall complete this chapter with a short discussion of classification in general. 

The many classification algorithms can ordinarily be split into two groups: parametric and non-parametric. The parametric methods generally aim to identify a set of coefficients, one for each variable, that express a combination of features whose output $Y$ can predict a certain event or class. Techniques such as Fisher's Linear Discriminant \cite{fisher36} rotate the axes in order to find a linear subspace that separates the classes in a single dimension. Since $Y$ is considered a probability, its value can be combined with prior probabilities using Bayes' theorem to obtain an answer that takes into account the relative abundances of different classes. Although the discriminant methods are intuitive, like all statistical techniques they are reliant upon on a number of rigid assumptions, such as feature independence, normal distributions or homoscedasticity, which rarely hold true for real world data.

A more pressing problem is that this kind of approach cannot accurately model non-linear relationships in data. The so-called Generalised Linear Model \cite{generalisedlinearmodel} is an extension which permits models to work with non normally-distributed data distributions, particularly those with an exponential distribution, using some form of link function. Of these, Logistic Regression, which also places fewer assumptions on the data, is one of the most extensively used techniques for parametric classification.

The advantage of the \emph{non-parametric} methods is that they do not place arbitrary restrictions on data as they are not always based on statistical theory. They usually require more training data in order to produce accurate solutions and often take longer to train than do the simpler statistical methods. 

One popular family of non-parametric techniques are the recursive partitioning algorithms, or decision-tree algorithms, of which the most well known is probably Quinlan's C4.5 \cite{EvoVision:h:1993}. The objective of the decision tree algorithm is to recursively split the dataset into two or more increasingly homogenous subgroups in order to improve the classification of a target variable. Various techniques exist to choose the point at which the data is split, but the general idea is that the root node is split by the variable that best divides the samples and so on. 

Although decision tree algorithms generally exhibit good performance as classifiers, and have the advantage of easy interpretation, they also suffer from two drawbacks. The first, more theoretical, drawback is that generally the splits can only be performed orthogonally with respect to the features, so the regions in space cut out by decision tree algorithms are hyper-rectangles. The algorithm may perform badly if the decision planes are actually diagonal (or some other shape!). The second problem is that they are prone to over-fitting, which occurs naturally if the splitting process is permitted to continue unchecked, although post-processing ``pruning'' techniques are designed to alleviate this problem. 

The most significant advantage of the non-parametric techniques is that they can develop arbitrarily complex models and thus are able to outperform parametric statistical techniques, provided they do not over-fit the data. Parametric techniques, which are usually fast to execute, may be useful when deciding which variables are important and which are irrelevant. The author shall make use of this in experiments in the following chapters.

Another non-parametric technique, the k-Nearest-Neighbour algorithm, is an example of instance-based learning. Novel feature vectors are compared to a database of the training data each according to some distance function, usually the Mahalanobis distance (which has the advantage of scale invariance). The most common class among the $k$ nearest of its ``neighbours'' is chosen as the appropriate label. As such, the training procedure is trivial, although the classification stage, to which the computation is deferred, can be slow when using large datasets; memory usage can also be a problem. The choice of $k$ is also difficult to ascertain in a principled way, although in general small values where $k >1$ make the algorithm more robust, while the choice of $k=1$ is generally suitable only for very small datasets (< 100 samples).

Neural networks are also often employed in classification. While Rosenblatt's \cite{rosenblattperceptron} classic single-layer perceptron shares much in common with a basic linear regression approach, the neural networks generally used for classification are perceptrons with multiple-layers, which are capable of learning complex non-linear relationships between data, due to the usually non-linear activation functions working within each neuron.

A problem with neural networks in general is that the choice of network topology has a significant impact on the viability of the network after it has been trained. The hidden layer, if too small, may render the network incapable of suitable approximation; if too large the net also becomes prone to over-fitting.  Irrelevant features can be a danger for neural networks, as they may make the back propagation learning process significantly slower.

% SVM info, relation of SVM to neural networks: http://www.dtreg.com/svm.htm

A closely related approach to neural networks is Support Vector Machines (SVMs), another non-parametric, supervised learning technique. Like discriminant analysis, SVMs aim to locate some form of decision plane that divides clusters of data, but SVMs are non-linear and also aim to maximise the margin between the plane and the groups' outliers, so wherever possible, the plane that provides the largest gap between groups is chosen. This provably reduces the upper bound on the expected generalisation error.

A significant advantage of SVMs is that the number of features in the training data does not adversely affect the performance of the completed SVM classifier, since the number of support vectors selected by the algorithm to define the hyper plane, is usually small. On the other hand, SVMs are generally unable to classify more than two classes at once, which calls for some form of binary decomposition, and certain parameter choices can leave the SVM prone to over-fitting its model to training data.

Generally speaking, SVMs and neural networks tend to perform better when dealing with high dimensional spaces and continuous features. Categorical data is best dealt with by the decision tree algorithms. As more sophisticated algorithms, however, both require more parameters to be set  than do other techniques.

Apart from the decision trees, non-parametric methods generally manifest themselves as ``black boxes'' since it is difficult to understand how or why they reach a particular decision. This is a particular disadvantage in areas of business, such as credit scoring, or medicine, where people are uneasy leaving important decisions to an algorithm they don't understand, but is less of a concern when producing vision systems\footnote{We are accustomed to not understanding how the human vision system works!}.

Many of the algorithms, both parametric and non-parametric, are in some way dependent upon the initial random choices assigned to certain values, whether it be parametric coefficients or neuronal weightings. An advantage of the population approach to learning, employed by most evolutionary learning algorithms, is that the solutions cover a broader surface of the search space instead of a single point, so initial random choices are less of an issue. Of course, the population paradigm places an additional computational overhead so different runs may yet provide different performances if not run for long enough.

Although the results in this chapter show that Genetic Programming is competitive with state-of-the-art techniques on given problems, perhaps more so than have done previous GP researchers, the results also correspond with a long line of comparative studies which all state that there exists no ``magic bullet'' solution to problems involving classification. Furthermore, although this discussion draws attention to the pros and cons of each technique in an analytical sense, these issues do not necessarily manifest themselves in real world scenarios: A study \cite{domingos97optimality} found that the naive Bayes' classifier, despite its requirement for feature independence, could sometimes be superior to more sophisticated algorithms.

Nonetheless the most appropriate course of action is to select the classification technique which appears most appropriate for the task. Given the kind of vision tasks tackled within this thesis, there are certain techniques that can be ruled out. Linear discriminant analysis, for instance, generally requires that the classes have equal numbers of members, which is rarely the case in vision and certainly not in generic vision. k-NN places a similar requirement and like neural networks is regarded as sensitive to noise and irrelevant features, both of which may be present in images.

Evolutionary techniques are not often mentioned in discussions of classification. Unlike the above approaches, genetic techniques are particularly bound by any given representation: GAs can be used to determine neural network weights, or weights for discriminant functions in place of the least squares technique. GP can readily develop decision trees, and the concept of a margin can be built into a GP fitness function to offer advantages similar to SVMs. We've seen that the author's ICS classification technique makes use of different classification approaches dependent upon the task to be solved, which may be advantageous. In the following chapters we shall see how well equipped is Genetic Programming as a generic creator of vision systems.

% The above discussion replaces this one down here, which was a bit of a mess, and based too much on opinion, in my opinion :)
%The following is a brief discussion of the advantages and disadvantages of different classification approaches with reference to GP.

%\paragraph{SVMs}

%SVMs are a linear classifier
%Multiclass SVM - Binary Decomposition, either one versus all or one-versus-one

% Potential Accuracy of other classifiers
%Even if GP does learn to distinguish two clusters of data accurately, other techniques such as SVMs also aim to maximise the \emph{margin} between the decision plane and the members of each cluster in order to improve generalisation. Although the optimisation process of SVMs can also be computationally expensive, newer techniques have been shown to speed up the process markedly\footnote{The problem can be re-formed from a geometric perspective and converted into a problem involving reduced convex hulls, the upshot of which is the same solution can be discovered more quickly (Dimitriodis, 2008)}.

% Non linearity
% Again, mentions preconceptions
%One distinct flaw among other classification algorithms is their inability to manipulate features in a non-linear way. While one supplies the GP system with the same features as any other classification system, there is no encumbent need for GP to use them in their raw form. Perhaps the distinction between two classes is based on the difference between two of their features, rather than their absolute values. In this case GP should be able to find the solution (by dividing the two absolute values of the features and creating a new feature), but could other learning algorithms. In our quest to find generic vision systems, it seems prudent to choose a learning system that can continue to learn, even when the solution is beyond our preconceptions of the problem. Following the house-buying adage that one should always ``choose the worst house in the best neighbourhood rather than the best house in the worst neighbourhoor'', we choose not to use the best classifiers at this moment, but a classifier with the most potential for solving solutions in the future. Consequently a large part of this thesis investigates the ways in which GP can be made less parameter heavy, and how one can create good clasifier more effectively.

%\paragraph{Other Biologically Inspired Algorithms}

%It is the feature \emph{selection} capability of evolved techniques that motivates us to use Genetic Programming. The nature of artificial selection is to reward and experiment with useful code fragments, while discarding others. Therefore GP is quite good at automatically discarding those features that do not help with classification. In any case GP programs are not obligated to use each and every feature. We can, therefore, provide the learning system with a generous selection of imaging features in order to render it capable of solving a wider selection of problems. 

% Flexibility of GAs and NNs
%Genetic Algorithms and neural networks are not as flexible as GP: their representation is relatively fixed. A GA in its basic form aims to optimise a series of values; neural networks optimise a series of weights. The simplest adaptation of neural networks for image processing is to assign each input of the net to a pixel on the image and allow the net to learn some kind of useful relationship between different regions of the image. One may say the problem with this approach is that it needs to agglomerate a lot of separate (possibly redundant) information before arriving at any classification, which may render the net computationally too expensive. On a broader level the problem is that neural nets' fixed set of topologies make it hard to adapt them for generic problem solving.

%By contrast, a genetic program makes no assumptions about data, and implies fewer preconceptions about how problems may be solved in general. There is no reason why Genetic Programming may not devise completely different solutions for different problems, using completely different approaches. Anticipating the range problems to be faced later in this thesis, it seems a sensible technique to employ. Since GP is the only technique with the potential for creating classifiers that can be as varied as the problems themselves, this author believes that it is worthwhile to continue making inroads into classification by GP. 


%\section{Conclusion}

%\paragraph{Speed}
% Speed of GP - is it necessary to mention, especially when mentioned above.
%It is undeniable that learning software by GP is comparatively slow\footnote{Although if one considers that GP can develop, from scratch, a classifier competitive with some of the best human written classification techniques in a matter of minutes, then it is actually quite speedy!}. Although SVMs can also take some time to compute their solution, there exist tricks to improve their efficiency markedly. In GP, by contrast, the process of simulating natural selection, during which a significant number of individuals are evaluated then discarded, is inherently wasteful but largely unavoidable. Equally, the GP search operators are sometimes a blunt instrument by which to improve individuals incrementally.

%\paragraph{Feature Selection}
% Feature selection - but there is no feature selection in this Chapter - everything uses the same (small) set.

% GP Non Linearity
% More rubbish about preconceptions
%One distinct flaw among other classification algorithms is their inability to manipulate features in a non-linear way. While one supplies the GP system with the same features as any other classification system, there is no encumbent requirement for GP to use them in their raw form. Perhaps the distinction between two classes is based on the difference between two of their features, rather than their absolute values. In this case GP should be able to find the solution (by dividing the two absolute values of the features and creating a new feature), but could other learning algorithms. In our quest to find generic vision systems, it seems prudent to choose a learning system that can continue to learn, even when the solution is beyond our preconceptions of the problem. Following the house-buying adage that one should always ``choose the worst house in the best neighbourhood rather than the best house in the worst neighbourhoor'', we choose not to use the best classifiers at this moment, but a classifier with the most potential for solving solutions in the future. Consequently a large part of this thesis investigates the ways in which GP can be made less parameter heavy, and how one can create good clasifier more effectively.

% GP Makes no assumptions about the data
%TODO: Check this paragraph is accurate.
%\paragraph{Preconceptions}
%By contrast, a genetic program makes no assumptions about data, and implies fewer preconceptions about how problems may be solved in general. There is no reason why Genetic Programming may not devise completely different solutions for different problems, using completely different approaches. Anticipating the range problems to be faced later in this thesis, it seems a sensible technique to employ. Since GP is the only technique with the potential for creating classifiers that can be as varied as the problems themselves, this author believes that it is worthwhile to continue making inroads into classification by GP. 
