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

\setlength{\topmargin}{0.6cm}
\setlength{\oddsidemargin}{-0.8cm}
\setlength{\textheight}{23.6cm}
\setlength{\textwidth}{17.8cm}

\begin{document}
%\small
\def\bs{-0.5ex}
\newtheorem{theorem}{Theorem}

\title{Some Statistical Analyses of \\ 
       Fitness Landscape Created by \\
       the Hopfield Model of 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\\
        1-11-13-604 Abeno, Hannan, Osaka, 545-0021 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{}
\thispagestyle{empty}
\pagestyle{empty}
\maketitle

\begin{abstract}
\noindent
We apply evolutionary computations to Hopfield's neural network model of 
associative memory.
In the model, some of the appropriate configurations of the synaptic weights 
give a network a function of associative memory.
One of our goals is to obtain the distribution of these configurations 
in the synaptic weight space.
For the purpose, we explore a fitness landscape defined on the weight space.
Although there have been a fair amount of studies regarding the ruggedness 
of the fitness landscape,
all of them are for discrete genes.
In this paper, we apply these methods to our continuous genes which represent 
the synaptic weights of the Hopfield network.
\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.
In 1982, Hopfield~\cite{hopf} proposed a fully connected neural network model 
of associative memory
in which information is stored by being distributed among neurons and retrieved 
by being relaxed dynamically.

The dynamical behavior of its neuron states strongly depends on 
synaptic strength between neurons.
The synaptic strength from neuron $j$ to neuron $i$ is called a {\it weight} 
and denoted as $w_{ij}$ in this paper.
For the fully connected neural networks with $N$ neurons, all the possible 
configurations of $w_{ij}$ construct $N^2$-dimensional Euclidean space.
Hereafter, we will call this a {\it weight space}.
Every configuration of $w_{ij}$ is represented as a point in weight space.
Fitness values of a point in the space is estimated according 
to the capability of the network that is determined by the configuration.
The process of finding a higher fitness configuration is called a {\it learning},
which is, as Kauffman wrote, a walk seeking one of the global peaks
on the fitness landscape. 
Our previous experiments show that the task to locate one of 
the optimum weight configurations of the Hopfield network by a GA 
becomes difficult as the number of patterns to be stored increases
(see, e.g.,~\cite{imad-1,imad-13,imad-5,imad-11}).
We conjecture that this phenomenon is due to the increased ruggedness 
of the fitness landscape.

The concept of the fitness landscape was first introduced 
by Wright \cite{wrig} to study biological evolutionary process.
Since then, this concept has been used not only in biology but also 
in many fields like physics and computer science.
For example: 
the free energies of RNA folding into secondary structures \cite{font};
the chemical affinity of the antibody for the antigen 
in immune response \cite{macke};
the Hamiltonian energy of disordered system \cite{derr-6};
traveling salesman problem \cite{mand};
elementary cellular automata \cite{lips};
and of Kauffman's M-K model \cite{kauf-1,kauf-2,kauf-3,kauf-4} 
which is formulated as the more general form  
of fitness landscape \cite{hord,wein-1,wein-2,bak,flyv,vass}.

Some authors provided a way to study fitness landscapes in terms of
statistical measures such as
autocorrelation function of a landscape \cite{mand,lips};
correlation coefficient of a genetic operator 
%(as a function of distance between parent and child)
\cite{mand,lips}; 
correlation length \cite{mand,lips};
mean walk length to a peak \cite{wein-1,flyv,macke,lips};
the Fox-Jenkins approach to statistical time series of fitness \cite{hord};
the information content and stability \cite{vass} and so on.

The Hopfield model described in this paper,
when synaptic weights are selected randomly, 
can be considered as the Sherrington-Kirkpatrick model of 
Ising spin-glasses (SK-model) \cite{kirk}.
%Bray et al. \cite{bray-1,bray-2} 
Bray et al. \cite{bray-1} 
studied the number of meta-stable states 
of the SK-model, using correlations between the Hamiltonian energies of 
the meta-stable states.
Derrida et al. \cite{derr-5} solved exactly the number of meta-stable states 
in one dimensional spin-glass chain,
answering the question of what stable state will it fall into
if a spin configuration is evolve in time.
Amitrano et al. \cite{amitr} analyzed the Hamiltonian energy landscape 
in the study of chemical evolution of {\it information-carrying macromolecules}
represented by a set of Ising-spin.

Thus, fitness landscapes of the spin-glass model, or equivalently, 
the Hopfield model of associative memory have been fairly well studied. 
However, it was {\it discrete} fitness landscapes that were explored in these studies.
Namely, the landscapes were defined on binary string space.
On the other hand, Gardner \cite{gard} discussed weight configurations of the Hopfield
associative memory in terms of the volume of solutions in synaptic weight space,
where the number and distribution of solutions in weight space 
is unfortunately still an open issue.
This is one of the reasons of our interest in the fitness landscape 
defined on weight space rather than defined on pattern space.

To construct a fitness landscape and explore it, 
we need two rules, as Macken wrote \cite{macke}.
One is to determine the fitness value of each point in the space, 
and the other is to specify evolutionary paths on the landscape.
In the following two subsections, we describe these two rules.
\subsection{Random Gaussian Mutation}
\noindent
Usually, to make a point explore the landscape defined on
{\it binary} string space, a bit-flip-mutation is employed. 
However, this mutation does not make sense on our {\it continuous} space.
In this paper, a point moves by Gaussian Mutation.
That is, a point
\begin{displaymath}
(x_1, x_2, \cdots, x_N)
\end{displaymath}
is mutated by adding a random Gaussian variable to each coordinate $x_i$, i.e., 
\begin{displaymath}
x_i^\prime = x_i + \sigma \cdot N_{i}(0, 1),
\end{displaymath}
where $N_{i}(0, 1)$ is normally distributed random variable of mean 0 
and standard deviation 1 sampled for each individual $i$.
Note that  the step length in Euclidean distance between parent and child is 
\begin{displaymath}
\left(  \sum_{i=1}^{N} { \left(  \sigma \cdot N_{i}(1, 0)  \right) ^2} \right) ^{1/2}.
\end{displaymath}

\subsection{Fitness Evaluation}
\noindent
Assume that $p$ random bipolar patterns, sequences of 1 and $-1$,
\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{Statistical Analyses}
\noindent
Our previous studies of finding an appropriate configuration
of synaptic weights using GAs
show that the more the number of patterns to be stored, 
the more difficult the task.
This is probably due to both of the increasing local optima 
and the decreasing 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.
To obtain the information to answer these questions,
the ruggedness of the fitness landscape is investigated statistically here.
The ultimate goal is to learn the whole geometry of the fitness landscape.

The simplest way to learn the distribution of fitness values would be 
by enumerating the fitness value of each point of weight space.
This, however, is not realistic due to the huge number of points in our weight space. 
In the current problem, even if we restricted each weight value 
to the floating-point number from $\{-1.00, -0.99, -0.98, \cdots, 1.00\}$, 
the weight space is constructed with $201^N$ points.
%In addition, peaks in our landscapes are extremely narrow
%in contrast to the rugged low fitness flat region extended all over 
%the whole landscape (see e.g., \cite{imad-17}).
As such, statistic properties of a collection of randomly sampled points 
picked up either from the whole landscape, 
or along an evolutionary path are employed.

In the following subsections, 
two methods which were originally devised for discrete landscapes
are applied to our continuous landscape of the Hopfield network,
with the aim being similar.
%The measurements were made on two fitness landscapes constructed 
%by $p=6$ and $p=49$.

\subsection{Correlation Coefficient}
\noindent
Both Manderick et al. \cite{mand} and Lipsitch \cite{lips} proposed a method 
to calculate the correlation coefficient of a single evolutionary operator
such as a mutation or a crossover.
To be more specific, the correlation coefficient of a set of fitness pairs of 
two points generated by the operator. 
We use this method to calculate the correlation coefficient 
$\rho$ of random Gaussian mutation.
From weight space, $q$ points are randomly chosen as parents.
Then, by applying a random Gaussian mutation of mean zero 
and standard deviation $\sigma$ to each point, 
another $q$ points, mutants of the original $q$ points, 
are obtained as children.
Fitness values of both parents and children are denoted as 
$f^{i}_{p} (\sigma)$ and $f^{i}_{c}(\sigma) \hspace{.05in} 
(i = 1, 2, \cdots, q)$, respectively.
These are repeatedly evaluated  for the value of $\sigma$ from 0.001 to 0.5.
And the correlation coefficient as a function of $\sigma$ is obtained as follows:
\begin{displaymath}
\rho(\sigma) = \frac {
\displaystyle{
\sum_{i=1}^{q} { 
(f^{i}_{p} (\sigma) - \overline{f_{p}})(f^{i}_{c} (\sigma) - \overline{f_{c}})
}}}
{\displaystyle{
\left( \sum_{i=1}^{q} { (f^{i}_{p} (\sigma) - \overline{f_{p}})^2} \right)^{1/2}
\left( \sum_{i=1}^{q} { (f^{i}_{c} (\sigma) - \overline{f_{c}})^2} \right)^{1/2}}
}
\end{displaymath}
where $\overline{f_{p}}, \overline{f_{c}} $ denotes average 
over $q$ samples of parents and children, respectively.

In Fig. \ref{correlation}, we show four examples of 
correlation coefficient of the landscapes
for $p=1, 6, 49$ and $98$, 
as a function of step length by a Gaussian mutation.
The number of sampled points, $q$, was 600.
As Lipsitch wrote:
correlation 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.\\
\indent
The results, as shown in Fig.~\ref{correlation}, suggest that 
fitness values between two separate points are more correlated when $p$, 
the number of patterns to be stored, is larger.
This is against our intuition that the landscape 
becomes more rugged as $p$ increases.
Though we suspect the results are probably because of 
increasing area of flat region where the fitness is relatively low,
we have not known the reason of this phenomenon.

Lipsitch defined the {\it correlation length} of a landscape 
as the value of $\sigma$ 
at which $\rho(\sigma)$ first becomes non-positive \cite{lips}.
The figure suggests that the correlation length is longer for larger $p$. 
This is also against our intuition.

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=correlation-of-random-samples.eps,width=5.5cm,height=5.5cm}
   \caption{Fitness correlation coefficient between two samples.}
   \label{correlation}
 \end{center}
