%\documentstyle[twocolumn,epsf]{article}
\documentstyle[twocolumn,eclepsf]{article}

\textheight 230mm
\textwidth 175mm
\topmargin -10mm
\oddsidemargin -7mm

\begin{document}

\title{Evolution of Random Synaptic Weights of the Hopfield Associative Memory: How Chaotic Trajectories Turn into Fixed Point Attractors?}


\author{\begin{small}
        \begin{minipage}[t]{8.5cm}
        \begin{center}
        Akira Imada\\
        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]{8.5cm}
        \begin{center}
        Keijiro Araki\\
        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
        \end{center}
        \end{minipage}\end{small}}

\date{}
\maketitle

\noindent
{\bf Abstract} -- We apply evolutionary computations to Hopfield's neural network model of associative memory.
We reported elsewhere that a fully connected neural network with random synaptic weights evolves to create fixed point attractors 
exactly at the locations of patterns to be memorized by a genetic algorithm.
In this paper, we present the process in which a network that has shown chaotic behaviors at the start evolves eventually
to converge to fixed point attractors.

\section{Introduction}
\noindent
Associative memory is a dynamical system which has a number of stable states with a domain of attraction around them~\cite{koml}.
If the system starts at any state in the domain, it will converge to the stable state.
In 1982, Hopfield~\cite{hopf} proposed a fully connected neural network model of associative memory
in which we can store information by distributing it among neurons, and we can recall it from its noisy and/or partial input.

The dynamical behavior of its neuron states strongly depends on synaptic strength (weight) between neurons.
Hopfield used  the Hebbian rule~\cite{hebb} to prescribe the weights.
We explore it with a genetic algorithm (GA)~\cite{holl,gold}.

Previously, we reported that a fully connected neural network with random synaptic weights evolves to create fixed point attractors 
exactly at the locations of patterns to be memorized by a GA~\cite{imad-2,imad-8}.
Here, we study the evolution in more detail by analyzing the network states visited by the dynamics.

\section{The Hopfield Model}
The model consists of $N$ neurons and $N^2$ synapses.
Each neuron can be in one of two states $\pm 1$, and $p$ bipolar patterns
\begin{displaymath} 
{\xi}^{\nu} = ({\xi}^{\nu}_{1},\cdots,{\xi}^{\nu}_{N}), \hspace{.2in}{\nu} = 1, \cdots, p
\end{displaymath}
where $\xi^{\nu}_{i}$ takes the value of either 1 or $-1$, are to be memorized as equilibrium states.
Hopfield employed a discrete-time, asynchronous update scheme.
Namely, at most one neuron updates its state at a time\footnote
{Though Hopfield chose one neuron at a time {\it randomly}, in this paper, a neuron is chosen according to pre-assigned order 
(once in a cycle).}, according to 
\begin{displaymath}
s_{i}\hspace{.02in} (t+1) = sgn \hspace{.02in} \left( \hspace{.04in} \sum_{j \ne i}^N { w_{ij} s_{j}(t)} \hspace{.04in} \right),
\end{displaymath}
where $s_{i}(t)$ is a state of $i$-th neuron at time $t$.
The behaviors of the collective states of individual neurons are characterized by the synaptic weights.
When these synaptic weights are determined appropriately, the network stores some number of patterns as fixed points.
Hopfield specified these $w_{ij}$'s by the Hebbian rule \cite{hebb}, i.e.,
\begin{displaymath}
w_{ij} = \frac{1}{N} \sum _{ \nu = 1}^{p} {{ \xi }_{i}^{ \nu }{ \xi }_{j}^{ \nu }}\hspace{.1in}(i \ne j), \hspace{.1in} w_{ii} = 0.
\end{displaymath}
Then giving one of the memorized patterns to the network as an initial state, possibly including a few errors, 
will result in the stable state after certain time steps of updating.

\section{GA Implementation}
\noindent
In this simulation, a weight matrix $R_{ij}$ is produced randomly before the start of the GA run, and remains unchanged during the evolution.

In each generation, chromosomes, made up of mostly 1 but a few of -1 and 0 (allele), 
modify this initial matrix by multiplying the alleles to the component of $R_{ij}$
to produce a population of weight matrices.
%% $w_{ij}$, i.e.,
%%\begin{displaymath}
%% w_{ij} = c_{ij} \times R_{ij}, \hspace{.08in}  c_{ij} \in \{1, 0, -1\}.
%%\end{displaymath}

