\documentstyle[12pt,eclepsf]{llncs}
\begin{document}

\title{What does a Peak in the Landscape\\ of a Hopfield Associative Memory Look Like?}
\author{Akira Imada}
\institute{Nara Institute of Science and Technology\\
           1-11-13-604 Abeno, Hannan, Osaka 545-0021 Japan\\
           ai@kk.iij4u.or.jp}
\maketitle

\begin{abstract}
\noindent
Performance of an evolutionary algorithm usually depends on the shape of fitness surface (landscape)
defined on the solution space.
Hence, learning a geometry of the surface is a very important issue 
to predict the performance of an evolutionary algorithm.
In real world problem, however, it is usually very difficult to know the information of the surface
such as the number and distribution of peaks on the surface, the height and width of the peaks and so on.
In this paper, we address how we can learn the shape of a peak on the surface
by using the fairly well studied Hopfield model of associative memory as a test function.
\end{abstract}

\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.
Hopfield \cite{hopf} proposed a fully connected neural network model of associative memory
in which information is stored by being distributed among neurons, and
we can retrieve the information from dynamically relaxed neurons' states.
In the model, some of the appropriate configurations 
of synaptic weights give the network a function of associative memory.
Namely, the network stores a {\it fixed} set of bipolar patterns, sequences of $+1$ and $-1$, as attractors.
Thus, the capability to store a set of patterns defines a fitness landscape on synaptic weight space,
or equivalently, a hyper-plane defined on all the possible configurations of weight values of a network.
In contrast, a {\it fixed} configuration of synaptic weights also defines fitness landscape on {\it pattern space}.
For example, the weight configuration prescribed by the learning algorithm proposed by Hebb \cite{hebb} 
to store a set of given patterns 
creates a fitness landscape which has the {\it global} peaks at the locations of given patterns 
as well as many other {\it local} peaks.
In this paper, we explore the landscape constructed on synaptic weight space.
The ultimate goal of this study is to learn the whole geometry of the landscape
including the number and distribution of the solutions in weight space, which is still an open issue.
Towards this goal, we address the shape of peaks on the landscape here.

The remainder of this paper is organized as follows. 
Since we explore a fitness landscape,
some remarks on the concept of fitness landscape is briefly given in Section 2.
Section 3 gives some descriptions about the Hopfield model and how the fitness is evaluated there.
Some methods employed to obtain the information as to peak shape is described in detail in Section 4. 
After experimental results and discussion are given also in Section 4, we present concluding remarks.

\section{Fitness Landscape}
\noindent
The concept of the fitness landscape was first introduced by Wright \cite{wrig} in 1932
to study biological evolutionary processes. 
Since then, this concept has been used not only in evolutionary biology 
but also in chemistry, physics, computer science and so on.

In chemistry, for example, a molecule can be represented as a string 
of $N$ letters with each letter being chosen from an alphabet of size $k$ \cite{mack}.
Twenty amino acids ($k=20$) for proteins or four nucleotides ($k=4$) 
for nucleic acids can be considered as examples of the alphabet.
The $k^N$ possible combinations of the letters construct a configuration space of the string.
Then, for example, the free energy of RNA folding into secondary structures \cite{font},
or the ability of peptides to bind to a particular substrate to catalyze a specific reaction \cite{mayn}
is assigned as a fitness value to each configuration.
In physics, the Hamiltonian energy of Ising spins defines a fitness landscape on the configuration space of $N$ spins.
Each spin takes the value either 1 or $-1$ ($k=2$).
Bray and Moore \cite{bray} argued about the number and distribution of meta-stable states (local optima) 
of the Hamiltonian energies.

