\documentstyle[twocolumn,eclepsf]{article}

\textheight    247mm
\textwidth     160mm
\topmargin     -20mm
\oddsidemargin 2.5mm

\title{{\bf A-mesa-in-desert vs a-needle-in-haystack --- \\
A fitness landscape on weight space 
of an application using spiking neurons under rate coding.}}

\author{{\bf Akira Imada} \\
\hspace*{0.1in}\\
Brest State Technical University\\
           Moskowskaja 267, 224017 Brest, Republic of Belarus\\
           akira@bsty.by}
\date{}

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

\noindent
{\bf abstract:} {\it Evolutionary comnputaitons sometimes work very efficiently and effectively,
but not always as we all know. During our study of an associative memory model
by neural network with spiking neurons, we came across a very tough problem
to be attacked by evolutionry computations. Given a set of patterns, 
we need to prescribes a configuration of synaptic weights in order to store these 
patterns as an associative memory. Previously, we found a lot of such weight 
solutions in the Hopfield model. However when in a model using spiking neurons
we found it almost impossible to search for such solutions, though we know
at least one solution using Hebb's rule. Here we discribe our geuss of
why it's so difficult and how we could overcome.}

\hspace*{1in}\\
\noindent
{\bf keyword:} {\it associative memory by spiking neurons, 
fitness landscape on synaptic weight space,
evolutionary hill climbing and downhill walk,
Hinton-Nowlan's experiment.}

\section{Introduction}
\noindent
Evolutionary computations search for peaks in a landscape
which is a hyper-surface defined as how good is 
each configuration of parameters.
This surface is called {\it fitness landscape.} That is, in evolutionary
computations, in general, candidate solutions of parameter configuration, 
which are randomly created at the begining,  explore this fitness landscape
searching for the top of the peak, and hopefully locate eventually the optimal 
configulation under which fitness takes a maximam value.
This works very efficiently and effectively sometimes but not always. \\

\noindent
During our study of associative memory model using spiking neurons,
we came accross a very difficult fitness landscape to be explored.
One of the most difficult fitness landscape to explore is,
as Hinton \& Noraln \cite{hint} called it
{\it search-for-a-needle-in-haystack,}
the one in which only one point on configuration space
has the fitness one, the global optimum, and all the other points 
have the fitness zero. See Fig.~1 (a).
The landscape we observed in our problem of finding optimal weights
looked like a little more easier to be explored.
That is, although almost everywhere low-land of fitness zero,
the peak has some top reagion, not a pin point.
And one the other of our observation is the sidewall is extremely steep.
We might say that the shape of the peak is like a mesa rather than a hill.
See Fig.~1 (b).

\begin{figure}[hbtp] \label{fig:1}
 \begin{center}
   \epsfile{file=a-needle.eps,width=8cm,height=3cm}
\caption{Schematic view of (a) a-needle-in-haystack type of landscape and (b)
our fitness landscape of a-mesa-rather-than-a-peak.}
 \end{center}
\end{figure}

\noindent
Associative memory is a memory system in which we can store information
and recall it later from its partial and/or imperfect stimuli. 
An information is stored as a number of stable states with a domain of attraction
around each of the stable states.
If the system starts with any stimulus within the domain 
it will converge to the attractor following a trajectory, hopefully a short one. 
This models human memory in the sense that
we can recognize our friend's face even without meeting for a long time, or
we can recall a song immediately after listening to a very beginning part of the song.
Hopfield~\cite{hopf} proposed a fully connected neural network model of 
associative memory in which a set of patterns is stored distributedly 
among neurons as attractors. Since then the model had been fairly well studied
for more than a decade, and we now know it is not so practical,
partly due to its small storage capacity. 
Though we still have some interesting unknown issues in the model
such as the number and distribution of the weight solutions,
and these issues still attract interests of, say,  some physicists,
we study another model using spiking neurons instead of 
McCulloch-Pitts neurons \cite{mccu}. 
The goal is to overcome problems
like small storage capacity and, more importantly,  
to look for more biologically plausible models of human memory.

\section{Spiking Neuron Model}
\noindent
Some regions in our brain such as {\it neocortex} or {\it hippocampus} are said to be 
made up of two categories of neurons, that is, {\it pyramidal cells} and {\it interneurons}.
Typically, the pyramidal cells communicate with each other via {\it excitatory synapses} 
(positive influences), while interneurons send signals to pyramidal cells via
{\it inhibitory synapses} (negative influences). \\

\noindent
As  Wilson~\cite{wils} wrote in his book, Marr~\cite{marr} was one of the first to propose 
this {\it hippocampal model} involving both recurrent excitation via Hebbian \cite{hebb}
synapses and inhibition.

\subsection{A description of the model by differential equations.}
Probably one of the most fundamental differential equations is 
\begin{equation}\label{eq:1}
\frac{dR}{dt} = -\frac{1}{\tau}R
\end{equation}
where $R$ is assumed to be a function of time and $\tau$ is referred 
to as {\it time constant}. \\

\noindent
In this paper the variable of our interest is 
the number of spikes emitted from one neuron in unit time as a function of time. 
We call it {\it spiking ratio}  and denote it $R(t)$.
In his book, Wilson~\cite{wils} wrote that
a single neuron which emits spike train 
when it receives an external stimulus $P(t)$ could be modeled simply by adding $S(P)$ 
to the right hand side of Eq.~(\ref{eq:1}) without describing shape and timing 
of each individual spike explicitly. That is,
\begin{equation}
\frac{dR(t)}{dt} = \frac{1}{\tau}(-R(t) + S(P))
\end{equation}
As stimulus $S(P)$,  Wilson~\cite{wils} proposed to employ, among many alternatives, 
Naka-Rushton~\cite{naka} function:

\begin{equation}\label{eq:2}
S(P) = \left\{
\begin{array}{ll}
%%\frac{MP^N}{\sigma^N+P^N} & \hspace{.2in}\mbox{if} \hspace{.1in} P \le 0 \\
M \cdot P^n/(\sigma^n+P^n) & \hspace{.2in}\mbox{if} \hspace{.1in} P \ge 0 \\
0 & \hspace{.2in}\mbox{if} \hspace{.1in} P <0 \\
\end{array}
\right.
\end{equation}
where $M$ and $\sigma$ are called {\it saturation} and {\it semi-saturation constant},
respectively, and $n$ is a integer parameter for its graph to fit a phenomena.\\

\noindent
We now assume $N$ pyramidal cells and implicit number of interneurons. 
We simulate these pyramidal cells with spiking neurons which interact with each other
using electric current via plastic synapses.
Pyramidal cells are also interacted by interneurons by global inhibition.
To be more specific, stimuli to one pyramidal cell are given from 
all the other pyramidal cells as well as 
interneuron cells whose number is reduced to only one in this paper,
via synaptic strength. See Fig.~2 bellow.


\begin{figure}[hbtp] \label{fig:2}
 \begin{center}
   \epsfile{file=wilson.eps,width=8cm,height=3cm}
\caption{Schematic diagram with three, instead of $N$, pyramidal cells (P) and one global 
interneuron cell (I). Connections with arrow indicate excitatory synapses and with closed circle
inhibition.}
 \end{center}
\end{figure}

\noindent
The synaptic strength from pyramidal cell $j$ to $i$ is denoted as $w_{ij}$ and 
all the inhibitory synapses from interneuron is assumed to have a value $g$.
Then stimulus to the $i$-th pyramidal cell $P_i$ is described as
\begin{displaymath}
P_i = (\sum_{j=1}^{N} w_{ij} \cdot R_j - g \cdot G)_{+}^2
\end{displaymath}
where $(\cdot)_{+}$ means that we use the value if and only if inside the parentheses is 
positive and zero otherwise.
Following Wilson~\cite{wils}, we experiment with
$\sigma = 10$, $M = 100$, and $n=2$ in Eq.~(\ref{eq:2}).\\

\noindent
Thus, our equation of spiking ratio of the $i$-th pyramidal cell $R_i$ and 
the one of the interneuron $G$ is given as

\begin{displaymath}
\tau_R \frac{dR_i}{dt} = -R_i +
\frac{100 (\sum_{j=1}^{N} w_{ij} R_j - 0.1 G)_{+}^2}
     {100 + (\sum_{j=1}^{N} w_{ij} R_j - 0.1 G)_{+}^2}
\end{displaymath}

\begin{displaymath}\label{eq:3}
\tau_G \frac{dG}{dt} = -G - 0.07 \sum_{j=1}^{N} R_i
\end{displaymath}

\noindent
where, both $\tau_R$ and $\tau_G$ are to be set to 10.
Also note that $w_{ii}$ $(i = 1, \cdots N)$ should be set to all zero.

\subsection{To encode patterns.}
We have a fair amount of ways to encode $N$-bit patterns using $N$ spiking neurons.
(1) {\it Firing-rate} of a neuron within certain time window could express 
a continuous real number, or binary number according to whether the rate exceeds
a threshold or not. (2) {\it Time-to-first-spike} could also express a continuous real number.
In this case, we neglect informations about spike trains after the first spike.
(3) {\it Spike-timing} also could encode real number on the condition that emergence of spike 
of every neuron is periodic and only one spike in one period. 
Or, in this scheme binary bit could also be encoded according to
presence/absence of spike in the period. In this paper, we exploit the first scheme, 
that is, firing-rate. 

\subsection{To store \& recall patterns.}
In what he calls {\it CA3 network} in his book, Wilson~\cite{wils}  employed 256 pyramidal cells 
so that these cells represent a pattern constructed by $16\times16$ array of pixels. 
The network also incorporates one interneuron cell to provide pyramidal 
cells feedback inhibition.
The task of the network is to recognize four given patterns from its noisy input.
Each of the four patterns is represented by 32 active cells plus other 224 quiet cells.
Network has learned to recognize these four patterns by modifying the synapses according to
the following what might be called Hebb's rule.
\begin{equation} \label{eq:4}
w_{ij} = k \cdot \mbox{sgn}(R_i - 0.5M) \cdot \mbox{sgn}(R_j-0.5M),
\end{equation}
where $M$ is a saturation level in Eq.~(3), and $\mbox{sgn}(x)$ is 
equal to 1 if $x>0$ and 0 otherwise.
The equation is called Hebb's rule in the sense that
$w_{ij}$ will be modified
if and only if both the neuron $i$ and $j$ should be activated.
Also note that Eq.~(4) is applied only if the previous value of $w_{ij}$ is 0, 
otherwise, $w_{ij}$ will remain intact. Here, $k$ is set to 0.016. \\

\noindent
A noisy input of a pattern is constructed by randomly picking up
about one-third of the active cells of the selected pattern
with adding them other 20 quiet cells, also chosen at random,
after turning them active. \\

\noindent
Then one of these four patterns is given to the network, that is, network starts 
the dynamics with the pattern as the initial configuration of its neurons' state.
Network updates the state according to Eq.~(3).
The dynamics is observed during a total of 100ms (assuming step of $dt$ of $dr/dt$ 1ms), 
while the noisy input remains ON for the 1st 20 ms.

\section{Experiment}
In his book, Wilson \cite{wils} assigns values of $w_{ij}$ 
employing the Hebbian algorithm as mentioned above,
and succeeded in storing four patterns and recalling each of them from each of their
noisy input. We tested Wilson's experiment with the same set of patterns and 
succeeded in obtaining the similar results.\\

\noindent
The synaptic plasticity in this model is very robust. 
If we modify lots of weights, the network 
still recall the pattern correctly. 
That suggests that the top region of the Hebbian
peak in weight space has a wide area. 
However, when a weight configuration reaches the outside edge of the top region of 
the peak, all neurons become immediately quiescent, or for other such configurations
all of them fire at their maximum rate.
This obserbation is very different than the Hopfield model where 
stored patterns maintain their original form fairly well for a weight configuration
outside the top region. See \cite{imad-2}.



\subsection{Are Hebbian weights unique?}
The next question which might arise 
is ``Are Hebbian weights unique solution?''
Or, ``Are Hebbian weights
biologically plausible?'' In order to tackle this issue, we search for other 
configuration of weight values. For the purpose we employ an evolutionary computation.

\subsection{Searching for other solutions.}
Since the number of synapses among pyramidal cells is $N^2$,
We represent one candidate solution of a weight configuration by one dimensional
binary string of length $N^2 = 256 \times 256 = 65,536$ called chromosome.
Fitness, the degree to which how good each corresponding phenotype of the chromosome performs, 
is evaluated as
the ratio of how many pixels out of 256 are
correctly recovered when it's noisy input is given as the initial state, 
using Wilson's example of four patterns as a memory to be stored.
Result, however, is unpredictably horrible. It is as if a  search for
only one needle in a large haystack. What we observed is a series of fitness zero 
even after observing thousands of randomly created chromosomes. 

\subsection{Downhill walk from the top of Hebbian peak.}
In order to know what is going on, we learn 
what does the fitness landscape on the weight space look like
in which the hight of the land is almost everywhere zero except for the already known
Hebbian peak area. \\

\noindent 
Downhill walk is in two different ways. The one is by flipping only the bit that is one.
The other is opposite, that is, by flipping the bit one to zero. 
Both are by flipping a gene bit by bit.  

\subsection{Can climbers clime the peak to the top again?}
To learn what does the side wall of the peak look like, hill-climbers try to
climb the peak starting from the point that the downhill walker above walked three steps further
after the walker reached the flat land of fitness zero. Even from this very close point 
to the edge of the peak, we found it a very difficult task to find the point which has 
a fitness higher than zero. One of out experiment shows that 1411 trials are needed to 
find, say, 20 chromosomes whose fitness is not zero. \\


\noindent
Thus we have a population of non-zero-fitness points one of which walker should proceed.
The walker proceed to the maximum-fitness-point of the population of these points.
These points are expressed with $256 \times 256$ genes.
Then by flipping only one gene out of $256 \times 256$ genes 
of the first point the walker has proceeded,
again a population of points are obtained.
The point of the maximum fitness of the population is the second step the walker proceeds.
By iterating these procedure the walker hopefully climb the top of the hill again. 
The number of the points in the population is set here to 20. 

\subsection{A Needle in Haystack}
\subsubsection{Hinton \& Nowlan's model}
Hinton \& Nowlan~\cite{hint} proposed to employ a {\it life time learning} of each individual
to search for {\it a-needle-in-haystack} type of search. 
The problem Hinton \& Nowlan proposed is to search for only one configuration of 
20 bits of one and zero, that is, the search space is made up of $2^{20}$ points
all of which except for one point are assined fitness zero. 
Only one points, say, $(11111111110000000000)$ is assigned fitness one. That is
why this is called search for a needle in haystack. It is almost impossible
to solve if we use a simple genetic algorithm. Hinton \& Nowlan~\cite{hint} exploited
{\it life time learning} of each individal. That is, chromosome is made up of genes of which
about 25\% are ``1'',  25\% are ``0'', and the rest of the  50\% are ``?''. 
During an evolution all the ``?'' position
is assigned one or zero at random and fitness is evaluated, which is called {\it life time 
learning} of each individual. Each individal repeats the learning 1000 times.
If it reaches the point of fitness one at the $n$-th trial, 
then the {\it degree to which learning succeeded} is calculated as
\begin{displaymath}
1+19\cdot (1000-n)/1000.
\end{displaymath}
Our observation was that this value was zero for almost all individuals.
So we modify the model in which we create the first population by waiting
until the current population will be filled with 
non-zero success-of-learning individuals.
An example of run shows we have to try  118,499 random chromosomes to obtain such 
a population of 100 individuals.
Anyway we can find the needle in haystack in this way.

\subsubsection{Search for a mesa in desert}
Our chromosome consits $256\times256 = 65,536$ genes which is much larger than 20 genes
in the Hinton \& Nowran's Experiment.
We might call it  {\it a tiny mesa in the huge prairie.} \\

\noindent
Hinton \& Nowlan's model is a sort of thought-experiment to study how
the {\it life time learning} affects an evolution. 
The location of the unique solution (whose fitness is one, while all other's is zero)
is assume to be known before a run. It is not of the case in real world problems. 
In our current problem, on the other hand, fitness of every points can be calculated
although we don't know which points have the maximum fitness. Hence the model can be
applicable to our problem.

%\noindent
%We now are studying the Hinton \& Nowlan's model works in our problem.
%The results will be shown in the conference.

\section {Results \& Discussion}
\noindent
Two traces of a downhill walker from the top of the Hebbian peak 
are shown in Fig.~3 and Fig.~4.
%are shown in Fig.~\ref{fig:3} and Fig.~\ref{fig:4}.

\begin{figure}[h]\label{fig:3}
 \begin{center}
   \epsfile{file=one-to-zero.eps,width=8cm,height=5.1cm}
\caption{A downhill walk from top of the Hebbian peak with flipping only a gene
whose allele is one.}
 \end{center}
\end{figure}

\begin{figure}[h]\label{fig:4}
 \begin{center}
   \epsfile{file=zero-to-one.eps,width=8cm,height=5.1cm}
\caption{A downhill walk from top of the Hebbian peak with flipping only a gene
whose allele is zero.}
 \end{center}
\end{figure}

\noindent
As shown in both figures, the top region of the peak is not extremely narrow.
Of course the ratio of area of top region of the peak is a kind of infinitesimal
if we compare it to the whole area of search space. However, this is not
so special case. Generally, the solution to a problem does not have a top region
but just a point. 
Then why is the search for a solution to our problem so difficult? 
We guess it is due to
a very steep slope of side wall 
of the peak. 
It is terribly difficult to find a-little-better-solutions-than-others
on that steep side wall to climb the wall approaching the top.

\noindent
The results are very different from the similar experiment in Hopfield model.
As we previously reported, 
The peak has fairly dull side walls. See \cite{imad-1}, for example.\\

\noindent
A trace of a hillclimber who started from the point that the above mentioned 
downhill walker walked three steps more after he reached the flat land 
of fitness zero is shown in Fig.~5.

\begin{figure}[h]\label{fig:5}
 \begin{center}
   \epsfile{file=hc-c3memory.eps,width=8cm,height=5.1cm}
\caption{A trace of hillclimber who tried to climb the peak again from the very 
edge of the peak.}
 \end{center}
\end{figure}

\section{Conclusion}
We have described a fitness landscape 
in which we found it extremely difficulty to search for peaks.
We came accross the landscape when we studied
a neural network model of associative memory using spiking neurons.\\

\noindent
We explore the Wilson's model \cite{wils} where a number of binary patterns
are stored according to whether the number of spikes that each neuron emits
exceeds a threshold or not.
Wilson employed Hebb's rule to adjust
the strength of communication 
among neurons so that they store the given set of patterns.
Though we also observed that the Hebb's rule successfully stores 
a number of patterns,
we doubt this is not the only solution.
Then in order to search for other solutions, we employ 
evolutionary computations.
The result, however, was miserable.
It was worse than a search for a-needle-in-hay-stack. 
Even with a huge population of the random initial population,
the fitness of all individuals were zero. 
How could they evolve seeking a little better offspring in this situation? \\

\noindent
We know, however, we have at least one such solution, Hebbian one.
So we observed traces of a downhill walker from the top of this Hebbian peak,
and we learend the shape of the peak is more like a mesa --- with certain area
of top region and very steep side wall.
We conclude the difficulty in searching for the peak is due to this shape.
It is too steep to be attacked. 
Then we simulated a hill-climbing which tries to climb the mesa
from just the outskirt of it, and we observed the struggle of the walker,
though the walker eventually found the path to the top region again
after a huge number of trials.
But this is only on the condition that it start from an edge of the side wall. \\

\noindent
As a next step, we now are experimenting an evolution
in which each individual employs his/her learning during lifetime,
like the famous experiment by Hinton \& Nowlan \cite{hint}, so that we expect
that we will find a tiny mesa from huge desert. However we have not had 
satisfactory results yet.\\





\begin{thebibliography}{99}

\bibitem{hint}G. E. Hinton and S.J. Nowlan (1987)
{\em How Learning can Guide Evolution.}
Complex Systems, 1, pp.495--502. 

\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. (1949)
{\em The Organization of Behavior.} Wiley.

\bibitem{mccu}W. S. McCulloch and W. Pitts (1943) 
{\em A Logical Calculus of Ideas Immanent in Nervous Activity.}
Bulletin of Mathematical Biophysics, 5, pp.115--113.

\bibitem{wils}H. R. Wilson (1999)
{\em Spikes, Decisions, and Actions: The Dynamical Foundations of Neuroscience.}
Oxford University Press.

\bibitem{marr}D. Marr (1971)
{\em A Theory for Archicortex.}
Philosophical Transactions of the Royal Society of London, B262, pp.23--81,

\bibitem{naka}K. I. Naka and W. A. Rushton (1966)
{\em S-potentials from Colour Units in the Retina of Fish.}
Journal of Physiology, 185, pp.584--599.

\bibitem{imad-2}A. Imada (2001)
{\em A Visualization of Weight Solutions of a Neural Network Model of Associative Memory.}
Proceedings of the Turkish Artificial and Nerve Network Symposium, pp.69--77.

\bibitem{imad-1}A. Imada (1999)
{\em What does a Peak in the Landscape of a Hopfield Associative Memory Look Like?}
Proceedings of International Work-Conference on Artifcial and Natural Neural Networks, 
Vol. 1, Springer Verlag, Lecture Notes in Computer Science, No.1606, pp.357--366. 

\end{thebibliography}

\end{document}




\bibitem{imad-2}A. Imada (2002)
{\em A Fate of Two Evolutionary Walkers after the Departure from the Origin.}
Proceedings of the International Conference on Neural Networks and Soft Computing,
Advances in Soft Computing: Neural Networks and Soft Computing Physica-Verlag, pp.346--351.


%The conclusins here up to this moment are twofolds.
%One is about the solutions of weight configuration which 
%give a network a function of associative memory.
%The other is as to why the search of these solutins by 
%evolutionary computations is so difficult.