\documentstyle[eclepsf]{llncs}

\title{Can a fuzzy rule look for a needle in a haystack?}
\author{Akira Imada}
\institute{Brest State Technical University\\
           Moskowskaja 267, 224017 Brest, Republic of Belarus\\
           akira@bsty.by}
\date{}

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

\begin{abstract}
\noindent
This paper reports a snapshot of our on-going experiments in which a common target we call 
{\it a-tiny-island-in-a-huge-lake} is explored with different methods ranging from 
a data-mining technique to an artificial immune system. 
In this paper, we explore the {\it lake} with a fuzzy rule approach. 
Firstly, in order to verify the approach, 
we simply evolve a random fuzzy rule specified with a set of five 
fixed shaped triangle/trapezoidal membership functions 
to eventually emerge a rule which can look for the {\it island}.
We found it is quite easy if the island is fairly large.
Our concern, then, is the limit to which how tiny the island can be looked for.
To learn this issue, a fuzzy rule extraction system
in which membership functions are Gaussian whose shape is adaptively determined.
When we make the size of the island shrink to zero, 
it will be what they call {\it a-needle-in-a-haystack} which is still open, as far as we know.
\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 many problems in which it is easy to access to 
any one of the many candidate solutions which could be the true solution 
but most likely not, which we don't know in advance.\\

\noindent
The ultimate extreme is called {\it a-needle-in-a-haystack} problem. 
The needle originally proposed by Hinton \& Nowlan~\cite{hint} 
was exactly the one configuration of 20 binary bits.
In other words, the search space is made up of $2^{20}$ points and 
only one point is the target. 
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 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 \le 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
Our implicit interest is a network intrusion
detection where we usually do not know what does an illegal transaction pattern
look like until it completes the intrusion when actually it is too late.
Hence, our interest is to train the intrusion detection system only using
legal patterns. From this context, we assume data floating in the {\it lake} 
are normal while those found on the {\it island} are abnormal. 

\noindent
In this paper, we approach the problem from this view point.
That is, we take it, more in general,  just a pattern classification problem,  
but 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. 
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
We have so far exploited (i) {\it artificial immune system} approach, 
especially a {\it negative selection} algorithm in which constant or variable
sized hyper-sphere detectors detect non-self cells; (ii) {\it immuno-fuzzy}
approach where a set of fuzzy rules is designed to cover non-self region; 
(iii) {\it evolutionary computation} approach where 
a set of detectors randomly created at the beginning
eventually evolves to detect non-self; and so on.\\

\noindent
In this paper, we study {\it a fuzzy rule extraction using a neural network}
proposed by Castellano et al.~(2000)~\cite{cast}.
The system they proposed were neatly described in the paper,
and it seems to be very sound and efficient, except for the way in that
their normal/abnormal data applied by their detection system.
They employed an {\it Iris-database} in a popular public domain.
The database contains three different classes of iris family 
%%each of which is  made up of 
%%50 data represented by 4-dimensional continuous value vectors. 
and one class is assumed to be self
whilst the other two are assumed to be non-self.
The training samples are chosen at random from these two classes
and train the system. Then system is tested using the rest of the data in the database.
The result was successful.
We, however, doubt the real applicability of the idea of 
using artificial data set in such a way, at least in a context of intrusion detection.
This is principally because of the following two reasons: 
(i) the number of non-self (anomaly) data available is extremely fewer than the number
of self (normal) data; and (ii) we don't know what does a non-self datum look like
until it completes its intrusion successfully. It would be too late.\\

\noindent
Hence our current interest is also two-fold.
Firstly, (i) the non-self region should be tiny, 
and secondly, (ii) training should be made only by self data. 
We explore these two points using two different fuzzy models.


\section{Method}
\noindent
Two fuzzy models are as follows.