\end{figure}

\subsection{Autocorrelation Function}
\noindent
In this subsection, we apply the autocorrelation function  
proposed by Manderick et al. \cite{mand} 
to continuous landscapes given by the Hopfield model.

First, we produce a random walk on the search space. 
It starts with a point chosen at random and the next point 
in the walk is determined repeatedly by adding 
a Gaussian random variable of mean zero and 
standard deviation $\sigma$ to each coordinate of current point.
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 random 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}
%\end{displaymath}
%\begin{displaymath}
\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=$ 1, 6 and 49 are shown in Fig.~\ref{autocorrelation}.
For each value of $p$, we observed ten walks with different random number seed.
Following Lipsitch (1993), we defined {\it correlation length} 
of a landscape as the step length at which $\rho (h)$ first becomes non-positive,
and two representative results each of which has the shortest and 
the longest correlation length (out of ten runs) were shown.
We can see the results vary from one run to another.
Moreover, we cannot find any dependence of the results on $p$.
These observations indicate that the fitness landscape is not isotropic.

Manderick et al.\cite{mand} also defined the correlation length $\tau$ 
as the distance where the autocorrelation function is
\begin{displaymath}
\rho(\tau) = 1/2.
\end{displaymath}
As Fig.~\ref{autocorrelation} says, the correlation lengths of the 
landscapes seem to be too long as a number of 
steps keeping the information of the initial points.

