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

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

\begin{document}

\title{Evolved Asymmetry and Dilution of Random Synaptic Weights in Hopfield Network
       Turn a Spin-glass Phase into Associative Memory}
%%\title{Evolutionary Asymmetry and Dilution of Random Synaptic Weights: Departure from Spin-glass to an Associative Memory}

\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

%%\begin{small}
\noindent
{\bf Abstract} -- We apply evolutionary computations to Hopfield's neural network model of associative memory.
Previously, we reported that a genetic algorithm can enlarge the Hebb rule associative memory 
by pruning some of over-loaded Hebbian synaptic weights.
In this paper, we present the genetic algorithm also evolves {\it random} synaptic weights 
to store some number of patterns.
%%was evolved to recover all the retrieval states by prunning some of its synaptic weights with a genetic algorithm.
%%The storage capacity was 33% of the number of neurons. 
%%to more challenging random synaptic weight matirx instead of Hebbian one. We successfuly evolve it to store patterns of \%16 of the number of neruons.
%%\end{small}

\section{Introduction}
\noindent
There have been a lot of researches which apply evolutionary techniques to layered neural networks
(see e.g.,~\cite{whit,yao} and references quoted therein).
However, their applications to fully-connected recurrent neural networks remain few so far.
In this paper, we present some basic behaviors of the Hopfield model of associative memory under simple evolutionary processes.

Associative memory is a dynamical system which has a number of stable states 
with a domain of attraction around them \cite{koml}.
Applying a vector 
\( \mbox{\boldmath $x$}_{0} \) 
as the initial state of the dynamical system results in the state trajectory
\( \{ \mbox{\boldmath $x$}_{t} \}_{t \ge 0} \).
If we start the system with 
\( \mbox{\boldmath $x$}_{0}=\mbox{\boldmath $u$} + \mbox{\boldmath $\delta u$} \) 
in the vicinity of some fixed point \( \mbox{\boldmath $u$} \), 
and the state trajectory converges to \( \mbox{\boldmath $u$} \), i.e., 
\( \lim_{t \to \infty} \mbox{\boldmath $x$}_{t} = \mbox{\boldmath $u$} \),
then we can regard the system as an associative memory.

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.
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{.1in}({\nu} = 1, \cdots, p)
$
%%\end{displaymath}
are to be memorized as equilibrium states.
He employed a discrete-time, asynchronous update scheme.
That is, each neuron updates its state, one at a time, according to 
%%the sign of the weighted sum of of the states of all other neurons, i.e.,
\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 $s_{i}(t)$ is a state of $i$-th neuron at time $t$, $w_{ij}$ is a synaptic weight from neuron $j$ to neuron $i$, 
and $f(z) = 1$ if $z \ge 0$ and $-1$ otherwise. 

%%Asynchronous update means that at most one neuron is updated its state at each time step.
The behaviors of the collective states of the individual neurons are characterized by the synaptic weights.
%%the $N^{2}$ synaptic weights $w_{ij}$.
When these synaptic weights are determined appropriately, networks store some number of patterns as fixed points.
Hopfield specified $w_{ij}$'s by the Hebbian rule \cite{hebb}, i.e.,
\begin{displaymath}
%%$
w_{ij} = \sum _{ \nu = 1}^{p} {{ \xi }_{i}^{ \nu }{ \xi }_{j}^{ \nu }}\hspace{.02in}(i \ne j), \hspace{.02in} 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.
He suggested by using computer simulation that the maximum number $p$ of the patterns to be stored in a network with $N$ neurons is $0.15N$,
if a small error in recalling is allowed.
Later, this was theoretically calculated by Amit et al.~\cite{amit} by using {\it replica} method. 
They showed that the storage capacity is $ p=0.14N $.
%%Amit, Gutfreund \& Sompolinsky\cite{amit}
In 1987, McEliece et al.~\cite{mcel} proved that when
%%McEliece, Posner, Rodemick \& Venkatesh\cite{mcel}
%%\begin{displaymath}
$
p < N / 4 \ln N
%%p < \frac {N}{4 \ln{N}}
$
%%\end{displaymath}
holds, the Hopfield's model will recall the memory without error.