\subsection{Preliminary Experiment --- Immuno-Fuzzy Model}
\noindent
A set of fuzzy rules is used to cover the non-self patterns. As already mentioned,
self/non-self sells are represented by $n$-dimensional real valued vectors each of
whose coordinate lies in $[-1, 1]$.
That is, the self/non-self space is $[-1,1]^n$, and a self/non-self pattern
is represented by a vector $(x_1, \cdots, x_n)$ where $x_i \in [-1,1]$.
Then a fuzzy rule to detect non-self patterns is
\begin{center}
If $x_1$ is $T_1$, $\cdots$, and $x_n$ is $T_n$ then {\bf x} is non-self
\end{center}
where $T_i$ is a fuzzy linguistic terms which is either of 
\begin{center}
\{Low, Low-Middle, Middle, Middle-High, or High\}.
\end{center}
Each of $T_i$ maps the $x_i$ to a real value between 0 and 1,
expressing the degree to how it is likely to the linguistic value.
This is calculated by a membership function, which is defined
here using triangular and trapezoidal fuzzy membership functions.\\

\noindent
Then a genetic algorithm evolves these fuzzy rules,
with chromosomes being $(T_1, \cdots, T_n)$, starting with those
chromosomes randomly created. 
To be more specific, our chromosome is made up of $n$ integer genes
whose value is chosen from $\{0, 1, 2, 3, 4\}$.
The fitness of a rule is calculated by applying the rule
to all the self patterns one by one.\\

\noindent
Each of such rules are applied to a pattern $\mbox{\bf x} = (x_1, \cdots, x_n)$
and evaluated how the pattern {\bf x} is likely to be a non-self by the equation
\begin{displaymath}
\mbox{eval}_{R}(\mbox{\bf x}) = \min_{i=1, \cdots, m} \{ \mu_{T_i} (x) \}
\end{displaymath}

\noindent
Fitness evaluation of a rule is made according to
\begin{displaymath}
\mbox{fitness} (R) = \frac{\sum_{\mbox{\bf x} \in Self} \mbox{eval}_R (\mbox{\bf x})}
{\vert Self \vert}
\end{displaymath}
which implies how the rule covers the non-self space.\\

%% \noindent
%% The size of self cells is fixed to 400; each GA run is iterated for 1000 generations;
%% size population of chromosmes are 100, to be comparable with 
%% the original Dasgupt et al's experiment~\cite{gome}.


%% \begin{figure}[h]
%%  \begin{center}
%%  \epsfile{file=member-s.eps,width=10cm,height=4cm}
%% \caption{An example of experimental result of a membership function of 
%% one antecedent membership function of a rule (Left), and one of the two
%% output singletons of the same experiment (Right). Training Samples are
%% from the assumed legal data exist in the {\it lake},
%% while the illegal data is assumed to be in the {\it tiny island} defined as $a=0.1$.}
%%  \end{center}
%% \end{figure}


\subsection{A Fuzzy Neural Network Approach}
\noindent
The goal is to classify the data taken from the $n$-dimensional data-set 
into either of the pre-defined $m$ classes.
For the purpose, 
Castellano et al.~\cite{cast}
used the inference mechanism of the zero-order Takagi-Sugeno fuzzy model;
then realized the idea by a fuzzy neural network model.
To train the fuzzy neuronal network, 
%% Castellano et al.~\cite{cast} 
they employed
a combination of (i) {\it a competitive learning} to determine the architecture of 
the fuzzy neural network at first and (ii) {\it a gradient descent learning} to optimize 
the synaptic weights afterwards.
We, on the other hand, employ an evolutionary computation technique to train the network,
since we already know the optimal network structure under our current interest,
and as such, our concern is just to obtain 
the solution of weight configuration of the fuzzy neural network.\\

\noindent
In the following three sub-subsections, Takagi-Sugano fuzzy model, 
a realization of the model by fuzzy neural network, and 
how we optimize the weight of the fuzzy neural network by an evolutionary computation
are described more in detail.


