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

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


\title{How Can a Peak on a Completely Flat Land Searched for? \\
--- Hinton \& Nowlan's Experiment Revisited}
\author{Akira Imada\\
        Brest State Technical University, \\
        Moskowskaja 267, Brest, 224017, Republic of Belarus\\
        e-mail: akira@bstu.by}
\date{}

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

\section{Data Mining with Fuzzy Rules by Artificial Immune System}

\section{Anomaly Detection in General}
The objective is to design a set of {\it detectors} which detects {\it anomaly}.
{\it Detector} is also called {\it antibody} and {\it anomaly} is sometimes called
{\it antigen} and {\it non-self} depending on context. 
Here in this section the term {\it detector} and {non-self} or {\it anomaly}
are used. 

Anomaly to be detected is $n$-dimensional vector whose elements are binary or continuous
values. Detector is a certain region which covers one or multiple of those
non-self vectors, to be more specific,  
{\it ``Self-nonself discrimination partitions a universe of data points into
two sets: self and nonself and detectors cover subsets of nonself.}
This is paraphrased from Espond et al.~(2004).

The goal is to create detectors each of which 
will cover, or equivalently, match
a subset of nonself {\it effectively.}


%% sample of non-self points to learn how non-self called a {\it negative sample} 
%% is used In real world problem, is usually much smalle than the self points. 

Probably the first idea of this idea of self non-self discrimination based on
artificial immune system was by Forrest et al.~(1994).



\subsection{Anomaly Detection by Artificial Immune System I --- Negative Selection}

\subsubsection{Design of Detector to Detect non-Self in Binary Space}

\noindent
Before discussing detection in the real-valued Eucledian space, we survey
two papers which are for detection of binary patterns in discret binary space.\\


\noindent
{\bf Exhaustive Detector Generating Algorithm:} This is picked up from
Ayra et al.~(2002)

\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}

``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. ``


\subsubsection{Design of Detector to Detect Real-valued Self and non-Self}
\noindent
{\bf Augmented Negative Selection Algorithm
with Variable-Coverage Detectors}

\noindent
constant size detectors



\begin{algorithm}[Constant Size Sphere Detectors Generating Algorithm]
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[1.] Prepare S ---  a set of self samples; set m --- number of detectors 
and r --- radius of self.
\item[2.] Set D --- set of detector to empty set.
\item[3.] Pick up $x$ at random from $[-1,1]$ at random
\item[4.] For every $s_i$ in S
   \begin{itemize}
   \item[(i)] calculate $d$ --- Euclidean distance between $s_i$ and $x$.
   \item[(ii)] If $d < r$ then do nothing, otherwise add $x$ to D
   \end{itemize}
\item[5.] Step 3 and 4 are repeated until  $\vert D \vert < m$ reeat 3 and 4, otherwise 
\item[6.] Return D
\end{itemize} 
\end{algorithm}


\begin{algorithm}[Variable Size Sphere Detectors Generating Algorithm]
The goal is to find an appropriate set of sphere detectors whose
center is $x$ and radius is $r$.
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[1.] Prepare S ---  a set of self samples; set m --- number of detectors
\item[2.] Sample $x$ at random from $[-1,1]^n$
\item[3.] For each detector $d_i$
   \begin{itemize}
   \item Calculate Euclidean distance between center of $d_i$ and $x$ --- $r(d_i, x)$.
      \begin{itemize} 
      \item if $r(d_i, x)$ is smaller than the radius of the detector $i$ then
         \begin{itemize}
         \item Increment $t$
         \item if  
         \end{itemize} 
      \end{itemize} 
   \end{itemize} 
\end{itemize} 
\end{algorithm}







\subsection{Anomaly Detection by Artificial Immune System I --- Cronal Selection}

\section{Anomaly Detection in Particular}


\section*{Reference}
\begin{description}
\setlength{\itemsep}{0pt}
\item[]
Ayara, M., J. Timmis, R. D. Lemos, L. N. D. Castro, and R. Duncan (2002) 
``Negative Selection: How to Generate Detectors.'' 
Proceedings of 1st International Conference on Artificial Immune Systems (ICARIS). 
pp. 89--98.

%\item[]
%M. Ayara, J. Timmis, et al. (2002). 
%An Investigation into Negative Selection for Change Detector Generation, 
%Technical Report, Computing Laboratory, University of Kent at Canterbury, U.K.

\item[]
Esponda, F., S.~Forrest, and P.~Helman (2004)
"A formal framework for positive and negative detection." 
IEEE Transactions on Systems, Man, and Cybernetics 34:1 pp. 357-373 

\item[]
Forrest, S.,  A. S. Perelson, L. Allen, and C. R.Cheru R. Kuri (1994) 
``Self-non-self Discrimination in a Computer''
Proceedings of the IEEE Symposium: Research Security Privacy.




\item[]Hopfield, J. J. (1982) 
{\em Neural Networks and Physical Systems with Emergent Collective Computational Abilities.}
Proceedings of the National Academy of Sciences, USA 79,  pp.2554-2558.

\item[]Yoshioka, M (in press)
{\em The Spike-timing-dependent Learning Rule to Encode Spatiotemporal
Patterns in a Network of Spiking Neurons.}
Physical Review.

\item[]Edelman, G.\ M.\ (1987)
{\em Neural Darwinism: The Theory of Neuronal Group Selection}
Basic.
\end{description}







\end{document}