To explore these fitness landscapes, we need a rule by which a point in the space moves to one of its neighbors.
Then, consecutive movements of a point to the neighbors form a {\it walk} on the landscape.
Macken et al.\ \cite{mack} used {\it random point mutation} 
that changes a single letter in the string to specify neighbors of the string.
Then, by sampling points along an {\it evolutionary walk} 
in which point moves to the {\it firstly found fitter} neighbor,
they  studied the statistical properties of the landscape of the chemical 
affinity of antibody for  antigen in immune response. 
Weinberger \cite{wein} used two different walks: {\it ``gradient walk''}
in which the walker steps to the {\it best} of its neighbors and {\it ``random adaptive walk''} 
in which the next step is chosen {\it at random} from the set of better neighbors,
to investigate the Kauffman's NK landscape which is a model formulated in more general form \cite{kauf}.
\section{Hopfield Model and Fitness}
\subsection{The Model}
\noindent
The Hopfield model consists of $N$ neurons and $N^2$ synapses.
Each neuron state is either active (+1) or quiescent ($-1$).
When an arbitrary $N$-bit {\it bipolar pattern} is given to the network as an initial state,
the dynamical behavior of neurons' states afterwards are characterized by the strengths of the $N^2$ synapses.
The synaptic strengths are called {\it weights}, and the weight from neuron $j$ to neuron $i$ is denoted 
as $w_{ij}$ in this paper.
Provided the synaptic weights are determined appropriately, network can store some number of patterns as attractors.
Hopfield employed the so-called Hebbian rule \cite{hebb} to prescribe the weights.
That is, to store $p$ bipolar patterns $\xi^{\nu}$:
\begin{displaymath} 
{\xi}^{\nu} = ({\xi}^{\nu}_{1},\cdots,{\xi}^{\nu}_{N}), \hspace{.2in}{\nu} = 1, \cdots, p,
\end{displaymath}
the weight values are determined as:
\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}
An instantaneous state of a neuron is updated asynchronously (one neuron at a time) as:
\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 the $i$-th neuron at time $t$.
If an initial state converges to one of the stored patterns $\xi^{\nu}$ 
as an equilibrium state, then the pattern is said to be {\it recalled}.
Furthermore, if an initial state chosen from the stored patterns remains unchanged from the beginning,
then the pattern is said to be stored as a {\it fixed point}.

In analyzing the Hopfield model, 
there have been basically two different approaches:
one is to explore {\it pattern space} searching for attractors under a specific weight configuration, and 
the other is to explore {\it weight space} searching for an appropriate weight configuration
that stores a given set of patterns. 
To be more specific, the former is an analysis of the Hamiltonian energy 
as a function of all the possible configurations of bipolar pattern to be given to the network,
where the synaptic weights are pre-specified using a learning algorithm, usually the Hebb's rule, 
so that the network stores a set of $p$ given patterns.
In this context, the model for $p=1$ corresponds to the Mattis model of spin-glass \cite{matt},
in  which the Hamiltonian energy has two minima,
while the model for infinitely large $p$ corresponds to the Sherrington-Kirkpatrick model \cite{SK}, 
in which the synaptic weights become  Gaussian random variables.
Analyses of the former type have been made in between these two extreme cases (see Amit \cite{amit}).
The latter analysis, on the other hand, was addressed by Gardner \cite{gard}.
She discussed the optimal weight configurations for a {\it fixed} number of given patterns
in terms of the volume of the solutions in weight space, 
suggesting that the volume shrinks to vanish when $p$ approaches to $2N$.
In short, the former approach searches 
for the optimal pattern configurations which minimize the Hamiltonian energy 
{\it in pattern space} {\it with the weights being fixed},
while the latter searches for the weight configurations {\it in weight space} 
that optimally store a set of given {\it fixed patterns}.

So far, we have studied the model with the latter approach.
We have explored  fitness landscapes of the model {\it defined on weight space}, and 
have found many solutions that store more patterns 
or store them with larger basin of attractions than, e.g., 
the Hebbian synaptic weights \cite{imad-1,imad-12,imad-11,imad-5}.
Now, our interest is in the number and distribution of these solutions over the whole weight space, 
which is still an open problem.

\subsection{Fitness Evaluation}
\noindent
Assume that $p$ random bipolar patterns,
\begin{displaymath}
{\xi}^{\nu} = ({\xi}^{\nu}_{1},\cdots,{\xi}^{\nu}_{N}), 
               \hspace{.2in}{\nu} = 1, \cdots, p
\end{displaymath}
are stored as an associative memory in the network.
When one of these memorized patterns ${\xi}^{\nu}$ is given to 
the network as an initial state, 
states of neurons vary from time to time afterwards 
(unless ${\xi}^{\nu}$ is stored as a fixed point).
In order for the network to function as an associative memory, 
the instantaneous network state must be similar to the input pattern $\xi^{\nu}$. 
The similarity 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 neuron $i$ at time $t$. 
This $m^{\nu}(t)$ is referred to as {\it overlap}.
The quality of retrieval of memorized patterns are 
represented by $\left \langle m^{\mu} \right \rangle$, 
a temporal average of $m^{\nu}(t)$ over certain time interval $t_0$.
We evaluate the fitness value of each network by further averaging 
these $\left \langle m^{\mu} \right \rangle$'s over all $p$ memorized patterns. 
Namely, the fitness $f$ is
\begin{displaymath}
f = \frac {1}{p \cdot t_{0}}
{\sum _{\nu=1}^{p}\sum_{t=1}^{t_{0}}{m^{\nu}(t)} }.
\end{displaymath}
Then the fitness 1 implies all the $p$ patterns are stored as fixed points, 
while all other cases have a fitness less than 1.
In this paper, $t_{0}$ is set to $2N$, twice the number of neurons.