\subsubsection{Takagi-Sugeno Model.}
Though Castellano et al.~\cite{cast} stated the method very clearly in their paper,
let us briefly describe it with an intention of making this paper self-contained.
Takagi-Sugeno fuzzy inference model is made up of a set of $H$ rules, such as 
\begin{center}
$R_k$: IF ($x_1$ is $A_1^k$) and $\cdots$ and ($x_n$ is $A_n^k$) \hspace{3in}
\end{center}
\begin{center}
\hspace*{1in}THEN ($y_1$ is $\nu_{k1}$)  and $\cdots$ and ($y_m$ is $\nu_{km}$)
\end{center}
where $R_k$ is the $k$-th rule $(k = 1, \cdots H)$, 
$x_i$ denotes the $i$-th variable of the input data $(i=1, \cdots, n)$,
$y_j$ denotes the $j$-th output variable $(j=1, \cdots, m)$,
$A_i^k$ denotes a fuzzy set which is usually expressed by a linguistic term
such as {\it ``Medium-Large''} but here expressed by a shape of membership function
defined one by one on the corresponding input variable,
and $\nu_{kj}$ denotes a fuzzy singleton each defined on the output variables 
indicating the likeliness of how the input belongs to
the $j$-th class according to the  $k$-th rule.\\

\noindent
$A_i^k$ is defined by Gaussian membership functions
\begin{displaymath}
\mu_{ik}(x_i) = \exp \{ -(x_i - w_{ik})^2/\sigma_{ik}^2\}.
\end{displaymath}


\noindent
Then defuzzification for an input ${\mbox{\bf x}}^0 = (x_1^0, \cdots, x_n^0)$ 
is via the equation:
\begin{displaymath}
y_j^0 = \{ \sum_{k=1}^H (\mu_k(\mbox{\bf x}^0)\cdot \nu_{kj}) \}/
\sum_{k=1}^H \mu_k(\mbox{\bf x}^0)
\end{displaymath}
where
\begin{displaymath}
\mu_k(\mbox{\bf x}^0) = \prod_{i=1}^n \mu_{ik}(x_i^0)
\end{displaymath}
is the results of application of the Larsen product operator.\\

\noindent
In other words, the procedure of inference is as follows.
When an input $\mbox {\bf x} = (x_1, \cdots x_n)$ is given,
each of the $H$ rules evaluates the {\bf x} and output the likeliness of the class, 
from one class to the next, to which $\mbox {\bf x}$ belongs to.
The evaluation by $k$-th rule of $x_i$ 
is by the corresponding membership function $\mu_{ik}(x_i)$
which is specified by giving two parameters $w_{ik}$ and $\sigma_{ik}$
so that it returns a value ranging from 0 to 1. 
See, e.g., Figure 1 where
the $i$-th coordinate of the input {\bf x} is evaluated by $A_i^k$,
the $i$-th antecedent of the {\it IF} part of the ${\mbox{Rule}_k}$, which is 
represented by a membership function not by a usual linguistic term like {\it ``Small''}.
The returned membership value in this example in the figure is 0.71, suggesting, say,
``The likeliness of if the variable is ``Medium Large'' is 0.71.''\\

\begin{figure}[h]
 \begin{center}
 \epsfile{file=mu-2.eps,width=8cm,height=4cm}
\caption{A fictitious sketch of an evaluation of $x_i$, the $i$-th entry 
of the input {\bf x}, 
by the $i$-th antecedent part of the $k$-th rule $A_i^k$.}
 \end{center}
\end{figure}



\noindent
Using those $n$ values of $\mu_{ik}(x_i)$,  
each of the $H$ rules calculates $\mu_k(\mbox{\bf x})$,
and finally these $H$ values are combined 
to calculate $m$ values of $y_j$, the resultant defuzzified value 
for each of the $m$ classes.\\

