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

\begin{document}

\title{Searching Real-Valued Synaptic Weights of Hopfield's Associative Memory \\using Evolutionary Programming}

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

\maketitle

\begin{abstract}
\noindent
We apply evolutionary computations to Hopfield model of associative memory.
Although there have been a lot of researches which apply evolutionary techniques to layered neural networks, 
their applications to Hopfield neural networks remain few so far.
Previously we reported that a genetic algorithm using {\it discrete encoding chromosomes}
evolves the Hebb-rule associative memory to enhance its storage capacity.
We also reported that the genetic algorithm evolves a network with random synaptic weights eventually  
to store some number of patterns as fixed points.
In this paper we present an evolution of the Hopfield model of associative memory
using evolutionary programming as a real-valued parameter optimization.
%%In this paper we present that an evolutionary programming evolves the Hopfield model of associative memory
%%as a real-valued parameter optimization.
\end{abstract}

\section{Introduction}
\noindent
Associative memory is a dynamical system which has a large number of stable states with a domain of attraction around them~\cite{koml}.
If the system starts at any state in the domain of attraction, it will converge to the stable state.\\

\noindent
In 1982, Hopfield proposed his fully connected neural network model of associative memory~\cite{hopf}.
The model consists of $N$ neurons and $N^2$ synapses, in which $p$ bipolar patterns 
\begin{displaymath}
{\xi}^{\nu} = ({\xi}^{\nu}_{1},\cdots,{\xi}^{\nu}_{N}) \hspace{.2in}({\nu} = 1, \cdots, p)
\end{displaymath}
are memorized in the form of stable equilibrium states.
He employed a discrete-time, asynchronous update scheme, i.e., 
each neuron receives inputs from all other neurons and updates its state according to the weighted sum of them. Namely,
\begin{displaymath}
s_{i}\hspace{.02in} (t+1) = f \hspace{.02in} \left( \hspace{.04in} \sum_{j \ne i}^N { w_{ij} s_{j}(t)} \hspace{.04in} \right),
\end{displaymath}
where $w_{ij}$ is a synaptic weight from neuron $j$ to neuron $i$, $s_{i}(t)$ is the state of $i$-th neuron at time $t$, 
and $f(z) = 1$ if $z \ge 0$, $-1$ otherwise. 
Asynchronous update means that at most one neuron is updated at a time.
Hopfield specified the synaptic weights $w_{ij}$ using the Hebbian rule~\cite{hebb},
\begin{displaymath}
w_{ij} = \sum _{ \nu = 1}^{p} {{ \xi }_{i}^{ \nu }{ \xi }_{j}^{ \nu }}\hspace{.1in}(i \ne j), \hspace{.2in} w_{ii} = 0.
\end{displaymath}
Then giving one of the memorized patterns, possibly including a few errors, to the network as an initial state
will result in the stable state after certain time steps of updating.
Hopfield suggested by using computer simulation that the maximum number of patterns to be stored in a network with $N$ neurons is $p=0.15N$,
if small errors in recalling are allowed.\\

\noindent
Later, this was theoretically calculated by Amit, Gutfreund \& Sompolinsky~\cite{amit} by using {\it replica} method, and showed that $ p=0.14N $.\\

\noindent
In 1987, McEliece, Posner, Rodemick \& Venkatesh~\cite{mcel} proved that when
\begin{displaymath}
p < \frac {N}{4 \ln{N}}
\end{displaymath}
holds, the network will recall the memory without error.\\

\noindent
The storage capacity is strongly dependent on how synaptic weights are specified. This is conventionally referred to as {\it learning}.
Other learning schemes instead of the Hebbian rule have been proposed for their increased storage capacity. 
For example, Kohonen \& Ruohonen~\cite{koho} proposed the {\it pseud-inverse matrix method} which has the capacity $p=0.5N$, and 
Pancha \& Venkatesh~\cite{panc} proposed the {\it spectral algorithm} which has the capacity $ p= N $.
Both are extensions of the Hebbian learning.\\

\noindent
On the other hand, if we prune the Hebbian synaptic weights, it will affect the storage capacity.
Derrida, Gardner \& Zippelius~\cite{derr} studied symmetrically diluted Hebbian synaptic matrices, and showed that 
the capacity, measured per surviving synapse, is significantly higher than that of fully connected network.\\

\noindent
In an earlier paper~\cite{imad-1}, we reported that fully-connected neural network with {\it random} synaptic weights 
evolved to store some number of patterns by optimally pruning some of its connections by means of a genetic algorithm~\cite{holl}.
The genetic algorithm uses {\it ternary} chromosomes made up of mostly 1 but a few of 0 and -1.
The resultant capacity was $p=0.16N.$
Note that we choose some connections {\it adaptively} and pruned them, while Derrida Gardner and Zippelius made it {\it randomly}.\\

\noindent
We also showed that the genetic algorithm enlarges the capacity of Hebb-rule associative memory~\cite{imad-2}.
In this experiment, we started with a network learned patterns more than the storage capacity by the Hebbian rule.
This matrix does not function reliably as associative memories because of these over-loaded patterns ($p > 0.15 N$).
Then the genetic algorithm evolved this matrix in the same way as above, and eventually all learned patterns became fixed point attractors.
The capacity was $p=0.33N$.\\

\noindent
Then what is the ultimate capacity obtained only by exploring learning schemes within the Hopfield's frame work?
The storage capacity, in general, is traded off against the basin size.
Gardner~\cite{gard} studied the optimal storage capacity as a function of the size of the basin of attraction.
She showed that the ultimate capacity will be 
\begin{displaymath}
p=2N,
\end{displaymath}
as basin size tends to zero. At the same time Gardner proposed an algorithm to obtain the weight matrix to realize the ultimate capacity.\\

\noindent
The storage capacity also depends on other aspects of neural networks.
For example, we can increase the storage capacity exponentially instead of proportionally by modifying the architecture of the network.
Chiueh \& Goodman~\cite{chiu} proposed a new architecture in which storage capacity scales exponentially with the number of neurons $N$,
and show that $2^N$ might be the ultimate storage capacity.\\

\noindent
From the discussions above, it does not seem to be interesting to study Hopfield model of associative memory any more.
However, there are almost infinite number of solutions in the synaptic connection's space.
Although a modest amount of them have been reported already as we mentioned above, they were all found heuristically. 
One reason why we are interested in the Hopfield's model is to obtain the insight into the overall distribution of these solutions.
Furthermore, due to its simplicity, Hopfield model of associative memory could be used as a test function for evaluation of  evolutionary computations.
The model has lots of local minima, some of which we already know as well as the global minimum in the sense of Gardener.
Hence our objective is to search these solutions by exploring the huge space rather than to seek the method of realizing high storage capacity.
Our search strategy is by giving a small perturbation $\eta_{ij}$ to each synaptic weight $W_{ij}$, as  Sompolinsky~\cite{somp} did, i.e., 
\begin{displaymath}
 w_{ij} = W_{ij} + \eta_{ij}.
\end{displaymath}

\noindent
From this point of view {\it evolutionary programming}~\cite{foge} seems to be very appropriate to start with.
Evolutionary programming is a technique for searching real parameter values by 
adding each parameter a normally distributed variance which undergoes adaptation.\\

\noindent
In the next section, we describe our evolutionary programming implementation briefly.

\section{Evolutionary Programming Implementation}
\noindent
In this simulation, a set of random bipolar patterns ${\xi}^{\nu}$ (${\nu} = 1, 2, \cdots, p$) are produced before each run.
The goal of the evolutionary programming is to find a weight matrix which stores all these patterns as fixed points.
A population of chromosomes are initialized at the beginning of a run. 
Each chromosome is constituted with $2N^2$ real-valued alleles 
which are $N^2$ object parameters, i.e., synaptic weights of a corresponding network (phenotype)
and the $N^2$ strategy parameters, i.e., standard deviations.
\begin{displaymath}
(w_{11}, \cdots, w_{NN},\eta_{11}, \cdots, \eta_{NN})
\end{displaymath}
In each generation, the chromosomes are modified through mutation operation.
The fitness values of each phenotype is evaluated.
According to the fitness values, individuals of the next generation are selected,
The cycle of reconstructing the new population with better individuals and restarting the search is repeated until a perfect
solution is found or a maximum number of generation has been reached.
Specific details of the operations are  as follows.

\begin{description}
\item[]{\bf Initialization:}
In the first generation, all chromosomes are initialized to be identical.
The phenotype corresponding to them is either of the following two. 
(a) All components of matrix are set to zero, or
(b) the matrix learns the pre-determined patterns more than capacity by the Hebbian rule.
In both cases, networks do not function as associative memories.
\item[] {\bf Fitness evaluation:}
When one of stored patterns ${\xi}^{\nu}$ is given to the network as an initial state, 
the state of neurons varies from time to time afterwards (unless ${\xi}^{\nu}$ is a fixed point).
In order for the network to function as an associative memory, these two states must be similar.
The similarity as a function of time is defined by,
\begin{displaymath}
m^{\nu}(t) = \frac{1}{N} \sum_{i=1}^{N} { {\xi}_{i}^{\nu} s^{\nu}_{i}(t) },
\end{displaymath}
where $s_{i}^{\nu}(t)$ is the state of the $i$-$th$ neuron at time~$t$.
This $m^\mu(t)$ is calculated for each stored pattern and averaged. We denote this as $\left \langle m(t) \right \rangle$
Then we define fitness value as a temporal average of this $\left \langle m(t) \right \rangle$.
Namely, the fitness value $f$ is
\begin{displaymath}
f = \frac {1}{t_{0} \cdot p}
\sum_{t=1}^{t_{0}}{\sum _{\nu=1}^{p}{m^{\nu}(t)} }.
\end{displaymath}
In this paper, $t_{0}$ is set to $2N$, twice the number of neurons.
Note that the fitness 1 implies all the $p$ patterns are stored as fixed points, while fitness less than 1 includes many other cases.
\item[] {\bf Selection:}
The fitness value of {\em each} individual of the union of $\mu$ parents and $\mu$ offspring
is compared with those of $q$ individuals randomly selected also from the union of $\mu$ parents  and $\mu$ offspring. 
Then the $2\mu$ individuals are ranked with the number of wins out of these $q$ tournaments, and $\mu$ best individuals survive to the next generation.
\item[] {\bf Mutation:}
The object parameters are mutated by
\begin{displaymath}
w^{k \mbox{(offspring)}}_{ij} = w^{k \mbox{(parent)}}_{ij} + {\eta}^{k}_{ij} \cdot N^{k}(0,1),
\end{displaymath}
where $N^{k}(0, 1)$  is a Gaussian random variable with mean 0 and standard deviation 1, sampled for each individual $k$.
This process is repeated and produces a total of $\mu$ offspring from $\mu$ parents. 
Then strategy parameters are mutated by
\begin{displaymath}
{\eta}^{k \mbox{(new)}}_{ij} = {\eta}^{k \mbox{(old)}}_{ij} + \sqrt{0.01 \cdot f^k} \cdot N^{k}(0,1).
\end{displaymath}
where $ f^{k}$ is the fitness value of $k$-th individual.
\end{description}

\section{Experiment}
\noindent
The parameters we used in the evolutionary programming are as follows.
The population number is 128. This is just because of our computer resources.
All the standard deviations in the first generations are set to 0.5.
The number of tournaments $q$ is chosen to be 32.
Searching procedure is iterated until 12000 generation unless perfect solution is not found.
These were determined mainly on the basis of trial and error.
All simulations were carried out on networks with 49 neurons.

\section{Results and Discussion}
\noindent
The goal of the algorithm is to find a solution, i.e., 
a combination of synaptic weights which gives the network a function of associative memory.\\

\noindent
The initialization of the individual matrices in the first generation is made in the following two ways.
One is to start with individual matrices whose components are all zero.
The other is to start with matrices which learn the memory patterns with Hebbian rule, but the number exceeds the capacity.
In both cases, all individuals in the first generation are the same, and they do not function as associative memory.\\

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=evolution.eps,width=9cm,height=9cm}
   \caption{\bf Fitness of the Best of Generation}
   \label{evolution}
 \end{center}
