\chapter{Classification by Genetic Programming (DRAFT)}
\label{ch:gp-classification}

Many problems in computer vision, such as detection, recognition, and segmentation, involve the classification and recognition of patterns. Patterns are to be found in almost any collection of data, which in our case is acquired after taking certain measurements from an image. If the measurements are useful ones, then patterns in the data may reveal something about the content of the image. Before we discuss exactly what kind of measurements one might wish to take from a image, we first need to study the design of classifiers, which make decisions about given sets of data. These decisions are used by vision systems to identify or locate certain features or objects of interest within images. In this Chapter we shall look at the ways in which we can employ Genetic Programming to evolve classifiers, and then evaluate how well they work.

%TODO: Ref needed for the not successful part
One might ask: Since there already exists a plethora of techniques for classification, why use Genetic Programming at all? It is true that classification by Genetic Programming is usually not as successful as other techniques, which already include MLP neural nets, k-nearest-neighbour, and Baye's Classifier, to name but three. However, Genetic Programming certainly has the potential to equal any of these methods, even if modern computing power is not quite capable of doing so yet. Given enough time (and the right data and tool set), there is no reason why Genetic Programming could not develop a Bayesian classification system itself, or indeed any other classification technique. But why stop there? What is more interesting is whether there exists a better technique than any of these, that simply hasn't been considered yet - only Genetic Programming has the potential to find such a technique out automatically. 

%TODO: Check this paragraph is accurate.
One must also remember that many human-written techniques were designed in certain conditions that impose  limitations on the classifier's applicability or assumptions regarding properties of the input data. These assumptions may not cause problems in many situations, but it is the case that k-nearest neighbour and neural nets can be confused by large values and that Baye's classifier is dependent upon several assumptions about the world that may not hold true. Thus none of the other classification techniques constitutes a "magic-bullet" solution, which consistently outperforms all others for all problems. Sometimes one approach is better, sometimes less so; classification techniques might be described as "horses for courses". 

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. 

Before continuing this discussion, we'll define a \emph{classifier} as:

\begin{quotation}
{}``A function that takes an $n$ dimensional feature vector as input, and describes it using a 1 dimensional class label.''
\end{quotation}

So, given the numerous ways in which software can be developed to satisy this definition, how do you evolve a classifier using Genetic Programming? The flexible nature of GP naturally permits classifiers to be developed in a number of different ways. In each case, the GP system is used to learn the relationship between a set of inputs and expected output(s). Programs are usually learned using a set of training or teaching data consisting of a number of instances for which the correct output has already been established.

Unlike other learning algorithms such as MLP Neural Nets (whose outputs map to specific classes almost by definition), it is necessary to embellish our genetic programs with certain additions to make them more suited to solving classification problems. While some of these additions may be seen as adding preconceptions or assumptions of their own, their main purpose is simply to interpret the logic within the Genetic Program. 

Classification problems solved by genetic programming therefore present two separate sub-problems: the search for a function which distinguishes members of a particular class from the rest of the data, and the search for an algorithm which can correctly interpret the function's output.

We shall first consider a basic, {}``vanilla'' genetic program which takes a number of inputs $X=\left\{ x_{0},x_{1},\ldots,x_{n}\right\} $, processes them in some way then returns a single, one-dimensional numeric output:

\[
output=f\left(X\right)\]

A threshold is all that is needed to render such a function capable of making binary decisions for some data that may belong to one of two classes.  Placing the threshold at 0 is a tidy choice: all negative outputs attributed to one class, and all zero-valued or positive outputs attributed to the other, so the number space is equally divided. Over the course of the evolution, programs become better and better at producing output that straddles the zero origin. 

% TODO: Include some references {[}references].

Although binary problems are often sufficient for detection phases, many other problems in vision require the recognition of more than two classes. Situations involving shape, gesture, digit, vehicle or face recognition each require various different classes to be discriminated from eachother. By definition these problems require more than one threshold, yet there is no longer a set of thresholds that divides the number space equally.

Of course, all multi-class problems can be decomposed into a series of binary problems (to be discussed later in this Chapter), but this approach actually suffers from limitations even in the binary situation (for the same reason that Genetic Programming was chosen as the authors preferred classification technique). A single threshold contains an inherent assumption that two classes within the data can be inhabit clusters that can be distinguished by a single plane. In fact, it may well be that the members within one arbitrarily defined class actually belong to two or more distinct clusters, in which case the classifier would fail. Therefore this technique may well not be flexible enough, even for binary problems.

\subsection{Binary Decomposition}
As has been already stated, a straightforward reaction to multi-class classification is to split the problem into a series of component binary classification tasks, breaking it into smaller, possibly simpler pieces (See \cite{spivak:2002:DOCRAGP} for an example using GP). A solution is evolved for each class, with the solutions chained together to solve the whole problem. 

%TODO: How did Spivak do it?

As each class requires a solution be evolved separately the total evolution time may be longer. The final solution may be less efficient since the problem of bloat in GP may be multiplied {[}reference]. Solutions have been proposed to reduce the effect of this disadvantage, such as running programs to discover the most commonly occuring classifiers first, but it remains an imperfect solution.

