\documentstyle[eclepsf]{llncs}

\title{Can a Negative Selection Detect an Extremely few Non-self
among Enormous Amount of \\Self Cells?}

\author{Akira Imada}
\institute{Brest State Technical University\\
           Moskowskaja 267, 224017 Brest, Republic of Belarus\\
           akira@bsty.by}

\begin{document}
\maketitle
\pagestyle{empty}
\thispagestyle{empty}

\begin{abstract}
We have had lots of reports in which they asserted 
a negative selection algorithm successfully distinguished non-self cells
from self cells, especially in a context of ``network intrusion detection'' 
where self patterns are  assumed to represent normal transactions
while non-self patterns represent anomaly. 
Furthermore they went on to assert a negative selection gives us
an advantage that we use only a set of self cells as training samples.
This would be really an advantage 
since we usually don't know what do anomaly patterns 
look like until they complete an intrusion when it's too late.
We, however, suspect, more or less, its applicability to a real system.
This paper gives it a consideration to one of the latest such approaches.
\end{abstract}

\section{Introduction}
\begin{quotation}\begin{small}
\noindent 
{\it 
\noindent
A sultan has granted a commoner a chance to marry one of his 100 daughters 
by presenting the daughters one at a time letting him know her dowry that had been 
defined previously.
The commoner must immediately decide whether to accept or reject her 
and he is not allowed to return to an already rejected daughter. 
The sultan will allow the marriage only if the commoner picks the daughter 
with the highest dowry. 
--- ``Sultan's Dowry Problem''~\footnote{
According to the author(s) of the web-page of 
Cunningham \& Cunningham, Inc. (http://c2.com)
the problem was probably first stated in Martin Gardner's Mathematical 
Recreations column in the February 1960 issue of 
The Scientific American.
To explore the problem more in detail, 
see, e.g., http://mathworld.wolfram.com. 
We thank Mariusz Rybnik at University Paris XII 
for suggesting that the problem is reminiscent of our context.}
} \end{small}\end{quotation}

\noindent
In real world, we have a problem in which we can easily access to 
any one of the possible candidate solutions,
most likely not but still have a few chance to be the true one,
which we don't know in advance.\\

\noindent
The ultimate extreme of such a problem
is sometimes called {\it a-needle-in-a-haystack} problem (see Fig.~1).
\begin{figure}[hb]
 \begin{center}
 \epsfile{file=a-needle-0.eps,width=8cm,height=1.5cm}
 \caption{A fictitious sketch of fitness landscape of 
          {\it a-needle-in-a-haystack}. The haystack here is drawn 
          as a two-dimensional flat plane of fitness zero.}
 \end{center}
\end{figure}
One of such a needle, originally proposed by Hinton \& Nowlan~\cite{hint},
is exactly the one configuration of 20-bit binary string, hence
the search space of which is made up of $2^{20}$ points and 
only one point is the target to be searched for. 
Therefore, no information such as 
how close is a currently searching point to the needle.\\

\noindent
Yet another problem, {\it a-tiny-flat-island-in-a-huge-lake} --- 
this is a problem 
we once came across when we had explored a fitness landscape
defined on all the possible synaptic weight values of   
a fully-connected spiking neurons to give them 
a function of associative memory~\cite{akir}. 
To simplify it we formalized the problem in more general form as follows.

\newtheorem{test-function}{Testfunction}
\begin{test-function}[A tiny flat island in a huge 
lake]\footnote{It is not necessarily to be said for the top of the island 
to be ``flat'', but the originally this was a test-bed for evolutionary 
computations, and the fitness of the island region is one, and zero 
in a lake region. That is why.}
Find an algorithm to locate a point in the region $A$ all 
of  whose coordinates are in $[-a, a]$ $(a < 1)$ in an universe of 
the $n$-dimensional hypercube 
all of whose coordinate $x_i$ lie in $[-1,1]$ $(i=1, �c,n)$.
\end{test-function}

\noindent
Many researchers in artificial immune system community
have suggested us that the problem might be easy 
if we use the concept of negative selection.
To simply put, the negative selection is 
an evolutionary selection mechanism by which 
immune system trains itself only using {\it self cells} 
as training samples, 
so that it can recognize {\it non-self cells} afterwards.\\

\noindent
The simplest 
%%search is a random but not exhaustive one, that is,
option is to test a set of samples one by one, as many as possible,
to know whether each of those samples is the true solution or not.
If we have a good luck, then our goal is attained. 
However, should we rather be more than lucky? 
As a trial, we train the system in parallel using those samples
during the procedure, regardless of 
whichever the real solution might be found or not as a result.
Then even if we are unlucky, 
we can at least expect that the system will recognize 
the true solution later after the training easier than before.\\

