\subsection{Michigan Classifier Systems}
\label{sec:Michigan-Classifier-Systems}

Genetic Algorithms provided the learning component for a separate system, invented by Holland (1986), and later refined by Wilson (1994, 1995). As classification is a major theme in this thesis, a detailed description of these classifier systems is presented below. 

A starting point for many classification algorithms is the architecture introduced by Holland \cite{holland1992} who proposed a system consisting of a population of rules {[}P], each comprising a condition and associated action, which compete in order to correctly label a given input vector.

{}``Good'' rules, which contribute to correct classifications, accumulate credit from the environment by way of reinforcement, constributing to the {}``strength'' of the rule. A Genetic Algorithm is used to improve the accuracy of rules in the system.

The condition, which is used to match the input vector, is represented by a fixed length bit string. In the case where the input vector may contain either 1 or 0, the bit string is created from the binary alphabet plus a wild card: $\{0,1,\#\}$. The wild card, or {}``don't care'' symbol, $\#$ permits general conditions, which match more than one input, to be formed. For instance the bit string $``01\#"$ would match two input vectors: $``010"$ and $``011"$. 

All rules which match a given input are added to a {}``match set'' {[}M], from which an action is chosen with probability proportional to the sum strength of the rules which advocate the action ( the rules are placed in an action set {[}A] ). In the simplest case the action consists of a discrete label ( $\{0,1\}$ in the binary case) for classification of the input vector.

In the event that the match set {[}M] is empty, a {}``covering operation'' is invoked where a new rule is created with a matching condition bit string and a random action, replacing another rule in the classifier, after which point the algorithm continues as normal. More detail about this kind of classifier system is presented in the next two sections which concern two implementations of Holland's Classifier System, ZCS and XCS.

\subsubsection{Zeroth Level Classifier System (ZCS)}

Holland's specification defined a number of complex interactions and
mechanisms which are difficult to understand and model. A basic system
was developed by Wilson \cite{wilson94zcs} (named ZCS) as a baseline
implementation of Holland's ideas. A few further details of ZCS are
presented below:


\paragraph{Reinforcement in ZCS}

Reinforcement in ZCS is as follows. A fraction of the strength $\beta$
$(0<\beta\leq1)$ of each member in the action set {[}A] is removed
and placed into a common, empty {}``bucket''. Any immediate reward
$r_{imm}$ from the environment as a result of taking the action,
a quantity is added to each classifier in {[}A], the quantity being
$\beta r_{imm}/[A].size()$. Classifiers in the action set $[A]_{-1}$have
their strengths incremented by:

\[
\frac{\gamma\times bucket}{\left|[A]_{-1}\right|}\]


Where $\gamma$ $(0<\gamma\leq1)$ is a discount factor. After which
point {[}A] replaces $[A]_{-1}$ and the bucket is emptied. Wilson
stated that the discount factor should be significantly less than
1 in order for the learning process to proceed.

Matchinng classifiers in {[}M] which suggest actions other than the
selected one are weakened by $\tau$, which is similar in magnitude
to the learning rate $\beta$.


\paragraph{Learning in ZCS}

Although classifiers may initially be created by the {}``covering''
operation, they are improved using a basic Genetic Algorithm. The
GA is executed at a given rate throughout the learning cycle. Each
time it is invoked, two classifiers are selected from the population,
with probability proportional to their strength. Crossover and / or
mutation is performed to generate two children, and the two children
are inserted back into the population. If the population is already
{}``full'', then two other classifiers are first removed with probability
inverse of their strengths. Therefore good classifiers are able to
reproduce more often.

\paragraph{Extensions to ZCS}

Wilson suggested the use of \emph{s-expressions }(or Genetic Program
parse trees) instead of bit strings. Ahluwalia and Bull \cite{ahluwalia:1999:agpcs}
did use Genetic Programming to implement this in their experiments
discovering feature detectors. Lanzi \cite{lanzi:1999,lanzi:1999b}
implemented these ideas in more detail, moving from the bit-string
representation to a {}``messy'' GA, to conditions encoded using
Genetic Programming parse trees {[}results?].

\subsubsection{Classifier Fitness Based on Accuracy (XCS) }

In ZCS, a classifier's strength is measured by its ability to correctly
identify inputs and recieve payoff. It can only do this once it is
a member of {[}A], however its likelihood of joining {[}A] is also
dependent on its strength. Wilson \cite{wilson95classifier}questioned
the validity of this scheme, stating that if different niches within
the environment had different payoff levels, the system would unfairly
encourage classifiers which identify particularly generous payoffs.

Wilson theorised that classifiers using a high number of wild cards
(\#) would appear in more match sets {[}M] and therefore have more
chances to receive payoff and increase their strength.

To address these problems, Wilson designed an improvement to ZCS called
XCS, which used a different approach to measuring the fitness of a
classifier which would be a measure of the \emph{accuracy} of the
prediction rather than the prediction itself.

The prediction strength would still be used to choose the action set
{[}A], but the probability of the classifier being selected by the
Genetic Algorithm for reproduction would be dependent only on the
fitness. Wilson stated that this which would pressurise the creation
of accurate generalisations.

Secondly, he proposed a \emph{niche-based} Genetic Algorithm to treat
match sets {[}M] more fairly.

\paragraph{XCS Parameters}

XCS uses a number of parameters in its algorithms. These are summarised
here for reference.

\begin{center}
%
\begin{table}
\begin{centering}
\begin{tabular}{|c|c|c|}
\hline 
Variable & Default & Description\tabularnewline
\hline
\hline 
$p_{j}$ &  & The {}``strength'' of the prediction\tabularnewline
\hline 
$\varepsilon_{j}$ & 0.0 & Prediction error\tabularnewline
\hline 
$\kappa_{j}$ &  & The accuracy of the classifier given the error\tabularnewline
\hline 
$\kappa'_{j}$ &  & Relative accuracy of the classifier to other members of {[}A]\tabularnewline
\hline 
$F_{j}$ & 0.01 & The fitness of the classifier, based on the accuracy\tabularnewline
\hline 
$\alpha$ & <1 & Falloff parameter for calculating accuracy from error $(0<\alpha\leq1)$\tabularnewline
\hline 
$\beta$ & 0.1 & The learning rate parameter $(0<\beta\leq1)$\tabularnewline
\hline 
$\chi$ & 1 & Probability of crossover on two classifiers in {[}M]\tabularnewline
\hline 
$\mu$ & 0.05 & Probability of mutation on two classifiers in {[}M]\tabularnewline
\hline 
$\gamma$ &  & Discount factor used to calculate $P$\tabularnewline
\hline 
$N$ &  & Maximum number of rules in the population\tabularnewline
\hline 
$\theta$ & 50 & The number of iterations before the GA is evoked on {[}M]\tabularnewline
\hline 
$\delta$ & 0.1 & Value of the fraction in deletion method (2)\tabularnewline
\hline 
$\varepsilon_{0}$ & 0.01 & Error threshold beneath which accuracy is set to 1\tabularnewline
\hline
\end{tabular}
\par\end{centering}

\caption{Parameters used in XCS}
\label{tab:xcsparameters}
\end{table}

\par\end{center}


\subsubsection{XCS Fitness Calculation Procecure}

In normal ZCS a condition C causes an action A, which in turn predicts
a payoff P via its prediction\emph{ strength}. This strength both
predicts payoff and functions as the classifier's fitness for the
Genetic Algorithm. In XCS, there are several fitness parameters associated
with each classifier:

\begin{itemize}
\item Fitness $F$ which tends towards the \emph{relative accuracy }which
is calculated from the...
\item Prediction error $\varepsilon$, which is calculated as the difference
between the discounted reward (P) and the...
\item Predicted payoff $p$
\end{itemize}
Reinforcement occurs by updating $p$, $\varepsilon$, and $F$, and
occurs every time a classifier belongs to the previous action set
$[A]_{-1}$ (or {[}A] in single step problems). 


\paragraph{Adjusting Fitness F}

Fitness is a metric which defines the classifier's accuracy relative
to the other classifiers in the set. For each classifier in $[A]_{-1}$,
the fitness $F_{j}$is recalculated using the current value of $\varepsilon_{j}$
in three steps:


\paragraph{Calculating the accuracy}

The accuracy $\kappa_{j}$ of the classifier is calculated, based
on the prediction error $\varepsilon_{j}$ and the error threshold
$\varepsilon_{0}$:

\[
\kappa_{j}=exp\left[(ln\alpha)(\varepsilon_{j}-\varepsilon_{0})/\varepsilon_{0}\right]\]


Alternatively:

\[
\kappa_{j}=\alpha\left(\frac{\varepsilon_{j}}{\varepsilon_{0}}\right)^{-n}\]


For $\varepsilon_{j}>\varepsilon_{0}$, otherwise $1$. This function
weights the accuracy highly for low values of $\varepsilon_{j}$ with
a sharp drop-off for higher values (depending on the value of $\alpha$).
The second function is displayed graphically in Figure \ref{fig:xcs-accuracy-graph}
below.

%
\begin{figure}
\begin{centering}
\includegraphics[width=0.5\textwidth]{accuracy-from-error}
\par\end{centering}
\caption{An accuracy function in XCS}
\label{fig:xcs-accuracy-graph}
\end{figure}



\paragraph{Adjusting Fitness}

The \emph{relative }accuracy $\kappa'_{j}$ for the classifier is
computed by dividing its accuracy by the total of accuracies in the
action set.

Relative accuracy adjusts the fitness $F_{j}$. If fitness has been
adjusted at least $\frac{1}{\beta}$ times, $F_{j}\leftarrow F_{j}+\beta\left(k'_{j}-F_{j}\right)$
otherwise $F_{j}$ is set to the average of the current and previous
values of $\kappa'_{j}$.


\paragraph{Calculating the discounted reward P}

Take the maximum prediction value $p(a_{i})$ value from the prediction
array. Discount it by multiplying by $\gamma$, and add to it any
immediate external reward from the \emph{previous time step}. The
resulting quantity is named $P$.

\[
P=max\left(p(a_{i})\right)\gamma+r_{imm_{-1}}\]



\paragraph{Adjusting the prediction error $\varepsilon_{j}$}

$\varepsilon_{j}$ is adjusted using $P$ and the current value of
$p_{j}$, this is done by adjusting $\varepsilon_{j}$ so that it
tends towards the absolute difference $\left|P-p_{j}\right|$:

\[
\varepsilon_{j}\leftarrow\varepsilon_{j}+\beta\left(\left|P-p_{j}\right|-\varepsilon_{j}\right)\]


Only if the classifier has been adjusted at least $1/\beta$ times.
Otherwise the new value is the average of the previous and current
values. Therefore, if the difference between $P$ and $P_{j}$ is
large, the error will increase and the fitness will decrease.


\paragraph{Adjusting $P_{j}$}

$P$ is then used to update the predictions of the classifiers in
$[A]_{-1}$using the following rule:

\[
p_{j}\leftarrow p_{j}+\beta\left(P-p_{j}\right)\]


Only if the classifier has been adjusted at least $1/\beta$ times.
Otherwise the new value is the average of the current and previous
values of $P$. This is called Moyenne Adaptive Modifiee (MAM), and
exists to ensure that the initial (arbitrary) value of $P_{j}$ can
move to its {}``true'' position first.


\paragraph{Niche Based Genetic Algorithm}

The GA is run in a match set if the number of time-steps since the
last GA in that match set exceeds a certain threshold. Each classifier
is time stamped at birth with the current time-step. When a match
set is performed its \emph{average} time stamp is calculated. The
GA is executed if the average time is older than the threshold$\theta$. 

This \emph{niche} based GA, (as opposed to the \emph{panmictic} GA
in ZCS which operates on the population at large), helps to remove
competition between niches that would cause high payoff actions to
dominate the population. It may also improve the learning rate as
crossover between necessarily similar classifiers in a match set is
more likely to be lress destructive than crossovers between possibly
completely unrelated individuals.

As in ZCS the genetic algorithm works on the match set {[}M] from
which two classifiers are selected using fitness proportional selection.
Crossover is performed on the copies with probability. If {[}P] contains
fewer than $N$ members, no deletion need occur to make room. For
the deletion scheme when this is not the case, see Section \ref{sub:Extended-Deletion-Scheme}.


\paragraph{Macroclassifiers}

When a new classifier is generated by the Genetic Algorithm, the population
is scanned to see if another one exists with the same condition and
action. If this is the case then the \emph{numerosity} on the existing
classifier is increased by one, rather than having two copies. This
allows the number of classifiers, $N$ to remain constant, but the
working number of classifiers actually decreases so performance improves
as better generalisations are discovered.

If a macroclassifier is selected for deletion its numerosity is decreased
by one, if numerosity is 0 then it is removed from the population
altogether.


\paragraph{Extensions to XCS}

\subparagraph{Genetic Algorithm}

Wilson later suggested an improvement \cite{wilson98generalization},
to conduct the GA on the action sets {[}A] and $[A]_{-1}$instead
of the match set {[}M]. Wilson stated that if a match set {[}M] is
to contain accurate and maximally general classifiers for all available
actions, they would often have different conditions. Therefore if
these are bred together, the crossover operator may still be destructive.
Therefore crossover should only occur on actions with similar conditions
and similar actions.

\subparagraph{Subsumption Deletion}

Wilson proposed a nice addition to his system \cite{wilson98generalization},
in which a new classifier whose condition is subsumed by an existing,
accurate, more general classifier, the new classifier is replaced
with a clone of the subsuming classifier, that is to say that the
subsuming classifier becomes a macroclassifier. This would remove
\emph{unnecessarily }specialised classifiers.

Wilson suggested that when two parents produce an offpspring, the
offspring should be checked to see if the child's condition is logically
subsumed by either of its parents' conditions. If this is the case
then the offspring is removed and the subsuming parent's numerosity
is increased by one.


\paragraph{Pitfalls using XCS}


\subparagraph{NB: Classification Accuracy}

Kovacs and Kerber \cite{kovacs-high2004} demonstrated Wilson's argument
that high classification accuracy alone does not imply effective genetic
search. The covering algorithm in ZCS and XCS allows the system to
improve without the use of the evolutionary algorithm. They showed
that XCS was able to provide good results on boolean multiplexer problems
even when the GA was complely turned off although it requires a much
larger population of rules.


\subparagraph{Extended Deletion Scheme \label{sub:Extended-Deletion-Scheme}}

Kovacs \cite{kovacs99deletion} pointed out that the deletion schems
in XCS is the same as that in standard Genetic Algorithms, despite
XCS having a different evaluation mechanism. An XCS classifier can
only be fully evaluated after many interactions (at least $1/\beta$)
with the environment. Therefore the outcome of removing classifiers
with regard only to their fitness may actually penalise \emph{new}
individuals instead of truly unfit ones. He suggested a system to
protect poorly evaluated chromosomes and demonstrated that it can
outperform both of Wilson's original techniques.

Wilson suggested two deletion techniques for XCS. The first, which
applies no deletion pressure on unfit individuals is as follows:

\begin{quotation}
{}``1. Every classifier keeps an estimate of the size of the match
sets in which it occcurs. This estimate is updated every time the
clasifier takes parts in an {[}M] using the MAM%
\footnote{Moyenne Adaptive Modifiee%
} technique with rate $\beta$. A classifier's deletion probability
is set proportional to the match set size estimate, which tends to
make all match sets have about the same size''
\end{quotation}
The second technique was a slight modification on the first so that
unfit individuals are deleted with higher probability.

\begin{quotation}
{}``2. The classifier's deletion probability is as in (1), excepts
if its fitness is less than a small fraction $\delta$ of the population
mean fitness. Then the probability from (1) is multiplied by the mean
fitness divided by the classifier's fitness''
\end{quotation}
Kovacs suggested that each of these techniques is an extreme, with
one which doesn't punish unfit classifiers at all, and the second
one which punishes all unfit classifiers, which may prevent new classifiers
from becoming established.

He proposed a third scheme:

\begin{quotation}
{}``3, A hybrid in which (1) is used until a classifier has been used on $n$ occasions, after which (2) is used''
\end{quotation}
He showed that this scheme performed better on both the 6-bit-multiplexer problem and the even parity problems (both of which are single-step problems). As the problems in computer vision covered by this project are largely single-step problems, we will also implement this modification.

\paragraph{Experiments}
The results from experiments by Wilson using XCS have generally concerned boolean multiplexer problem, or a multi-step animat problem in a {}``woods'' environment. Each of these problems is noiseless and has a small number of inputs. {[}Make mention of non-markovian environments].