%%\documentstyle[epsf]{llncs}
\documentstyle[eclepsf]{llncs}

\begin{document}

\title{Basin of Attraction of Associative Memory\\as it Evolves from Random Weights}

\author{Akira Imada\inst{1} and Keijiro Araki\inst{2}}

\institute{
        Graduate School of Information Science\\  
        Nara Institute of Science and Technology\\
        8916-5 Takayama, Ikoma, Nara, 630-01 Japan\\
        akira-i@is.aist-nara.ac.jp\\
        \hspace*{1in}\\
\and
        Department of Computer Science and Computer Engineering\\
        Graduate School of Information Science and Electrical Engineering\\
        Kyusyu University\\
        6-1 Kasuga-koen, Kasuga, Fukuoka, 816 Japan\\
        araki@c.csce.kyusyu-u.ac.jp}

%%\institute{
%%\begin{minipage}[t]{6cm}
%%\begin{center}
%%        Graduate School of Information Science\\  
%%        Nara Institute of Science and Technology\\
%%        8916-5 Takayama, Ikoma, Nara, 630-01 Japan\\
%%        akira-i@is.aist-nara.ac.jp
%%\end{center}
%%\end{minipage}
%%\begin{minipage}[t]{6cm}
%%\begin{center}
%%        Department of Computer Science and Computer Engineering\\
%%        Graduate School of Information Science and Electrical Engineering\\
%%        Kyusyu University\\
%%        6-1 Kasuga-koen, Kasuga, Fukuoka, 816 Japan\\
%%        araki@c.csce.kyusyu-uac.jp
%%\end{center}
%%\end{minipage}
%%}

\maketitle

\begin{abstract}
We apply genetic algorithms to fully connected Hopfield associative memory networks.
Previously, we reported that a genetic algorithm can evolve networks with random synaptic weights 
to store some number of patterns by pruning some of its synapses.
%%Previously, we reported that the network can evolve to store some number of patterns 
%%starting with a random weight matrix by pruning some of its connections with a simple genetic algorithm.
The associative memory capacity obtained in that experiment was around 16\% of the number of neurons.
However the size of basin of attraction was rather small compared to the original Hebb-rule associative memory.
In this paper, we present a new version of the previous method trying to control the basin size.
As far as we know, this is the first attempt to address the size of basin of attraction of associative memory by evolutionary processes.
\end{abstract}

%%\hspace*{1in}\\
%%\begin{center}
%%\begin{small}
%%{\bf Key Words:}\\
%%\end{small}
%%\bigskip
%%Associative Memory, Genetic Algorithm, Storage Capacity, Basin of Attraction
%%\end{center}


\section{Introduction}
Associative memory recall is a process in which an incomplete or a noisy input of a stored pattern 
results in the retrieval of its complete pattern.
The error-correcting capability is due to their distributed storage of patterns among neurons, though they have a limited capacity.
%%Associative memories have an error-correcting capability 
%%due to their distributed storage of patterns among neurons, though they have a limited capacity.
We are investigating basic behaviors of the associative memory under simple evolutionary processes.\\

\noindent
In 1982, Hopfield\cite{hopf} proposed a neural network model of an associative memory system.
He specified synaptic weights by Hebbian rule\cite{hebb} to store a set of random bipolar($\pm 1$) patterns.
He estimated the storage capacity to be at most 15\% of the number of neurons with computer simulations.
%Later the capacity was verified more analytically by Amit, Gutfreund, \& Sompolinsky (1987) with spin-glass theory,
%and by Amari \& Maginu (1987) with statistical neuro-dynamical method.
Since then, many researchers have been trying to enlarge the storage capacity in various ways (see e.g., \cite{yana}, \cite{mori}).\\