\begin{figure}[hbtp]
 \begin{center}
   \epsfile{file=correlation-along-a-walk-01.eps,width=5.5cm,height=5.5cm}
   \epsfile{file=correlation-along-a-walk-06.eps,width=5.5cm,height=5.5cm}
   \epsfile{file=correlation-along-a-walk-49.eps,width=5.5cm,height=5.5cm}
   \caption{Fitness correlation coefficient along a random walk.}
   \label{autocorrelation}
 \end{center}
\end{figure}

\section{Conclusion}
\noindent
We have described,
in the context of our {\it continuous} fitness landscape of the Hopfield model,
two statistical methods that were successfully employed to measure 
the ruggedness of {\it discrete} fitness landscapes.

One method showed the opposite result to our conjecture,
and the other was found not to work in our problem.
Our conjecture is that the fitness landscape becomes more rugged 
as the number of patterns to be stored increases.
Namely, the number and the diversity of local optima increases and 
their basin of attraction becomes smaller.

One of the possible reasons of these unsuccessful results is that
the sampled points are not representatives of the whole fitness landscape.
This holds true whichever these samples may be taken
uniformly at random from the space, or along a random walk.
For example, it is highly unlikely that sampled points include
the global optimum, or even a local optima.
Therefore, we started to study the fitness landscapes 
by directly observing the traces of down-hill-walks from a peak
\cite{imad-17} which gives us a little bit more precise image 
of the shape of peaks.
However, the information in this case is quite a local one.
Hence the statistical analysis will still be needed.
Now, we study other statistical methods like {\it information measure} 
proposed by Vassilev \cite{vass}.


