%%\documentstyle[12pt,eclepsf]{article}
\documentstyle[eclepsf]{article}
\textheight 260mm
\topmargin 5mm
\textwidth 180mm
\oddsidemargin -7mm

\pagestyle{myheadings}
\markright{(ACS-CISIM'2005 -- at Elk, Poland)}
\thispagestyle{empty}

\begin{document}
\begin{Large}


%% --- (title) ---
\begin{center}
{\LARGE {\bf
Can a negative selection detect an extremely few non-self
among enormous amount of self cells?
}} \\
\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\ 
Akira Imada  \\
\hspace*{1in}\\
Brest State Technical University \\ 
Belarus
\end{center}

%% ----- motivation -----
\clearpage
\begin{center}
{\bf
Our Interest\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
a NETWORK INTRUSION DETECTION SYSTEM\\
\hspace*{1in}\\
in which \\
\hspace*{1in}\\
we need a set of TEST-DATA  \\
\hspace*{1in}\\
to TRAIN and TEST the system with.\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
a consideration on such a test-data.
}
\end{center}


%% --- 
\clearpage
\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\

\begin{center}
{\bf 
So many artificial data-samples have been proposed so far. \\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
Let's categorize them 
}
\end{center}


% ---
\clearpage
\noindent
{\bf $\Box$ Fictitious 2-D pictures of test-sample}
\begin{figure}[h]
 \begin{center}
  \epsfile{file=universe-minus-2.eps,width=4.5cm,height=6cm}
 \end{center}
\end{figure}

\begin{center}
%%{\large
E.g., \\
\hspace*{1in}\\
Fisher's IRIS Flower \\
KDD-cup 1999/2003
$\cdots$
%%}
\end{center}

% ---
\clearpage
\noindent
{\bf $\Box$ A visualization of IRIS data}\\
\begin{figure}[h]
 \begin{center}
   \epsfile{file=final-2d.eps,width=18cm,height=8cm}
 \end{center}
\end{figure}


% ---
\clearpage
\noindent
{\bf $\Box$ The data from KDD challange cup 98}\\

\begin{center}
4,920,210 data are given\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
each is made up of 42 attributes of which\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
4-crisp + 17-binary + 6-integer + 15-real\\
\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\
\noindent
Still infinitely large not-defiened possible transactions remain!
\end{center}

% ---
\clearpage
\noindent
{\bf $\Box$ Fictitious 2-D pictures of test-sample}\\
\begin{figure}[h]
 \begin{center}
  \epsfile{file=universe-minus-1.eps,width=10cm,height=6cm}
 \end{center}
\end{figure}

\noindent
{\large
\hspace*{1.7in}Fisher's IRIS Flower \hspace{0.85in}Ayara et al.\\
\hspace*{1.7in}KDD-cup 1999/2003    \hspace{0.85in}$\cdots$ \\
\hspace*{1.7in} $\cdots$
}

% ---
\clearpage
\noindent
{\bf $\Box$ Ayara's Random Anomaly in 8-bit Binary Universe}\\
\begin{figure}[h]
 \begin{center}
   \epsfile{file=ayara.eps,width=8cm,height=4cm}
 \end{center}
\end{figure}

\noindent
Asserted that successfully trained.

% ---
\clearpage
\noindent
{\bf $\Box$ What if abnormal sample are only a few?}\\
\begin{figure}[h]
 \begin{center}
   \epsfile{file=ayara-2.eps,width=8cm,height=4cm}
 \end{center}
\end{figure}

\noindent
Still can we train the system with normal and abnormal sample?


% ---
\clearpage
\noindent
{\bf $\Box$ Fictitious 2-D pictures of test-sample}\\
\begin{figure}[h]
 \begin{center}
  \epsfile{file=universe.eps,width=16cm,height=6cm}
 \end{center}
\end{figure}

\noindent
{\large
\hspace*{0.45in}Fisher's IRIS Flower \hspace{0.95in}Ayara et al.\\
\hspace*{0.45in}KDD-cup 1999/2003    \hspace{0.95in}$\cdots$ \\
\hspace*{0.45in} $\cdots$
}

%% --- forgery
\clearpage
\begin{center}
{\bf A sommelier who is trained only by real champagne \\
can tell the difference when given a bootleg or other sparkling wine?}\\
\end{center}
\hspace*{1in}\\
\noindent
{\bf $\Box$ Three of our concerns.}
\begin{itemize}
\item[1.] Data should cover the whole universe.
\item[] \hspace*{1in}$\Rightarrow$ We could miss crucial abnormal in 
                                   no-defined area. \\
\item[2.] Abnormal Sample should be assumed extremely tiny. 
\item[] \hspace*{1in}$\Rightarrow$ This is of usual case. \\
\item[3.] Can we train the sytem only by NORMAL data?
\end{itemize}





%% ----- motivation -----
\clearpage
\begin{center}
{\bf

Our Goal is \\
\hspace*{1in}\\
to search for only a few ABNORMAL (no-self) pattern \\
\hspace*{1in}\\
hidden in \\
\hspace*{1in}\\
an enormous amount of NORMAL (self) patterns\\
\hspace*{1in}\\
by \\
\hspace*{1in}\\
training using only NORMAL patterns
}
\end{center}



%% --- Our peculiar fitness landscape is somehow ...
\clearpage
\noindent
{\bf $\Box$ A test-sample
-- A tiny-flat-island-in-a-huge-lake}\\
\begin{figure}[h]
 \begin{center}
  \epsfile{file=universe-2.eps,width=4cm,height=4cm}
 \end{center}
\end{figure}

\begin{itemize}
\item Lake  $\Rightarrow$ $x_i \in [-1, 1]$ \hspace{.15in} $(i=1, �c,n)$
\item Island $\Rightarrow$ $x_i \in [-a, a]$ \hspace{.25in} $(a < 1)$.\\
\end{itemize}
\noindent
\hspace*{1.5in}--- We can control the complexity by changing the size. \\

%% --- Our peculiar fitness landscape is somehow ...
\clearpage
\noindent
{\bf $\Box$ From a fitness landscape point of view}\\
\begin{figure}[h]
 \begin{center}
  \epsfile{file=island-1.eps,width=15cm,height=3cm}
 \end{center}
\end{figure}




%% --- our problem might remind us of
%% also a schematic skecth on fictitious 2D-space
\clearpage
\noindent
{\bf $\Box$ A Needle in a Haystack}\\

\noindent
A schematic skecth on fictitious 2D-space
\begin{figure}[h]
 \begin{center}
   \epsfile{file=a-needle-0.eps,width=15cm,height=3cm}
 \end{center}
\end{figure}

\noindent
The original Hinton \& Nowlan's Needle: 
\begin{itemize}
\item A-needle $\Rightarrow$ Only one configuration of 20 bits of binary string.
\item Haystack $\Rightarrow$ $2^{20}-1$ search points.
\end{itemize}




%% due to a synaptic plasticity
%% cirtain reageon of top area

%% this is our terget function and  we can controll the complexity by...
%% but essentially equivalent to a-needle...
%%
%% but here our target is the extreme case of needle

%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ How can the detector be trained?}\\
%% Hinton Nowlan's needle is one configuration of 20 binary bits. So...

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=needle-b-box.eps,width=13.5cm,height=6cm}
 \end{center}
\end{figure}




%% --- how difficult
\clearpage
\noindent
{\bf $\Box$ How difficult?}\\

\begin{itemize}
\item Random Search  %% example  
\begin{center}
$2^{20} = 1,048,576$
\end{center}
%% within, say, 1 minute search at most.
%% we observed however, more than 25
\item[]
\item Lifetime Learning -- Baldwin Effect (Hinton \& Nowlan 1995?)
%% again not possible for more than 25 bits
\end{itemize}
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=a-needle-0.eps,width=10cm,height=2cm}
%% \caption{Search with lifetime learning (Boldwin Effect)}
 \end{center}
