%\documentstyle[a4,epsf]{article}            % for AIST
%\documentstyle[a4,epsf,epsfig]{article}    % for ATR
\documentstyle[eclepsf]{article}    % for lulu

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\myepsfile#1#2#3{\epsfile{file=#1,width=#2,height=#3}}     % for AIST
%\def\myepsfile#1#2#3{%
%        \leavevmode\epsfig{figure=#1,height=#3,width=#2}}       % for ATR
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\makeatletter
%\long\def\@makecaption#1#2{%
%  \vskip 10pt
%  \setbox\@tempboxa\hbox{#1: #2}%
%  \ifdim \wd\@tempboxa > \hsize
%    \begin{quote}#1: #2\end{quote}
%  \else
%    \hbox to\hsize{\hfil\box\@tempboxa\hfil}%
%  \fi}
%\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{Mutually Connected Neural Network Can Learn Some Patterns by Means of GA}
%\title{Genetic Algorithm as a Learning Method in Associative Memory}

\author{Akira Imada\\
        akira-i@is.aist-nara.ac.jp\\
        \hspace*{1in} \\
        Keijiro Araki\\
        araki@is.aist-nara.ac.jp\\
        \hspace*{1in} \\
        Nara Institute of Science and Technology\\
        8916-5 Takayama, Ikoma, Nara, 630-01 Japan\\
        phone: +817437-2-5083}

\date{}

\maketitle

\begin{center}
{\bf abstract}
\end{center}

In the simulation of associative memory with mutually connected neural network,
we successfully made the connection matrix learn some binary patterns
only by means of genetic algorithm. 
Although the memory capacity is about 12 \% of the number of neurons,
the fact that it was made without any learning algorithm like Hebbian rule
is very interesting. The structure of connection matrices we obtained was
quite different from that of Hopfield network.\\ 
%Therefore we concluded 
%the genetic algorithm has its own ability of learning patterns, 
%and we could use it as a new learning method of associative memory.\\
\indent
Our overall goal for this research is two fold. One is to know if we can use 
genetic algorithm as a more effective learning method than that proposed so far,
and another is to understand this learning mechanism of the genetic algorithm.

\section{Introduction}
Associative memory has a limit in capacity depending on the
learning rule in memorizing patterns with.
In 1982, Hopfield proposed his model with using 
Hebbian rule, and his associative memory system has the memory capacity 
of about 15 \% of the number of neurons as in standard literatures.
Since then there have been many approaches to enlarge the capacity. 
In another paper, we challenged it by a genetic algorithm,
and we showed that the memory capacity of connection matrix 
which learned some patterns by Hebbian rule 
can be enlarged to about 30 \% of the number of neurons, i.e. about twice
as much as the one in Hopfield network.\\
\indent
In this report, on the other hand, we apply genetic algorithm
to the connection matrices generated randomly instead. Neural networks with
randomly generated connection matrices can not retrieve any given patterns
of course. But after applying genetic algorithm to them,
we were able to make the network memorize some patterns. 

\section{Method}
One of the features of our genetic algorithm is that the initial connection matrix 
is remained fixed over the time of evolution.
Our chromosomes have a fixed length of 
${(number\hspace{.05in}of\hspace{.05in}neurons)}^2$, 
and their allele values are chosen randomly from  either 
$-1$, 0, or 1, in which 0 implies to prune the connection
and $-1$ to reverse the role of enforcement or suppression of the weight.\\
\indent
In the simulation here, each element of the initial matrix is chosen randomly from 
\{$-1$, 1\}. Hence the matrix does not memorize any patterns at the beginning.
And the matrix does not include any zeros, and are not symmetrical at 
the start of genetic algorithm.\\
\indent
To evaluate the fitness, we summed up all the overlapping at each time of update 
not more than certain time $t_{0}$. That is, our fitness $f$ is 

\begin{displaymath}
f = \frac {1}{p \cdot (t_{0} - 1) \cdot 49}   \sum _{\mu=1}^{p} \sum_{t=2}^{t_{0}} 
{ \sum _{j=1}^{49} {\xi_{j}^{\mu} s_{j}^{\mu}(t)}}, \\
\end{displaymath}
\noindent
where $( { \xi}_{1}^{ \mu}, { \xi}_{2}^{ \mu},{ \xi}_{3}^{ \mu},
\cdots , { \xi}_{49}^{ \mu})$ is the $\mu$-th pattern, $s_{i}^{\mu}(t) $ 
is the corresponding state of update of i-th neuron at time t, and $t_{0}$ = 98.
Fitness 1.000 implies that all the initial patterns are fixed points, 
while fitness less than 1.000 includes many possible cases. 

\section{Results and Analysis}
In Figure \ref{evolution}, we showed some examples of the fitness vs. generation 
for 4, 6, 7, 8, and 12 
patterns, where $t_{0}$ was two times of number of neurons.

\begin{figure}[hbtp]
 \begin{center}
   \myepsfile{evolution.eps}{6cm}{6cm}
   \caption{\bf Fitness vs. Generation}
   \label{evolution}
 \end{center}
\end{figure}

In Table \ref{fixed}, we showed the fitness values and the number of fixed 
points obtained at the 3000-th generation with increasing number of 
initial patterns. 
In the case of 4, 5, and 6 patterns, we obtained the fitness value of 1.000 within
3000 generations.
This implies that all the initial patterns are fixed points for the obtained
weight matrix as described above.
So far we have not obtained the fitness value of 1.000 for the patterns more 
than six.\\
\begin{table}[hbtp]
\begin{center}
\caption{Maximum Number of Fixed Points ($t_{0} = 98$)}
\label{fixed}
\vspace{.2in}
\begin{tabular}{c c c c c c c} \hline \hline
patterns     &   4   &    5    &    6    &   7    &   8   &  12   \\   \hline
fitness      & 1.000 &  1.000  &  1.000  & 0.976  & 0.959 & 0.900 \\ 
fixed-point  &   4   &    5    &    6    &   3    &   2   &   1   \\   \hline \hline
\end{tabular}
\end{center}
\end{table}
\indent
In Hopfield network, connection matrix is symmetric and the elements are not 
zero except for the diagonal elements.
Our matrices, on the other hand, do not contain any zero including the diagonal
elements. In creating individuals, however, some elements could become zero
by being multiplied by zero. These zeros are generated at the rate of 0.02
in the beginning, and later the rates vary according to the selection pressure 
during evolution.
And the degree of symmetry of our matrix is almost zero from the beginning.



\begin{figure}

\begin{center}
   \myepsfile{zero.eps}{6cm}{6cm}
   \myepsfile{symm.eps}{6cm}{6cm}
   \caption{\bf Rate of Zero (left) and Degree of Symmetry (right)}
   \label{symmandzero}
\end{center}
\end{figure}




In Figure \ref{symmandzero}, we showed the behaviors of the rate of zeros and 
the degree of symmetry of the connection matrix, which are of the elitest individual in each
generation. The definition of degree of symmetry $\eta$ here is

\begin{displaymath}
\eta = \sum_{i=1}^{N} \sum_{j=1}^{N} {w_{ij} w_{ji}} 
/ \sum_{i=1}^{N} \sum_{j=1}^{N} {w_{ij}^{2}}.\\ 
\end{displaymath}
\noindent
As we can see in those Figures, the behavior of these parameters are close 
to those of the fitness.\\
\indent
As described earlier, $-1$ in the chromosome reverses the roll of enforcement or suppression 
of the weight, and 0 prunes the connection. 
To ascertain the effect of $-1$ and 0 in the chromosome,
we made the following two experiments. One is with the chromosomes chosen from $\{-1, 1\}$ and another is from
$\{0, 1\}$ under the same condition of a simulation with the chromosomes chosen from $\{-1, 0, 1\}$ above.
We showed  the results in Figure \ref{crom}.
As we can see in Figure \ref{crom}, although the chromosome chosen from (a): $\{-1, 0, 1\}$ worked most effectively,
the chromosome made up of both (b): $\{-1, 1\}$ and (c): $\{0, 1\}$ also worked.
The number of fixed points resulted in the experiment (b) was 4, whereas 1 in the experiment (c).
The roll of $-1$ seems to be more important than 0, but we needed 0 to obtain 6 fixed points in the experiment (a). \\
\begin{figure}[hbtp]
 \begin{center}
   \myepsfile{cromosome.eps}{6cm}{6cm}
   \caption{\bf The Roll of $-1$ and 0 in the Chromosome}
   \label{crom}
 \end{center}
\end{figure}
\indent
Consequently we conjectured that both of rate of zero and degree of symmetry have 
something to do with learning, though we need further research.  
\section{Conclusions}
We successfully made the random matrices memorize some patterns only by means
of genetic algorithm. 
This time we simulated with the neural networks with
49 nodes, and we obtained the maximum of 6 fixed points of associative memory.
Although the memory capacity of the connection matrix achieved are less than 
that of Hopfield network, it may lead to useful applications to get the higher
capacity of associative memory, as well as helping to clarify 
the process of learning.
The matrices we obtained here are quite different from that of Hopfield's one.
Those are asymmetric and include about 20\% of zeros. And the behaviors of both 
rate of zeros and degree of symmetry are very close to those of fitness. 
Hence, we conjectured that these parameters play an important roll to make 
them memorize some patterns, 
and genetic algorithm could have its own unique learning mechanism which 
we have not found in the already known learning algorithms. \\

\section*{Acknowledgments}
We wish to thank Peter Davis at ATR (Advanced Telecommunication 
Research Institute) for his insightful ideas on the evolution of 
mutually connected neural networks.

\begin{thebibliography}{99}
\bibitem{imad}Imada,A., and Araki,K. Genetic Algorithm Enlarges the Capacity of Associative Memory. ICGA-95 (to be submitted)
\end{thebibliography}

\end{document}

%%% Local Variables: ***
%%% mode: japanese-latex ***
%%% fill-column: 78 ***
%%% End: ***