\noindent
%%However, the enlargement of capacity spoils the error correcting capability of the network, namely,
%%the size of basin of attraction is traded off against the storage capacity as Gardner showed\cite{gard}. 
Within the capacity,
%%($ p<N/4 \ln N $), 
{\it all} the incorrect inputs at a distance 
$\rho \hspace{.05in} (\rho \in (0, 1/2))$ 
from each of the $N$-bit stored patterns are corrected (McElice et al.\cite{mcel}, Personaz\cite{pers}),
which implies that each stored pattern has a spherical domain of attraction of {\it same} radius $\rho N$ (Pancha et al.\cite{panc}).
However, as $p$ increases, the size of the basin of attraction guaranteed by the Hebbian rule 
becomes smaller (see, e.g., \cite{gard}).
%%than the Hamming distance between stored patterns. 
It could be optimized so that the radius of an attraction domain will be extended to a half of the distance from its nearest neighbor
(in $N$-dimensional space).
%%The size of basin of attraction decreases as the number of storage patterns increases as Gardner showed, 
%%In fact, Personnaz et al.\cite{pers} indicated that 
%%the basin of attraction of a stored memory falls sharply as the number of patterns approaches to a half of the number of neurons.
In this paper we explore the trade-off between storage capacity and basin size with using a genetic algorithm.\\
%%So far, there are some amounts of approaches to the basin of attraction. For example,
%%And Verleysen, Sirletti, Meulebreecke, \& Jespers (1989) propose an algorithm which maximizes each basin for a set of given patterns.

\noindent
Genetic algorithms are a class of global search algorithm(\cite{holl}, \cite{gold}).
Since the late 1980's, genetic algorithms have been used extensively to search the
optimal set of synaptic weights of neural networks and/or their optimal architectures (see \cite{whit}, \cite{yao}, and references quoted therein).
However all of these researches were for layered neural networks, and applications of genetic algorithms to Hopfield networks remain few so far,
probably because of the fact that Hopfield networks have a fixed architecture.
However, sparse connectivity has a possibility to enhance the original associative memory capacity of Hopfield network\cite{yana}.
Therefore, genetic algorithms can be used for Hopfield neural networks to explore their architectures 
as well as to determine their synaptic weights.\\

\noindent
Previously, we showed that randomly generated weight matrices evolve to store some number of patterns 
using a genetic algorithm without any learning rules\cite{imad}.
We also showed that the genetic algorithm enlarges the capacity of Hebb-rule associative memory\cite{imad-2}.
The genetic algorithm was based on pruning some synaptic weights of the networks.
In these two reports, we did not refer to the basin of attraction of the associative memory.
In this paper, we redesign the genetic algorithm to try to control the size of basin of attraction.\\

\noindent
The overall goal for this research is 
to understand the mechanism of the {\it learning} under evolutionary processes,
rather than to use the genetic algorithm as a more effective learning method than those proposed so far.\\

\noindent
The following section provides a brief review of associative memory.
Section~3 provides an overview of our genetic algorithm implementation.
Then results of the new implementation on the basin size are described in Section 4.

\section{Associative memory}
A Hopfield network constituting of $N$ neurons can store some number of $N$-bit bipolar patterns, 
if all the synaptic weights are determined appropriately.
Patterns are $n$-dimensional random vectors whose elements take the values $\pm 1$ randomly with equal probability.
The $\mu$-$th$ pattern is denoted as
\begin{displaymath}
{\xi}^{\mu} = ( {\xi}^{\mu}_{1}, {\xi}^{\mu}_{2}, \cdots , {\xi}^{\mu}_{N}) ,
\end{displaymath}
\noindent
where ${\xi}^{\mu}_{i}$ is the $i$-$th$ bit of the ${\mu}$-$th$ pattern.
To store these patterns, each connection weight has to be appropriately specified.
Under Hebbian learning, for example, the weight $w_{ij}$ is determined as follows:

\begin{displaymath}
w_{ij} = \sum _{ \mu = 1}^{p} { { \xi }_{i}^{ \mu }{ \xi }_{j}^{ \mu }},
\end{displaymath}

