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

% Read this:http://nlp.stanford.edu/IR-book/html/htmledition/the-bias-variance-tradeoff-1.html

% The difficulty of making decisions
Computers are excellent at crunching numbers and can do so substantially faster than we can.  Accordingly they are also very good at taking measurements, for instance from images. After taking these measurements, however, the machine becomes rather less useful: commanding a computer to perform more subjective tasks, such as recognising patterns, is less straightforward. Of course we humans have no difficulty in recognising the patterns, shapes and objects in the world around us -- it is something that our human brains can perform astonishingly well. If challenged, most people would find it extremely difficult to objectify how or why certain things are so instantly understandable. It is so difficult, in fact, to describe why our brain works the way it does that a word was invented for it: ``intuition'', which in turn is difficult to define! Although intuition will probably remain a trait reserved for living organisms for some time to come, in this chapter we shall discuss how machines may learn to make subjective decisions based on objective information.

% What is classification?
Classification is the process by which a series of measurements may be transformed into a decision regarding the object from which the measurements were taken. Decision making in general, and classification in particular, is not a topic confined to computer vision. Technology now permits information to be collected and stored faster than ever before, so finding algorithms to make sense of the piles of data we've amassed has been of interest to data-miners and information theorists for some time. Many problems in computer vision too, such as detection, recognition and segmentation, may be dependent upon the classification or matching of patterns.  In later chapters we shall consider exactly how one might take useful measurements from an image, but here we shall confine ourselves to making decisions based on arbitrary sets of data. We shall study the ways in  which Genetic Programming can be employed to evolve classifiers and investigate means to make the process more accurate and generic.

We shall start by briefly considering the definition of a classifier. Almost any ``object'' can be expressed in terms of its measurable characteristics. If the object is an animal, for instance, we might describe it in terms of its pigmentation, number of legs, eyes or relative size. If we take  $n$ measurements from each animal, then each individual beast may be represented as a tuple $\{x_0, x_1, \dots, x_{n-1}\}$. A classifier may be defined as any function that takes such an n-dimensional feature vector as input and describes it using a one-dimensional class label. In general, classification is about discovering groups and patterns in data and the boundaries that define them.

As we will see in Chapter \ref{ch:gpcomparison}, there is a whole range of different classification algorithms, since satisfying the above definition of a classifier is an ill-defined problem. There are various parametric and non-parametric algorithms developed for the purposes of classification, where parametric methods are typically linear transformations and non-parametric methods generally permit non-linear processing. The latter group of techniques includes decision tree builders, neural networks and support vector machines (SVMs). Decision tree builders work by iteratively partitioning the feature space into progressively smaller, more uniform portions that can each be allocated a particular class. Trained neural networks are weighted in such a way that particular combinations of features will lead to certain output neurons. SVMs aim to identify the decision plane that best separates two classes. We shall discuss the pros and cons of each in the next chapter, but first we shall consider the various means by which Genetic Programming can be applied to classification.

\section{Representing Classifiers in GP}
Genetic Programming is an abstract means by which to go about automatic programming. As such its use does not imply any particular approach towards the task of classification any more than would a standard programming language. In general terms, the GP system is used to learn the relationship between a set of inputs and expected output(s). The reader will recall that we can insert the inputs via \emph{terminals} at the bottom of the GP tree; processing takes place further up with a final, usually numeric, output expressed from the root node. Unlike other learning algorithms, such as multi-layer perceptron neural networks, whose outputs map to specific classes almost by definition, it is necessary to embellish our genetic programs with certain operators or other additions to ensure the process yields suitable classifiers. While some of these additions may add preconceptions or assumptions of their own, the purpose is to interpret or translate the logic encoded within the genetic program into the all-important class label. There are various means by which GP can be used to develop classifiers, a few of which are summarised below.

\subsection{Evolving Decision Trees}
% Read http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html#3
Many school children will be familiar with classification in the form of dichotomous decision trees, which allow non-experts to identify particular species or types by answering a series of straightforward ``yes or no'' questions: a favourite in biology field trips. This sort of approach is one of the most intuitive means of making a classification, not least because it can actually be written down on paper! Accordingly there is a number of decision tree algorithms, which aim to develop classification keys automatically. Algorithms such as such as the C4.5 algorithm by Quinlan \cite{EvoVision:h:1993} (and previously ID3 \cite{id3} and CART \cite{cart}) have been used for classification for some time. The goal, to divide the feature space into a series of increasingly homogenous areas, is implemented by representing a hierarchy of decisions in a tree structure. As a non-parametric method, decision trees can develop arbitrarily complex models to fit data and thus can handle multi-class problems with relative ease.

%From: http://shs.westport.k12.ct.us/mjvl/biology/animalia/dichotomous_key.GIF
%\begin{figure}[h]
%\begin{centering}
%\includegraphics[width=0.50\textwidth]{images/dichotomous-key}
%\caption[A Dichotomous Key]{An example of a dichotomous key used to determine the phylum of a particular animal. Decision trees work on a similar basis.}
%\label{fig:dichotomous-key}
%\end{centering}
%\end{figure}

Since Genetic Programming is at heart a tree building and optimisation technique, it is also well suited for developing decision trees, albeit in a more \foreign{ad hoc} manner. Still, a little work must be undertaken first in order to render GP capable of producing such trees. The key function node is an $IF(\cdots)$ statement, which permits conditional logic. As we saw in Chapter \ref{ch:gpsurvey}, it is useful to implement strong typing to help ensure the conditions make semantic sense. It is also necessary to develop a new type of terminal node to act as a ``return'' function, returning the decision up to the top of the tree. An example of such a tree is displayed in Figure \ref{fig:decision-tree}. 

\begin{figure}
\begin{centering}
\includegraphics[width=0.65\textwidth]{images/gp-example}
\caption[An Example of a Decision Tree Classifier]{An Example of a Decision Tree Classifier for Distinguishing 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, using a method similar to that described above. They were able to use their system to solve some multi-class problems involving up to seven different classes. Bot and Langdon's evolved solutions were not always competitive with specialist decision tree algorithms. Why might this be? The principal problem here is the mixing of genotype and phenotype, of structure and behaviour: since the tree is responsible for both the logic and its translation into class outputs, there is a high degree of dependency between parts of the tree. For a branch to work properly, it must not only include the right logic but also terminate with the correct return class. Disruption to either aspect may cause the tree to stop functioning, so the crossover operator has even more scope for mischief! Because of this dependency, making incremental improvements without breaking existing functions becomes difficult. The author's classification system will be compared to Bot and Langdon's results in Chapter \ref{ch:gpcomparison}.

\subsection{$f(X)$ Representations}
An alternative approach is to have the GP process compute a value from some or all of the features, then interpret the meaning of the value afterward. Indeed, the learning process can be made more straightforward if the interpretation is performed by a separate algorithm, leaving Genetic Programming to learn only the discriminant function: the logic that underpins the eventual decision. The evolved function generally takes 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)
\]