%%Chromosomes, made up of mostly 1 but a few of -1 and 0, modify this initial matrix in each generation
%%to produce a population of weight matrices $w_{ij}$, i.e.,
%%\begin{displaymath}
%% w_{ij} = c_{ij} \times R_{ij}, \hspace{.08in}  c_{ij} \in \{1, 0, -1\}.
%%\end{displaymath}
Then the obtained matrices are evaluated their fitness values by counting how many patterns are stored as fixed points.
According to the fitness values, two parent chromosomes are selected to be recombined to make one offspring.
The offspring is mutated occasionally and reconstructs the next generation.\\
\indent
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.
The specific details are as follows.
\begin{description}
\item[(1)]{\bf (initialization)}
Chromosomes are $N^2$-dimensional vectors, 
and they are initialized so that their components are randomly selected from $\{1, 0, -1\}$ with the probability of .98, .01 and .01, respectively.
\item[(2)] {\bf (fitness evaluation)}
When ${\xi}^{\nu}$, one of the patterns to be stored, 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 is referred to as {\it overlap} by convention. 
In evaluating the fitness value, 
the temporal average of the overlap 
%%until certain time $t_0$, 
$\left \langle m^{\nu} \right \rangle$
is calculated for each stored pattern.
Then they are also averaged over all patterns. That is, 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.
%%, and we observed that was enough.
Note that the fitness 1 implies all the $p$ patterns are stored as fixed points, while fitness less than 1 includes many possible other cases.
\item[(3)] {\bf (selection)}
Two parent chromosomes are chosen {\it randomly} from the best 40\% of the population to be recombined.
\item[(4)] {\bf (recombination)}
Recombinations are made with {\it uniform crossover} \cite{sysw}, 
operating on alleles of the selected parents' chromosomes, i.e., 
two parents $(u_1, \cdots, u_n)$ and $(v_1, \cdots, v_n)$ produce an offspring $(w_1, \cdots, w_n)$
such that $w_i$ is either $u_i$ or $v_i$ with equal probability.
\item[(5)] {\bf (mutation)}
Mutation is made by rotating the allele as follows.
\begin{displaymath}
\{1\} \rightarrow \{-1\}, \hspace{.1in} \{-1\} \rightarrow \{0\}, \hspace{.1in}\{0\} \rightarrow \{1\}
\end{displaymath}
\end{description}
The procedures (3)--(5) are repeated until all the individuals in the worst 60\% of the population are replaced with the offspring.



\noindent
%%The above operations and parameter values were determined mainly on the basis of trial and error.

\section{Experimental Results}
\subsubsection*{Evolution of Random Synaptic Weights}
\noindent
Since the initial matrix is completely random,
all the networks in the first generation do not function as an associative memory.
The goal of the GA is to find the optimal combinations of $c_{ij} \in \{1, 0, -1\}$ which modify 
the initial matrix by multiplying them to the corresponding components of the matrix.
 
All simulations were carried out on networks with 49 neurons.

First, the effect on evolution of varying $p$, the number of given patterns, is studied.
We repeat each simulation 30 times with different random number seed for the same $p$. 
If we find the perfect solution(s) then we increment $p$.
Thus, we found a matrix evolved to store a maximum of seven patterns.
In Figure~\ref{evolution}, we show the representative sample of the best fitness vs. generation for these seven patterns.
At generation 2312, a network that stores all the seven patterns as fixed points emerges.

In the next two subsections, we present the dynamical behavior of this evolution.

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

\subsubsection*{How the Chaotic Trajectories turn to Attractors?}
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=trajectory-0154.eps,width=6.3cm,height=3.2cm}
   \epsfile{file=trajectory-0200.eps,width=6.3cm,height=3.2cm}
   \epsfile{file=trajectory-0210.eps,width=6.3cm,height=3.2cm}
   \epsfile{file=trajectory-0240.eps,width=6.3cm,height=3.2cm}
   \epsfile{file=trajectory-0300.eps,width=6.3cm,height=3.2cm}
   \epsfile{file=trajectory-1000.eps,width=6.3cm,height=3.2cm}
   \epsfile{file=trajectory-2200.eps,width=6.3cm,height=3.2cm}
   \caption{\bf Trajectories Resulted from 7 Inputs.}
   \label{trajectory}
 \end{center}