\begin{thebibliography}{99}
\small
\setlength{\itemsep}{0pt}

\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{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, pp413--420.

\bibitem{imad-13}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, pp784--791.

\bibitem{imad-5}A. Imada, and K. Araki (1996)
{\em ``Lamarckian Evolution of Associative Memory.''}
Proceedings of IEEE International Conference on Evolutionary Computation, pp676--680.

\bibitem{imad-11}A. Imada, and K. Araki (1997)
{\em ``Application of an Evolution Strategy to
       the Hopfield Model of Associative Memory.''}
Proceedings of IEEE International Conference on Evolutionary Computation, pp679--683.

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

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

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

\bibitem{derr-6}B. Derrida (1981)
{\em ``Random-energy model: An Exactly Solvable Model of Disorders Systems.''}
Physical Review, B.24(5),  pp2613--2626.

\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{kauf-1} S. A. Kauffman, and S. Levin (1987)
{\em ``Towards a General Theory of Adaptive Walks on Rugged Landscapes.''}
Journal of Theoretical Biology, 128, pp11--45.

\bibitem{kauf-2} S. A. Kauffman, (1989)
{\em ``Adaptation on Rugged Fitness Landscapes.''}
Lectures in the Sciences of Complexity (Santa Fe Institute), Addison-Wesley, pp327--618.

\bibitem{kauf-3} S. A. Kauffman (1993)
{\it The Origins of Order.}
Oxford University Press.

\bibitem{kauf-4} S. A. Kauffman (1995)
{\it At Home in the Universe.}
Oxford University Press.

\bibitem{hord}W. Hordijk (1995)
{\em ``A Measure of Landscape.''}
Santa Fe Institute Report, No.95-05-049.

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

\bibitem{wein-2}E. Weinberger, and P. Stadler (1933)
{\em ``Why Some Fitness Landscapes are Fractal.''}
Journal of Theoretical Biology, 163,  pp 255--275.

\bibitem{bak}P. Bak, M. Flyvbjerg, and B. Lautrup (1992)
{\em ``Co-evolution in a Rugged Fitness Landscape.''}
Physical Review, A46, pp6724--6730.

\bibitem{flyv}M. Flyvbjerg, and B. Lautrup (1992)
{\em ``Evolution in a Rugged Fitness Landscape.''}
Physical Review, A46, pp6714--6723.

\bibitem{vass}V. K. Vassilev (1997)
{\em ``An Information Measure of Landscapes.''}
Proceedings of 7th International Conference on Genetic Algorithms, pp49--56.

\bibitem{kirk} S. Kirkpatrick, and D. Sherrington (1978)
{\em ``Infinite-ranged Models of Spin-glasses.''} 
Physical Review, B17, pp4384-4403.

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

%\bibitem{bray-2}A. Bray, and M. Moor (1981)
%{\em ``Metastable States in Spin Glasses with Short-ranged Interactions.''}
%Journal of Physics, C: Solid State Physics, 14, pp1313--1327.

\bibitem{derr-5}B. Derrida, and E. Gardner (1986)
{\em ``Metastable states of a Spin Glass Chain at 0 Temperature.''}
Journal of Physique, 47, pp959--965.

\bibitem{amitr}C. Amitrano, L. Peliti, and M. Saber (1987)
{\em ``Population Dynamics in a Spin-glass Model of Chemical Evolution.''}
Journal of  Molecular Evolution, 29, pp 513--525.

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

\bibitem{imad-17}A. Imada, and K. Araki (1997)
{\em ``What does the Landscape of a Hopfield Associative Memory Look Like?''}
Proceedings of the 7th Annual Conference on Evolutionary Programming,
Springer Verlag, Lecture Notes in Computer Science (in press).

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

\end{thebibliography}
\end{document}