Smart and Zhang \cite{SmartZhang05} proposed communal binary decomposition in which a set of binary classifiers is evolved at the same time, allaying some of the speed problems of binary decomposition. They tested their system on  low-order multiclass problems consisting of four classes.

A key problem with binary decomposition is that each sub-solution must be as accurate as possible, otherwise mistakes such as False Positives will accumulate to a point at which accuracy is significantly affected.

\subsection{Modi Program Structure}

Zhang and Zhang \cite{YunZhang:04:ivcnz} proposed a different kind of GP program in which they dispensed with the $f\left(X\right)$representation in favour of a different, {}``modi'' tree type, in which any node may affect a vector of different outputs, each corresponding to a class. Each node in the tree is processed as usual, but if  bound to a particular class, it passes its value to the vector upon execution. The class with the highest value assigned to it after the tree is executed is determined to be the chosen class. 

% My interpretation of the theoretical reasoning behind this idea:
The modi approach permits a single tree to behave as if it were several separate trees, although the modi subtrees may not be independent from eachother. One advantage is that branches further down the tree may work as completely separate units, or building blocks, for a particular class, and thus may not be so disrupted by the genetic operators. The modi method was able to make modest improvements to the overall effectiveness of GP, increasing performance up to 11\% on a range of tests. 

\subsection{One Individual, multiple trees}

Muni et al. \cite{muni:2004} proposed a single individual incorporating one tree for every class. He used various other enhancements to Genetic Programming, such as applying genetic operators probabalistically based on the \emph{unfitness} of certain trees, with the aim of improving poor performers while protecting good solutions. Other post processing methods (OR-ing) and heuristic rules for conflict resolution were used to boost the classifiers effectiveness. His results were broadly competitive with a number of other machine learning methods on benchmark tests (IRIS, WBC, BUPA, Vehicle, RS-Data), which tend to be dominated by non-gp learning techniques.

%TODO: What were the results of his experiments - were they any better?

\subsection{Decision Tree Classifiers}
This intuitive method involves the creation of programs similar in semantic structure to a decision tree, a specific structure which consists of a number of nested conditional if-then-else statements (example, Figure \ref{fig:decision-tree})

\begin{figure}
\begin{centering}
\includegraphics[width=0.50\textwidth]{images/gp-example.eps}
\caption{An example of a decision tree classifier for distinguishing three shapes.}
\label{fig:decision-tree}
\end{centering}
\end{figure}

Bot and Langdon \cite{bot:2000:GPilct} used GP to evolve decision trees capable of solving a variety of different problems. Strongly typed GP was used to constrain the tree builder to produce trees with the correct syntax. They were able to use the system to solve some multiclass problems involving up to seven different classes, although
the GP was not always competitive with specialist decision tree learning algorithms such as ID3, CART, OC1 and C4.5.

%TODO: Mention POLI - MOST

\subsection{Range Selection}
An extension to the binary thresholding technique is range selection, in which a series of ranges are defined by pairs of thresholds, each range representing a certain class label.

The problem is how to set the thresholds that define the ranges (and which class labels to associate with each range). In its simplest form, the thresholds are set at an even spacing on the number line from some negative number to the same positive number, producing a series of ``slots'', each of which is assigned a class (see Fig. \ref{pcm}). A value from the GP program is matched against the relevant slot, whose classID is returned. The class labels may either be assigned before evolution begins (static range selection), or optimised in some way to {}``fit'' the output of individual programs (dynamic range selection). 

\begin{figure}
\begin{centering}
\includegraphics[width=0.33\textwidth]{images/pcm.eps}
\caption{A program classification map divides a number range into a series of slots, and associates a class with each slot. The class ID associated with each slot may be predefined (static range selection), or discovered at runtime per individual (dynamic range selection).}
\label{fig:pcm}
\end{centering}
\end{figure}

%TODO: Who invented DRS? - Need CITATION

The original \emph{dynamic} range selection method placed a few constraints on the output of the program. Firstly, they stated that the output should be rounded to the nearest integer, and constrained within the range from -250 to +250 to create 500 slots, each of which could be assigned to a class. Dynamic class allocation was performed by first calculating the appropriate slot membership for every item of training data. The most common training data classID from its ``members'' was then assigned as the slot's own classID.

%TODO: Who came up with this idea - was it Loveard and Ciesielski?

A similar solution solution aims to map the output of a program given a certain class onto a probability density function which can then be used to identify the classes (see Smart \& Zhang, 2005). While this has the advantage of providing a level of confidence estimation (provided the data is distributed in accordance with a similar density distribution), it may affect the processing speed, a recurrent issue in image processing.

In a paper comparing five common multiclass representations, Loveard and Ciesielski \cite{lovcie01} showed this method to be the best representation on a number of different benchmarks, when compared to other representations including decision trees, evidence accumulation, static range selection and binary decomposition. Dynamic Range Selection has been relatively widely used. Zhang \emph{et al.} \cite{zhang:2003:jasp} were able to use this strategy with some success on three different problems, although the largest multiclass problem studied consisted of only four classes. 