As a minimum, the function set is composed of basic arithmetic operators. Many GP researchers leave it at that. Other operators, for instance logical operators, trigonometric functions or statistical methods can also be added to render GP capable of evolving more complex non-linear transformations.

The simplest interpretation of the output's meaning  is achieved using a threshold, which yields a binary classifier (see Figure \ref{fig:fx-representation}). Placing the threshold at 0 is a tidy choice: all negative outputs are attributed to one class and all zero-valued or positive outputs are attributed to the other; the number space is equally divided. Over the course of the evolution, the programs should become better and better at producing meaningful output that straddles the zero origin. A disadvantage of this approach is that it is limited to binary discrimination between exactly two classes. While binary classification is sufficient for certain tasks, such as detection algorithms, we shall see later in this thesis various examples of classification problems which involve more than two classes. By definition, these problems require more than one threshold; yet there is no longer a set of thresholds that divides the number space equally.

\begin{figure}
\begin{centering}
\includegraphics[width=0.75\textwidth]{images/fx-representation}
\caption[The $f(x)$ Classifier Representation]{The $f(x)$ Classifier Representation, producing a floating output which is translated by a threshold operator}
\label{fig:fx-representation}
\end{centering}
\end{figure}

The key problem with this technique, however, is that it doesn't fully disassociate the interpretation of a class from the logic. $f()$ still needs to ensure that its outputs fall around the zero-crossing in order to attain a reasonable fitness score. Although this kind of representation is quite restrictive, it is nonetheless often used in GP classification. 

\subsection{Binary Decomposition}
Having mentioned \emph{intuition} at the very start of this chapter, one may take inspiration from human approaches to problem solving. One natural, intuitive, strategy is to break up problems into smaller, more straightforward pieces. We've already seen how this is done using decision trees. If the training data are composed of examples from more than two classes, then it may be more reasonable to learn a solution for each class. The individual solutions can be chained together at the end to produce software that can work for all classes. If the representation is limited to binary decisions, then this is the only approach to generate multi-class classifiers.

There are two ways by which a multi-class problem can be decomposed into smaller pieces.  The first may be referred to as ``complete'', or ``one-vs-one'' binary decomposition in which a classifier is created to distinguish every class from each other class on an individual basis, breaking the problem down into small pieces. For an $n$ class problem the complexity is $O(n^2)$, which soon becomes a limitation: it may take substantially longer to evolve the solution and the classifier may take longer to execute. The second is by class (``one-vs-others''), where a classifier is evolved to distinguish each class from all others; an $n$ class problem therefore has complexity $O(n)$.

Binary decomposition is widely used in the pattern recognition community. It has also been used by GP researchers, such as Spivak \cite{spivak:2002:OCR} who used GP to develop solutions to a character recognition task. 

Since each class now requires a separate process of evolution, the total learning time may well be longer. 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 reported some success after testing their system on problems consisting of four classes (which is reasonably modest compared to some of the problems considered in later chapters). Regardless of the evolution time, however, the most important consideration is whether binary decomposition can yield more effective classifiers. The author shall present some empirical investigations into binary decomposition later in this chapter. For now, we shall continue looking at different classifier representations in GP.

\subsection{One Individual, Multiple Trees}
We have seen two techniques so far. In the first, decision trees, it is difficult to ensure that each branch of the tree's logic associates itself with the appropriate return class. This issue does not apply to the second approach, binary classification. The latter is, of course, limited to two-class problems unless one splits up the problem into pieces.

A compromise was suggested by Muni \emph{et al.} \cite{muni:2004}, who proposed the evolution of a single individual that incorporated several sub-trees, one allocated to each class. The process of binary decomposition could therefore be attempted during the course of a single GP run. In order to ensure that most attention was paid to the weakest parts, Muni suggested applying the Genetic Operators probabilistically based on the \emph{unfitness} of certain trees, aiming to improve 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. Muni's trees used a zero threshold to determine their response, so his representation was still limited by an incomplete separation of genotype and phenotype. Muni's results shall be compared with the author's in the next chapter. 

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

\subsection{Modi Program Structure}
Zhang and Zhang \cite{YunZhang:04:ivcnz} proposed a different (``modi'') program structure , 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 in winner-takes-all fashion. 

The modi approach permits a single tree to behave as though it were several separate trees, although the modi sub-trees may not be independent of each other. One advantage is that branches further down the tree can 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 over ``standard'' GP\footnote{The authors did not, however, define what ``standard'' GP was.}, increasing performance by up to 11\% on a small set of datasets. However, the effectiveness of each sub-tree is dependent on which class it chooses to contribute towards. As the number of classes increases, so too does the chance that the node will choose the wrong class! The modi approach again does not permit the logic and the translation to be truly disassociated.

\begin{figure}
\begin{centering}
\includegraphics[width=0.40\textwidth]{images/modi}
\caption[Modi Classifier Representation]{A Modi representation. Some nodes can affect an output vector from which the class is then chosen using a winner-takes-all strategy.}
\label{fig:modi}
\end{centering}
\end{figure}


%TODO: Mention POLI - MOST

\subsection{Range Selection}
\label{pcm}

Arguably none of the techniques so far have completely separated the individual's genotype from the phenotype, the logic from its interpretation. Loveard \cite{LovCie01} suggested interpretation using a program classification map (PCM), which divides the number range into a series of slots, each of which is assigned a particular class (see Figure \ref{fig:pcm}). The output from the individual is matched to the relevant slot and the slot's class is returned.

\begin{figure}[!ht]
\begin{centering}
\includegraphics[width=0.6\textwidth]{images/pcm}
\caption[A Program Classification Map]{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 run-time for each individual (dynamic range selection).}
\label{fig:pcm}
\end{centering}
\end{figure}

The class labels associated with each slot may be assigned class labels before evolution begins (\emph{Static Range Selection}), in which case each class is usually allocated an equal number of slots. This has the significant disadvantage that the classes are arbitrarily ordered and the ranges chosen may not suit the clustering of different classes. An improved technique is to choose the class ID for each slot \emph{at runtime} to fit with each individual, referred to by the authors as \emph{Dynamic Range Selection} (DRS). Classes are allocated as follows:

\label{drs-calculation}

\begin{enumerate}
\item For each slot $i$
\item Find the tuples of training data $M$ which, following processing by the GP program, are 	 allocated to slot $i$.
\item Among those tuples in $M$, select the most common class label and set this as the class label of slot $i$.
\end{enumerate}

The advantage of Dynamic Range Selection is that the GP programs can produce output within a larger range and are not as restricted to arbitrary thresholds or orderings. Appropriate thresholds are automatically allocated after the individual has been developed, so the GP system does not have to evolve a specific translation component, beyond ensuring the output is within the range of values.