\section{Experimental Results and Discussion}
\subsection{Two Peaks Studied}
\noindent
Simulations were carried out on a network with 49 neurons.
A fixed set of 6 random bipolar patterns is given to the network to be stored as associative memory.
The configurations of $49^2$ weights that allow the network to store these 6 patterns as associative memory
correspond to the peaks on the landscape.
As test samples, we picked up two peaks found by Evolutionary Programming (EP) \cite{foge,foge-0}.

The EP proceeds as follows.
A population is constructed by $\mu$ points each of which has $49^2$ coordinates $x_i$ $(i = 1, 2, \cdots, 49^2)$
representing weight values of a network.
Each point has additional $49^2$ variables $\sigma_i$ $(i = 1, 2, \cdots, 49^2)$
which are used for mutating the point itself.
In this paper, all the $x_i$ are initialized to zero 
and all the $\sigma_{i}$ are initialized to 0.002.
Each of these $\mu$ points is mutated by adding a Gaussian random variable of
a standard deviation $\sigma_i$ to each $x_i$. That is,
\begin{displaymath}
x_i^{\mbox {\scriptsize {new}}} = x_i^{\mbox {\scriptsize {old}}} + {\sigma}_{i} \cdot N_{i} (0, 1).
\end{displaymath}
This mutation produces $\mu$ mutants.
After the mutation, these $\sigma_i$ are also modified as:
\begin{displaymath}
\sigma_i^{\mbox {\scriptsize {new}}} = \sigma_i^{\mbox {\scriptsize {old}}} 
                     + 0.01 \cdot {\sigma}_{i}^{\mbox {\scriptsize {old}}} \cdot N_{i} (0, 1).
\end{displaymath}
We now have the original $\mu$ points and their $\mu$  mutants.
The fitness value of each of the $2 \mu$ points are compared to those of $q$ points which are chosen randomly 
at every time of the comparison from the whole $2\mu$ points.
Then the $2\mu$ points are ranked according to the number of wins, 
and the best $\mu$ points survive ($q$-tournament selection).
The cycle of reconstructing the new population with better fitness points and restarting the search are repeated until 
one of the global optima is found or a set maximum number of generation has been reached.
In this paper, both $\lambda$ and $\mu$ are set to 200 and $q$ is chosen to be 10.

Thus, we picked up two different global peaks to analyze their shape here:
one that was found at a comparatively early (9,199-th generation)
and one that required very long time to be found (53,735-th generation).
In Fig. \ref{ep-fitness}, we show the best fitness versus generation of these two evolutions. 

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=ep.eps,width=8.0cm,height=6.0cm}
   \caption{Two peaks found by EP.}
   \label{ep-fitness}
 \end{center}
\end{figure}


%% \subsection{Methods to Learn the Shape of a Peak}
\subsection{Downhill Walk.} \label{hill-climb-walk} 
\noindent
In his Ph.D dissertation, Jones \cite{jone} argued that 
{\it ``a reverse hill-climbing algorithm allows the determination of details of 
the basin of attraction of points on a landscape.''}
Jones also wrote that {\it ``the method makes it possible to compute statistics 
regarding basins of attraction in a landscape graph.''}
The landscapes that Jones explored were defined on discrete domain, i.e., on vertices of a hyper cube.
Here, we extended the idea to a landscape that is defined on continuous domain. 

Since our landscape is defined on real-valued variables, 
the Gaussian mutation is employed in the same way as in EP described above.
That is, in order for a point to move to one of its neighboring points at random,
we give a small perturbation on each coordinate of the current  point, $x_i$  $(i = 1, 2, \cdots, 49^2)$,
using the Gaussian random variables with mean 0 and standard deviation $\sigma_0$, i.e.,
\begin{displaymath}
x_i^{\mbox {\scriptsize {new}}} = x_i^{\mbox {\scriptsize {old}}} + {\sigma}_{0} \cdot N_{i} (0, 1),
\end{displaymath}
where  $\sigma_{0}\cdot N_{i}(0, 1)$ implies a {\it step length}.
The walker walks down a hill as follows.
Starting at the top of a peak, the Gaussian mutation is given $\lambda$  times to the current point.
Then, the point which obtains the lowest fitness value among $\lambda$ mutants is selected as the next point.
This enables us to expect the path to be almost the steepest one.
Thus, the plot of fitness values along the walk reflects the gradient of the slope of the hill.