\noindent
where $p$ is the number of patterns to be stored.
This process of determining $w_{ij}$ is referred to as {\it learning}.
These $w_{ij}$'s define an energy function on an $N$-dimensional bipolar state space, i.e.,
\begin{displaymath}
E(S) = - \frac{1}{2} \sum_{i,j(i \ne j)} w_{ij}S_{i}S_{j},
\end{displaymath} 

\noindent
where $S$ moves over all possible combinations of $N$-dimensional vector $\{-1, 1\}^{N}$ and $S_{i}$ is the $i$-$th$ component of the state $S$.
If the number of stored patterns is small enough, 
this function takes a local minimum where $S$ corresponds to one of stored patterns.
The stored patterns are said to be {\it attractors} and the size of this local minimum are referred to as {\it basin of attraction}.
As the number of stored patterns $p$ increases, spurious minima become more frequent and finally they become randomized.\\

\noindent
The retrieval of one of stored memories is as follows.
The state of each neuron is asynchronously updated by
\begin{displaymath}
s_{i}^{\mu}(t+1) = sgn(\sum _{j=1}^{N} { w_{ij}s_{j}^{\mu}(t)}),
\end{displaymath}

\noindent
where $s_{i}^{\mu}(t) $ is the state of the $i$-$th$ neuron at time $t$ when the $\mu$-$th$ pattern is given to the network.
For each neuron, the weighted sum of its inputs is computed, and if this is
greater than or equal to zero, the state of the neuron takes the value of 1, and $-1$ otherwise.
Each neuron is chosen according to pre-assigned order (once per cycle), instead of chosen randomly, at each step of updating.\\

\noindent
When input is one of the stored patterns, which is given small noise within the size of basin of attraction,
this input pattern relaxes to the original stored pattern after several steps of the update.
If we do not give any noise to the input, on the other hand, i.e., one of stored patterns is given to the network, 
all the states remain unchanged from the start, and the patterns are said to be stored as {\it fixed points}.
We evaluate the storage capacity by the upper bound of the number of patterns stored as fixed points.
However the goal in this paper is to obtain larger size of basins rather than the higher capacity.\\

\noindent
A comprehensive review of associative memory can be found in~\cite{hass}.

\section{Genetic Algorithm Implementation}
%%The genetic algorithm used in this study is schematically illustrated in Figure~\ref{overview}.
%%\begin{figure}[hbtp]
%% \begin{center}
%%   \epsfile{file=overview.eps,width=9cm,height=4.5cm}
%%   \caption{Schematic representation of our genetic algorithm.}
%%   \label{overview}
%% \end{center}
%%\end{figure}
\noindent
The genetic algorithm used in this study is as follows.
\noindent
{\bf (1)} A weight matrix $W_{0}$ is  generated in certain way. In this paper, we use a weight matrix obtained from the previous version of 
our genetic algorithm (no noisy-input)
in which random weights eventually evolve to store all the given patterns perfectly as fixed points.
As we simulate with 49 neurons of Hopfield network, the size of $W_{0}$ is 49$\times$49.
This original weight matrix remains unchanged during the evolution.
{\bf (2)} Then 256 chromosomes are generated randomly. The chromosome has a fixed length of 2401(=49$\times$49) alleles, 
and these alleles are chosen randomly from $ \{ -1, 0, 1\}$,
where the probability of choosing either $-1$ or 0 is set to 0.02.
As will be mentioned in procedure(3) below, each component of the original weight matrix $w_{ij}$ is multiplied by one of these alleles.
Allelic value of 0 corresponds to pruning the connection to which it is multiplied, and $-1$ to reverse excitatory/inhibitory connection.
We denote the $i$-$th$ allele of the $n$-$th$ chromosome as $c^{(n)}(i)$.
{\bf (3)} Each chromosome modifies the original weight matrix $W_{0}$ as follows: 
\begin{displaymath}
w^{(n)}_{ij} = w_{ij} \cdot c^{(n)}(49i+j) \hspace{.2in} (i,j = 0, 1,2, \cdots , 48; \hspace{.1in} n = 1,2,3, \cdots 256),
\end{displaymath}
where $w^{(n)}_{ij}$ denotes $i$-$j$ component of the $n$-$th$ weight matrix in the population.
In each generation, this produces 256 weight matrices slightly different from $W_{0}$.
We note that the larger the population number, the higher the performances.
Due to computational resource's limits, however, we set it to 256.
{\bf (4)} To evaluate fitness value $f$, randomly chosen $\nu$ bits of each stored pattern are flipped.
Then they are given to the network and updated.
Each inner product of the updated state and its corresponding stored pattern  
is averaged over all time steps up to certain time $t_{0}$ and over all the patterns.
%%Then each inner product of one of stored patterns and updated neuron-states after giving noisy input is averaged
%%over all time steps up to certain time $t_{0}$ and over all the patterns.
This process is repeated for $n$ different combinations of the $\nu$-bit noisy inputs
and averaged over them. That~is,
\begin{displaymath}
f = \frac {1}{n \cdot p \cdot (t_{0} - 1) \cdot 49}   \sum_{k=1}^{n} \sum_{\mu=1}^{p} \sum_{t=2}^{t_{0}} 
{ \sum_{j=1}^{49} {\xi_{j}^{\mu} \cdot s_{j \nu k}^{\mu}(t)}}, \\
\end{displaymath}