The process of determining class memberships for the map on a per-individual basis does impose additional processing and memory requirements. This second learning step may be thought of as the difference between genotype and phenotype in natural life: although the purpose of our genes is to build a body and a brain, the learning of language, or how to play chess, is not hardwired - it comes through practice during the individual's lifetime\footnote{This difference between genotype (the DNA of an individual) and the phenotype (its eventual behaviour) is not very often apparent in GP, which tends to concentrate on the former. The second step, of learning by experience, is often missed out - this may account for why GP programs do not always perform as well as other algorithms - it is equivalent to asking a newborn baby to start working on some complex problem.}. In any case, once initialised, the class mapping for a particular value can be extracted rapidly.

\section{Experiments with DRS}
The reasons above have compelled this author to use dynamic range selection for the purpose of generating GP classifiers. As a chosen technique, the author has therefore dedicated some time to analyse and improve this technique. This section covers enhancements to basic DRS, and presents supporting results.

\subsection{More Dynamic DRS}
Dynamic range selection removes the necessity for the individual to evolve both a discriminative function and a classifier. Since the fitness function is one dimensional, it is difficult to establish whether an individuals performance is hampered by its logic, or its inability to translate its decision onto the expected class boundaries. However, basic dynamic range selection still assigns slots within a specific range from -250 to +250. If the features generally have very large or very small values, the function may still need to incorporate a multiplier to ensure that values fall into the slot range. As well as dependency on such a multiplier in some circumstances, some slots in the range may not be used which may make decisions less accurate.

%TODO: Although mention multiobjective GP.

For these reasons the author implemented a variant on dynamic range selection, where the range itself is also dynamic, ranging from the lowest known output of the individual to the highest. The removal of arbitrary thresholds may increase the genericity of this approach, provided it can perform as well as the normal DRS method.  This enables all the available slots to play a part in the classification process, and saves the individual having to scale its output up or down to match the thresholds imposed by the range selection technique.

%TODO: Need experimental results from one more data set.
\begin {table}[tp]
\centering 
\begin {tabular}{ llccc }
\toprule %
Data Set 	& DRS Method	& $F_{training}$& $F_{testing}$	& Size		\\ \toprule
Sat Image	& Normal	& 0.273		& 0.320		& 23.5		\\
		& Updated	& 0.241		& 0.302		& 22.5		\\ \midrule
PENDIG		& Normal	& 0.399		& 0.455		& 21.5		\\
		& Updated	& 0.393		& 0.449		& 22.1		\\ \bottomrule
\end {tabular}
\caption { DRS Method Comparison }
\label { drs-comparison } 
\end {table}

%TODO: Standard deviation to indicate plus minus confidence?

Results of experiments with the two DRS techniques on two public data sets are displayed in Table\ref{drs-comparison}. Each result is the average over 15 runs, each of which lasted 20 minutes. The results appear to show that the updated DRS technique achieves lower fitness values, indicative of more accurate classifiers (ideal accuracy is awarded a fitness score of 0). The updated DRS technique also has slightly smaller program size, which may be explained by the individual not needing to scale to an arbitrary range.

%TODO: Mention Generalisation comparison.

Therefore, this would appear to be an enhancement to DRS. It offers the additional advantage of removing two parameters from the system, which makes it more suitable for our generic system where the number of parameters would ideally be as small as possible.

\subsection{Number of Slots}
A second factor to be studied is the number of slots used by the DRS map. Larger numbers of slots will tend to permit the range selection to better fit the training data and to place thresholds in more exact locations. Extremely large numbers of slots may result in only one unique instance fitting into each slot, at which point the DRS map would start to resemble $k=1$ k means clustering and may degrade the classifier's generalisation capabilities. Smaller numbers of slots may improve the generalisation capabilities of the classifier, although too few slots may not adequately divide the classes. It is necessary, therefore, to investigate what constitutes ``large'' and ``small'' numbers of slots, and how slot numbers affect the classifier's performance.

An experiment was devised to examine the differences between classifiers that utilise DRS classifiers with varying numbers of slots. Updated DRS was used as it guarantees that every slot has at least a chance of being used. The results of this experiment are presented in Fig. \ref{drs-slots}, in which the average fitness values are plotted against the DRS slot count. Each average is calculated from the result of 15 evolutionary runs on the SatImage data set. The Testing Performance Chart on the right appears more easy to interpret: the testing performance appears to worsen beyond 50 slots. This would appear logical - with so many slots the DRS classifier is not providing the GP system any incentive to generalise, hence the increasingly poor performance on the test data. If one disregards the questionably anomalous result at 80 slots (which has the best training performance but the worst test performance), it would appear that classifiers with fewer than 50 slots perform less well. For this particular dataset, therefore, it would appear that 50 slots provides a good balance between accuracy and maintaining generality. 

\begin{figure}
\begin{centering}
\includegraphics[width=0.75\textwidth]{images/drs-slot-experiments.eps}
\caption{Fitness results for classifiers evolved using 6 different DRS slot sizes. Results obtained on the SatImage data set.}
\label{fig:drs-slots}
\end{centering}
\end{figure}.