Among the design choices is how to set the thresholds that define the range and the slots within. Usually the map occupies a range of values, say from $-n$ to $n$, with $s$ slots, such that each slot occupies a range of size $2n/s$. The authors appear to have chosen the values of $n$ and $s$ relatively arbitrarily. They stated that the output from the GP program should be rounded to the nearest integer and that the map should occupy the range $-250$ to $+250$, creating $501$ separate slots.

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 once again be thought of as analagous to the difference between genotype (the DNA of an individual) and phenotype (its eventual behaviour) in natural life. To put it another way: although the purpose of our genes is to build a body and a brain, the learning of language, or how to play chess for instance, is not hard-wired -- it comes through practice during the individual's lifetime. As was mentioned in Chapter \ref{ch:gpsurvey}, this distinction is not very often apparent in GP, which tends to concentrate on the genotype. 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 an algebra problem! In any case, once initialised, the class mapping for a particular value can be extracted rapidly. Zhang \emph{et al.} \cite{zhang:2003:jasp} were able to use DRS with some success on three different problems, although the largest multiclass problem studied consisted of only four classes. 

A similar 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 \cite{smartZhang04}. This has the advantage of providing a level of confidence estimation, provided that the chosen probability density function models the distribution of the data accurately. However, it imposes a heavier burden of computation on the system. We shall see later in this chapter an improvement to DRS by the author which permits an indication of confidence to be calculated in a more efficient manner.

\subsection{Computer Vision Inspired Techniques}
By now the reader may have the impression that GP researchers are quite good at contriving new ways to solve particular problems. As we have seen, one of these problems is how to select thresholds automatically. Although Dynamic Range Selection is one flexible solution, the computer vision literature also suggests established techniques for tackling this kind of task, usually for the purposes of grey-value segmentation. A couple are introduced briefly below.

\subsubsection{Variance Based Thresholding}
\label{variance}
Assume that the output of the classifier, when plotted, yields a bimodal distribution. The first peak in the ditribution belongs to one class, and the second belonds to another. It is necessary to find a threshold that divides the distribution into two. One simple means of automatic theshold search uses the variance between classes compared to the overall variance of both classes in order to establish a reasonable threshold position, proposed by Otsu \cite{otsu79}. If the output of the solution for every sample is collected, then a histogram of its output may be computed. As the histogram forms a discrete probability distribution of $N$ samples over a range of different values $i$, then a threshold $t$ will divide the distribution into two classes whose values of $i$ are either less than $t$ or greater-than-or-equal to $t$. The idea is choose the value of $t$ that maximises the between-class variance $\sigma^2_{b}$, an indicator of the ``distance'' between two classes:

\[
\argmax_{t \in \{0,1,2,...255\}} \left(\sigma^2_{b}\right)
\]

\noindent where the between-class variance is calculated as:

\[
\sigma^2_{b} = p_0\left(\mu_0 - \mu_t\right)^2 + p_1\left(\mu_1 - \mu_t\right)^2
\]

\noindent where $p_n$ is the total probability of class $n$, $\mu_n$ is the mean of class $n$ and $\mu_t$ is the global mean. Since the total variance is equal to:

\[
\sigma^2_{T} = \sigma^2_{b} + \sigma^2_{w}
\]

\noindent then by maximising the \emph{between}-class variance $\sigma^2_{b}$ , the \emph{within} class variance  $\sigma^2_{w}$ is minimised. Once the threshold has been discovered, the output of the GP program for each value may be decided and the fitness calculated as before. Since the process of finding the threshold is unsupervised, GP is compelled to search only for useful discriminant functions.

\subsubsection{Entropy Minimisation}
Another approach, first proposed by Kapur \cite{kapur90}, aims to identify an optimum value for $t$ by  minimizing the entropy within the two class distributions defined by $t$. Distributions whose entropy is low tend to be clustered together neatly. Again, $t$ is chosen by evaluating through a series of different values and choosing the value that yields the lowest entropy:

\[
\argmin_{t \in \{0,1,2,...255\}} \left(H_0 + H_1\right)
\]

\noindent Where $H_0$ is the entropy of the distribution to the left of $t$, and $H_1$ is the entropy of the distribution to the right of $t$. They are calculated using the standard entropy equations:

\[
H_0 = - \sum_{i=0}^t\frac{p_i}{p_0}\log \frac{p_i}{p_0}
\]

\[
H_1 = - \sum_{i=t+1}^N\frac{p_i}{p_1}\log \frac{p_i}{p_1}
\]

Both of these techniques are well suited to interpreting the output of a binary GP classifier, and do not appear to have been used for this purpose before. Having described a number of representations for classifiers, it is now necessary to decide upon which is most appropriate for the author's classification system.

%Smart and Zhang (2003) compared two different dynamic range selection methods for image classification. The first, Centered Dynamic Range Selection attempted to find the average result of the population for a particular class, weighted to favour the results of the best performing individuals. The second, Slotted Dynamic Range Selection, assigned a much larger set of slots, each of which would be marked as having a particular class. It was found that each dynamic selection method could outperform static range selection on all but the simplest tasks, but centered dynamic range selection appeared to work the fastest and the best. It should be noted that their range selections techniques were averages for the  population as a whole, whereas the thresholding suggested by Poli was to be calculated individually for each program.



\subsection{Choosing a Representation}
\label{entropy-drs}
Loveard and Ciesielski \cite{LovCie01} published results comparing five GP representations: decision trees, evidence accumulation (very similar to the ``modi'' program structure), binary decomposition and static and dynamic range selection (DRS), on a series of classification benchmarks. Their results showed that DRS often yielded the best results when classifying a number of datasets; these results are confirmed by the author's own experiments, which are not shown here. Other comparative investigations by GP authors are relatively few and far between. In this section the author shall make some of his own, slightly different, investigations, starting with a comparison between DRS and the threshold choosers borrowed from computer vision. Although DRS is also applicable to multi-class classification, in the binary case it is worthwhile investigating its performance relative to the variance or entropy thresholding techniques, which are each based on a theoretical framework for identifying an optimal threshold.

At this point, the author must beg forgiveness from the reader for presenting experiments using a Genetic Programming system which has not yet been described! More details about the GP set-up itself, including parameters and the function set, await in the following chapter. For now let us assume that we have access to a suitable GP system, which simply allows us to measure  the \emph{difference} in fitness between different classifier representations. 

In the first experiment, GP was used to discover classifiers for five different public classification datasets concerned with binary classification. The datasets are described at the beginning of this thesis, and will be used throughout the following chapters. Fifty classifiers were evolved for each dataset using three different classification representations: DRS, Variance and Entropy Thresholding. The average results on test data are shown in Figure \ref{fig:drs-vs-thresholding}. The results show that the DRS representation chosen by Loveard can itself be outperformed by both thresholding techniques on each of the five datasets. The differences between DRS and the thresholding algorithms were statistically significant in each case. Although classifiers using thresholding techniques need to check many different values of $t$ in order to decide upon the optimum threshold, they do not take substantially longer to evolve than with the DRS technique. In any case, they will execute slightly more quickly following evolution\footnote{The variance and entropy methods require only a single threshold comparison to make decisions, dynamic range selection requires division and an array access to choose the class.}. Of the two thresholding techniques, entropy thresholding appears to outperform variance thresholding in most cases, although the difference is not always significant. Interestingly, the two thresholding techniques typically achieved worse \emph{training} fitness than DRS, but were found to be more accurate on test data: an indication that the classification map was over-fitting the training samples.