\subsubsection{Fuzzy Neural Network Implementation.}
\noindent
The procedure described in the previous sub-subsection
can be realized  when we assume a neural network architecture
such as depicted in Figure 2.
The 1st layer is made up of  $n$ input neurons. 
The 2nd layer is made up of $H$ groups of a neuronal structure 
each contains $n$ neurons where
the $i$-th neuron of the $k$-th group has a connection to the $i$-th neuron 
in the 1st layer with a synaptic connection 
which has a pair of weights $(w_{ik},\sigma_{ik})$.
Then $k$-th group in the second layer calculates the value
$\mu_k(\mbox{\bf x})$ 
from the values which are received from each of the $n$ neurons in the first layer. 
The 3rd layer is made up of $m$ neurons each of which collects
the $H$ values from the output of the second layer, that is
$j$-th neuron of the 3rd layer receives the value from $k$-th output in the second layer
with the synapse which has the weight $\nu_{kj}$

\begin{figure}[h]
\begin{center}
\epsfile{file=fuzzy-nn.eps,width=8cm,height=6cm}
\caption{Architecture of the proposed fuzzy neural network which
infers how an input $\mbox {\bf x} = (x_1, \cdots x_n)$ is likely to belong to the $j$-th class 
by generating outputs $y_j$ each of which reflect the degree of the likeliness. 
In this example, a 20-dimension data input 
will be inferred 
to which of the 3 classes the input belongs  by using 2 rules.}
\end{center}
\end{figure}

\subsubsection{How it learns?}
Castellano et al.~\cite{cast} used 
(i) a competitive learning to determine how many rules are needed 
under initial weights created at random.
Then, in order to optimize the initial random weight configuration, 
they use (ii) a gradient method performing the steepest descent on a surface
in the weight space employing the same training data, that is, supervised learning.\\

\noindent
Here, on the other hand, we use a simple genetic algorithm,
since our target space is specific enough to know the network structure in advance, 
i.e., only unique rule is necessary.
Our concern, therefore, is just  obtaining the solution of weight configuration of the network.
That is to say, all we want to know is a set of parameters
$w_{ik}$, $\sigma_{ik}$ and $\nu_{kj}$ 
$(i= 1, \cdots n)$, $(k= 1, \cdots H)$, $(j= 1, \cdots m)$ 
where $n$ is the dimension of data, $H$ is the number of rules, and 
$m$ is the number of outputs. 
Hence our chromosome has those $n \times H \times m$ genes.
Starting with a population of chromosomes whose genes are randomly created,
they evolve under {\it simple truncate selection} where higher fitness chromosome are chosen,
with {\it uniform crossover} and occasional {\it mutation} by 
replacing some of a few genes with randomly created other parameters,
expecting higher fitness chromosomes will be emerged. 
These settings are determined by trials and errors experimentally.\\