\noindent
In this paper, we approach the problem from this view point.
Or rather more in general, we take it a pattern classification problem,  
under the constraint that 
we have two classes one of which includes an extremely few patterns
while the other includes an almost infinite number of patterns. 
Thus, we might as well take it  a task of discrimination of 
a few of non-self cells as anomaly patterns
from enormous amount of self cells which represent normal patterns.\\

\noindent
One of such latest approaches among others is by 
Zhou~Ji and Dasgupata~\cite{ji}. They wrote

\begin{quotation}
\noindent
{\it The idea of negative selection was from T cell development process 
in the thymus. If a T cell recognizes self cells, it is eliminated 
before deployment for immune functionality. In an analogous manner,
the negative selection algorithm generates the detector set
by eliminating any detector candidates that match self
samples. It is thus used as an anomaly detection
mechanism with the advantage that only the negative (normal) 
training data are needed.} 
\end{quotation}

\noindent
Recalling our universe is $n$-dimensional Euclidean space, 
let us check two algorithms they proposed: one is to generate detectors
of constant sized hyper-spheres and 
the other is to generate variable sized hyper-spheres. 
They concluded that detectors which detect anomaly patterns 
are successfully created just by training with normal patterns.\\

\noindent
When we think of a network intrusion detection, we usually don't know
what do anomaly patterns look like in advance. Hence this feature of
training with only normal patterns is really advantageous.
Our concern then is what if the number of non-self cells 
is extremely smaller than the number of self cells, which is of usual cases 
when we think of a network intrusion detection. 
In order to explore this issue, we apply their algorithms to 
{\it a-tiny-island-in-a-huge-lake} mentioned above.
We can control the difficulty of the task by changing the value of $a$,
as well as the dimension of the universe.
%%and we set it to a very small value.
The ultimate case is when 
all of the coordinates of the target points shrink to zero,
and this is the problem known as {\it a-needle-in-a-haystack}.


\section {Algorithm}
\noindent
So far lots of algorithms to distinguish non-self patterns 
from self patterns have been proposed.
The goal of these algorithms is to create detectors 
which cover non-self space as much as possible.
Here, in this paper, we concentrate on the algorithm called 
{\em ``Augmented Negative Selection Algorithm with 
Variable-Coverage Detectors''}
proposed in 2004 by Zhou Ji and Dasgupata \cite{ji}, 
as well as its simpler version
in which detector size is constant instead of variable,
also proposed by the same authors in the same article.
The followings are these two algorithms that
we paraphrased the original ones with the semantics being intact.
Firstly, the simpler version is:

\newtheorem{algorithms}{Algorithm}
\begin{algorithms}[Constant-sized Detector Generation] After setting
(i) $N_t$, the number of training samples;
(ii) $r_d$, the radius of detector;
and (iii) $N_d$, the total number of detectors:
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[1.] Create $N_s$ samples of self cells at random.
\item[2.] Create a hyper-sphere which has the radius $r_d$ and whose
center locates at random in $[-1,1]$. 
This is a candidate detector to detect non-self cells.
\item[3.] If this-hyper sphere does not contain any sample self cells, 
then put it as a detector in $D$, the detector's repertoire. Otherwise delete the hyper-sphere.
\item[4.] Repeat 2-3 until we find $N_d$ detectors.
\end{itemize}
\end{algorithms}

\noindent
This algorithm, in our humble opinion, 
does not contain the concept of negative selection 
or whatever in an immune system metaphor neither, 
if not at all. The second one is:

\begin{algorithms}[Variable-sized Detector Generation]
After setting
(i) $N_t$, the number of training samples;
(ii) $r_s$, the radius of self cells;
(iii) $c_0$,  expected coverage, i.e., the degree
to how much those created detectors cover non-self cells;
(iv) $c_{\mbox{\tiny max}}$, the upper bound of self coverage;
and (v) $N_d$, the maximum number of detectors: 
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[1.] Empty $D$, the detector's repertoire. 
\item[2.] Try to find a point $\mbox{\bf x} = 
(x_1, \cdots, x_n) \in [-1,1]^n$
which is not contained by any of the valid detectors so far created, 
unless the number of those trials exceeds $1/(1-c_0)$.
If no such {\bf x} is found, then terminate 
the run.~\footnote{This is because
when we have sampled $m$ points and only one point was not covered, 
the expected coverage is $1-1/m$. Hence the necessary number of 
tries to ensure expected coverage $c_0$ is $m = 1/(1-c_0)$.}
\item[3.] If $r$, the distance between {\bf x} and 
its closest self sell in the training sample, is larger 
than the radius $r_s$, i.e.,
if the candidate doesn't include any of the sample self cells,   
then add the sphere whose center is {\bf x} and radius 
is $r$ to $D$ as a new valid detector.
\item[4.] If no such {\bf x} can be found within the consecutive trials of 
$1/(1 - c_{\mbox{\tiny max}})$ time,
then terminate the run.~\footnote{See also the footnote above 
replacing $c_0$ with
$c_{\mbox{\tiny max}}$.}
Otherwise repeat 2 and 3, until we find a total of $N_d$ detectors.
\end{itemize}
\end{algorithms}

