%\documentstyle[eclepsf]{article}
\documentstyle{article}

\textheight 230mm
\topmargin 5mm
\textwidth 160mm
\oddsidemargin -2mm

\begin{document}
\noindent
{\bf Greedy Detector Generating Algorithm:} This is also picked up from
Ayra et al.~(2002) Let me quote what authors wrote, rather than paraphrase it:

\begin{quotation}{\it
Assuming a binary representation of
the self and detector strings, the r-contiguous bits
matching rule compares a sequence of bits (of length r)
in one string with a sequence of bits of the same length
in the second string to see if they match. 

Assuming a matching threshold r, an alphabet size m
(usually binary) and a length l, which is the length of
each string, the first phase involves the generation of
valid detector templates from a total number of $m^r$
possible combinations. 

Templates are strings with r-contiguous
significant bits that start from a specified bit
position; and l - r insignificant bits replaced with don�ft
cares. 

Each template is constructed from a sequence of
r bits that can be extended to fully specified detector strings. 

The set of valid templates are based on the self-data,
such that only templates with no match in self are generated. 

These templates make up the first template array 
$T_S$ where the nonzero entries constitute the valid
templates.

During the second phase, detectors are generated
through the extension of the templates to fully specified
detector strings. After the generation of each detector
string, all the templates that match the detector are
removed from the set of valid templates for generating
detectors. This prevents the generation of redundant and
inefficient detectors at each step.

Work in (de Castro and Timmis 2002) proposed a slight
modification of the exhaustive stage of the negative

Somatic hypermutation:
Briefly, the procedure proposed the following: (1)
define self data; (2) generate a candidate detector
randomly; and (3) match each candidate detector with
self data, if it matches, perform guided mutation on
detector away from self. The guided mutation is
performed on the candidate detector, which matches the
self data. Mutation is then performed on the parts of the
candidate detector that match with the self element. The
mutation is adaptive, based on the affinity of the closely
matching self element to a candidate detector. This
means that the probability of mutation is directly
proportional to affinity. Thus, the greater the affinity,
the higher is the mutation probability. This idea was
taken from the affinity maturation process of B-cells to
antigenic patterns in the immune system. In this
algorithm, however, the reference is the self-set, instead
of non-self set. Hence, the mutation is performed
proportionally to affinity to self-set, such that the
candidate detector is changed so as not to match self-set.
Also, this mutation approach was further
augmented by the introduction of a life time indicator
for a candidate detector. This in effect restricted the
number of times mutation is performed on a candidate
detector before a non-improved mutant is discarded. It
was thought to have the desired effect of reducing the
search space and hence, the number of candidate
detectors generated.

The affinity between these binary strings (for the self-set,
detector set and test data) was determined using the
r-contiguous bits matching rule. The optimal value for
matching threshold ( r ) had to be obtained by changing
values of r from 1 to l. This process was done in order
to obtain the combined values of correct and incorrect
classification by detectors generated using a specific
threshold. Correct classification value is derived from
the sum of true positive (rate at which non-self is
correctly detected) and true negative (rate at which self
is correctly not detected). While incorrect classification
is the sum of false positive (rate at which self is
incorrectly detected) and false negative (rate at which
non-self is not detected). Both the correct and incorrect
classification values are used to determine the
appropriate values of r.

The following procedure was carried out to determine this parameter:
1. Generate self and test sets from the data sets being experimented upon;
2. Generate required detectors $N_R$,using equation: 
\begin{displaymath}
N_R=\frac{-\ln (P_f)}{P_m}
\end{displaymath}
for different values of r which are varied from 1 to l;
3. Test the detectors generated on the test file to
obtain their correct and incorrect classification rates;
4. Use the value of r for which there is minimal
incorrect classification and maximum correct
classification rates in subsequent experiments.

The mutation probability (mutProb) is a threshold that
determines whether a bit position in a binary string will
be mutated or not. This value was initially implemented
using an adaptive mechanism which is calculated as the
length of the matching bits in two binary strings divided
by the length l of the binary string. The value generated
is a real number between 0.0 and 1.0. This threshold
value is then used to determine whether a bit position is
subjected to mutation. For each bit position to be
mutated, if a randomly generated number between 0.0
and 1.0 is less than the mutation probability, the bit is
mutated. The converse is the case when the random
number is greater than the mutation probability. In
(Ayara, Timmis et al. 2002), the adaptive mutation
probability was discovered to degrade the time
complexity of the algorithm if the probability is greater
than a specific value. This is because the probability
indicates that a sizeable fraction of the total number of
bits in a random binary string matches self. Hence the
process of mutating a random detector is restricted to
limited options. This can be explained by a matching
threshold r = 8. In this case, the mutation probability is
1 and the process of mutation just flips a random
detector to its image. In a situation that the image also
matches self, mutation flips back to the original
detector which also matches self. If this is the case for a
significant number of random detectors generated, the
time complexity is increased considerably. However
there is a threshold value below which this will not
occur. For example, the results of experiments in
(Ayara, Timmis et al. 2002) show that using 8-bits
binary data generated randomly the maximum mutation
probability that will not make the algorithm worse off
than the original exhaustive, for threshold values of 7
and 8, was confirmed to be 0.8. This directed the choice
of mutation probability for subsequent experiments,
which was set to 0.5.

The detector life-time indicator (mutLim) determines
the number of attempts that mutation can be performed
on a random detector. When values of this parameter
are greater than 1, it was found to increase the time
complexity of NSMutation when used with adaptive
mutation probability. This phenomenon can be linked to
the explanation given in section 6.1.3, which accounts
for the poor behaviour of the algorithm using adaptive
mutation probability. In a situation when the mutation
probability is above a specific value, and the limited
detector options that mutation can generate also match
with self, an increase in life-time indicator only extends
the time for the flipping the detector back and forth
between the image and the original detector.
}
\end{quotation}


\newtheorem{algorithm}{Algorithm}

\begin{algorithm}[Exhaustive Detector Generating Algorithm]
After preparing S --- a set of self samples
and setting D --- set of detectors to empty set, algorithm follows:
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[1] Create a population of candidate detector at random.
\item[2] For each of candidate detector:
   \begin{itemize}
   \item[(i)] match the candidate detector with self data;
   \item[(ii)] If it matches with any self data, then it is descarded
               ELSE it is added to D
   \end{itemize}
\item[3] Step 1 and 3 are repeated until  $\vert D \vert < m$.
\item[4] Return D
\end{itemize} 
\end{algorithm}


\end{document}