\begin{figure}
\begin{centering}
\includegraphics[width=0.8\textwidth]{images/drs-types}
\caption[Comparing Automatic Threshold Representations]{The average errors of three different automatic thresholding techniques on five public datasets concerned with binary classification.}
\label{fig:drs-vs-thresholding}
\end{centering}
\end{figure}

Our quest for a suitable GP classifier would appear to be one step closer: for binary problems entropy thresholding seems to produce the most accurate classifiers. Problems in vision such as detection or background subtraction may be well suited to this kind of representation. 

However, it has already been stated that many (perhaps most) other tasks in vision are multi-class in nature. Situations involving shape, gesture, digit, vehicle or face recognition each require various different classes to be discriminated from each other. In order to develop a classifier that is sufficiently generic to solve a variety of vision problems, the representation must be capable of solving multi-class problems -- which suggests the use of DRS. Although we have seen that multi-class problems may be decomposed into a series of binary problems, the thresholding techniques shown here suffer from limitations even in the binary situation (for the same reason that Genetic Programming was chosen as the author's preferred classification technique). A single threshold contains an inherent assumption that two classes within the data can inhabit clusters that can be distinguished by a single plane (if $f(x)$ is linear). In fact, it may well be that the members within one arbitrarily-defined class actually belong to two or more distinct clusters, or that the range is defined by two thresholds -- in either case the thresholding technique would produce worse results. 

For these reasons the author's classification \emph{system} shall use both entropy thresholding and DRS, dependent on the type of problem to be solved. Before discussing the classification system as a whole, the author shall introduce various enhancements that improve the accuracy, genericity and functionality of DRS.

%Still, variance and entropy thresholding may be useful for unsupervised learning by GP -- a topic that is rarely researched.

\section{Investigating Range Selection}
Previous research has shown that DRS is the one of the more suitable classification representation for solving multi-class datasets. Nonetheless, the author has  dedicated some time to analysis and improvements to this technique. This section covers enhancements to DRS and presents supporting results.

\subsection{DRS Filling}
The reader may have been wondering what becomes of those slots that are not touched by any training data and are therefore not assigned a class label during training. Such slots are incapable of producing a classification, so may reduce the ability of the DRS classifier to generalise, or indeed may cause the classifier to behave unreliably on seemingly straightforward test data.

Using a synthetic dataset whose points are defined by two attributes, one can plot the positions of training data in two dimensions and visualise the problem (see Figure \ref{fig:drs-unfilled}). The figure shows that GP can find a decision plane that divides the two classes, but while all the training data can be classified correctly, some slots remain unassigned. The gaps left by unassigned slots may cause an unseen sample to be classified unreliably, even if it is well within the normal range for  its class. The author's original solution was, for data falling into an unassigned slot, to perform a local search until it found a neighbouring slot that was assigned a class, then to return that class. As well as being inefficient, this method does not preserve any margin of error between classes that may exist: returning an unassigned class may be a genuine indication of ambiguity, which could be useful.

\begin{figure}[ht]
\begin{centering}
\includegraphics[width=0.33\textwidth]{images/drs-nofill}
\caption[Unassigned Slots in DRS]{Each sample in the 2D dataset is plotted, along with the decision of the classifier at every point in 2D space (red for one class and blue for another). This figure shows that the DRS map needs to be filled in to ensure classification is reliable.}
\label{fig:drs-unfilled}
\end{centering}
\end{figure}

This author's solution is to invoke a separate algorithm once after training which deals with unassigned slots by ``filling them in'', while retaining any margin between the classes, a technique hereafter referred to as \emph{fDRS}. The author developed the following algorithm for this purpose:

%\begin{mylisting}
%\begin{verbatim}
\begin{lstlisting}[language=c]
for each slot i in slots[] {    
    if (slot is unassigned) {
        // see whether this slot can be "filled in" to make the DRS translator more reliable
        before = first unassigned class before this slot
        after = first unassigned class after this slot
        // if both before and after are the same, then "fill in" the gap
        if (before == after) {
            slots[i] = before;                    
        }        
    }
}
\end{lstlisting}
%\end{verbatim}
%\end{mylisting}

An important characteristic of a good classifier is its ability to \emph{generalise}, or demonstrate good performance on data that it has not encountered during training. The effect of this algorithm is shown in Figure \ref{fig:drs-filled}. By filling in the slots, the generalisation capabilities of the map are increased, especially in circumstances where the training data are sparsely distributed or the number of slots is high. The algorithm maintains the margin between the two classes (if there is one), so that the unassigned result comes to indicate genuine ambiguity. 

\begin{figure}[ht]
\begin{centering}
\includegraphics[width=0.33\textwidth]{images/drs-filled}
\caption[Filling-in Unassigned Slots]{The result of the filling algorithm on the same program classification map}
\label{fig:drs-filled}
\end{centering}
\end{figure}

Although the algorithm appears to work quite well on our simple 2D example, does it improve the generalisation capabilities of GP-based classifiers on real multidimensional data? The algorithm was put to work on ten different commonly-used datasets. The results are shown in Table \ref{tab:drs-filling-results}, which shows the average test error both with and without the filling algorithm running and the difference between the two expressed as a percentage. On datasets without separate test sets the appropriate k-fold cross validation technique was used to estimate the error. Each result is the average over 25 runs.

%TODO: Is the difference significant in each case?
\begin{table}
\centering
    \begin{tabular}{lrrr}
      Dataset 		& Test Error \% (DRS)	& Test Error \% (fDRS) 	& Percentage Improvement \\ \toprule
      BUPA	 		& 0.361						& 0.356 					& +1.24					 \\ \midrule
      Glass			& 0.423						& 0.415 					& +1.98					 \\ \midrule
      Heart			& 0.228						& 0.214 					& +6.07					 \\ \midrule
      Ionosphere	& 0.119						& 0.107 					& +10.57				 \\ \midrule
      Iris			& 0.127						& 0.065 					& +48.29				 \\ \midrule
      Pima			& 0.250						& 0.247 					& +1.29					 \\ \midrule
      SatImage		& 0.251						& 0.250 					& +0.11					 \\ \midrule
      Thyroid		& 0.027						& 0.026 					& +3.28					 \\ \midrule
      Vehicle		& 0.405						& 0.404						& +0.45					 \\ \midrule	
      WDBC		& 0.053						& 0.041 					& +23.61				 \\ \bottomrule

\end{tabular}
\caption{DRS Generalisation Improvement by using the DRS filling algorithm}
\label{tab:drs-filling-results}		
\end{table}

% TODO: Is Paired T test appropriate?
The results in Table \ref{tab:drs-filling-results} show that the filling algorithm in fDRS has an exclusively positive effect all the unseen portions of the datasets. Of course, this is not particularly surprising but it does confirm that the choices made by the algorithm improve the program's generality (the training data fitness would not be affected). Although the difference is slight in some cases, a paired T-test nonetheless shows the difference to be statistically significant in each case. While the filling algorithm can be executed in a single pass on any program classification map quickly, it can have a significant effect on the generalisation capability of the classifier, which in the case of the Iris dataset, demonstrated a substantial improvement. The algorithm has most effect on datasets whose samples are few or sparsely arranged.

\subsection{Parameter Free DRS -- ``DRS2''}
\label{drs2}
Since the fitness function is one dimensional, it is difficult to establish whether an individual's performance is hampered by its logic or by its inability to translate its decision onto the expected class boundaries. Dynamic range selection partly removes the need to evolve the latter, which reduces the complexity of the problem so that accurate individuals may be evolved faster.  However, ``basic'' dynamic range selection still assigns slots within a specific range, for instance from $-250$ to $+250$. Since the output of the individual is to some extent dependent on the magnitude of the feature vector values, the range may be restrictive: the function may still need to incorporate a multiplier to ensure that values generally fall within the given range. Even if the classifier's output is within the range, it may not occupy the \emph{whole} range, so the number of effective slots may be smaller and the position of the thresholds may be less accurate.

For these reasons the author implemented an extension upon fDRS, hereafter referred to as \emph{DRS2}, 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 fall within an arbitrary range.

%TODO: Standard deviation to indicate plus minus confidence?
\begin {table}[tp]
\centering 
    \begin{tabular}{lrrr}
      Dataset 		& Test Error \% (fDRS)	& Test Error \% (DRS2)  & Result \\ \toprule
      BUPA	 		& 0.356	& 0.339 	& Not Significant		 \\ \midrule
      Glass			& 0.415	& 0.377 	& DRS2 Better			 \\ \midrule
      Heart			& 0.214	& 0.216 	& Not Significant		 \\ \midrule
      Ionosphere	& 0.107	& 0.104 	& Not Significant		 \\ \midrule
      Iris			& 0.068	& 0.064 	& Not Significant		 \\ \midrule
      Pima			& 0.247	& 0.245 	& Not Significant		 \\ \midrule
      SatImage		& 0.250	& 0.242 	& DRS2 Better			 \\ \midrule
      Thyroid		& 0.026	& 0.024 	& Not Significant		 \\ \midrule
      Vehicle		& 0.404	& 0.376	& DRS2 Better			 \\ \midrule	
      WDBC		& 0.043	& 0.038 	& DRS2 Better			 \\ \bottomrule
\end{tabular}
\caption { DRS Method Comparison, including the result of an unpaired samples T Test. }
\label {drs-comparison} 
\end {table}

Results of experiments with the two DRS techniques on ten public data sets are displayed in Table \ref{drs-comparison}. The results show that the updated DRS technique, DRS2, is either equivalent to with or superior to the previous algorithm on all occasions. It was also observed that the DRS technique yields programs of a slightly smaller size, which may be explained by the individual not needing to scale to an arbitrary range. As well as helping to ensure all slots have the chance to be used, DRS2 does away with two parameters, which helps make it more readily applicable to unknown tasks. In the following chapter the author shall present further attempts to rid GP of various parameters. 

%TODO: Does it also generalise better?

\subsection{Number of Slots}
The final arbitrary parameter associated with a program classification map is the number of slots to be used. Larger numbers of slots will permit the map  to  place thresholds in more exact locations and fit the training data better. Excessively large numbers of slots may result in only one unique instance fitting into each slot, at which point the DRS map would begin to resemble a 1-nearest-neighbour algorithm and may become less able to generalise. Smaller numbers of slots may improve the generalisation capabilities of the classifier, although too few slots may not be enough to divide the classes adequately. It is therefore worthwhile to investigate what constitutes ``large'' and ``small'' numbers of slots and see how slot numbers affect the classifier's performance and generalisation ability.

The original number of slots, $501$, appears to be excessive for most situations. Providing such a number of independently assignable slots may tempt the GP process to simply evolve some means of \emph{dispersing} the data samples across the whole range. This would yield increasingly good results on training data, but poor results on testing data. The author's experiments with more modest numbers of slots indicate this trend -- that increases in training fitness correspond to decreases in unseen test fitness, a symptom of over-fitting.

The author's first deed was to define the slot count not as an arbitrary value but as a multiplier of the number of classes, a crude indicator of the problem's complexity. An experiment was devised to examine the differences between classifiers that use DRS for different slot count multipliers. DRS2 was used as it guarantees that every slot has a chance of being used. Again, each classifier was evaluated against a number of benchmark datasets, with each experiment repeated 25 times to determine the average error on each. The results of the experiments are presented in Figure \ref{fig:drs-slots}, in which the average fitness values are plotted against the slot count for each dataset. 

% drs-slots.xls
\begin{figure}
\begin{centering}
\includegraphics[width=0.95\textwidth]{images/drs-slots}
\caption[Results for Different DRS Slot Sizes]{Fitness results for classifiers evolved using 5 different DRS slot ratios.}
\label{fig:drs-slots}
\end{centering}
\end{figure}

The figure shows that increased slot count ratios typically brought about a modest reduction in error on training data, although in some cases the difference was more substantial. On the equivalent test data, by contrast, the error remains roughly at the same level for many datasets, indicating that the classifier is over-fitting the training data. However, for some datasets, the improvement on test data is substantial for increased values of the ratio. A casual analysis of the graph shows that a ratio of 7 appears to satisfy the majority of datasets. Having investigated a reasonable way of determining the slot size and chosen a value that seems to deliver a good balance, the DRS technique may be regarded as parameter-free, which is a positive step towards developing a generic learning component.

\subsection{Confidence Estimation}
\label{confidence}
Moving on towards more substantial adaptations of the DRS technique, there are certain additions that can be made to increase its functionality, including giving some measure of confidence. As we have seen, the majority of classification representations by GP produce ``hard'' classifications, where a feature vector is assigned a class label without any indication of the classifier's certainty on the matter. This is adequate for some straightforward classification problems, where there is a reasonable margin between classes, but is not so helpful in other tasks where there is some degree of overlap between classes. Indeed, in some cases it may be more appropriate to suggest more than one potential class for a given feature vector. One example, to be tackled later in this thesis, is optical character recognition (OCR), which is characterised by a reasonably large number of classes, some of which appear quite similar to others. For such a problem, it is difficult to differentiate every class with a high degree of certainty. In these situations it is more helpful to provide the likelihoods that the feature vector belongs to \emph{each} class. If, for some reason, the most likely character seems inappropriate, the system can fall back to the next most likely and so on. This would be the case if the characters represented the postcode of an address, for example.

%TODO: Mention GP with confidence estimation here

As we've seen so far, dynamic range selection returns only ``hard'' classifications. Interestingly though, the algorithm \emph{does} have access to information that can be used to compute some measure of confidence. The reader will recall from page \pageref{drs-calculation} that the class of a particular slot is chosen by first identifying all the items of training data $M$ that are allocated to the slot by the GP program, then choosing among them the most popular class using a winner-takes-all strategy. If $M$ is entirely homogenous, that is to say that all members have the same class $c_0$, then the classifier can be reasonably certain that $c_0$ is the most appropriate label to return. However, if $M$ is composed of, say, 6 instances of class $c_0$ and 5 instances of class $c_1$, then the slot should still choose to label itself with $c_0$ but it should not be so certain. If the slot can express its confidence, it might state that, for an output within its range, there is a $6/11$ chance that it is $c_0$ and a $5/11$ chance that it is $c_1$. Therefore, confidence estimates for each class can 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 the author's second DRS variant, referred to henceforth as \emph{DRS2C}.

It is rather difficult to measure the effect of confidence estimation directly: it can not be used explicitly but instead is made use of by subsequent processes, as was alluded to in the postcode OCR example above. The system may be interested in the $n$ most significant classes for a particular feature, or may choose to consider only data points that can be classified with a particular level of certainty. Each case may be task specific. In the next section we shall investigate some post-classification techniques using GP that permit a quantitative assessment of confidence estimates.

\section{Classification Frameworks}
Although the representation of evolved programs plays a key role in the learning of accurate classifiers, there are nonetheless various different means of improving classification solutions, which may include additional processing before, during or after the course of evolution. In this section we shall look at three techniques intended to improve the accuracy and speed with which classifiers may be evolved using GP.

\subsection{Classifier Fusion}
Depending on the course that evolution takes, different individual classifiers may devise completely different ways of solving a problem -- much the same as humans! Genetic Programming may be particularly prone to this, owing both to the relatively random manner in which the search is conducted and the potentially large size of the solution space. Thus, while all individuals may have equivalent overall fitnesses, they may make different sorts of mistakes on different samples of training data. Although the accuracy of individual classifiers cannot be improved after the evolutionary process has completed, if we ask several classifiers to identify each data point, then we may reach a consensus opinion which is, on average, more accurate than that of any of the individuals. This is the motivation behind \emph{multiple classifier systems} (and parliamentary democracies!) which aim to produce results which are more robust than those of an individual classifier. Of course, it is important that individual classifiers are \emph{independent} from each other, so that their ``fusion'' together is meaningful: if each of the classifiers always agree, then the technique is adding a computational burden without its consensus providing offering any improvement in accuracy. A straightforward way of ensuring sub classifiers are independent is to train each on different sections of the training data, or to weight the training data differently for each classifier; \cite{freund96experiments}.

There exist various approaches for combining classifiers. A couple of straightforward ones are described briefly below.

\subsubsection{Majority Vote}
Given three or more binary ``sub-classifiers'', each makes a decision with regard to a particular input vector. Each classifier is allocated one ``vote'' with which to support its chosen class. The class which receives the most votes overall is chosen and returned. This approach does not require an estimate of confidence. As such, for the consensus to be meaningful, all sub-classifiers should be equally certain, and all sub-classifiers should have roughly equivalent accuracy.

A more rigorous approach extends the fusion technique to weight the overall vote of any sub-classifier by its own fitness, such that the fitter classifiers have more say in the decision making process.

\subsubsection{Committee Voting}
The majority technique is quite democratic, implementing as it does the ideal of ``one decision one vote''. However, in the world of classification not all decisions are created equal! Giving equal weight to both certain and uncertain classifications may incorrectly reward the wrong class. The author's \emph{DRS2C} technique makes it possible to quantify how certain a particular vote is. Using the concept of confidence, it may be possible to reach fairer decisions using so-called \emph{committee voting}.

In the committee approach every class may receive some credit from every sub-classifier. In contrast to majority voting, each vote is weighted according to the classifier's confidence. Thus each sub-classifier still contributes the same amount, but is able to hedge its bets over different classes when appropriate. This appears to be fairer, although it is reliant upon the confidence estimates themselves being accurate.

\subsubsection{Experiments}
The two techniques provide a means of assessing whether confidence estimation can bring about improvements in accuracy. It is also necessary to measure any improvement in accuracy that ensemble classification techniques in general can yield over single classifiers. Since multiple classifier systems are inevitably more computationally expensive than single classifiers, it is worthwhile to assess whether they improve accuracy sufficiently as to justify their increased computational ``cost''.

In order for the comparison to be fair, the fusion classifier should take the same amount of time to evolve as a ``single'' classifier. In order to ensure this, the author devised a strategy that makes use of \emph{island selection} (see page \pageref{island-selection}), a technique which divides the population into separate sub-populations or ``islands'' (in this case 7 islands), within which evolution can proceed partly or entirely independently. In this situation the islands were entirely independent, permitting several classifiers to be evolved simultaneously. Each island was allocated training data which were partitioned in a manner similar to that used in cross-validation -- randomly, but maintaining class distributions in each\footnote{This was done by allocating all the training samples into bins, one for each class. Each bin was then shuffled, with one sample taken out of each bin for each partition in round robin fashion, until all bins were empty. This is a fair way of ensuring that each partition has a roughly equal class distribution, and have as similar sizes as possible.}. Thus each island would concentrate on a different part of the training set, helping to ensure that the classifiers evolved were independent. In fact, this approach requires \emph{less} computation, since it uses the same number of individuals but each individual is evaluated against a smaller number of samples. The single classifier was trained on all the data for the equivalent amount of time.

At the end of evolution, the best individual from each of the 7 islands was chosen, yielding 7 potential members of the multiple classifier system. The same individuals were tested both in majority voting ``mode'' and committee voting ``mode', permitting direct comparisons to be made. As before, the experiment was repeated 25 times; results are averages of performance on test data. The results on test data are summarised in Figure \ref{fig:fusion-results}.

%From complex-island-fusion.xls
\begin{figure}
\begin{centering}
\includegraphics[width=0.95\textwidth]{images/complex-island-fusion}
\caption[Fitness Results for Different Classifier Fusion Techniques]{Fitness results for classifiers evolved by regular GP, then with those combined in Majority and Committee Voting scenarios.}
\label{fig:fusion-results}
\end{centering}
\end{figure}

The results show that fusion techniques broadly outperformed equivalent single classifiers, sometimes by a substantial margin; particularly so on some of the larger multi-class datasets (PenDigits and SatImage). The difference between confidence and majority is most marked on the PenDigits dataset, which is concerned with the recognition of 10 digits and is the kind of task that motivated the development of a DRS variant that could produce confidence estimates. On the 8 occasions where the difference between the fusion techniques were significantly different, the committee voting scheme produced the best results on 5. This would appear to show that, for some datasets, the additional information provided by the confidence estimate can make a significant contribution to the accuracy of the system. 

The figure also shows the results when the majority and committee classifiers were executed in two sub-modes: one giving equal weight to each classifier and the other weighting the classifier's votes by its fitness, so that fitter classifiers would have a proportionally larger vote than less fit classifiers. The chart shows that this addition can make a modest improvement to results from the majority fusion technique, but generally yields little difference for the committee ensemble.

It is difficult to assess which committee technique is ``better'' overall from these results. Langdon \cite{langdon:2001:groc} pointed out that\footnote{In fact Langdon used Genetic Programming to develop the fusion technique itself.}:

\begin{quotation}
\noindent ``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}