\noindent
We do not think this algorithm strongly reflects an immune system either,
despite the title of the original paper indicates it.
However at least the title holds true
in the sense that detectors are chosen 
by trying to match them to the self strings and if a detector matches 
then it is discarded, otherwise it is kept. This is, above all, 
what we call a natural selection algorithm.


\section{Evaluation of How it Works}
We use a measure originally proposed by Lopes et al.~\cite{lope} in which
four quantities, i.e., 
(i) true-positive, (ii) true-negative, (iii) false positive, 
and (iv) false negative are used.
Here we assume positive sample is non-self and negative sample is self,
since detectors are designed to detect non-self cells.
Hence, these four terms  are defined in the sence that
(i) $t_p$ (true positive) --- true declaration of positive sample, i.e., 
non-self declared as non-self
(ii) $f_p$ (false positive) --- false declaration of positive sample, i.e., 
self declared as non-self
(iii) $t_n$ (true negative) --- true declaration of negative sample, i.e., 
self declared as self
(iv) $f_n$ (false negative) --- false declaration of negative sample, i.e., 
non-self declared as self.
Under these definitions 
$d_r = t_p/(t_p + f_n)$ implies detection rate, and 
$f_a = f_p/(t_n + f_p)$ implies false alarm rate.

\section{Experiment, Results, and Discussion}
As a preliminary experiment, we tried a random search
for the needle in the 20-dimensional haystack by creating 
5000 candidate strings at random,
and checking, one by one, if each of the sample is the needle or not.
We assume we have only one needle which principally we don't know where.
The result is shown in Fig.~2, and we found
it is still not such a difficult problem if we use
a standard PC found everywhere nowadays.\\ 

\begin{figure}[h]
\begin{center}
\epsfile{file=mesa-random-modified.eps,width=7cm,height=4cm}
\caption{The number of happened-to-be-the-needle out of 
          5000 random creations of the candidate.}
\end{center}
\end{figure}
\noindent
Taking this random search as our {\it placebo} experiment,
what will happen if we exploit one of the lately reported
more sophisticate methods?
We now assume
the whole universe is $n$-dimensional hyper-cube $[0, 1]^n$ 
as mentioned already;
any point all of whose coordinates lies in $[(0.5-a), (0.5+a)]$ ($0<a<0.5$)
%% where points in $0<a<0.5$ are
is non-self cell, whilst other points in the universe are 
self cells~\footnote{We modify our Testfunction-1 for the sake of 
simplicity of coding in this way, which keeps  the problem
equivalent to the original one.}; and all the self cells are 
hyper-sphere whose radius is  $r_s$.

\subsection{A 2-dimensional version of an-island-in-a-lake}
First of all, in order for our eyes to be able to observe 
the behavior of the algorithms, our experiment is performed on 
a 2-dimensional space, that is, we set $n=2$. 
We employ a set of 500 randomly selected points in the self region 
as the training samples,
and 1000 points randomly chosen from entire space is the test data.
The reason of these settings is to enable us
to compare our results with those in the original proposition~\cite{ji}.\\

\noindent
Both the regions claimed normal and abnormal when $r_s$ is set 
to 0.1 are shown in Fig.~3.
The location of the self points in the training sample
and the created detectors when we set $r_s = 0.1$ which is 
the value recommended by the original proposition~\cite{ji} 
are shown in Fig.~3. So far so good.
\begin{figure}[h]\label{fig:self-nonself}
 \begin{center}
 \epsfile{file=self.eps,width=6.0cm,height=4.6cm}
 \epsfile{file=detector.eps,width=6.0cm,height=4.6cm}
 \caption{A set of five hundred self-points employed as training 
          samples (Left),and a set of five hundreds detectors created by 
          the Algorithm-1 with $a=0.25$ and $r_s = 0.1$ (Right) from 
          an experiment in 2-dimensional space.}
 \end{center}