%% \noindent
%% To evaluate fitness of each chromosome, 
%% we use a measure originally proposed by Lopes et al.~\cite{lope} and used widely nowadays. 
%% It includes four quantities, i.e., 
%% (i) true-positive, (ii) true-negative, (iii) false positive, and (iv) false negative.
%% Here we assume positive sample is non-self and negative sample is self,
%% since detectors is designed to detect non-self cells.
%% Hence, these four terms  are defined in a sense 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; and 
%% (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.
%% Then we plot $d_r$ versus $f_a$, and
%% the resultant graph is called {\it Receiver Operating Characteristics (OCR)}~\cite{prov}
%% which reflects a tradeoff between false alarm rate and detection rate.\\

%% \noindent
%% Efficiency and effectiveness of this learning by an evolutionary computation,
%% instead of competitive learning originally proposed by Castellano et al.~\cite{cast}
%% will be discussed in another place. 

\section{Experiment}
\noindent
Castellano et al.~\cite{cast} used {\it Iris} data 
found in a public domain in a clever way.
%% , writing as follows.
%% \begin{quote}
%% {\it
%% The validity of our approach to fuzzy inference and rule extraction 
%% has been tested on the well-known benchmark Iris data problem. 
%% The classification problem of the Iris data consists of classifying 
%% three species of iris flowers (setosa, versicolor and virginica). 
%% There are 150 samples for this problem, 50 of each class. 
%% A sample is a four-dimensional pattern vector representing four attributes 
%% of the iris flower (sepal length, sepal width, petal length, and
%% petal width).
%% }
%% \end{quote}

\noindent
However, we doubt this way of using {\it Iris} data 
as an artificial data at least in the context of network intrusion detection.
One reason of our doubt is that illegal patterns are usually unknown
and it cannot be represented by certain specific patterns, if not al all.
The other reason is the sparseness of this data set. What if the system
meets a pattern which does not belong to either of the two classes?
See another report of us \cite{imad-2} regarding this issue.\\

\noindent
An experiment was carried out in the 20-dimensional space.
Our assumption is normal data exist in the {\it lake} region 
while abnormal data in the {\it island} region.
We control the size of the island by changing the parameter value $a$. 
Hence, it is easy for us to guess that only one  inference rule is enough to classify
an input into either of the two classes.
The architecture of the fuzzy network is, therefore, 20 input nodes, 1 rules, and 2  output nodes.

\section{Results and Discussion}
Though our experiments have sometimes reversed our expectations 
depending on parameter setting,
we are obtaining a series of successful results,  such as shown in Figure 3 where
we showed an example of obtained membership function corresponding to 
one antecedent of the rule (Left), as well as one of the 
output singletons obtained in the same experiment (Right). Training Samples are
from the assumed  legal data exist in the {\it lake} region to identify the
illegal data exists in the {\it tiny island} region defined as $a=0.1$.

\begin{figure}[h]
 \begin{center}
 \epsfile{file=mu-1.eps,width=5.85cm,height=3cm}
 \epsfile{file=singleton.eps,width=5.85cm,height=3cm}
\caption{An example of experimental result of a membership function of 
one antecedent membership function of a rule (Left), and one of the two
output singletons of the same experiment (Right). Training Samples are
from the assumed legal data exist in the {\it lake},
while the illegal data is assumed to be in the {\it tiny island} defined as $a=0.1$.}
 \end{center}
\end{figure}
\noindent
In the figure, although only one example of membership function is shown out of 20 others,  
the other 19 membership factions are more or less similar to the one shown in the figure.
This suggest that 
\begin{center}
$R_1$: IF all of $x_n$ is near the origin THEN ($y_1$ is HIGH)  and ($y_2$ is LAW).
\end{center}
Namely, the input belongs to the abnormal class.

\section{Summary}
In this paper, we have reported our on-going investigations, that is,
how already proposed methods work on a special situation of 
what we call {\it a-tiny-island-in-a-huge-lake}.
When we increase the difficulty of the problem by making the size of the island
shrink to zero, it will  become what they call {\it a-needle-in-a-haystack} \cite{hint}.
As far as we know, this issue has resisted to be fully solved and still remains open.
Though our results so far has not been matured yet,
we hope a lot of experiments await our exploration which might result in 
useful observations in considering how we design 
a network intrusion detection system.


\begin{thebibliography}{99}

\bibitem{cast} G.~Castellano and A.~M.~Fanelli(2000)
"Fuzzy Inference and Rule Extraction using a Neural Network." 
Neural Network World Journal Vol. 3, pp.~361--371.

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

%% \bibitem{prov} F.~Provost, T.~Fawcett, and R.~Kohavi (1989)
%% ``The case against accuracy estimation for comparing induction algorithms.''
%% Proceedings of international conference on machine learning, pp.~445--453.

\bibitem{imad-2} A.~Imada (2005)
``When One Iris Flower is Normal Then are Others Abnormal?''
Proceedings of International Conference on Pattern Recognition and Information Processing,

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