\documentstyle[12pt,eclepsf]{article}
\textheight 238mm
\textwidth 165mm
\topmargin -10mm
\oddsidemargin -3mm

\title{\bf CAN DOWNHILL WALKERS FROM\\ THE TOP OF A HILL CRIMB IT AGAIN?}

\author{Akira Imada\\
        \hspace*{1in}\\
        Dokuz Eyl\"{u}l University\\
        Computer Engineering Department\\
        Bornova, Izmir, 35100 Turkey\\
        akira@cs.deu.edu.tr}
\date{}

\begin{document}
\maketitle
\pagestyle{empty}
\thispagestyle{empty}

\begin{abstract}
\noindent
Thus far, using evolutionary computations,
we have found many different solutions of the fully connected 
neural network model of associative memory. We now compare
them in shape by regarding them as peaks in fitness landscape 
defined on synaptic weight space.
We found that the peak located by an EP search are very different
than the Hebbian peak. In this paper, we study this issue
by using hill-climbers.
\end{abstract}

\section{Introduction}
Although the fully connected neural network model 
of associative memory, such as the Hopfield's model, 
is somehow an old topics,
many interesting issues from physics point of view are still 
unknown. The number and distribution of attractors in 
synaptic weight space, or the fate of specific 
trajectories when some of the weight values are slightly 
modified are these examples. To attack these issues, 
we use evolutionary computations that explore the fitness 
landscape defined on weight space of a fully connected 
neural network model of associative memory (Imada et al., 1998).

Techniques to learn statistically a geometry of fitness 
landscapes have been fairy well studied (e.g., (Manderick et al., 1976)). 
However, It was discrete spaces that were analyzed by 
those techniques, and analyses of those defined on 
a continuous domain remain few.
We have not succeeded in applying these techniques 
to our problem, probably due to our real-valued weights
and the lack of isotropic nature of the landscape. 

We have also employed reverse hill-climbing to learn 
shape of peaks in our fitness landscape (Imada, 1999). 
By walking down a peak from the top, 
we can obtain information of its shape of the peak.
However, because of a plasticity of synaptic weight of 
neural networks, peaks are made up of many flat regions of small area,
and downhill walkers are trapped by or skip some of the small flat regions 
when walking down a side wall, and hence it was not possible to obtain
a precise shape of a peak.
So, we proposed somewhat of a new method of 
learning more precise profile of peaks utilizing the 
evolutionary programming (EP) capability of escaping 
the domain of attraction.
%% add reference of 2001
%% In this paper ...
These studies are steps to learn a whole geometry of the fitness landscape.

\subsection{Associative Memory}
Associative memory is {\it a dynamical system 
which has a number of stable states with a domain of 
attraction around them} (Koml\'{o}s and Paturi 1988).
If the system starts at any state in the domain, 
it will converge to the stable state.
Hopfield~(1982) proposed a fully connected 
neural network model of associative memory
in which information is stored by being distributed 
among neurons, and is retrieved from dynamically 
relaxed neurons' states.
In the model, some of the appropriate configurations 
of synaptic weights give the network a function of 
associative memory.

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}, 
a sequence of $+1$ and $-1$,
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 (Hebb, 1949) 
to prescribe the weights.
That is, to store $p$ bipolar patterns $\xi^{\nu}$:
\begin{equation} \label{eq:one}
{\xi}^{\nu} = ({\xi}^{\nu}_{1},\cdots,{\xi}^{\nu}_{N}), 
\hspace{.2in}{\nu} = 1, \cdots, p,
\end{equation}
the weight values are determined as:
\begin{equation} \label{eq:two}
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{equation}
An instantaneous state of a neuron is updated 
asynchronously (one neuron at a time) as:
\begin{equation} 
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{equation}
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 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 (Mattis, 1976),
in  which the Hamiltonian energy has two minima,
while the model for infinitely large $p$ corresponds 
to the Sherrington-Kirkpatrick model
(Serrington and Kirkpatrick, 1975), 
in which the synaptic weights become  
Gaussian random variables.
Analyses of the former type have been made in between 
these two extreme cases (Amit, 1989).
The latter analysis, on the other hand, was addressed by Gardner (1988).
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} with 
the weights being fixed, while the latter searches for 
the weight configurations {\it in weight space} 
that optimally store a set of given fixed patterns.

In this paper, our concern is on weight space where some 
points give a network a capability to store 
a pre-specified one pattern ($p=1$), 
and we call these points solutions.