\noindent Fortunately it is not necessary to make such an assessment -- since the author's multiple classifier system can operate in either mode, at the end of the run both can be tried in order to find the better one for a given problem\footnote{However, it is acknowledged by the author that there are \emph{other} classifier fusion techniques in addition to these.}. The reader may also be wondering what the best committee size might be on each occasion -- the author's software implements an approach whereby the seven classifiers are used in all different permutations in order to discover the most appropriate ``sub-committee''. This process takes a couple of seconds to complete, but need only be performed once per evolutionary run. The author would claim to have produced a classifier fusion technique which is sufficiently flexible as to try different classification techniques, while requiring no more evolution time than a single GP classifier.

\subsection{Classifier Evolution by Partial Solutions (PS)}
\label{ps}
The author's second approach aimed to address the time taken to evolve classifiers in a general sense. Inspired by the boosting of weak classifiers in \cite{EvoVision:Freund-Shapire:1996} and classifier systems in general, the author developed a scheme in which GP programs are evolved as simple expressions which solve only part of the overall solution and are thus termed \emph{partial solutions}. As each partial solution is not expected to correctly classify every sample, the programs are small and so may be discovered and evolved quickly.

As useful partial solutions are identified they are added to a separate, ``strong'' classifier whose scope exists outside of the GP system (see Figure \ref{fig:partial-solutions}). A useful partial solution is one that can correctly classify parts of the training data that have not been solved already. Following the discovery of such a solution, the problem is subsequently 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. This prevents regression in a more granular way than does elitism (page \pageref{elitism}) The system 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}
  \caption[Classification by ``Partial Solutions'']{GP by Partial Solutions creates a strong classifier from a number of smaller solutions.}
  \label{fig:partial-solutions}
  \end{centering}