The storage capacity depends strongly on how synaptic weights are specified. 
The specification of the synaptic weights is conventionally referred to as {\it learning}.
Other learning schemes instead of Hebbian rule have been proposed for their increased storage capacity. 
The {\it pseud-inverse matrix} method by Kohonen et al.~\cite{koho}
and {\it spectral algorithm} by Pancha et al.~\cite{panc} 
are the examples, and the capacity is enlarged to $ p=0.5N $ and $p=N$, respectively.
%%by Kohonen \& Ruohonen\cite{koho}
%%{\it spectral algorithm} by Pancha \& Venkatesh\cite{panc}
Both are extensions of the Hebbian learning.

%The specification of synaptic weights also implies that pruning the connection of Hebbian weights.
%%Derrida et al.~\cite{derr} studied a symmetrically diluted Hebbian synaptic matrices and showed that 
%%the capacity, measured per surviving synapse, is significantly higher than that of the fully connected network.

Then, what is the ultimate capacity when only the learning scheme is explored within the Hopfield's framework?
Generally the storage capacity is traded off against basin size.
Gardner\cite{gard} studied the optimal storage capacity as a function of the size of basin of attraction.
She showed that as basin size tends to zero the ultimate capacity will be 
%%\begin{displaymath}
$
p=2N,
$
%%\end{displaymath}
%%as well as proposing an algorithm to obtain weight matrix to realize the capacity.
proposing an algorithm to obtain the weight matrix.

The storage capacity also depends on the other aspects of neural networks.
%%For example, we can increase the storage capacity exponentially instead of proportionally by modifying the architecture of the network.
For example, we can increase the capacity {\it exponentially} instead of {\it proportionally} by modifying the architecture of the network.
%%Chiueh \& Goodman\cite{chiu}
Chiueh et al.~\cite{chiu} proposed a new architecture in which 
storage capacity scales {\it exponentially} with $N$, the number of neurons.
They showed that $2^N$ might be the ultimate upper bound for the capacity.\\
\indent
However, for some reason,  we are interested in exploring synaptic weight space with Hopfield's scheme unchanged.\\
\indent
In this framework, we previously used a genetic algorithm \cite{holl,gold} to modify the Hopfield's Hebbian synaptic weights \cite{imad-2}.
If the patterns which exceed the capacity are learned by Hebbian rule, the memories are more or less collapsed.
We succeeded in evolving this over-loaded Hebbian weights to re-store all the patterns as fixed points,
and obtained the capacity $p = 0.33N$.
In this paper, we apply the genetic algorithm to more challenging random synaptic weights.

\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.
Chromosomes 
in each generation modify this initial matrix to produce a population of weight matrices as follows.
\begin{displaymath}
 w_{ij} = c_{ij} \times R_{ij}, \hspace{.08in}  c_{ij} \in \{1, 0, -1\}.
\end{displaymath}
These are evaluated their fitness values.
According to the fitness values, two parent chromosomes are selected to be recombined to produce 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.
%%, i.e.,ternary chromosome.
\item[(2)] {\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 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 these 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)}
We use ($\mu + \lambda$)-selection in evolution strategy terminology.
Two parent chromosomes are chosen {\it randomly} from the best 40\% of the population ($=\mu $).
\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}
The procedures (3)--(5) are repeated until all the individuals in the worst 60\% of the population (= $\lambda$) are replaced with the offspring.

\end{description}

\noindent
The above operations and parameter values were determined mainly on the basis of trial and error.
%%Note that both are not necessarily optimized.

\section{Results and Discussion}
\noindent
Since the initial matrix to start with is completely random,
all the networks in the first generation do not function as an associative memories, but are full of spin-glass attractors.
The goal of this paper 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$ 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 7 patterns.
We shows representative sample of the best fitness vs. generation in Figure \ref{evolution}.
\indent
In this experiment, optimization are made by pruning  synaptic connections as well as balancing the number of excitatory/inhibitory synapses,
with using $c_{ij} \in \{1, 0, -1\}$.
For comparison purposes, we also experimented with $c_{ij} \in \{1, -1\}$ and with $c_{ij} \in \{1, 0\}$.
The results for 7 patterns are also shown in Figure~\ref{evolution}. We can see that balancing the number of excitatory/inhibitory synapses 
plays  more important roll than pruning synapses. 
The number of patterns each resultant matrix can store as fixed points is 3 and 0, respectively.
And the maximum $p$ in each experiment is 6 and 3, respectively.