\end{figure}


\noindent
The effect of varying the number of patterns to be stored is studied.
Starting with a certain number $p$, we repeat the simulations 30 times with different random number seeds for each $p$.
If we find the perfect solution(s) we increment the number $p$.
Thus, we found a matrix evolved to store a maximum of 6 patterns 
starting with weight matrices of all zero components,
and a maximum of 13 patterns starting with over-loaded Hebbian weight matrices. 
In Figure~\ref{evolution}, we show the results.
Both converge to the perfect solution at generation 7848 and 10858, started with random and Hebbian matrices respectively.\\

\noindent
As Hertz, Grinstein \& Solla\cite{herz} and Parisi\cite{pari} suggested in their analysis using Ising model,
we conjectured that the success in the case of starting with over-loaded Hebbian matrices
is due to the destabilization of the spin-glass attractors by the asymmetry of synaptic weights introduced by mutations.\\

\noindent
To see this, we investigated the time evolution of degree-of-symmetry of weight matrices.
The degree-of-symmetry is defined by
\begin{displaymath}
\sigma = \sum_{i=1}^{N} \sum_{j=1}^{N} {w_{ij} w_{ji}} \cdot \left( \sum_{i=1}^{N} \sum_{j=1}^{N} {w_{ij}^{2}} \right)^{-1},
\end{displaymath}
following after Krauth, Nadal \& Mezard~\cite{krau}.
We show the results of both experiments in Figure~\ref{symmetry}. 
Clearly, the figure show that the two resultant matrices above belong to different classes of solutions.\\