The number of slots is rather dependent on the data provided, of course. Although it is difficult to define the difficulty of a problem in simple terms, one measure of a problem's difficulty is the number of classes it requires classification on.The SatImage dataset consists of 6 classes so the DRS classifier assigns roughly 8 slots to each class, on average. Further experiments are required in order to see whether 50 slots remains the optimum number for a problem with fewer classes.

%TODO: How about getting data from the DRS about how many slots are being used by each class?
%TODO: Run the experiment again on a lower order (preferably binary) classification problem and see how it compares.

\subsection{Confidence Estimation}
\label{confidence}
GP programs usually produce ``hard'' classifications, where a feature vector is assigned a class label without any degree of confidence estimation. This works well for well defined problems where each class is completely distinct, but is not so helpful in other tasks where it may be more appropriate to output more than one potential candidate class for a given feature vector\footnote{For example optical character recognition, where certain characters look similar.}. 

%TODO: Mention GP with confidence estimation here

Interestingly, Dynamic Range Selection does have access to information useful for confidence estimation while the map is being built. When the DRS Map is built, the output of the GP function for each sample is calculated, and the relevant slot is identified. The slot's own counter for that sample's class is then incremented. Once all the samples have been processed, the slot chooses its own classID according to the class that appeared most often, in a winner-takes-all strategy. However, a confidence estimate can easily be computed according to the proportion of members from the winning class out of the total number of hits the slot received. This is the basis behind our second DRS variant.

\section{Classifier Fusion}
An individual classifier can be sensitive to the tuning of the training data or learning parameters or to certain defects or local minima in the training data. Another classifier may behave differently, even if trained on the same data. For this reason, \emph{multiple classifier systems} (MCS) have been developed which aim to produce results which are more robust than those of individual classifiers. There exist several approaches for combining classifiers. A couple of popular approaches are described briefly below.

\paragraph{Majority Vote}
Given three or more binary classifiers, each may reach an decision regarding a particular input vector. To arrive at a consensus one approach is to take a majority vote to be the overall classification. This is an appropriate classifier fusion technique for binary classifiers, or classifiers that do not give a confidence indication.

\paragraph{{}``Committee'' Voting}
Majority vote gives each classifier an equal vote. Therefore an odd number of classifiers (at least 3) is needed to reach a decision. If the classifiers can provide a confidence estimation, they can be combined in a {}``committee'' approach, where their outputs can be weighted to produce an average, consensus decision. 

It is important that sub classifiers are \emph{independent} from eachother, so that the fusion is meaningful. If each of the classifiers always agree, then the fusion is adding a computational burden without any improvement in accuracy. A simple way of ensuring sub classifiers are independent from oneanother is to train each on different sections of the training data.

\subsection{Experiments}
A couple of experiments were performed in order to assess the usefulness of different fusion techniques on GP evolved classifiers. The first experiment was designed to discover the relative performance and reliability of fusion techniques in comparison to single evolved classifiers. Classifiers for the 6 class StatLog problem were evolved in batches of three.  The training data was divided in a 3-fold cross validation style, so that each classifier would have the potential to be different. Each batch was then combined into a fused classifier which could operate in two modes, the first using majority vote, and the second using committee voting, based on the confidence estimates whose computation was discussed above (in Sect. \ref{confidence}). The fusion classifiers were then evaluated in exactly the same fashion as the evolved classifiers, so that the effect of different fusion techniques could be compared directly with the performance of the individual classifiers. 10 batches of classifiers were evolved, fused, and evaluated in this way. 

\begin{figure}
\begin{centering}
\includegraphics[width=0.75\textwidth]{images/fusion-chart.ps}
\caption{Fitness results for classifiers evolved by regular GP, then with three combined in Majority Vote and Committee Voting scenarios.}
\label{fig:fusion-results}
\end{centering}
\end{figure}.

Based on Training Data performance, the fusion techniques broadly outperformed the single classifiers. The Committee voting scheme outperformed its components on 21/20 occasions (70\%), and the Majority Voting Scheme outperfomed its components 27/30 times (90\%). The results of this first experiment are presented grahically in Fig. \ref{fusion-results}. Of interest is the comparison between the performance variations of the individual classifiers, which is quite substantial, and the fusion classifiers, which is much smaller. Based on these results, two conclusions can be drawn.
\begin{itemize}
 \item That these classifier fusion techniques may be used improve the reliability and consistency of results, given several classifiers, which may be a benefit for generic systems.
\item That Majority Voting appears to be a more effective classifier fusion technique in this case.
\end{itemize}

While Majority Voting outperformed Committe Voting on each case on this experiment, Langdon \cite{langdon:2001:groc} pointed out that\footnote{In fact Langdon used Genetic Programming to develop the fusion technique itself.}:

\begin{quotation}
{}``There is no single, best combination scheme nor any unequivocal
relationship between the accuracy of a multiple classifier system
and the individual constituent classifiers''

W. B. Langdon
\end{quotation}

Therefore one should always try both. Fortunately the author's software makes this easy to do, as the fusion techique can work in both ``modes''.