\end{figure}

\paragraph{Fitness Criteria}
The fitness of a partial solution with regard to a particular class $c$ is calculated by dividing $TP_c$, the number of times it correctly labelled a sample with class $c$, by the total number of training samples $N$, added to the number of missed classifications of $c$ samples, $FP_c$, as shown below:

\[
  \mbox{fitness}_c = \frac{\alpha TP_c}{N + \beta FP_c}
\]

\noindent The factors $\alpha$ and $\beta$ allows the fitness measure to be adjusted to affect the individuals' sensitivity or specificity.

But what is $c$? Each partial solution is treated as a binary classifier with respect to a class $X$, which is chosen by evaluating the partial solution with respect to the set of classes $C$ in the task, and choosing the class for which it has best fitness:

\[
	X = \argmax_{c \in C} \mbox{fitness}_c 
\]	

\noindent This is a brute force approach but ensures that the logic and interpretation are kept separate. 

\paragraph{Adding to the Strong Classifier}
Fitness is used to drive the evolution of partial solutions. 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 separate 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 of training data 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 binary 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 classes.
\end{enumerate}

\noindent 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 characteristic which makes GP by partial solutions faster. 

A version of island selection is used with crossover only occurring between parents with the same value of $X$, 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.

\subsubsection{Experiments}
A series of experiments were conducted by the author in order to explore the practicality and effectiveness of the partial solutions approach. It was found that for certain problems, partial solutions could deliver more accurate solutions an order of magnitude more quickly than could conventional GP. 