The results are shown in Fig. \ref{down-hill-walk}.
We can see that the global peak found at generation 9,199 is steeper than the one found at generation 53,735.
We also show in the figure the down-hill walk from a Hebbian peak, and we observed that
the both peaks found by EP are much steeper than the Hebbian peak.
\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=fitness.eps,width=8.0cm,height=6.0cm}
   \caption{Fitness along a Down-hill Walk.}
   \label{down-hill-walk}
 \end{center}
\end{figure}

\subsection{Statistical Analyses}
\noindent
Our studies of finding appropriate configurations of synaptic weights for associative memory 
using evolutionary algorithms have revealed that the more the number of patterns to be stored, 
the more difficult the search becomes.
This is probably because of increasing number of local optima as well as decreasing number of global optima.

The questions now are how many local/global optima are, how they are distributed, 
how large their basins of attraction are, and so on.
In order to obtain the information to answer these questions, 
measuring the ruggedness of the fitness landscape will be helpful.

The simplest way to learn the ruggedness would be by enumerating the fitness value of each point of weight space.
This, however, is not realistic due to infinite number of points in our weight space. 
So, statistical properties of a collection of sampled points picked up randomly from the whole landscape, 
or along an evolutionary path are employed.

\subsubsection*{Correlation Coefficient of an Evolutionary Operator.}
Manderick et al.\ \cite{mand} and Lipsitch \cite{lips} proposed a method to measure
how a pair of points on a fitness landscape is correlated with each other.
The method proceeds as follows.
A parent point is sampled at random from the fitness surface; 
a single evolutionary operation is applied to the parent point yielding an offspring; and
the correlation coefficient between the fitness values of parent-offspring pair is calculated.
This procedure is repeated, 
and the correlation coefficients are plotted against the distance between the parent and offspring.

As Lipsitch wrote, the correlation coefficient plot as a function of parent-offspring distance
provides a measure of how rugged a given landscape is.
Highly correlated landscapes are smooth because nearby points have similar fitness values,
while less correlated landscapes are more rugged having larger fluctuations in fitness over short distance.

Previously we applied this method to our fitness landscape of the Hopfield model of associative memory \cite{imad-19}.
However, we were not able to obtain satisfactory results, probably because our landscape is not isotropic.

\subsubsection*{Autocorrelation Function along a Down-hill Walk.}
Manderick et al.\ \cite{mand} proposed another statistical method called an autocorrelation function
in which pairs of points are sampled along an evolutionary walk rather than from the whole space.
We extend the method to our continuous landscape as follows.
First, we produce a down-hill walk described in Section \ref{hill-climb-walk} from the top of a peak in the landscape. 
The walk lasts $q$ steps. At each point, fitness value is calculated.
Thus, we obtain a sequence of fitness values:
\begin{displaymath}
f_0, f_1, f_2, \cdots, f_q
\end{displaymath}
where $f_0$ is a fitness value of the starting point.
The autocorrelation function $\rho (h)$ of the fitness sequence represents 
the correlation coefficient between a pair of fitness values of two points separated by $h$ steps of the walk,
and is calculated as follows:
\begin{displaymath}
\rho(h) = \frac {R(h)}{R(0)}
\end{displaymath}
where
\begin{displaymath}
R(h) = \frac {1}{M} \sum _{i=0}^{q-h} (f_i - \overline{f})(f_{i+h}- \overline{f})
       \hspace{.1in}{\mbox {\small and}}\hspace{.1in} \overline{f} = \frac{1}{q+1} \sum_{i=0}^q {f_i}.
\end{displaymath}
This roughly corresponds to the distance one can jump maintaining some information about the fitness.

The results for $p=$ 6 are shown in Fig.~\ref{autocorrelation}.
We can see the peak found at generation 9,199 is less rugged than the one found at generation 53,735.
We surmise that the more rugged the peak is, 
the more difficult it becomes for an evolutionary algorithm to reach the peak.

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=correlation.eps,width=8.0cm,height=6.0cm}
   \caption{Autocorrelation function along a down-hill walk.}
   \label{autocorrelation}
 \end{center}
\end{figure}


\section{Conclusion}
\noindent
We have described some methods using a down-hill walk from the top of a hill
to learn the shape of peaks on the fitness landscape defined by the Hopfield model of associative memory.
Here we have studied the two global peaks found by EP.
One is a peak found at a comparatively early, and the other is a peak found after a long time of wandering.
We observed that the peak found earlier is steeper and less rugged than the peak found by taking more generations.
This reasonable result verifies the methods more or less.

Although these methods require prior knowledge of the locations of the optima that is unlikely in real-world problems,
the methods are useful to evaluate an evolutionary algorithm and predict its performance.
At the same time, this study shed new light on analysis of the Hopfield model of associative memory
in which many issues are still open.