%\section {Novelty Detection by GP}
%As the classifiers evolved using Genetic Programming are not based on the balance of probabilities, each of these representations usually produces a ``hard'' classification without an indication of confidence. If the training set is complete and comprehensive then this may not be regarded as too much of a problem. However, what happens when a new object appears which is unlike anything in the training set? The classifier may well classify the object incorrectly: this is to be expected; but critically the classifier will not notice that the new object is outside of its usual experience. In essence it is incapable of detecting novelty. 

%Is novelty detection important? Like Donald Rumsfeld's ``unknown unknowns'', the world is full of information outside of our immediate knowledge. Therefore any advanced learning system -- and theoretically the CIA -- should not only be capable of making decisions, but also be able to judge its capability of making that decision, given its experience. This leads to a much more exciting state of affairs in artificial intelligence, where the learning system can begin to identify new training data required to expand its knowledge base. Certain problems in computer vision too, such as fault detection, specifically require the recognition of the unusual. As faults can concievably occur outside of predicted patterns, an automatic system which recognises only known faults cannot compare to or replace human inspection.

%The recognition of the unusual is relatively straightforward: it is proportional to the distance of a particular object from the ``norm''. The difficulty is in defining the distance and the norm. In this paper we present two different classifier representations using Genetic Programming which calculate the ``normal'' value of a data in an objectiver manner. We demonstrate its usefulness on two vision systems each comprising a classification and novelty detection component, both evolved using Genetic Programming.

\section{Classifier Evolution by Partial Solutions (PS)}
\label{sec:partial-solutions}

\subsection{Partial Solutions}
Inspired by the boosting of weak classifiers in \cite{EvoVision:Freund-Shapire:1996} and classifier systems in general, the author has developed a scheme in which GP programs are evolved as simple expressions which solve only part of the overall solution and are termed \emph{partial solutions}.

As useful partial solutions are identified (see below for details) they are added to a separate, `strong' classifier which exists outside of the GP system (see Fig. \ref{fig:partial-solutions}). The scheme continues to evolve partial solutions until the strong classifier is capable of a certain level of accuracy. 

\begin{figure}
  \begin{centering}
    \includegraphics[width=0.75\textwidth]{images/partial-solutions-diagram.eps}
  \caption[]{GP by Partial Solutions creates a strong classifier from a number of smaller solutions}
  \label{fig:partial-solutions}
  \end{centering}
\end{figure}

As each partial solution is not expected to solve the whole problem, the programs are small and so may be discovered and evolved quickly. Once a partial  solution is identified as being useful -- that is, it can solve part of the problem that has not already been solved -- it is saved in the strong classifier and the problem is redefined to include only the remaining  training data. This removes the need for already-solved data to be continuously re-evaluated, as is the case with standard GP, and also ensures that the `knowledge' of the partial solution is protected\footnote{The actions of genetic operators and the sampling effect inherent in tournament
selection may each cause useful subtrees to be destroyed or lost inadvertently in standard GP.}.

\subsection{Fitness Criteria}
Each partial solution is treated as a binary classifier with respect to a class $C$. $C$ is chosen by evaluating the partial solution with respect to each class $c$ in the problem and choosing the value of $c$ for which it has best fitness. 

The fitness with regard to a particular class $c$ is calculated by dividing the total number of correct
classifications $TP_c$ by the total number of training samples $N$
added to the number of missed classifications $FP_c$, as shown below:
\begin{equation}
  \label{eq:fitness}
  \mbox{fitness}_c = \frac{\alpha TP_c}{N + \beta FP_c}
\end{equation}
The factors $\alpha$ and $\beta$ allows the fitness
measure to be adjusted to affect the individuals' sensitivity or
specificity.

Fitness is used to drive the evolution. However, in order to decide whether a partial 
solution should be added to the strong classifier --- that is to
say that it is able to solve a new part of the overall solution --- four
criteria were devised:
\begin{enumerate}
\item \emph{Does the partial solution discriminate?}  If the solution
  returns only `true' or only `false' it is not capable of making decisions.  
  GP often evolves this kind of lazy solution in
  response to training data that are weighted in favour of one
  particular class. GP by partial solutions avoids this form of code bloat. 
\item \emph{Is the partial solution unique?}  If the classifier
  returns the same results for every instance as another partial
  solution that has already been chosen, then this classifier is
  usually discarded\footnote{Unless it is smaller or less dependent than the existing one, in which case the existing solution is replaced.}.
\item \emph{Does the partial solution return `true' for data that
  have not yet been solved?}  Each item of training data has a field
  indicating whether it has already been solved.  Each candidate partial
  solution has to identify at least one instance that has not yet been
  solved in order to be used.
\item \emph{Does the partial solution return `false' for data in other
    classes?}  If a classifier returns `true' for instances of one
  class, it should return `false' for all instances of other classes.
  However, it \emph{may} return `true' mistakenly for other classes provided
  that they have already been completely solved by other partial
  solutions. We describe this solution as being \emph{dependent} on the
  other classses.
\end{enumerate}

If the partial solution matches all these criteria, it is added to the strong classifier.
Several partial solutions may be discovered during the course of a single generation --
another feature which makes GP by partial solutions faster. 

A version of island selection is used with crossover only occuring between parents with the same value
of $C$ which are more likely to share some similarity.

The strong classifier produces classifications by evaluating each of
its partial solutions in turn (starting with the first added). If the partial solution
returns `true' for a given input vector, the class $C$ associated with the
partial solution is returned, otherwise the next partial solution is executed
and so forth.