\end{figure}

In the Hopfield model of associative memory, 
an initial state of the network determined by an input is to be updated from time to time.
We can observe this by the temporal expansion of the Hamming distance between an instantaneous network state and the input.

In Figure~\ref{trajectory}, the Hamming distance of instantaneous network state from the input is plotted against updating time
as snapshots during the evolution.

Since we started with random synaptic weights, any input of the given patterns results in the chaotic trajectory in an early generation
(Figure~\ref{trajectory}-a).
Then, an attractor appears (Figure~\ref{trajectory}-b).
Thereafter, the number of the attractors increases (Figure~\ref{trajectory}-c).
As evolution proceeds further, chaotic trajectories disappear (Figure~\ref{trajectory}-d).
In the mean time, some limit cycle trajectories occasionally appear and disappear (Figure~\ref{trajectory}-e).
In the last stage of the evolution, the  location of the most of these attractors are shifted towards the patterns to be memorized.
At generation 1000, for example, the locations of five out of seven attractors coincide with the given patterns, 
and the other two locations are within 5 hamming distance from the patterns (Figure~\ref{trajectory}-f).
It requires a long time for these near-fixed-point-attractors to disappear (Figure~\ref{trajectory}-g).
Finally, at generation 2312, seven fixed point attractors are created exactly at the location of each given pattern.

\subsubsection*{There Still Remains Spurious Attractors}
We observed the basin size of the network as follows.
An input is randomly sampled from the given patterns.
After $d$ bits are flipped at random, this is given to the network.
The temporal average of the {\it overlaps} between the input and  the network state visited by the dynamics is calculated.
In Figure~\ref{basin}, the averaged overlap over 800 runs are plotted against noisy-bit $d$.
We also show the result of the Hebb rule associative memory which stores the same seven patterns.

As shown in the figure, the obtained matrix has comparatively small basin of attraction.
This is probably due to  remaining spurious attractors around the created memories.

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=basin.eps,width=6.3cm,height=6.3cm}
   \caption{\bf Basin of Attraction}
   \label{basin}
 \end{center}
\end{figure}

\section{Conclusions}
We have shown that a fully connected neural network with random synaptic weights evolves to function as an associative memory.
This is by pruning some of the connections and reversing some excitatory/inhibitory connections {\it adaptively} by a GA.
Before the GA runs, the network shows chaotic behavior due to its random synaptic weights.
As evolution proceeds, these chaotic trajectories turn to attractors, though their locations are apart from the patterns to be memorized.
Then, they gradually approach to the location of the given patterns.
Finally, all locations of these attractors coincide with the given patterns.
We have shown this process by showing some input trajectories during the evolution.

It is surprising to see that the learning of the patterns is only by finding the optimum combination of 1, 0, -1 
to be multiplied to the component of a randomly chosen weight matrix $R_{ij}$.
The absolute values of the synaptic weights remain unchanged except that some of them are zeroed.
We conjectured that the evolution is partly due to the destabilization of the spin-glass attractors 
by the asymmetry and dilution of synaptic weights, as Herz et al.~\cite{herz} suggested.

However, we have not known the reason of this process well, so far.
Especially, the fate of the chaotic trajectories in the early stages of the evolution 
and the possibility to remove the still-remained-spurious-attractors are interesting to be revealed.
We leave these problems to our future study.



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

\begin{thebibliography}{99}

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

\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,  2554.

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

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

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

\bibitem{imad-2} 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, 803.

\bibitem{imad-8}A. Imada, and K. Araki (1997)
{\em Evolved Asymmetry and Dilution of Random Synaptic Weights in Hopfield Network Turn a Spin-glass Phase into Associative Memory.}
The 2nd International Conference on Computational Intelligence and Neuroscience,
Proceedings of Joint Conference of Computer Science, vol. {\bf 2},  pp223--226.

\bibitem{sysw}G. Syswerda (1989)
{\em ``Uniform Crossover in Genetic Algorithms.''}
Proceedings of the 3rd International Conference on Genetic Algorithms, 2.

\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 No.275 Springer-Verlag, 538.

\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, 2995.

\end{thebibliography}

\end{document}