\noindent
where $s_{j \nu k}^{\mu}(t) $ is the state of the $j$-$th$ neuron at time $t$ 
when the $k$-$th$ combination of $\nu$-bit noisy $\mu$-$th$ pattern is given to the network.
In this paper, $t_{0}$ is set to 98, i.e., twice the number of neurons, and we observed that was enough.
We must note that fitness 1 implies that all the noisy patterns are retrieved correctly,
while fitness less than 1 includes many possible cases.
If we evaluated the fitness at one point of updating time instead, some solutions might be limit cycle.
We adopted the above time-consuming fitness evaluation in order to avoid the oscillatory solutions.
{\bf (5)} Two parent chromosomes are chosen uniformly at random from upper 40\% of the population which is ranked by fitness.
Then those are recombined to make one child chromosome, and an individual in the lower 60\% of the population is replaced with it.
This process is repeated until all the individuals in the lower subpopulation are replaced.
{\bf (6)} Recombinations are made with uniform-crossover.
We tested several types of crossover including one- and two-point-crossover, and observed that the uniform-crossover outperformed the others.
Furthermore, the offspring are mutated in time with probability 0.01 (mutation rate),
where mutation rotates the value of randomly chosen allele in chromosome $c^{(n)}(i)$ cyclically, i.e.,
\begin{displaymath}
(1) \rightarrow (-1), \hspace{.1in}(-1) \rightarrow (0), \hspace{.1in}(0) \rightarrow (1).
\end{displaymath}
%%The mutation rate is set to 0.01.
{\bf (7)} Unless highest fitness value reaches the value of 1 nor generation exceeds 12000, 
individuals in upper subpopulation (40\%) survive to constitute the next generation with their offspring (60\%),
and the processes from (2) to (7) are repeated.\\

\noindent
Both these operations and parameter values were determined empirically.

\section{Results and Discussions}
In this section, 
we compare the results of the fitness evaluation using noisy inputs with the one obtained from our previous no-noisy version.
All these simulations were carried out on networks consisting of 49 neurons.\\