\subsection{Experiments and Results}
\label{sec:results}
A series of experiments has been conducted to explore the practicality
and effectiveness of the approach outlined above, namely colour recognition, hand gesture
identification, and a standard image classification benchmark.  These
are deliberately rather different in nature and are discussed in the
following sub-sections.  
The authors' own GP engine, \emph{SXGP}, forms a common base for the different GP-based schemes discussed to ensure
that the comparisons are meaningful; the performance of the popular GP engine \emph{ECJ} \cite{ECJ} (using dynamic range selection) is also presented to aid comparison. Genetic Programming parameters are summarised in Table \ref{tab:parameters}. The table also highlights any differences between conventional GP and GP by partial solutions\footnote{In GP by partial solutions a larger population size is used to ensure each `island' has sufficient individuals. As each partial solution is intended to be smaller, the maximum tree size for each is reduced.}.

\begin{table}
\centering
\begin{tabular}{lll}
Parameter & Standard GP & Partial Solutions \\ \toprule
$P(\mbox{crossover})$ & 0.80 & Same \\ \midrule
$P(\mbox{mutation})$ & 0.15 & Same \\ \midrule
Selection Method & Tournament Selection ($t=2$) & Same \\ \midrule
Max Tree Size & 575 nodes & 100 \\ \midrule
Population Size & 500 & 1500 \\ \midrule
Time Limit & 600 seconds per run & Same\\ \bottomrule
\end{tabular}
\caption{Genetic Programming Parameters}
\label{tab:parameters}
\end{table}

\paragraph{Colour Recognition}
Problems of this type typically represent the first evolved stage of our
vision system. Here, we are concerned the recognition of seven different colours
(red, green, blue, black, silver, white, yellow), with sample pixels
taken from photographs of different vehicles.  Although the number of
classes involved is not large in absolute terms, it represents roughly
the upper limit of classes to which GP has been reported successfully
to date. 

The classification algorithms were provided with a feature set which
consisted of basic colour information about each sample pixel, such as its
red/green/blue components and corresponding hue/saturation/lightness.
Further features included data about the distribution of these
components in a $3\times3$ region around the central pixel, including
the mean, standard deviation and range.  Equivalent measures for the
entire image were also included for context.

A training set of 213 samples was created, and a further set of 10,470
samples was used to test the evolved solutions.  The training set and
test set are disjoint, consisting of pictures taken on different days
and in different weather conditions. The images
were all taken with a Nikon~D70 camera using the camera's automatic
white balance function.

\begin{table}
\centering
    \begin{tabular}{lrrr}
      Technique & Training \% & Testing \% & Time \\ \toprule
      \|SXGP| (PS) 	&  100.0 $\pm$ 0.0 & 96.9 $\pm$ 1.9 &  60 secs \\ \midrule
      \|SXGP| (DRS) &   80.4 $\pm$ 3.3 & 77.3 $\pm$ 3.5 &  603 secs \\ \midrule
      \|SXGP| (DT)  &   72.1 $\pm$ 9.7 & 70.2 $\pm$ 9.9 &  603 secs \\ \midrule
      \|ECJ| (DRS)  &   82.3 $\pm$ 7.5 & 78.4 $\pm$ 8.7 &  599 secs \\ \bottomrule		
\end{tabular}
\caption{Colour Recognition Performance}
\label{tab:colour-recognition}		
\end{table}

A comparison of the performances of different GP-based approaches is
given in \tabref{tab:colour-recognition}.  For each experiment we
present the performance of the best-evolved classifier from each
approach on training and test data, averaged over 10 runs. The $\pm$
marks indicate the standard deviation from the average.  The average evolution
time to evolve the individual is also given.  

Comparing the performances obtained using dynamic
range selection (DRS) and decision trees (DT), it is apparent that dynamic range selection yields rather
better results on average, and appears to do so more consistently. However,
when the same GP engine is used with the `partial solutions' (PS) approach, all
the training data are recognised and the performance on unseen test data increases to
$>95$\%. Although the evolution times cannot be directly compared -- as the non
partial solutions approaches never discover an optimal individual within the given time period --
it is clear that Genetic Programming by partial solutions is substantially faster, in this
case by an order of magnitude.

The average performances of \|ECJ| and \|SXGP| on this problem appear broadly similar 
although \|ECJ| is able to evaluate individuals more rapidly.  Both \|ECJ| and \|SXGP| are written in Java
and executed on the same platform, so this is a meaningful comparison. 

\paragraph{Hand Gestures}
This experiment represents the kind of problem tackled in the second
stage of our vision system. The experiment involved the recognition of ten different hand
gestures\footnote{Open-Palm, Fist, Thumbs-Up, Live-Long, Pinch, Closed-Palm,
Point1, Point2, Okay and Bang; more information is available on our website.} from images captured using a webcam. Although this kind of problem has been
tackled very effectively by researchers using other learning techniques \cite{starner98realtime}, it has not previously been investigated
using Genetic Programming.

In the feature extraction stage a program was evolved to segment the hand from the
background by colour (using a program similar to those evolved in the first experiment).
Some 22 generic features about the shape of each hand were computed and suppplied to the classifier, including metrics approximating the
circularity, number of corners, density etc. Using these features,
a classifier was evolved to recognise the different gestures.  Some 100
samples were used for training with a further 200 samples being used for
testing.

\begin{table}
\centering
    \begin{tabular}{lrrr}
      Technique & Training \% & Testing \% & Time \\ \toprule
      \|SXGP| (PS) 	&  100.0 $\pm$ 0.0 & 81.4 $\pm$ 2.7 &  28 secs 	\\ \midrule
      \|SXGP| (DRS) &   75.4 $\pm$ 7.9 & 67.2 $\pm$ 8.4 &  603 secs 	\\ \midrule
      \|SXGP| (DT)  &   55.6 $\pm$ 6.3 & 51.6 $\pm$ 7.0 &  603 secs 	\\ \midrule
      \|ECJ| (DRS)  &   86.1 $\pm$ 3.8 & 73.7 $\pm$ 6.2 &  599 secs \\ \midrule
      \|K-NN| $(k=1)$&	& 52.5 & 	\\ \bottomrule
\end{tabular}
\caption{Hand Gesture Performance}
\label{tab:gestures}
\end{table}

The relative performances are summarized in \tabref{tab:gestures}.
Here, results from a $K$-nearest neighbour (K-NN) classifier are also
included as a benchmark algorithm.  Again, the partial solution
approach is the most effective, and was evolved dramatically faster than the ones using conventional GP.
Interesting, the K-NN algorithm was unable to solve the problem
acceptably, perhaps indicating that the training data are difficult or noisy.

 The authors have also
tackled other shape classification and optical character recognition tasks
using the same framework.
The metrics which produced the feature set for this experiment are
suitably generic to solve a variety of tasks, although the results show that they are not
yet sufficient to develop highly accurate classifiers. 


\paragraph{The SatImage Classification Benchmark}
This experiment explores a benchmark in image classification, the
Statlog SatImage data set
\cite{Asuncion+Newman:2007}.  This database was
generated from Landsat Multi-Spectral Scanner image data; it consists
of the values of each pixel in a $3\times3$ neighbourhood across four
spectral bands, thus producing 36 features in total.  Using these
data, the central pixel is classified into one of six classes
pertaining to the kind of soil present.  There are 4,435 items of
training data and 2,000 samples of test data.  Performance figures are
summarized in \tabref{tab:statlog-ps}, here consisting of the best individual from 
each method after 10 runs.  Here, the partial solutions
approach was trained on a reduced sample of 250 examples;
consequently, it is again the fastest to evolve by a factor of about 10 yet
still offers a performance commensurate with the other techniques
reported on the Statlog website.

\begin{table}
\centering
    \begin{tabular}{lrrrr}
      Technique & Training \% & Testing \% & Time (ms) & Error \\ \toprule
      \|SXGP| (PS)   &    NA &  83.9 &     57 secs & 0.161 \\ \midrule
      \|SXGP| (DRS)  &  74.9 &  73.4 &    606 secs & 0.192 \\ \midrule
      \|SXGP| (DT)   &  63.7 &  63.3 &    601 secs & 0.196 \\ \midrule
      \|ECJ|  (DRS)  &  73.0 &  72.1 & 		599 secs & 0.279 \\ \midrule
      \|K-NN|        &  91.1 &  90.6 &          NA & 0.094 \\ \bottomrule
\end{tabular}
\caption{Statlog SatImage Results for Partial Solutions (PS) and other techniques}
\label{tab:statlog-ps}
\end{table}

\section{Intelligent use of GP Classifiers}
As individuals get better, it becomes more tricky to improve them without breaking something, particularly when the search operator has no idea of what parts of the tree are useful and which parts are underperforming. This is a feature of the so-called stability-plasticity dilemma, which was demonstrated empirically in \cite{banzhaf:gp-introduction}.  In essence, learning by GP becomes more difficult as evolution progresses.

This motivates our research into classifiers that work by splitting the problem into smaller, more easily solvable pieces. One method, classification by partial solutions offers a number of advantages, notably the order of magnitude speed improvement while maintaining good classification capabilities, compared with other pure GP classification techniques. The major disadvantage of partial solutions is its rigidity which prevents it from making incremental refinements after its initial, frenetic learning process and the potential for it to over-fit data. As each partial solution is selected, the data that it solves correctly is removed from the training data, so the system is incapable of replacing it with a later, better individual which may be able to solve more instances of the same kind data, and thus offer better generalisation capabilities. There is nothing to say that partial solutions can't find a small set of generic solutions, instead of a large set of over-fitted solutions, but there is an inherent randomness in the process.

This randomness causes us some unease in using partial solutions as our sole classifier. For this reason the author developed a more "careful" classification scheme where the sub-classifiers are arranged more carefully, such that the easiest parts of the problem are solved first. If some distinctions within the data can be made with relatively high accuracy, it makes sense to evaluate those first so that the classifier is less likely to make mistakes early on (that cannot later be corrected). This may help the classifier to generalise better such that performance on unseen problems is improved. 

Our second classification system aims to emulate the steps that a human would take in developing a system by GP. The first stage is to decompose the problem into a series of binary problems, which is trivial. The second is to establish which problems are harder than others and then learn them in order (starting with the easiest). This is is established by running another (non-evolved) learning algorithm on the data, such as k-nearest neighbour, and analysing its class confusion matrix on a subset of untrained data. As there is only one classifier per class, there is only one chance for a class to be returned. Therefore after the classifier has been evolved, instances of that particular class are removed from the training set, so the problem becomes easier as time goes on. Naturally the most accurate classifiers should be run first, hence the need to identify which problems are easiest to solve.

After all of the binary classifiers have been evolved, the system evaluates each one and generates a class confusion matrix, in order to find which kinds of classes are most easily confused (such as ``0'' and ``O'' in an OCR-like task), and initiates the evolution of ``refinements'', which help improve accuracy, either by reducing false positives or false negatives. Refinements are executed in order of their potential improvement to fitness. The refinement procedure continues until further GP runs fail to deliver any more improvements, at which point the system completes its task. The system is able to make use of multiple CPUs running on a network, so can either run separate learning stages simultaneously, or execute the same run on different CPUs with different random seeds to improve accuracy. 

This amounts to a one-click learning system. The user only needs to drag in data created in our training data GUI, select how many CPUs to use, choose and how much time it should take. The classification then proceeds in a completely automated fashion.

\subsection{Results}
\subsection{The SatImage Classification Benchmark}
This experiment explores a benchmark in image classification, the Statlog SatImage data set \cite{Asuncion+Newman:2007}.  This database was generated from Landsat Multi-Spectral Scanner image data; it consists of the values of each pixel in a $3\times3$ neighbourhood across four spectral bands, thus producing 36 features in total.  Using these data, the central pixel is classified into one of six classes pertaining to the kind of soil present.  There are 4,435 items of training data and 2,000 samples of test data.  Performance figures are summarized in \tabref{tab:statlog}, here consisting of the best individual from  each method after 10 runs.

\begin {table}[tp]
\centering 
\begin {tabular}{ lr }
Technique   & Error	\\ \toprule
K-NN        &  0.094 \\ \midrule
LVQ         &  0.105 \\ \midrule
GP          &  0.135 \\ \midrule
CART        &  0.138 \\ \midrule 
Baytree     &  0.147 \\ \bottomrule
\end {tabular}
\caption { Statlog SatImage Results }
\label { tab:statlog } 
\end {table}

\subsection{The PENDIG Data Set}

% More information about the set is here: http://archive.ics.uci.edu/ml/datasets/Pen-Based+Recognition+of+Handwritten+Digits
The pen digit data set consists of 10,992 instances of digits written by a variety of authors using a graphics tablet. The observant reader will have deduced the data set comprises 10 classes. 7,494 are used as training data and 3,498 are reserved for testing. Results of our GP classifier are presented in Table {tab:pendig}.

\begin {table}[tp]
\centering 
\begin {tabular}{ lr }
Technique	& Error	\\ \toprule
MLP		& 0.047	\\ \midrule
GP		& 0.071	\\ \midrule
Fuzzy GA	& 0.101 \\ \bottomrule
\end {tabular}
\caption { PENDIG Results }
\label { tab:pendig } 
\end {table}

\section{Conclusions}
This Chapter has described a number of approaches for performing classification using Genetic Programming, and justified our usage of one in particular, dynamic range selection (DRS). Although other schemes, developed by the author, can outperform DRS based on a one-to-one comparison, the author's enhancement of DRS to deliver confidence estimates makes it much more suitable to classifier fusion by committee voting. 

Two different, novel approaches have been proposed: the faster partial solutions method and the slower but possibly more accurat approach which uses an enhanced means of DRS in a pseudo-intelligent manner. Although the concept behind both of these methods is to break the problem down into smaller pieces (as humans do), they go about it in very different ways. Partial solutions is all about speed, and intelligent DRS is about acuracy and careful refinement. Direct comparisons between the two would not reveal any particularly suprising differences in this regard, in any case the better technique is based on your preference for speed or accuracy. Instead each can be thought of as occupying a different niche. Partial Solutions is a good approach for "rapid prototyping", to see whether a set of data can be solved using GP. Intelligent DRS produces the equivalent of a final product, where accuracy is of the most importance. 

Having added these methods to our classification toolkit, we now turn our attention to certain problems in computer vision, and how such classifiers may be employed to solve them. Over the next couple of Chapters, these problems will be outlined in detail, culminating in the design of our vision system for solving a variety of generic problems.

%\subsection{Implementation}
%\subsection{Results}