\documentstyle[eclepsf]{llncs}

%% \title{Can a negative selection detect unique non-self cell 
%% in infinitely large sample of self cells?}

\title{Can a negative selection detect only a few non-self cells
existed in an 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 that assert
a negative selection algorithm can successfully distinguish non-self cells
from self cells, especially frequently in a context of ``Network Intrusion Detection
by Artificial Immune System'' in which self cell is assumed to represent normal transaction
while a non-self cells represent anomaly. 
They further assert a negative selection gives us
an advantage that we can only use 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. 
We, however, suspect its applicability more or less.
This paper gives it a consideration to one of the latest such approaches.
%% This paper, however, does not intend to show a counter example but instead intend to 
%% call challenges or at least to encourage
%% more robust system to detect a few anomaly patterns from enormous number of
%% normal patterns. 
\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 with showing the dowry 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}
} \end{small}\end{quotation}

\noindent
In real world, we have many problems in which it is easy to access to 
any one of the huge number of candidate solutions which could be a true sloution 
but mostlikely not and we don't know it in advance.\\

\noindent
The ultimate extreme is called {\it a-needle-in-a-haystack problem}. The originally proposed
form by Hinton \& Nowlan~\cite{hint} 
is that only one configuration of 20 binary bits should be searched for. 
In other words, the search space is made up of $2^{20}$ points and 
only one points is the target point. 
No information such as how close a currently point is to the needle. \


\noindent
Yet another one, {\it a-tiny-flat-island-in-a-huge-lake} --- this is a problem 
we came accross when we had explored a fitness landswcape
defined on all the possible synaptic weight values of   
a fully-connected spiking neurons to give them 
a function of associative memory. Our proposal is formalized as follows.


\newtheorem{test-function}{Test-function}
\begin{test-function}
{\bf (Tiny Flat Island in Huge Lake)} 
Assuming an $n$-dimensional hypercube all of whose coordinate $x_i$ $(i=1, �c,n)$
lies $[-1,1]$, find an algorithm to locate a point in the region $A$ all of  whose coordinates 
are in $[0, a]$ $(a \le 1)$.
\end{test-function}

\noindent
Many researchers in Artificial Immunne System community
have suggested us that it might be easy if we use Negative Selection.
The Negative Selection is a evolutionary selection mechanism by which 
immune system trains itself only using {\it self cells} as a training sample, 
so that it can recognize {\it non-self cells} afterwords.\\

\noindent
So, our idea is as follows. 
We try to test samples one by one, as many as possible,
whether each of those randomly picked up samples is the real solution or not.
If we find the {\it needle/island} during the search procedure by happen, 
then our goal is attained. We are more than lucky. 
During the procedure, whichever it might find the solution or not,
we train the system, in parallel, during the procedure with using those picked up samples. 
Then we expect the trained system will recognize the needle/island.\\

\noindent
In this paper, we approach the problem from this view point.
That is, we take it just a pattern classification problem, in general,  
under the constraint
that we have two classes one of which has an extremely few patterns
while the other has almost infinite number of patterns. 
Or, 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 the latest approaches, among others, from this point of view is by 
Ji \& Dasgupta~\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}
Then they proposed two algorithms: one is to generate detectors
of constant sized spheres and the other variable sized spheres. 
They asserted 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 self cells, which is of usual cases when we think of a network intrusion detection. 
In order to explore this issue, we formalize the problem as follows.
Assuming we have $n$-dimensional patterns all of whose real-valued coordinates lie
in $[-1,1]$ in which anomaly pattern has its coordinate whose value 
lie in $[-a,a]$ while all other patterns are normal patters.
This is just {\ a-tiny-island-in-a-huge-lake} mentioned above when we set $a$ a very small value.
We can control the difficulty of the task by changing the value of $a$.
In the ultimate case in which the pattern whose coordinates are all shrunk to zero,
is the problem called {\it a-needle-in-a-haystack}.


\section {Algorithm}
\noindent
Lots of algorithms to distinguish non-self patterns from self patterns have been proposed.
The goal of some of these algorithms is to create detectors 
which cover non-self space as much as possible.
Here, among others, we concentrate on the algorithm called 
{\em ``Augmented Negative Selection Algorithm with Variable-Coverage Detectors''}
proposed by Zhou Ji and D. Dasgupata (2004) and it's simpler version
in which constant sized detectors instead of variavle-sized are used proposed by 
the same authors in the same article~\cite{ji}.
The followings are these two algorithms 
we paraphrased the original ones with the semantics being intact.
Firstly, the simpler versions of the algorithm 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 randomly.
\item[2.] Create a hyper-sphere which has the radius $r_d$ and its
center locates at random in $[-1,1]$. 
This is a candidate detector to detect non-self cells.
\item[3.] If this-hyper shpere does not contain any self cells, then put it as a detector
in $D$ --- the detector's repertoire. Otherwise delete the hyper-shpere.
\item[4.] Repeat 2-3 until we find $N_d$ detectors.
\end{itemize}
\end{algorithms}

\noindent
This algorithm does not contain the concept of Negative Selection or whatever in Immune System
metophor neither. The second one is:

\begin{algorithms}[Constant-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 less than the radius $r_s$, 
then add the sphere whose center is {\bf x} and radius is $r$ to $D$ as a new valid detector.
\item[4.] If such {\bf x} cannot be found within the time
$1/(1 - c_{\mbox{\tiny max}})$
then terminate the run.\footnote{See also the footnote above.}
Otherwise repeat 2 and 3, until we find a predefined 
number of detectors.
\end{itemize}
\end{algorithms}

\noindent
We don't think this algorithm also does not strongly reflects an Artificial Immune System,
despite the title of the original paper indicates.
However at least title holds true
in the sense that detectors are chosen 
by matching them to the self strings and if a detector matches 
it is discarded, otherwise, it is kept.

\section{Experiment, Results, and Discussion}
We assume here
the whole universe is $n$-dimensional hyper-cube $[-1, 1]^n$;
any point all of whose coordinates lie in $[-a, a]$ where $0<a<1$ are
a non-self cell, whilst other points in the universe are self cells; 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 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 sample,
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 ones in the original proposition~\cite{ji}.\\

\noindent
% Both the regions claimed normal and abnormal when $r_s$ is set to 0.1are shown in the Figure 1.
Nomal moints and created detectors when we set $r_s = 0.1$ which is recommended
by the original proposition~\cite{ji} are shown in Fig.~1.

\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{The points employed in the 2-D experiments. A set of five hundred self-sells (Left),
and a set of five hundreds detectors created by the Algorithm-1 with the value of $a$ being 0.5
and $r_s = 0.1$ (Right).}
 \end{center}
\end{figure}

\noindent
Our goal, however, is to recognize non-self patterns from extremly tiny reageon.
Hence the next experiment is a dependency on the value of $a$.
Fig.~2 shows the number of required trial to find the pre-defined number of 
detectors, which is 500 here, and ... As we can see in the Figure
The dificulty of the task becomes hard exponentially, and therefore
we know this algorithm would not work if the region to be searched for 
is extremly tiny.

\begin{figure}[h]
 \begin{center}
 \epsfile{file=result-1.eps,width=6.0cm,height=4.6cm}
 \epsfile{file=result-2.eps,width=6.0cm,height=4.6cm}
\caption{The number of iteration required to find $N_d$ detectors 
versus the value of $a$ when we experimentd with the Algorihtm-1
with $r_s = 0.1$ (Left).}
 \end{center}
\end{figure}

\begin{figure}[h]
 \begin{center}
 \epsfile{file=hist-20.eps,width=6.0cm,height=4.6cm}
 \epsfile{file=hist-2.eps,width=6.0cm,height=4.6cm}
\caption{The number of iteration required to find $N_d$ detectors 
versus the value of $a$ when we experimentd with the Algorihtm-1
with $r_s = 0.1$ (Left).}
 \end{center}
\end{figure}

\noindent
Also the relation between $r_s$ and the detection-rate/false-alarm trade-off will be shown.
That is, correctly detected rate and false alarm rate will be plotted against $r_s$ changed 
from 0.01 to 0.20 (not shown in this submission paper, though.) 

\subsection{A 20-dimensional version of an island in a lake}
Here experiments are performed on the test-bed that we call 
{\it 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.}
which is an extension
of {\it a-needle-in-a-haystack-problem} --- a reminiscent of the seminal experiment by
Hinton \& Nowlan~\cite{hint}.\\

\noindent
In a preliminary experiment, we found it 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
to 10000 from 1000, the distribution of the sample is very sparce under the condition of
$n = 20$. If the algorithm works well, the detector are supposed to locate in the non-self region,
such as Fig.~1 (Right), while the result is not in that way as shown in Fig.~3 (Left).
The coordinates of whole detectors are almost uniformly distributed. 
We will furthe explore different parameter values
with the goal being to learn the limit of the size of non-self domain
in which the algorithm can detect the non-self cells. 
Then we will experiment by lowering the value $c_0$ which is
99.99\% and 99\% in the original version.\\

\noindent
Further, we give it a consideration of how the Algorithm-2, Variable sized detector,
improve the situation.












\section{Conclusion}
We have obtained the similar results with the experiments by Zhou et al~\cite{ji}
on the condition that the island is not so small, that is,
the value $a$ is sufficiently large.\\

\noindent
Usually, however, in the real world problem, anomaly patterns
are extremely fewer than the normal ones. 
As such, our concern is on this case. 
Unfortunately, we have not so far observed a satisfactory result under this situation.
In fact, Ji et al.~ denotes 
\begin{quotation}
\noindent
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 they went on to write {\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 a kind of comparable in usual such experiment.



%% \subsection{boundary dilemma}



\section{Others of our Related Works}
We are exploring the same target --- {\it a-tiny-flat-island-in-a-huge-lake},
or its binary version, with a number of different approaches.
So far we are progressing the experiments
using (1) a negative selection of binary detector using r-contiguous matching to detect
{\it a-needle-in-a-haystack}; (2) evolving a set of fuzzy rules to detect non-self cells
in {\it a-tiny-island-in-a-huge-lake}; (3) the same as (2) but using a data-mining techniques.\\

\noindent
The objective of these series of works is to detect anomaly phenomena
which take place only occasionally and hence we don't know how does it look,
while we have enormous amount of daily normal phenomena.
As far as we know this is still an open issue and we try to find some approaches,
or at least evoke interests to this problem.
The challenge awaiting us is to find a more effective algorithm to find detectors
to detect tiny amount of non-self patterns.





\begin{thebibliography}{99}

\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 (ACS) and Computer Information Systems
and Industrial Management Applications (CISIM), 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


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


\end{thebibliography}
\end{document}