\end{figure}


%% \clearpage
%% \noindent
%% {\bf $\Box$ Random Search vs Baldwin Effect}
%% \begin{figure}[h] 
%%  \begin{center}
%%  \epsfile{file=member-s.eps,width=7cm,height=3.5cm}
%%  \epsfile{file=mu-1.eps,width=7cm,height=3.5cm}
%%  -----
%%  \epsfile{file=mesa-random.eps,width=16cm,height=5.0cm}
%%  \epsfile{file=mesa-learning.eps,width=16cm,height=5.0cm}
%% \caption{Number of individuals who happens to be in a point in the target
%%          region $A$ out of randomly created 10,000 individuals.}
%% \caption{Average Number of random individuals needed to find a one who 
%%          succeeded in reaching the target via 1000 times of lifetime 
%%          learning.}
%%  \end{center}
%% \end{figure}

\clearpage
\noindent
{\bf $\Box$ Random Search}
\begin{figure}[h] 
 \begin{center}
 \epsfile{file=mesa-random.eps,width=14cm,height=6cm}
 \end{center}
\end{figure}


%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ Let's try lately reported approaches\\
\hspace*{2in}each claims very SUCCESSFUL.}\\

\begin{itemize}
\item Artificial Immune System
\item Evolutionary Computation
\item Fuzzy Rule
\item Data-mining Technique
\item etc
\end{itemize}