\noindent
In the simulation starting with over-loaded Hebbian matrices, the degree of symmetry decreases and 
asymptotically approaches to the value around 0.6 as retrieval states emerge.
On the contrary, in the simulation starting with all-zero matrices, we can see the ratio fluctuate around 0.1,
showing that we need some extent of symmetry to obtain the function of associative memory.
However the role of asymmetry of the synaptic weights is still an open question.

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=symmetry.eps,width=8cm,height=8cm}
   \caption{\bf Degree of Symmetry}
   \label{symmetry}
 \end{center}
\end{figure}

\noindent
To say a network an associative memory system, the tolerance for certain amount of noises should be shown.
That is, each memorized pattern must have a certain domain of basin of attraction.\\

\noindent
As the criterion of basin size, we used somewhat similar definition to the one by Verleysen, Legat, \& Jespers~\cite{verl},
That is, 1000 initial state patterns are generated by randomly picking up a memory pattern and flipping $d$ bits. 
Then they are given to the network 
and updated the state $2N$ times (possibly it reaches a stable state). The resulting states is then compared with the original memory pattern,
and the run is called a success if they match {\it exactly}. 
In Figure \ref{basin}, the number of successes out of 1000 runs of the above two experiments are plotted against the number of input errors $d$,
%%we also show the results of Hebbian synaptic weights without evolution for $p=8$ for convenience.
we also show the results of the weight matrices derived from Gardner's algorithm for the same number of patterns.
We can see that 
the network resulted from the above two experiments still maintain the tolerance of noisy input, although the size of basin of attraction is 
much smaller than those derived from  Gardner's algorithm. 
%%the Hebb rule associative memory.

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=basin.eps,width=8cm,height=8cm}
   \caption{\bf Error Correcting Capability}
   \label{basin}
 \end{center}