\section*{Acknowledgment}
\noindent
We thank Peter Davis at Advanced Telecommunication Research Institute (ATR)
for providing us great insights into the dynamics of the Hopfield neural networks.

\begin{thebibliography}{00} %{00} for numbered bibliography

\bibitem{koml}J.~Koml\'{o}s, and R. Paturi (1988)
{\em Convergence Results in an Associative Memory Model.}
Neural Networks, 1, pp.239--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,  pp.2554-2558.

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

\bibitem{wrig}S. Wright (1932)
{\em The Roles of Mutation, Inbreeding, Crossbreeding and Selection in Evolution.}
Proceedings of the 6th International Congress of Genetics, pp.356--366.

\bibitem{mack}C. Macken,  P. Hagan, and A. Perelson (1991)
{\em Evolutionary Walks on Rugged Landscapes.}
SIAM Journal of Applied Mathematics, 51, pp.799--827.

\bibitem{font}W. Fontana, and P. Schuster (1987)
{\em A Computer Model of Evolutionary Optimization.}
Biophysical Chemistry, 26, pp.123--147.

\bibitem{mayn}J. Maynard Smith (1970)
{\em Natural Selection and the Concept of a Protein Space.}
Nature, 225, pp.563--564.

\bibitem{bray}A. Bray, and M. Moore (1980)
{\em Metastable States in Spin Glasses.}
Journal of Physics C: Solid State Physics 13, pp.L469--L476.

\bibitem{wein}E. D. Weinberger (1990)
{\em Correlated and Uncorrelated Fitness Landscapes and How to Tell the Difference.}
Biological Cybernetics, 63, pp.325--336.

\bibitem{kauf} S. A. Kauffman, and S. Levin (1987)
{\em Towards a General Theory of Adaptive Walks on Rugged Landscapes.}
Journal of Theoretical Biology, 128, pp.11--45.

\bibitem{matt}D. C. Mattis (1976)
{\em Solvable Spin Systems with Random Interactions.}
Physics Letters, 56A, pp.421--422.

\bibitem{SK}D. Sherrington,  and S.Kirkpatrick (1975) 
{\em Solvable Model of a Spin Glass.}
Physical Review Letters, 35, pp.1792--1796.

\bibitem{amit}D. J. Amit (1989)
{\em Modeling Brain Function: The World of Attractor Neural Networks.}
Cambridge University Press.

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

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

\bibitem{imad-12}A. Imada, and K. Araki (1997)
{\em Evolution of Hopfield Model of Associative Memory by the Breeder Genetic Algorithm.}
Proceedings of the 7th International Conference on Genetic Algorithms, pp.784--791.

\bibitem{imad-11}A. Imada, and K. Araki (1997),
{\em Random Perturbations to Hebbian Synapses of Associative Memory using a Genetic Algorithm.}
Proceedings of International Work-Conference on Artificial and Natural Neural Networks,
Springer-Verlag, Lecture Notes in Computer Science, No.1240, pp.398--407.

\bibitem{imad-5}A. Imada, and K. Araki (1996)
{\em Basin of Attraction of Associative Memory as it Evolves from Random Weights.}
Proceedings of the 1st Asia-Pacific Conference on Simulated Evolution and Learning,
pp.271-278.

\bibitem{foge}D. B. Fogel (1995)
{\em Evolutionary Computation: Toward a New Philosophy of Machine Intelligence.} IEEE Press.

\bibitem{foge-0}L. J. Fogel, A. J. Owens, and M. J. Walsh (1966)
{\em Artificial Intelligence through Simulated Evolution.} Wiley.

\bibitem{jone}T. Jones (1995)
{\em Landscapes and Search.} 
Ph.D dissertation, The University of New Mexico.

\bibitem{mand} B. Manderick, M. de Weger, and P. Spiessens (1993)
{\em The GA and the Structure of the Fitness Landscape.}
Proceedings of the 4th International Conference on Genetic Algorithm, pp128--135.

\bibitem{lips}M. Lipsitch (1993)
{\em Adaptation on Rugged Landscapes Generated of Neighboring Genes.}
Proceedings of the 4th International Conference on Genetic Algorithm, pp143--150.

\bibitem{imad-19} A. Imada, and K. Araki (1998)
{\em Some Statistical Analyses of Fitness Landscape Created by the Hopfield Model of Associative Memory.}
Proceedings of the International Technical Conference on Circuits/Systems, Computer and Communication,
Vol.2, pp1031--1034.

\end{thebibliography}

\end{document}