%% ---
\clearpage
{\bf $\Box$ When a species of iris flower is normal 
then are others abnormal?}
\hspace*{1in}\\
\begin{center}
{\bf E.g., Kim \& Bentley (2001) claimed \\
\hspace*{1in}\\
assuming one subspieces of IRIS is abnormal 
while other two normal\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
the best TP rate reached 100\%  \\
the worst FP average rate was only 1\%.
}
\end{center}


%% ---
\clearpage
{\bf $\Box$ A Fuzzy Rule approach}
%% Not direct AIS but evolve fuzzy rule using AIS and or EC
%% 2. Fuzzy Rule for island -> figure
%%   (3 3 3 ... 3) -> but the smaller the more difficult

\begin{figure}[h]
 \begin{center}
   \epsfile{file=member-s.eps,width=7cm,height=3cm}
 \end{center}
\end{figure}

\begin{center}
$\Downarrow$ \\
\hspace*{2.5in}\\
$(M M M M M M \cdots M)$ \\
\hspace*{2.5in}\\
$\Downarrow$ \\
\hspace*{2.3in}\\
IF \{$x_1$ is Middle\}, $\cdots$, and \{$x_{20}$ is Middle\} THEN no-self.
\end{center}

%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ Island in the 6-D lake}\\  

\begin{center}
Fairly large island ($x_i \in [0.25, 0.75]$) 
\hspace{.1in}
vs.
\hspace{.1in}
Small island ($x_i \in [0.45, 0.55]$)\\
\hspace*{2.5in}\\
$\Downarrow$ \\
\end{center}


\begin{figure}[h]
\begin{center}
\epsfile{file=result-fuz2.eps,width=14cm,height=5.5cm}
\end{center}
\end{figure}


%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ A curse of dimension}\\
 
\begin{center}
For the island $x_i \in [0.45, 0.55]$ in the 20-D lake \\
\hspace*{2.5in}\\
$\Downarrow$ \\
\hspace*{2.3in}\\
(0 1 3 4 0 4 4 1 4 4 1 1 4 1 4 3 0 0 0 2)
\end{center}

\clearpage
\noindent
{\bf Shape/Location adaptive membersip function}
\begin{figure}[h]
 \begin{center}
   \epsfile{file=mu-2.eps,width=15cm,height=5cm}
%% \epsfile{file=singleton.eps,width=15cm,height=5cm}
 \end{center}
\end{figure}



\clearpage
\noindent
{\bf A Fuzzy Neural Network Approach}
\begin{figure}[h]
 \begin{center}
   \epsfile{file=fuzzy-nn.eps,width=15cm,height=7.5cm}
 \end{center}
\end{figure}





%% --- (Figure) ---
\clearpage
\noindent
{\bf A result of an evolution}

\begin{center}
{\it M}\\
\hspace*{2.5in}\\
$\Downarrow$ 
\end{center}


\begin{figure}[h]
 \begin{center}
   \epsfile{file=mu-1.eps,width=7cm,height=3.5cm}
 \end{center}
\end{figure}

%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ An immune approach
 --- Constant-sized hyper-shpere Detectors}\\
\begin{figure}[h]
 \begin{center}
   \epsfile{file=negative-s.eps,width=12cm,height=6cm}
 \end{center}
\end{figure}



%% ---
\clearpage
\noindent
{\bf $\Box$ A result in 2-D space}
\begin{figure}[h]
 \begin{center}
   \epsfile{file=detector.eps,width=12cm,height=6cm}
 \end{center}
\end{figure}

%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ What if top area shrinks to zero?}\\

\begin{figure}[h]
 \begin{center}
%% \epsfile{file=result-2.eps,width=6.0cm,height=4.6cm}
 \epsfile{file=result-1.eps,width=14cm,height=6cm}
%\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}


%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ Alas! As dimension grows...}\\