\end{figure}

\section{Conclusions}
We have described an application of evolutionary programming to fully connected neural network model of associative memory.
The objective of these experiments is to find some solutions of real-valued synaptic weight matrix 
which gives a network a function of associative memory.\\

\noindent
The simulations in this paper were made with 49 neurons.
This size of Hebb-rule associative memory would store at most 7 random bipolar patterns as fixed points.
The evolutionary programming finds  solutions one of whice stores 6 patterns ($p = 0.12 N$) 
and the other stores 13 patterns ($p = 0.27 N$) starting with zero and Hebbian matrices, respectively.\\

\noindent
We have also shown a brief analysis using time expansion of degree of symmetry.
Those phenomena we described in this paper seem to be
more or less due to asymmetry of weight matrix introduced by the evolutionary programming. \\

\noindent
Up to now, our investigations on the Hopfield model of associative memory using the evolutionary programming have not been conclusive.
Work is continuing in the problems such as:
\begin{itemize}
\item[(1)] exploring only within a small domain of a known solution, instead of wondering whole space as in this paper; and
\item[(2)] obtaining minimum amount of perturbation of a synaptic weight which affect the performance of associative memory.
\end{itemize}
These are possible only by the method without crossover like the evolutionary programming.
Finally, 
\begin{itemize}
\item[(3)] starting with random matrices uniformly distributed in whole space, instead of starting with all-zero-component matrices.
\end{itemize}
This may enable us to locate to the global optimum solution in the sense of Gardner.