\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*{Asymmetry and Dilution of Synaptic Weights}
We conjectured that the emergence of retrieval states is due to the destabilization of the spin-glass attractors 
by the asymmetry and dilution of synaptic weights, as Herz et al.~\cite{herz} suggested.\\
\indent
To see this, we investigated the time evolution of degree-of-symmetry and dilution rate 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 et al.~\cite{krau}.
As in Figure~\ref{symmetry}, both ratios increase from 0 and asymptotically approach to the value between 0.15 and 0.2 
as retrieval states emerge.
%%as stored memories are stabilized.

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=symm-zero.eps,width=6.3cm,height=6.3cm}
   \caption{\bf Degree of Symmetry and Dilution Rate}
   \label{symmetry}
 \end{center}
\end{figure}

\subsubsection*{Basin of Attraction}
To regard a network an associative memory system, it should show the tolerance for certain amount of noises.
That is, each memory pattern must have a certain domain of basin of attraction.\\
\indent
As the criterion of basin size, the definition by Verleysen et al.~\cite{verl} are used.
We generate 1000 initial state patterns by randomly picking up a stored 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 corresponding stored 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 are plotted against the number of input errors $d$.
We also plot the result of the original Hebbian synaptic weights for convenience.
Although the networks resulted from the above experiments have extremely small size of basin of attraction,
we can see that they still have an error-correcting capability.

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

\section{Conclusions}
We have described an application of a genetic algorithm to Hopfield model of associative memory. 
The genetic algorithm modify a pre-specified weight matrix by multiplying the alleles
of the ternary chromosome consists of 1, 0, and -1 to the corresponding components of the  starting matrix.\\
\indent
The simulations were made with 49 neurons.
This size of Hebb-rule associative memory would store at most 8 random bipolar patterns as fixed points.
The patterns stored by the matrix found by the genetic algorithm is a little fewer than that.
However this is amazing in that the evolution was started with completely random synaptic weights only 
by pruning some of its connection and by balancing the number of excitatory/inhibitory synapses.

We conjecture that the success is  more or less due to the asymmetry and dilution of synaptic weights introduced by the genetic algorithm.

%%\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{whit}J.~D.~Schaffer, D.~Whitley, and L.~J.~Eshelman (1992)
{\em ``Combinations of Genetic Algorithms and Neural Networks: A Survey of the State of the Art.''}
Proceedings of the Workshop on Combinations of Genetic Algorithms and Neural Networks, 1.

\bibitem{yao}X.~Yao (1993) 
{\em ``A Review of Evolutionary Artificial Neural Networks.''}
International Journal of Intelligent Systems, vol.8, 539.

\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{amit}D. J. Amit, H.~Gutfreund, and H.~Sompolinsky (1985)
{\em ``Storing Infinite Number of Patterns in a Spin-glass Model of Neural Networks.''}
Phys. Rev Lett. 55,  1530.

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

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

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

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

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

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

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

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

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

\end{thebibliography}

\end{document}

\bibitem{rech} I. Rechenberg (1965)
{\em ``Cybernetic Solution path of an Experimental Problem.''}
Royal Aircraft Establishment, Library Translation, p1122 (Hants UK).

\bibitem{back} T.~B\"{o}ck, and H.-P. Schwefel (1993)
{\em ``An Overview of Evolutionary Algorithms for Parameter Optimization.''}
Evolutionary Computation 1(1), p1.

%%\bibitem{srin}V. Srinivas, and K. Deb (1994)
%%{\em ``Multiobjective Optimization using Nondominated Sorting in Genetic Algorithms.''}
%%Evolutionary Computation (MIT Press) 2(3) pp221-248.

\bibitem{gold-2}Goldberg, and Richardson

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

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

\bibitem{rech} I. Rechenberg (1965)
{\em ``Cybernetic Solution path of an Experimental Problem.''}
Royal Aircraft Establishment, Library Translation No.1122 (Hants UK).

\bibitem{back} T.~B\"{o}ck, and H.-P. Schwefel (1993)
{\em ``An Overview of Evolutionary Algorithms for Parameter Optimization.''}
Evolutionary Computation 1(1), p1.

\bibitem{kirk} S. Kirkpatrick, and D. Sherrington (1978)
{\em ``Infinite-ranged models of Spin-glasses.''} 
Phys. Rev. B17, p4384.



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