\begin{figure}[h]
 \begin{center}
 \epsfile{file=t-positive.eps,width=14cm,height=8cm}
\end{center}
\end{figure}



%% ---
\clearpage
\noindent
{\bf $\Box$ Conclusion}
\begin{center}
{\bf 
We usually don't know many ABNORMAL samples\\ 
(when we know them it's too late) \\
while we have huge NORMAL samples. \\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
Can training be performed only by using NORMAL samples? \\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
a-needle or tiny-island\\
as testdata for network intrusion detection"\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
Results have not been so wonderful.\\
Though we now are negative more or less, still want to be neutral.
}
\end{center}

\end{Large}
\end{document}


%% ===============================================================








%% --- before that topic of exploiting spiking neurons, our interest was on traditional... 
%% --- also using evolutinary computations.
\clearpage
\noindent
{\bf $\Box$ Fitness Landscape on all possible configuration of weights}\\

\begin{itemize}
\item Traditional Hopfield Model 
   \begin{itemize}
   \item[]$\Rightarrow$ Everywhere rugged and many peaks.
   \end{itemize}
\item[]
\item Spiking Neurons 
   \begin{itemize}
   \item[]$\Rightarrow$ unique peak and everywhere else 
                        is flatland of fitness 0.
   \end{itemize}
\end{itemize}

%% --- what is fitness landscape
\clearpage
\noindent
{\bf $\Box$ A fictitious plot of fitness landscape}\\
\begin{figure}[h]
 \begin{center}
  \epsfile{file=fitness-ls-2d.eps,width=11.25cm,height=6cm}
 \end{center}
\end{figure}





\clearpage
\noindent
{\bf $\Box$ Baldwin Effect}
\begin{figure}[h] 
 \begin{center}
 \epsfile{file=mesa-learning.eps,width=14cm,height=6cm}
 \end{center}
\end{figure}


%% --- When we talk about this issue in our community, many people claimed
\clearpage
\begin{center}
{\bf
They say \\
\hspace*{1in}\\
``Why don't you use Artifitial Immune System? \\
It'll be easy?''  \\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
Is it really true?
}
\end{center}






%% --- (Figure) ---
\clearpage
\noindent
{\bf 3. Negative Selection}\\

%here
%negative selection 
%with the target of extreme case of needle not island

%% --- (Figure) ---
%actually we reach the needle if n is small enough

\newtheorem{algorithms}{Algorithm}
\begin{algorithms}[Exhaustive Detector Generating Algorithm]
\hspace{.5in}\\
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[1.] Create $N_s$ samples of self cells at random;
\item[2.] Create a population of candidate detectors at random; 
\item[3.] Discard it if it matches self, otherwise 
          take it as a detector.
%% If it matches with any self cell, then it is discarded, 
%% otherwise it is added to D
%% \item[5.] Repeat 2 - 5 until D has $N_d$ valid detectors.
\end{itemize}
\end{algorithms}


%% --- (Figure) ---
\clearpage
\begin{figure}[hb]
 \begin{center}
 \epsfile{file=result.eps,width=14cm,height=6cm}
 %% \caption{Number of iterations needed to find a detector 
 %%            to detect the needle}
 \end{center}
\end{figure}

%alas worse than random search

%% --- (Figure) ---
\clearpage
\noindent
{\bf 3. Negative Selection -- II}\\
\hspace*{1in}\\
\begin{algorithms}[Greedy Detector Generating Algorithm]
\end{algorithms}

\hspace*{1in}
``perfect matching'' $\Rightarrow$ ``$r$-contiguous'' 



%% --- (Figure) ---
\clearpage
$\bullet$ Some 2-contiguous matching, e.g. (11*)  works when
\begin{table}[h]
\begin{center}
\begin{tabular}{c c c c c c}
(110) & (111) & (010) & (011) & $\Rightarrow$ & SELF  \\
(000) & (001) & (100) & (101) & $\Rightarrow$ & NO-SELF  \\
\end{tabular}
\end{center}
\end{table}



$\bullet$ Any 2-contiguous matching fails to detect no-self correctly when
\begin{table}[h]
\begin{center}
\begin{tabular}{c c c c c c}
(110) & (100) & (011) & (001) & $\Rightarrow$ & SELF  \\
(101) & (111) & (000) & (010) & $\Rightarrow$ & NO-SELF  \\
\end{tabular}
\end{center}
\end{table}

%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ A conclusion up to this moment}\\

