\section{Feature Sets}
How many lines are there in a human face? A single one around the whole face? Separate ones for each eye? Nose? Mouth? Wrinkles? Hairs? There is no correct answer, so sometimes the information yielded from line or edge detection is not that useful. Some information, however, can define a face pretty well. Its a fair guess that of two adjacent rectangles, one over the eyes and one on the forehead, the one over the forehead will often have less variance in intensities. Low level information like this can be found using simple features based on pixel intensity information. These features can give important clues about texture or other features not as strongly indicated as edges or lines. 

\section{Feature Selection}
Before features can be used in classification, it is sometimes necessary to involve an additional stage of feature selection in which a decision is taken as to which features are suitable for solving a particular task and which are unlikely to be helpful in classification.

Additionally, in the case where the features are parameterised (the haar features are defined in terms of the size of rectangles and other factors and thus represent a large ``family'' of potential features) it may be necessary to search for good values using techniques, for instance using a Genetic Algorithm. These techniques will be discussed in depth later.

Some linear algorithms, such as Neural Nets, are susceptible to unhelpful features, and generally also require the features' outputs to be normalised so that the magnitude of values returned by a particular feature doesn't effect the output. In non linear techniques, such as Genetic Programming, it is not always necessary to perform this stage. Indeed the GP process offers several different means of discovering acceptable parameters while the evolution is in progress. However the concept of ``dimensionality reduction'' -- where irrelevant features which would otherwise add noise to the training data while adding little new information are removed -- can certainly help speed up the search process. 

In many cases it may be the computer vision researcher who decides which features should be included, based on intuition or experience. However, sometimes the scale of the data is overwhelming or the correlations difficult to distinguish. For this reason various algorithms have been developed in order to perform this task automatically, including:

\subsection{Existing Approaches}

\subsubsection{Linear Discriminant Analysis (LDA)}
The aim of LDA (in its simplest form) is to find the one dimension which best
separates examples from two classes. This makes LDA suitable for feature
extraction. More information to follow here. Also to mention Principal Component
Analysis.

\subsubsection{Princical Component Analysis (PCA)}
... information about PCA

\subsubsection{Kernel Discriminant Analysis}
... information about KDA

\subsubsection{Branch and Bound}
... information to follow

\subsubsection{Floating Search Method}
... information to follow

\subsection{Feature Construction by Genetic Programming}
Genetic Programming is a flexible learning technique. Given a set of raw data, it is capable of evolving a reasonable solution to a problem, given time and the appropriate tools (those tools will be discussed later). In order to generate a high-level solution to a particular problem, the raw, generic data requires processing in some way to make it suitably useful. 

The kind of features discussed earlier in this chapter are mostly parameter based, and therefore represent families of potential features. Some of these features will be useful for a particular task, and other will not. While Genetic Programming may be able to tune these parameters and find a suitable overall solution in a single pass, other approaches have been suggested which may be more efficient; some are introduced below.

\paragraph{Two Stage Evolution}
As the granularity of a GP system usually only extends as far as individual programs, in default GP implementations it is not easy to retain those parts of a tree which work very well. The system may evolve an excellent feature but if used incorrectly, the feature (and the rest of the program) may not be included in further generations (it should also be remembered that GP does not necessarily guarantee that even the best individual will be able to reproduce). In such a situation, the bluntness of the fitness measure causes the system to loose otherwise useful information. For this reason it may be useful to separate the evolution into smaller stages so the fitness function is more precise and less information is lost. 

A natural approach is to split the evolution into two stages. In the first stage, just the feature set is evolved. As complex objects, such as a human face, generally cannot be completely described by one feature, in the second stage the GP system learns how to combine a set of pre-evolved features in order to deliver an optimised result.

The evolution of the feature set is in essence a parameter optimisation problem, for which techniques such as Genetic Algorithms have been previously employed. As Genetic Programmins is essentially an extension of Genetic Algorithms, a GP approach may also be taken.

\paragraph{Coevolution}
A second approach also splits the evolution into two parts, but aims to learn them in parallel rather than sequentially.

\section{Making GP More Efficient}
In this section, various techniques for improving the general efficiency of Genetic Programming are explored. Desirable techniques are those which have some positive impact either on the speed of evolution or on the quality of the results produced. 

\subsection{Automatic Classifier Selection using Minimum Standard Deviation / LDA}

\subsection{Automatic Classifier Selection using Range Typing}

\subsection{ERC Optimisation}

\subsection{Training Data}
Genetic Programming, in general, works using a supervised learning paradigm. That is to say that the fitness of an individual is measured according to its performance against known training samples. The collection of such training data will be discussed later in Chapter \ref{ch:vision-system}, but here we discuss here the ways in which GP can be adapted to learn as much from the training data as possible.

It is widely recognised in pattern recognition that training data is likely to contain some level of bias. It may be that some parts of the problem are represented very well by a particular set of training data, while other parts may may be represented by fewer samples. Some training data may be significantly easier to solve than others. 

These situations present two problems. Firstly they may introduce local minima in the solution landscape, into which learning systems may easily become stuck. Secondly the bias of training data sample may not reflect the true bias of data unseen environments, which will reduce the predictive performance of the learned system.

\subsubsection{Ensemble Methods}
The general purpose of ensemble methods, which are widely used in pattern recognition, is to generate a series of different estimators through manipulation of the training data which improve the overall performance. Two exist: bagging and boosting. These two methods have been widely used to create more accurate classifiers. As meta algorithms they can be used to improve the accuracy of any set of weak classifiers. As such we'll not discuss them further here.

\subsubsection{P Learning}

\subsubsection{Training Data Weighting}
Genetic Programming may be used to generate the weak classifiers used by the ensemble methods, but we do want to ensure that the learning system is as efficient as possible in the first place. This reduces the number of weak classifiers required to reach a level of accuracy, and speeds up the learning process itself, which may be hampered by a boosting procedure.

GP is susceptible to local minima because it is a lot easier to break a working individual than to make it that much better that it can continue to make incremental improvements. If the training data can be weighted such that more difficult samples attract greater rewards, then the GP system may be able to break out of local minima more easily. The downside is that this may make the learning process less stable.

The difficulty of a particular item of data may be approximated according to how often it is wrongly classified. The benefit of this approach is that it is domain independent, and can be added into any learning system in which Genetic Programming is involved. Although it appears to be a logical approach, it may introduce instability into the learning process. A number of experiments were conducted to investigate its effect empirically.

The experiments were conducted on a widely used machine vision data set: the CBCL face database (version 1), which consists of thousands of face and non-face images, divided into training and test data sets. Training set comprises 2,429 faces and 4,548 non-faces, the test set: 472 faces and 23,573 non-faces.

``Regular'' Genetic Programming without any training data weighting, and the weighted version were both evolved over the course of 50 generations. The process was repeated 10 times each in order to gather an average measure of performance. The same random seeds were used for each. 



\paragraph{Results}
The following results were found after investigating training data weighting and ERC optimisation. \footnote{training-data-weighting-results2.ods}.

In general it was found that ERC optimisation and training data weighting had little overall impact on the results for the training data. Interestingly, both approaches appeared to improve the score on the unseen data when measured according to the same metric.