However, it was observed that, for certain problems with large amounts of training data, the system generated \emph{too many} partial solutions. Furthermore, the author was uneasy about the manner in which partial solutions could be added to the strong classifier but not changed or refined. As each partial solution is selected, the data that it solves correctly are 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 cannot 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.

\subsection{Intelligent Classification System (ICS)}
\label{ics}
We have seen that as individuals get better, it becomes more tricky to improve them without breaking something, particularly when the crossover/mutation operators have essentially no idea what parts of the tree are useful and which parts are under-performing. This is a characteristic of the so-called stability-plasticity dilemma, which has been demonstrated empirically by Banzhaf  \cite{banzhaf:gp-introduction}.  In essence, learning by GP becomes more difficult as evolution progresses. The concept of Partial Solutions is to protect useful components as much as possible to mitigate this problem. Still, the randomness of Partial Solutions caused the author some degree of unease. For this reason, a more ``careful'' classification scheme was developed which addresses this issue while still taking advantage of the underlying concept of partial solutions. It also makes use of the other innovations described in this chapter.

Rather than split the problem into pieces in a haphazard way, the author's third classification system, termed ``Intelligent Classification System'' (ICS), divides the problem in a repeatable and logical way. ``Intelligent'' refers to the way in which the system attempts to replicate the way a human would approach a problem -- it performs experiments along the way and otherwise attempts to choose the best parameters and approaches for particular problems. 

In general, ICS initiates a straightforward process of ``one-vs-all'' binary decomposition on the training data in order to split it into sub-tasks. Each sub-task is evaluated in order to assess its difficulty. A classifier for each sub-task is then learned, starting with the easiest. The classifiers are then assembled into a single multi-class classifier, of the type shown in Figure \ref{fig:bd}. A process of refinement then initiates in order to improve the classifier where possible. The means by which ICS goes about these tasks will now be covered in more detail.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.4\textwidth]{images/binary-decomposition}
  \end{center}
  \caption[Binary Decomposition]{Binary Decomposition of a multi-class Problem. Each class may be returned by one sub-classifier. If the classifier returns a negative result, the next classifier in the list is tried and so on.}
  \label{fig:bd}
\end{figure}

\subsubsection{The Choice of Binary Decomposition}
Before continuing further, it is worthwhile considering whether binary decomposition is a better means of producing accurate classifiers than evolving a single multi-class classifier. An experiment was run to assess the difference between the two techniques, given an equal time to develop a classifier in each case. The results are shown in Figure \ref{fig:bdvmc}, which shows that the binary decomposition approach yields classifiers with lower error than those from the single multi-class classifier, on average. Although the difference was not statistically significant on the Iris dataset, for the other 4 cases, the binary decomposition approach produced significantly more accurate results.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.9\textwidth]{images/binary-decomposition-vs-multiclass}
  \end{center}
  \caption[Binary Decomposition vs Multi-class Classification]{Binary Decomposition vs Multi-class Classification.}
  \label{fig:bdvmc}
\end{figure}