\noindent
In Figure~\ref{fitness}, we show the best-fitness vs. generation resulted from fitness evaluation with noisy/no-noisy input.
The dotted line in the figure is the representative sample from no-noisy version of the genetic algorithm.
A network with random weight is evolved and can store eventually a maximum of 8 patterns as fixed points at the \mbox{6449-$th$} generation.
Then this matrix is used as $W_{0}$ in noisy counterpart of our genetic algorithm.
The results are shown with solid line in the figure. The perfect solution emerged at the 6369-$th$ generation. 
This matrix also stores the above 8 patterns as fixed points.
In this latter experiment, we evaluate fitness by averaging over 20 repetitions giving 5 random noises each time.
Note that in this case, the best-individual will not be necessarily the best in the next generation even under the elitist strategy.
We also run this noisy version starting with random weight matrix instead,
however we have not obtained 100\% correct individuals to date (not shown in the figure).\\

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=fitness-08-r.eps,width=7cm,height=7cm}
   \caption{Fitness vs. generation for fitness evaluation with noisy/no-noisy input.}
   \label{fitness}
 \end{center}
\end{figure}

\noindent
This fitness evaluation with noisy input is designed to enlarge the size of basin of attraction.
In Figure~\ref{basin}, we show the degree of tolerance to noisy input of the two networks appeared in Figure~\ref{fitness}, 
together with the original Hebb-rule associative network.
In the figure, we plot the similarity of updated neuron-states for the noisy input to its complete pattern
as a function of number of noisy bits given to the input.
Network starts out with an initial configuration of neuron-states,
and this configuration changes in discrete time steps according to asynchronous update.
%% as was mentioned in Section 2.
When one of noisy input of stored patterns is given to the network, 
we are to obtain a configuration of the neuron-states after updating enough time steps (= 98 here).
And this is compared to the initial configuration of complete version of its input.
The comparison is made by using cosine of the angle between two vectors which represent the two configurations above.
These are averaged both over all inputs of stored patterns and over several runs (= 800 here).
To be more specific, 
each of the stored pattern $\xi^{\mu}$ is added $\nu$ bits of noise randomly, and given to the network to test the tolerance to the noise.
This is  repeated 800 times. 
Then the similarity $\zeta(\nu)$ is defined by
\begin{displaymath}
\zeta (\nu) = \frac {1}{800 \cdot p \cdot 49}  \sum_{k=1}^{800} \sum _{\mu=1}^{p} \sum _{j=1}^{49} {\xi_{j}^{\mu} \cdot s_{j \nu k}^{\mu}(98)},
\end{displaymath}
where $s_{j \nu k}^{\mu}(t)$ is 
the state of the $j$-$th$ neuron at time $t$ when the $k$-$th$ set out of these 800 combinations 
of $\nu$-bit-noisy $\mu$-$th$ pattern is given to the network.
The slower the decay of the curve, the broader the size of basin of attraction.
As we can see in the figure, the decay of the curve for the network obtained from no-noisy version is extremely steep.
It implies that although the genetic algorithm can evolve a random matrix to store all the 8 patterns as fixed points,
the size of basin of attraction is much smaller than that of the original Hebb-rule associative memory.
However, genetic algorithm with noisy input in evaluating fitness improves the size significantly,
though it is still smaller than the original Hebb-rule associative memory.

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=basin-08-r.eps,width=7cm,height=7cm}
   \caption{Similarity of updated states of a noisy input to its corresponding memory.}
   \label{basin}
 \end{center}
\end{figure}

\section{Conclusions}
In this paper, we have described an application of a genetic algorithm to fully connected Hopfield associative memory networks.
The feature of the proposed genetic algorithm is to use noisy input of the storage patterns in evaluating fitness values.
The goal is to enlarge the size of basin of attraction of the network.
Unfortunately, we found that it is very hard for the best-fit individual in the population to converge to 100\% correct solution,
compared to our previous implementation where fitness is evaluated with no-noisy input.
However, we are partly successful in enlarging 
the small basin size obtained in the previous implementation
by approximately a half of the size of the original Hebb-rule associative memory while maintaining its storage capacity.\\