\section*{Acknowledgments}
\noindent
We thank Peter Davis at Advanced Telecommunication Research Institute (ATR)
for providing us great insight into the dynamics of Hopfield neural networks.
Thanks are also due to anonymous reviewers for comments and encouragements on this work.

\begin{thebibliography}{99}

\bibitem{koml}J.~Koml\'{o}s, and R. Paturi (1988)
{\em ``Convergence Results in an Associative Memory Model.''} 
Neural Networks 1, pp239--250.

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

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

\bibitem{amit}D. J. Amit, H.~Gutfreund, and H.~Sompolinsky (1985)
{\em ``Storing Infinite Number of Patterns in a Spin-glass Model of Neural Networks.''}
Physical Review Letters 55, pp1530-1533.

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

\bibitem{koho} T. Kohonen, and M. Ruohonen (1973)
{\em `` Representation of Associated Data by Matrix Operators.''}
IEEE Trans. Computers C-22(7),  pp701--702.

\bibitem{panc}G. Pancha, S. S. VenKatesh (1993)
{\em ``Feature and Memory-Selective Error correction in Neural Associative Memory.''}
in M.~H.~Hassoun eds. Associative Neural Memories: Theory and Implementation,
Oxford University Press, p225--248.

\bibitem{derr} B. Derrida, E. Gardner, and A. Zippelius (1987)
{\em ``An Exactly Soluble Asymmetric Neural Network Model.''}
Europhys. Lett. 4,  pp167--173.

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

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

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

\bibitem{gard} E. Gardner (1988)
{\em ``The Phase Space of Interactions in Neural Network Models.''}
J. Phys 21A, pp257-270.

\bibitem{chiu} T. D. Chiueh, and R. M. Goodman (1991)
{\em ``Recurrent Correlation Associative Memories.''}
IEEE Trans. Neural Networks 2(2), pp275--284.


\bibitem{somp}H. Sompolinsky (1986)
Neural Network with Non-linear Synapses and Static Noise
Phys.Rev. A34  pp2571-2574

\bibitem{foge} D.~B.~Fogel (1992)
{\em ``An Analysis of Evolutionary Programming.''}
Proceedings of 1st Annual Conference on Evolutionary Programming, pp43--51.

\bibitem{herz} J. A. Hertz, G. Grinstein, and S. A. Solla (1987)
{\em ``Irreversible Spin Glasses an Neural Networks.''}
in L. N. van Hemmen and I. Morgenstern eds. Heidelberg Colloquium on Glassy Dynamics. Lecture Notes in Physics 275 Springer-Verlag, pp538--546.

\bibitem{pari} G. Parisi (1986)
{\em ``Asymmetric Neural Networks and the Process of Learning.''} J. Phys. A19, ppL675--L680.

\bibitem{krau}W. Krauth, J.-P. Nadal, and M.Mezard (1988)
{\em The Roles of Stability and Symmetry in the Dynamics of Neural Networks.}
J. Phys. A: Math. Gen. 21, pp2995--3011.

\bibitem{verl} M. Verleysen, J.-D. Legat, and P. Jespers (1993)
{\em Analog implementation of an Associative Memory: Learning Algorithm and VLSI Constraints.}
in M.~H.~Hassoun eds Associative Neural Memories: Theory and Implementation, Oxford University Press, pp265--275.

\end{thebibliography}

\end{document}