\end{figure}
\begin{figure}[h]
 \begin{center}
 \epsfile{file=result-2.eps,width=6.0cm,height=4.0cm}
 \epsfile{file=result-1.eps,width=6.0cm,height=4.0cm}
 \caption{The number of iteration required to find 500 successful 
          detectors (Left), and the number of successes when 500 detectors 
          tried to detect 500  non-self samples, that is, the number of 
          successes out of 25000 events (Right). Both are as a function of 
          value of $a$ when we experimented with the Algorithm-1 
          with $r_s = 0.1$ in 2-dimensional space.} 
 \end{center}
\end{figure}
However, our goal is to recognize non-self patterns from extremely 
tiny region.
Hence the next experiment is a dependency on the value of $a$.
Fig.~4 shows the number of required trials to find the pre-defined number of 
detectors, which is 500 here, and
the number of successes when those 500 detectors tried to detect 
the 500 non-self samples. 
Both are plotted as a function of value of $a$ 
using the Algorithm-1 with $r_s = 0.1$ to create the detectors. 
As we can see in the Figure,
the difficulty of the task becomes harder exponentially as $a$ 
becomes smaller, and therefore
we know this algorithm would not work if the region to be searched for 
is extremely tiny.\\

\subsection{A 20-dimensional version of an-island-in-a-lake}
Next of our interest is what happens when we increase dimensionality.
All we found was it becomes much more difficult than in the case $n = 2$.
What we found, for example, is even if we increase the number of 
training sample of self patterns from 1000 to 10000, 
the distribution of the coordinates of samples is very sparse when $n = 20$. 
If the algorithm worked well, 
the detector would be supposed to locate only in the non-self region,
such as Fig.~5 (Right) which is from a result of 
2-dimensional experiment for comparison purpose,
while the result in 20-dimensional experiment, as shown in Fig.~5 (Left), 
was not in that way.
\begin{figure}[h]
 \begin{center}
 \epsfile{file=hist-20.eps,width=6.0cm,height=4.0cm}
 \epsfile{file=hist-2.eps,width=6.0cm,height=4.0cm}
 \caption{The distribution of all the coordinates of the detectors 
          for an experiment with  $n=20$ (Left), and the distribution 
          when $n=2$ for the purpose of comparison (Right).}
 \end{center}
\end{figure}
We can see in the figure that 
the coordinates of the whole detectors are almost uniformly distributed, 
which means a failure to find a set of successful detectors.\\


\noindent
Then, we give it a consideration of how will 
the Algorithm-2 (Variable Sized Detector)
improve the situation. In an experiment in 20-dimensional space 
where the Algorithm-2 creates certain number of detectors 
with 1000 training samples of self patterns. 
Non-self region in this experiment
was $[0.495, 0.505]^{20}$ and radius of self was set to 0.1. 
As a result of a run under $c_0 = 0.99$, a total of 96 detectors 
are created.\\

\noindent
First, we studied how {\it true-positive} and 
{\it false-positive} rate are influenced by
dimensionality. As shown in Fig.~6 (Left), the perfect situation
when $n=2$ abruptly deteriorates even $n=3$. Alas!\\

\noindent
Next, we ran the algorithm for $n$ =  5, 15, 20, and 25 
to study a dependency of the degree to  how successfully the detector 
will be created on the dimension of search space.
The number of detectors created is somehow similar in each dimension, 
ranging from 91 to 96.
In Fig.~5 (Right), we show detection-rate and false-alarm-rate 
as a function of dimensionality.
Though not satisfactorily, we see somewhat of a successful result, 
at least as for detection-rate.

\begin{figure}[h]
 \begin{center}
 \epsfile{file=t-positive.eps,width=6cm,height=4cm}
 \epsfile{file=dr-fa-2.eps,width=6cm,height=3.85cm}
 \caption{(Left)   True-positive and False-positive as a function of 
                   dimensionality.
          (Right)  Detection-rate shown with circles and false-alarm-rate 
                   shown with rectangles as a function of dimensionality 
                   in a series of experiments where the Algorithm-2 creates 
                   certain number of detectors from 91 to 96 with 1000 
                   training samples of self patterns.}
 \end{center}
\end{figure}


\noindent
Further, we will explore different parameter values
with the goal being to learn the limit of 
how small non-self region and how large the dimensionality
under which the algorithm can detect non-self points successfully. 
Then we will experiment by lowering the value $c_0$ which is
99.99\% and 99\% in the original version.
Those results are not shown here
since our experiments have sometimes reversed our expectations so far.

\section{Conclusion}
We have obtained the similar results with the experiments 
by Zhou~Ji and Dasgupata~\cite{ji}
only on the condition that the domain of non-sell is not so small
and dimension is 2.\\