\noindent
Though the results reported are not so satisfactory, these are only the beginning of our continuing research project.
There might be other implementations to control the size of basin of attraction more effectively, which we are now exploring.
And in addition, we are also exploring the evolution starting with Hebbian learned weight matrix instead of random weight matrix.\\

\noindent
Finally, we are also thinking of using this Hopfield model of associative memory as a test function of multi-modality
as well as an example of a multi-objective function.

\section*{Acknowledgments}
We thank Peter Davis at Advanced Telecommunication Research Institute (ATR).
The ideas in this paper were originally derived from discussions with him.

\begin{thebibliography}{99}

\bibitem{hopf}Hopfield, J. J., 
Neural Networks and Physical Systems with Emergent Collective Computational Abilities. 
{\it Proceedings of the National Academy of Sciences, USA} {\bf 79} (1982) 2554--2558.

\bibitem{hebb}Hebb, D. O., 
{\it The Organization of Behavior.} 
Wiley (1949)

\bibitem{yana}Yanai, H., Sawada, Y, and Yoshizawa, S.,
Dynamics of an Auto-Associative Neural Network Model with Arbitrary Connectivity and Noise in the Threshold. 
{\it Network} {\bf 2}(3) (1991) 295--314.

\bibitem{mori}Morita, M.,
Associative Memory with Nonmonotone Dynamics. 
{\it Neural Networks} {\bf 6} (1993) 115--126.

\bibitem{mcel} McEliece R. J., Posner E. C., Rodemick~E.~R., and Venkatesh S.~S.,
The Capacity of the Hofpield Associative Memory.
{\it IEEE Trans. Information Theory} {\bf IT-33}, (1987) 461--482.

\bibitem{pers}Personnaz, L., Guyon, I., and Dreyfus, G.,
Collective Computational Properties of Neural Networks: New Learning Mechanisms.
{\it Physical Review} A{\bf 34}(5) (1986) 4217--4227.

\bibitem{panc}Pancha G., Venkatesh S. S.,
Feature and Memory-Selective Error Correction in Neural Associative Memory.
in M.~H.~Hassoun (eds.) {\it Associative Neural Memories: Theory and Implementation.},
Oxford University Press, (1993) 225--238.

\bibitem{gard}Gardner, E.,
The Phase Space of Interactions in Neural Network Models.
{\it Journal of Physics} A: Math. Gen., {\bf 21A} (1988) 257--270.

\bibitem{hass}Hassoun, M. H. (eds.),
{\it Associative Neural Memories: Theory and Implementation.} 
Oxford University Press (1993)

\bibitem{holl}Holland, J.,
{\it Adaptation in Natural and Artificial Systems.}
The University of Michigan Press (1975)

\bibitem{gold}Goldberg, D.,
{\it Genetic Algorithms in Search, Optimization, and Machine Learning.} 
Addison-Wesley (1989)

\bibitem{whit}Schaffer, J. D., Whitley, D., and Eshelman, L. J.,
Combinations of Genetic Algorithms and Neural Networks: A Survey of the State of the Art.
{\it Proceedings of the Workshop on Combinations of Genetic Algorithms and Neural Networks} (1992) 1--37.

\bibitem{yao}Yao, X.,
A Review of Evolutionary Artificial Neural Networks.
{\it International Journal of Intelligent Systems} {\bf 8} (1993) 539--567.

\bibitem{imad}Imada, A., and Araki, K.,
Mutually Connected Neural Network Can Learn Some Patterns by Means of GA.
{\it Proceedings of the World Congress on Neural Networks} {\bf 1} (1995) 803--806.

\bibitem{imad-2}Imada, A., and Araki, K.,
Genetic Algorithm Enlarges the Capacity of Associative Memory.
{\it Proceedings of 6th International Conference on Genetic Algorithms} (1995) 413--420.

\end{thebibliography}

\end{document}


