\documentstyle[eclepsf]{article}

\textheight 238mm
\textwidth 160mm
\topmargin -10mm
\oddsidemargin -3mm

\title{How Can a Peak on a Completely Flat Land Searched for? \\
--- Hinton \& Nowlan's Experiment Revisited}
\author{Akira Imada\\
        Brest State Technical University, \\
        Moskowskaja 267, Brest, 224017, Republic of Belarus\\
        e-mail: akira@bstu.by}
\date{}

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

\abstract
\noindent
We are exploring a weight configuration space searching for solutions which give
our neural network with spiking neurons a function of associative memory.
We already know one such solution --- Hebbian one, and we guess we have others
which we have not known so far. We employ an evolutionary computation where
solutions are regarded as peaks in landscape. What we have found is 
the landscape is almost everywhere completly flat low land and the Hebbian peak
is only a unique narrow high land whose side wall is extremely steep, 
like a mesa in desert. In this circumstance how evolutionary computation
could find other peaks that we assumed? We propose a test function representing
the circumstance in which we can controll the complexity of the problem.
Namely, this paper is a call for challange toward solutions.

\section{Introduction}
\noindent
Evolutionary computations usually search for the solution
by recombining multiple candidate solutions that are (a little) better than others.
The degree to which one is better than others is called fitness.
Then a hyper-surface is defined on the space of all the possible candidate solutions
which is called {\it fitness landscape}.


\section{Problem Description}
\subsection{An Associative Memory by Spiking Neurons}
\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 (1982) 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 {\it number and distribution of the weight solutions},
%% and these issues still attract interests of, say,  some physicists,
and we study another model using spiking neurons instead of 
McCulloch-Pitts (1943) neurons.
with the goal being to overcome those problems
%% like small storage capacity 
and, more importantly,  
to look for more biologically plausible models of human memory.\\
\indent
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).
As  Wilson (1999) wrote in his book, Marr (1971) was one of the first to propose 
this {\it hippocampal model} involving both recurrent excitation via Hebbian (1949)
synapses and inhibition.
In his book, Wilson (1999) wrote that
a single neuron which emits spike train 
when it receives an external stimulus $P(t)$ could be modeled by
\begin{equation}
\frac{dR(t)}{dt} = \frac{1}{\tau}(-R(t) + S(P))
\end{equation}
where  Wilson (1999) proposed to employ, among many alternatives, 
Naka-Rushton (1966) 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}
$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.
Here we 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 via synaptic strength,
as well as interneuron cells whose number is reduced to only one in this paper.
%% 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}

\indent
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 (1999), 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{equation}\label{eq:3}
\tau_G \frac{dG}{dt} = -G - 0.07 \sum_{j=1}^{N} R_i
\end{equation}

\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.\\
\indent
In order to encode $N$-bit patterns using $N$ spiking neurons,
we use in this paper {\it Firing-rate} of a neuron within certain time window 
which expresses binary number according to whether the rate exceeds
a threshold or not. \\
\indent
In what he calls {\it CA3 network} in his book, Wilson (1999) 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 a 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.~(5) 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. \\
\indent
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.
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.~(4).
The dynamics is observed during a total of 100ms 
(assuming step of $dt$ of $dr/dt$ to be 1ms), 
with the noisy input being continued to be fed for the 1st 20 ms.

\subsection{Fitness Landscape}
\indent
The concept of the fitness landscape was first introduced 
by Wright \cite{wrig} 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,
where 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 defined by 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-1}.

In this paper, we 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.

\subsection{Search for a Needle in a Haystack --- Hinton \& Nowlan's Experiment}

a-little-better-candidate-than-ohters. 
This is visualized 
However what if no such candidates exist?

This situation remeniscent of the seminal experiment by Hinton \& Nowlan (1987).

Hinton \& Nowlan~\cite{hint} proposed to employ a {\it lifetime 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 assigned 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 lifetime learning} of each individual. 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 lifetime learning} of each individual. Each individual 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 experiment so that 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.

Our chromosome consists $256\times256 = 65,536$ genes which is much larger than 20 genes
in the Hinton \& Nowlan'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 lifetime learning} affects an evolution ({\it Baldwin effect}).
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.


\section{Test-function: A mesa in dessert}

\section{Experiment}
\begin{figure}[hbtp] 
 \begin{center}
%   \epsfile{file=learned-firstly.eps,width=14cm,height=8cm}
\label{fig:1}
\caption{Schematic diagram with three,}
 \end{center}
\end{figure}

otherwise it repeat forever.

\section{Summary}
\end{document}