%% modified hearafter at Eskisehir



\section{Conclusions}
We have described comparisons of two peaks in the fitness 
landscape defined on weight space of the fully connected 
neural network model of associative memory.
And we have guessed why the Hebbian peak has not been so 
far located by our evolutionary searches.
Of course, the peak is just a needle among vast amount of 
other needles, and this is one of the main reason, but
we guessed the other two important reasons.
One is the shape of the Hebbian peak. 
The slope gradually becomes less steep as walkers 
approached the top area, while a peak which was easily 
found by EP has a slope the other way around.
The other reason is existence of other more reachable peaks 
in the vicinity of the Hebbian peak. We found that when 
walkers try to climb again the hill from a point on the slope, 
they rather select other easier-to-climb-peak.

Many other issues await our explorations.
It is possible that more tolerant unknown solutions 
exist in weight space. 
Will a run with specific $\sigma_{0}$ be able to
locate such a peak whose top is much wider than the top of 
the already known peaks?
Or, what is the distribution of these solutions?
We think we will be able to shed new light on these issues 
using evolutionary computations.

\subsubsection*{Reference}
\begin{description}

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

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

\item[]Fogel, L. J., A. J. Owens, and M. J. Walsh (1966)
{\em Artificial Intelligence through Simulated Evolution.}
Wiley.

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

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

\item[]Hopfield, J. J. (1982) 
{\em Neural Networks and Physical Systems with Emergent 
     Collective Computational Abilities.}
Proceedings of the National Academy of Sciences, USA 79,  
pp.2554-2558.

\item[]Hebb, D. O. (1949)
{\it The Organization of Behavior.} Wiley.

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

\item[]Imada, A (1999).
{\em Downhill Walk from the Top of a Hill by Evolutionary 
 Programming.}
Proceedings of the Congress on Evolutionary Computation,
pp.1414--1418.

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

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

\item{}Kauffman, S. A. (1993)
{\em The Origin of Order: Self-organization and 
     Selection in Evolution.}
Oxford University Press.

\item[]Koml\'{o}s, J., and R. Paturi (1988)
{\em Convergence Results in an Associative Memory Model.} 
Neural Networks 1, pp.239--250.

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

\item[]Manderick, B., 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, pp.128--135.

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

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

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

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

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

\end{description}
\end{document}

\subsection{Fitness Landscape}
\noindent
The concept of the fitness landscape was first introduced 
by Wright (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$ (Macken et al., 1991).
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 (Fontana et al., 1987), 
or the ability of 
peptides to bind to a particular substrate to catalyze 
a specific reaction (Maynard Smith, 1970)
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,
where each spin takes the value either 1 or $-1$ ($k=2$).
Bray and Moore (1980) 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.\ (1991) 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 defined by the chemical affinity of antibody 
for  antigen in immune response. 
Weinberger (1990) 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 (Kauffman et al., 1987).

In the context of the fully connected neural network model of 
associative memory, we have two types of fitness landscape.
The one defined on bipolar pattern space, and the other on
synaptic weight space (see above.) In both cases, top of peaks
constracts flat region, the former of which corresponds to
{basin of attraction of a pattern}, the latter to {plasticity
of synaptic weights.} In this paper, we focuse on the latter type,
and extend the concept of the discrete 
fitness landscape to a continuous one.
Namely, a capability of a fully-connected neural network 
to store a set of bipolar patterns as associative memory
assigns fitness on the configuration space of real-valued 
synaptic weights ($k=\infty$) of a network. 
A walker moves to its neighboring point determined by EP 
which uses Gaussian random mutation.


---
Walking down the hill, walkers seem to spread apart 
from the top where they start.  
In Figure~\ref{last-fig} (left), the Euclidean distances 
%%In Figure~\ref{distance-from-top}, the Euclidean distances 
from the Hebbian top during the downhill walk are shown. 
The data are taken from the downhill walk shown in 
Figure~\ref{two-peaks}.

%\begin{figure}[hbtp]
% \begin{center}
%   \epsfile{file=distance-from-top.eps,width=8.1cm,height=6.1cm}
%   \epsfile{file=again.eps,width=8.1cm,height=6.1cm}
%   \caption{Distance between each of the downhill steps 
%            and the original top (left), and
%            distance between each of the re-hillcliming 
%            steps and the original top (right).}
%   \label{last-fig}
% \end{center}
%\end{figure}