Of course, if the problem is already binary it cannot be split up further. In this case ICS uses the entropy and variance thresholding representations (discussed earlier in Section \ref{variance}), which were shown to be superior to DRS in binary situations. For multi-class problems, the algorithm must develop one classifier per class, with each classifier evolved to use the author's DRS2C representation. Although these classifiers are also binary in nature, experiments reveal that range selection outperforms entropy and variance thresholding here, as the classifier may need to delimit a particular class with more than one threshold. 

If provided with more than one CPU, ICS typically attempts several GP runs per class in its search for a classifier; variance and entropy thresholding are used alternately. 

\subsubsection{Estimating Difficulty}
The reader is referred once more to Figure \ref{fig:bd}. The multi-class classifier consists of a chain of binary classifiers. If the ``A'' classifier returns true then ``A'' is returned, otherwise the ``B'' classifier has an opportunity to classify the data and so forth. There are two observations that one can make from this architecture. The first is that the first classifier in the chain should be the most accurate, as errors will carry forward. The author submits that the eventual accuracy of a classifier is proportional to the difficulty of the task. Thus, if we can estimate or measure the difficulty of classifying each class beforehand, we can organise the binary chain in a manner that yields fewer errors. 

The second observation of this kind of architecture is that if classifier ``A'' returns false for whatever reason, there is no further opportunity for samples of ``A'' to be identified. Following the evolution of a classifier for ``A'', we can remove all the ``A'' samples from training data. This has two effects: the training time for subsequent processes of evolution is reduced and later problems become marginally easier to solve. This is the essential motivation behind partial solutions, except in this instance the partitions are chosen in a more systematic manner. %The most pleasing benefit of this approach is that the learning process actually accelerates as time goes on.

The first stage in ICS, therefore, is to estimate the ``difficulty'' of each component binary problem, so that the order of evolution can be established. This is performed by running a k-nearest-neighbour classifier on each problem and assessing its output on a subset of training data reserved for validation. Since k-nearest-neighbour requires no training as such, this step can be performed relatively quickly. The error of the k-NN classifier on each class is assumed to be indicative of class confusion. Classes for which k-NN achieved the lowest error are executed first, with the expectation that some of the class confusion will be alleviated as the training data is reduced.

The reader may be wondering whether k-nearest neighbour is an ideal predictor of GP performance. Indeed, the k-NN algorithm is an example of ``lazy learning'', where there is essentially no training procedure beyond committing sample data to memory. GP, by contrast, evolves an analytical solution to the problem, so the data that confuse k-NN may not be a problem for GP and vice versa. In order to assess the impact of class ordering, the author devised a series of experiments, in which the classes were ordered by the predicted ``easiest'', then ``hardest'' and randomly. These were each compared to ``standard'' binary decomposition, which did not implement any class removal. The hypothesis is that if the k-NN classifier's performance is a predictor of GP performance, then the runs for which classes were ordered by easiest tasks should return the lowest error. Ordering classes the opposite way, by the \emph{hardest}, should yield worse performance. Finally the classes were ordered randomly to make an additional comparison. The average results over the course of 25 runs each are shown in Figure \ref{fig:bd-results}.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.75\textwidth]{images/binary-decomposition-results}
  \end{center}
  \caption[Assessing Class Difficulty]{The effect of the author's ICS technique vs standard binary decomposition. ``No class removal'' indicates binary decomposition in which the training set is not adjusted in any way following evolution of classifiers. In Random/Easiest/Hardest, ``spare'' classes are removed -- this appears to have an exclusively positive impact on training data. Of the three ordering techniques, ordering by easiest yields the lowest error.}
  \label{fig:bd-results}
\end{figure}

The results show that the ordering of classes does indeed have a significant effect and that ordering by the hardest as opposed to easiest has a negative effect, indicating that the ordering derived from the k-NN algorithm is not arbitrary. There may, of course, be ordering methods which yield even better results than this method\footnote{Indeed it would be interesting for the computer to learn the best orderings itself. This is not as intractable as it seems, if the classifier accuracy for every ordering combination is computed (which would admittedly take some time), then a set of training data could be established correlating the orderings and their observed fitness. Another GP process could then be run to find rules that lead to the most appropriate ordering.}. It is also apparent that class removal yields more accurate solutions, since each GP classifier can concentrate on a more specific set of training data without being confused by irrelevant data. This also results the most beneficial aspect of this classification system: in contrast to most GP systems the rate of learning accelerates during evolution. Solutions to vision problems can generally be discovered within minutes, rather than hours.

\begin{figure}
  \begin{center}
    \includegraphics[width=1.0\textwidth]{images/cluster}
  \end{center}
  \caption[Distributed Processing]{ICS tries a number of different ideas for each problem. It is able to make use of an arbitrary number of computers to do so. Here is ICS preparing some of the results in Chapter \ref{ch:gpcomparison}.}
  \label{fig:cluster}
\end{figure}

\subsubsection{Other Features}
To return to the description of ICS, following the estimation of class difficulties, a solution to each component problem is then evolved in turn. Each run is repeated several times; the best classifier is chosen. Different parameter combinations are tried for different runs (see Chapter \ref{ch:gpcomparison}) in the cases where the ``best'' parameter is difficult to establish. Such experimentation is a bit indulgent and can lengthen the evolutionary process. To permit classifiers to be evolved in a timely fashion, the author's GP toolkit is able to distribute processing over an arbitrary number of computers on the local network or Internet, each of which can be readily converted into a GP server by downloading and running a small program. ICS evolves both single and ensemble classifiers and chooses the one which solves the problem most effectively. The author's mechanism permits different ensembles using different sub-committees and strategies to be discovered automatically.

\subsubsection{Refinement}
After all of the binary classifiers have been evolved, ICS 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 the user tires, or further GP runs fail to deliver any more improvements, at which point the system completes its task.

ICS nearly qualifies as a one-click classifier learning system. The user needs only to specify the training and testing data for the classifier to be evolved, select how many CPUs to use and suggest how long the classifier has to develop a solution. The classification then proceeds in a completely automated fashion.

\section{Conclusions}
This chapter has described a number of representations for performing classification using Genetic Programming and justified the author’s usage of two: entropy thresholding and dynamic range selection. The author has discussed the relative pros and cons of each and presented a number of ideas intended to improve the accuracy and applicability of DRS in particular. Two different  approaches have been proposed: the faster partial solutions method
and the slightly slower (but possibly more accurate approach) which attempts to evolve classifiers 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 different ways. Partial solutions is concerned mainly with speed while ICS concentrates on accuracy, replicability and careful refinement. Partial Solutions is a good approach for “rapid prototyping”, to see whether a set of data can be solved using GP. ICS produces the equivalent of a final product, where accuracy is of the most importance.

The following chapter will describe the author’s Genetic Programming toolkit in more detail and explain some of the other means by which GP can be rendered into a parameter-free learning tool. The next chapter shall also seek to validate the author’s classification system by comparing it to an established evolutionary computation toolkit, to results obtained by other GP researchers and the best works reported by other pattern recognition researchers.