\noindent
Usually, however, in the real world problem, anomaly patterns
are extremely fewer than the normal ones. 
As such, our concern is on an extreme case. 
Unfortunately, we have not so far observed any satisfactory results 
under this extreme situation.
In fact, Zhou~Ji and Dasgupata~\cite{ji} wrote 
\begin{quotation}
\noindent
{\it
As an exception, the algorithm may
also terminate when it fails to sample any non-self point
after many repetitions. That implies that the
self region covers almost the entire space. It may happen
when the self samples are randomly distributed over the
space, or the chosen self-radius is too big.}
\end{quotation}
\noindent
And as they went on to write concerning another experiment
in the same paper~\cite{ji} {\it ``One of the three types of IRIS data 
is considered as normal data, while the other two are considered abnormal,''}
the number of normal and abnormal is usually comparable 
in such experiments.\\

\noindent
We are exploring a number of other different approaches
to the same target, that is, {\it a-tiny-flat-island-in-a-huge-lake}
or its binary version {\it a-needle-in-a-haystack}. 
What we have tried so far are experiments
by means of 
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[$\bullet$] Negative selection of binary detectors
with $r$-contiguous matching (See \cite{akir-2});
\item[$\bullet$] Immuno-fuzzy approach (See \cite{akir-3});
\item[$\bullet$] Evolving a set of fuzzy rules (See \cite{akir-4});
\item[$\bullet$] Fuzzy neural network approach (See \cite{akir-5});
\end{itemize}
and so on..., to detect a {\it tiny-island} or a {\it needle}.\\

\noindent
Though still a lot of experiments have been resistant to be positively
analyzed,
this series of works is not to show a counter example for an assertion,
but to call for challenges. 
The objective is to detect anomaly phenomena
which take place only occasionally and hence we don't know 
what does it look like,
while we have enormous amount of daily normal phenomena.
As far as we know, this is still an open issue and we are trying to find 
approaches. We hope this paper will evoke interests in this problem 
in our community. The challenge is awaiting us.
%% is to find a more effective algorithm to find detectors 
%% to detect tiny amount of non-self patterns.

\begin{thebibliography}{99}
\bibitem{hint} G.~E.~Hinton and S.~J.~Nowlan (1987)
``How Learning can Guide Evolution.''
Complex Systems, 1, pp.~495--502. 

\bibitem{akir} A.~Imada (2004)
``How a Peak on a Completely-flatland-elsewhere can be Searched for?
--- A Fitness Landscape of Associative Memory by Spiking Neurons.''
Proceedings of Advanced Computer Systems and Computer 
Information Systems and Industrial Management Applications, Vol.2, 
pp.~171--150.

\bibitem{ji} 
Zhou~Ji and D.~Dasgupata (2004)
``Augmented Negative Selection Algorithm with Variable-Coverage Detectors.''
Proceedings of the Congress on Evolutionary Computation, pp.~1081--1088.

\bibitem{lope}
H.~S.~Lopes, M.~S.~Coutinho, and W.~C.~Lima (1997)
``An Evolutionary Approach to Simulate Cognitive Feedback Learning 
in Medical Domain.''
Genetic Algorithms and Fuzzy Logic Systems, World Scientific, pp.~193--207.

\bibitem{akir-2} A.~Imada (2005)
``Can a Negative Selection Detect Unique Non-self Cell
in an Infinitely Large Number of Self Cells?''
Proceedings of the International Conference on 
Pattern Recognition and Information Processing,
pp. 127--131.
%% (on 18-20 May 2005 at Minsk Belarus.)

\bibitem{akir-3} A.~Imada (2005)
``Can an Immuno-fuzzy Approach Detect Only
a Few Non-self Cells Existed in an Enormous Amount of Self Cells?''
Proceedings of the International Workshop 
on Intelligent Data Acquisition and Advanced Computing Systems: 
Technology and Applications,
pp. 74--77.
%%(September 2005, Sofia, Bulgaria.)

\bibitem{akir-4} A.~Imada (2005)
``Can a Fuzzy Rule Look for a Needle in a Haystack?''
Proceedings of the 
Turkish Symposium on Artificial Intelligence and Neural Networks,
pp.~63--70.
%%(16-17 June 2005, Cesme, Izmir, Turkey.)

\bibitem{akir-5} A.~Imada (2005)
``Can a Fuzzy Rule Extraction Find an Extremely Tiny Non-self Region?''
Proceedings of the International Workshop on 
Artificial Neural Networks and Intelligent Information Processing,
pp.~35--41.
%%(September 2005, Barcelona, Spain)

\end{thebibliography}
\end{document}