\begin{itemize}
\item Still not easy, if it might not be impossible.
\item[]\hspace*{2in} $\Downarrow$
\item  Our original interst  on ``SEARCH FOR WEIGHTS''\\
is now on ``INTRUSION DETECTION''
\item[]where
   \begin{itemize}
   \item[$\star$] Train the system with only NORMAL samples.
   \item[$\star$] Needle/Island $\Rightarrow$ INTRUSION.
   \end{itemize}
\end{itemize}



%% --- (Figure) ---
\clearpage
\noindent 
{\bf $\Box$ When a flower of iris is normal then are others abnormal?}\\

\begin{center}
Many propositions so-far reported used \\
Fisher's IRIS\\
as a test-data to test the system we are designing.\\
\hspace*{1in}\\
But why IRIS?  Why not the other one? \\
\hspace*{1in}\\
They just say  \\
``Because this is a widely used benchmark data.''  $\Rightarrow$ Tautology?
\end{center}

%% --- (Figure) ---
\clearpage
\noindent 
{\bf $\Box$ What is IRIS dataset}\\
\begin{table}[h]
\begin{center}
\begin{tabular}{c c c c c}                                   \hline \hline
5.1      &   3.5    &   1.4    &   0.2    &   setosa         \\
4.9      &   3.0    &   1.4    &   0.2    &   setosa         \\
$\cdots$ & $\cdots$ & $\cdots$ & $\cdots$ & $\cdots$         \\
7.0      &   3.2    &   4.7    &   1.4    &   versicolor     \\
6.4      &   3.2    &   4.5    &   1.5    &   versicolor     \\
$\cdots$ & $\cdots$ & $\cdots$ & $\cdots$ & $\cdots$         \\
6.3      &   3.3    &   6.0    &   2.5    &   virginica      \\
5.8      &   2.7    &   5.1    &   1.9    &   virginica      \\
$\cdots$ & $\cdots$ & $\cdots$ & $\cdots$ & $\cdots$         \\ \hline\hline
\end{tabular}
\end{center}
\end{table}


%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ Let's visualize the Iris Dataset of 4D --- Sammon Mapping}
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=init-2d.eps,width=18cm,height=8cm}
 \end{center}
\end{figure}

%%what is sammon

%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ An evolution \\
\indent
--- minimizing the difference in distance relation as much as possible.}
\begin{figure}[h]
 \begin{center}
   \epsfile{file=iris-evolution.eps,width=18cm,height=8cm}
 \end{center}
\end{figure}

koko
%%KDD cup


%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ So far so good, but... }\\

\begin{center}
E.g., Kim \&Bentley (2001) \\
\hspace*{1in}\\
by taking one set as a SELF set and the rest as a NON-SELF set \\
\hspace*{1in}\\
using tenfold cross-validation 
method \\

\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\

``The best TP rate reached 100\%.''  \\
``The worst FP rate was only 1\%.''

\end{center}

%% ----- for example
\clearpage
\noindent
{\bf $\Box$ Conclusion I}

\begin{center}
{\bf 
Our proposal is to let's use rather \\
\hspace*{1in}\\
``tiny-island-in-huge-lake''\\
``needle-in-haystack''\\
\hspace*{1in}\\
or\\
\hspace*{1in}\\
``a random set of NO-SELF and exhaustive other points as SELF. \\(Ayara et al.)\\
\hspace*{1in}\\
All points in the space should be representative of transaction.\\

\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\

We doubt IRIS is not such a case.
}
\end{center}





%% --- The topic as motivated by our work a couple of years ago ---
\clearpage
\begin{center}
{\bf 
We came accross \\
\hspace*{1in}\\
an extremely difficult \\
PEAK \\
to be searched for \\
\hspace*{1in}\\
in a \\
FITNESS LANDSCAPE \\
\hspace*{1in}\\
explored by an \\
EVOLUTIONARY COMPUTATION
}
\end{center}

%% --- to be more specific \clearpage
\clearpage
\begin{center}
{\bf 
To realize an \\
\hspace*{1in}\\
ASSOCIATIVE MEMORY\\
\hspace*{1in}\\
we use \\
\hspace*{1in}\\
SPIKING NEURONS \\
\hspace*{1in}\\
whose learning is by\\
\hspace*{1in}\\
EVOLUTIONARY COMPUTATIONS.
}
\end{center}
