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

\begin{document}

\title{A Visualization of Weight Solutions\\ of a Neural Network Model
       of Associative Memory}

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

\begin{abstract}
\noindent
We apply evolutionary computations to the Hopfield model of 
associative memory. In the model, a number of patterns can be 
stored in the network as attractors if synaptic weights are 
determined appropriately. Thus far, we have explored the weight
space and found many different such solutions of weight 
configurations. One of our goals of this study is to learn 
the number and distribution of these weight solutions, 
which is still an open problem. To address this issue, 
we test a method of visualizing these solutions in 
high-dimensional weight space.
\end{abstract}

\section{Introduction}
Although the fully connected neural network model of associative 
memory, such as the Hopfield's model, is nowadays said to be 
impractical, many interesting issues from physics point of view 
are still unknown. The number and distribution of attractors in 
synaptic weight space are one of these examples. 
This paper is a step toward learning the distribution of these weight 
solutions as a function of number of patterns to be stored.

Using evolutionary computations, we have found
many different solutions that give a fully connected 
neural network a function of associative memory. 
Especially, the Breeder Genetic Algorithm (BGA)
gave us a wide variety of such solutions that store 
almost an upper bound of storage capacity of a 
network (Imada et al., 1997), which are in general
a very difficult to be searched for.

Each solution is a  point in weight space of high dimensionality,
and they are visualized by being mapped into points 
in the two-dimensional (2D) space with the distance relation 
among the original points remaining as much as possible.
Shine et al.\ (1997) and Collins (1997)
argued such a technique, and Collins call this 
technique {\it ``Sammon Mapping''} after 
Sammon (1969) who proposed this technique 
originally. (Shine et al.\ call this 
{\it ``Distance Map''}.)
Since the technique is an optimization problem, 
we can also employ a genetic algorithm (GA) 
to solve this problem. 

In the following two subsections, associative
memory model and Sammon mapping are described
more in detail.

\subsection{Associative Memory}
Associative memory is a dynamical system 
which has a number of stable states with 
a domain of attraction around them 
(Koml\'{o}s et al., 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 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 Hebb's (1949) rule  
to prescribe the weights \footnote{The rule was at first advocated
by Hebb (1949) and later formalized by Cooper (1973)}.
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{equation} \label{eq:one} 
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{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 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 (1976) model of spin-glass,
in  which the Hamiltonian energy has two minima,
while the model for infinitely large $p$ 
corresponds to the Sherrington-Kirkpatrick (1975) 
model, 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 (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 fixed set of patterns, and we call 
these points solutions.

\subsection{Sammon Mapping}
As Collins (1997) wrote,
the dimension reduction has been an important technique 
for visualization of the space of high dimensionality.
The Sammon Mapping (Sammon, 1969) is one of these techniques.
This enables us to map a set of ${\cal N}$ points in 
$n$-dimensional space to 2D location data so that 
the distance information is preserved as much as possible, 
or as Shine et al.\ (1997) wrote {\it ``so that the 
$n$-dimensional distances are approximated by 
2 dimensional distances with a minimal error.''} 
This problem is an optimization problem.

Shine et al.\ (1997) and Collins (1997)
proposed a method to solve this problem by a GA, 
as follows. First, the distance matrix 
whose entries are Euclidean distances between all 
possible pairs of ${\cal N}$ points in the 
$n$-dimensional space is calculated. Then tentative 
${\cal N}$ points in the 2-dimensional space are 
determined representing the original 
${\cal N}$ points in the $n$-dimensional space.
The distance matrix of these ${\cal N}$ points
in the 2D space 
is also calculated, which then will be subtracted 
from the original $n$-dimensional distance matrix, 
yielding an error matrix. A GA is used to minimize 
this error matrix.


Since our experiments of the fully-connected 
neural network model of associative memory have 
been carried out on networks with 49 neurons, 
the weight space is $49^2 = 2401$ dimensional.
Hence, we restricted the dimensionality to 
2401 that is to be reduced to 2 in this paper.
Given $\cal N$ points in the 2401 dimensional space
\begin{displaymath}
X^1, \cdots, X^{\cal N}
\end{displaymath}
where each point $X^k$ is expressed by 2401 
coordinates as
\begin{displaymath}
X^k = ({z}^{k}_{1}, \cdots, {z}^{k}_{2401}).
\end{displaymath}
Then the square distance between the $m$-th point 
and the $n$-th point is calculated as
\begin{displaymath}
R^{mn} = \sum _{i=1}^{2401} 
{(z_{i}^{m} - z_{i}^{n})^2}.
\end{displaymath}
The values for all possible combination of 
$m$ and $n$ construct a distance matrix. Since the 
matrix is symmetric with zero diagonal elements,
we use the lower triangle elements ($m<n$).

Then we generate $\wp$ sets of the 
2D $\cal N$ points at random, i.e.,
\begin{displaymath}
\begin{array}{l}
 \mit\Psi^{1}(1), \cdots, \mit\Psi^{\cal N}(1) \\
 \mit\Psi^{1}(2), \cdots, \mit\Psi^{\cal N}(2) \\
 \cdots \\
 \mit\Psi^{1}(\wp), \cdots, \mit\Psi^{\cal N}(\wp) 
\end{array}
\end{displaymath}
where the $k$-th point of the $i$-th set is 
represented as:
\begin{displaymath}
\mit\Psi^k (i) = ({\zeta}^{k}_{1}, {\zeta}^{k}_{2}).
\end{displaymath}
Thus  the $i$-th set of these $\cal N$ points has 
its distance matrix whose elements are
\begin{displaymath}
r^{mn} (i) = \sum _{i=1}^{2} 
{(\zeta _{i}^{m} - \zeta _{i}^{n})^2}.
\end{displaymath}
The objective function of the $i$-th 
sets can be defined as 
\begin{displaymath}
f(i) = \sum _{m<n} {(r^{mn} (i) - R^{mn})}.
\end{displaymath}

Starting with a random configuration of 
${\cal N}$ points in the 2D space,
the GA corrects these points generation 
by generation applying  crossover 
and mutation\footnote{We employ uniform 
crossover (Syswerda, 1989) and BGA mutation 
(M\"{u}hlenbein et al., 1996).} to 2D coordinates.
The correction is repeated until the error 
converges to an acceptable minimum.

\section{Results \& Discussion}
In exploring weight space to search for the
solutions, $w_{ij}$ can take an arbitrary real 
value, there are infinite number of equivalent 
configurations which differ only by scaling factor.
In other words, for any scaling factor $\kappa$, 
$\kappa w_{ij}$ works exactly in the same way as 
$w_{ij}$ in updating neuron states (see equation 
(\ref{eq:one})).
These solutions construct hyper-lines emanating from the origin.
Therefore, as Gardner (1988) did, all the  
solutions are normalized on the surface of 
hypersphere of radius one whose center is at 
the origin, by regarding the solutions on 
a hyper-line as the cross point of the line and 
the sphere surface.

\begin{figure}[hbtp]
\begin{center}
\epsfile{file=sphere-one.eps,width=8.5cm,height=5.5cm}
\epsfile{file=sphere-one-small.eps,width=8.5cm,height=5.5cm}
\epsfile{file=sphere-two.eps,width=8.5cm,height=5.5cm}
\caption{The 2D points mapped from three different regions
         on hypersphere of the 2401 dimensional space: All positive 
         coordinates region (top); a subset of the region 
         above (middle); and two regions of the symmetric 
         positions (bottom). Filled-in circle $\bullet$ 
         indicates the origin. See text more in detail.}
\label{hypersphere}
\end{center}
\end{figure}

\begin{figure}[hbtp]
\begin{center}
\epsfile{file=hopfield-point-10-new.eps,width=8.5cm,height=7cm}
\epsfile{file=hopfield-point-90.eps,width=8.5cm,height=7cm}
\caption{2D points mapped from solutions in the 2401-dimensional 
         weight space. Filled-in circle $\bullet$ indicates the origin.
         The number of stored patterns is 1 (top) and 90 (bottom).}
\label{hopfield-point}
\end{center}
\end{figure}

In the following two subsections, the results 
of two different experiments are shown.
First, in order to see how the Sammon mapping works 
in our problem, a set of random points are picked up 
each from three different categories on the hypersphere 
surface of the 2401 dimensionality, and then observed 
how they are made visible in the 2D space.
Next, the method is applied to our solutions
for the associative memory network.

\subsection{Preliminary Experiments}
%%\noindent
%%{\bf Preliminary Experiments}\\
\noindent
As a preliminary experiment, random points from
the following three categories of region in 
the 2401 dimensional space:
(1) the region whose coordinates are all positive
values belonging to $[0,1]$;
(2) the smaller region whose coordinates are picked up
from $[0.5,1]$;
(3) two regions whose coordinates are either
$[-1,0]$ or $[0,1]$.
Then they are normalized on the hypersphere surface
and are visualized.
The results are shown in Figure \ref{hypersphere}.
We can see the results reflect the distribution 
of the original points in high dimensional space 
pretty well in all these three cases.\\

\subsection{Weight Solutions of Associative Memory}
%%\noindent
%%{\bf Weight Solutions of Associative Memory}\\
\noindent
As stated earlier, multiple configurations of 
weights give a network a function of associative 
memory. The number of these configurations is 
known to be dependent on $p$, the number of 
patterns to be stored. Storing just one pattern 
gives a maximum number of solutions of weights, 
while as $p$ approaches twice the number of 
neurons, all the solutions vanishes (Gardner, 1988).
However, the number and distribution as a function 
of $p$ is still unknown. So far, we have applied 
some variants of evolutionary algorithms to search 
for these solutions 
(Imada et al.\ (1995; 1996; 1997; 1998) and Imada (1999)).
Here, we study the solutions found by the BGA among 
others, since only this algorithm has been able to 
search for solutions for a wide range of $p$ 
(Imada et al., 1997).

Our experiments were carried out on networks with 49 
neurons and the BGA found solutions for up to $p=90$.
The solutions that the BGA found are also expected 
to be different from run to run, as M\"{u}hlenbein 
et al.\ (1996) wrote: {\it ``the BGA mutation scheme 
is able to optimize many multi-modal functions.''}
As a preliminary stage of the goal of learning 
distribution of the solutions as a function of $p$,
we sampled such solutions for $p=1$ and $90$.

We guess that the normalized solutions for 
$p=1$ are distributed uniformly on the surface 
of the hyper-sphere.
We show the results of the 2D points mapped from 
the 2401-dimensional space 
for the number of solutions ${\cal N} = 11$ 
in Figure \ref{hopfield-point} (top).
We observed that the 2D points corresponding 
to the solutions are almost uniformly distributed 
on the circle whose center corresponds to the origin 
of the 2401-dimensional space.

Next, we apply the technique to solutions also obtained 
by the BGA runs for $p=90$. This number of patterns to 
be stored is almost the upper bound of the storage 
capacity for a network with 49 neurons, and the solutions 
are expected to be localized in a small region of weight 
space (Gardner, 1988).
A result for ${\cal N} = 9$ 
is shown in Figure \ref{hopfield-point} (bottom).
Though resolution is not so good, we can imagine 
the localized solutions.


\section{Conclusion}
With our goal being a visualization of weight solutions
of neural network model of associative memory, we have 
described a technique to map a high-dimensional search 
space to 2D points remaining the distance relation of 
the source points being as much as possible.

Since the topic has not been the subject of extensive 
research, as Shine et al.\ (1997) pointed out, 
we preliminary applied the technique to three different
sets of random points picked up from a known shaped
region in the 2401 dimensional space,
and we have found that the technique can give us an
information of the distribution of the original points
fairly well.

Then, we applied the technique to our weight space 
in which we already had the solutions that give 
a network a function of associative memory.
If $p$, the number of patterns to be stored, is only 
one, then the solutions are expected to be uniformly 
distributed in the space. On the other hand, if $p$ 
is almost the upper bound of the storage capacity, 
then the solutions are expected to be highly localized.
And we obtained the expected results, that is, the 
solutions are distributed uniformly at random for 
$p=1$ and very localized for $p=90$.

\subsection*{Acknowledgments}
We thank Trevor D. Collins for answering us several 
questions about Sammon Mapping via e-mail.
%%Thanks are also due to anonymous reviewers for 
%%comments and encouragements on this work.

\subsection*{Reference}
\begin{description}

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

\item[]Collins, T.\ D.\  (1997)
{\em Using Software Visualization Technology to Help Evolutionary Algorithm 
     Users Validate their Solutions.}
Proceedings of the 7th International Conference on Genetic Algorithms, pp.307--314.

\item[]Cooper, L.\ N.\ (1973)
{\em A Possible Organization of Animal Memory and Learning.}
Proceedings of the 24th Nobel Symposium on Collective Properties 
of Physical Systems, pp.252--264.

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

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

\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[]Imada, A., 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.

\item[]Imada, A., and K.\ Araki (1996)
{\em Lamarckian Evolution of Associative Memory.}
Proceedings of IEEE International Conference on Evolutionary Computation, pp.676--680.

\item[]Imada, A., 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.

\item[]Imada, A., and K. Araki (1998)
{\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, pp.647--656.

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

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

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

\item[]M\"{u}hlenbein, H., and D.\ Schlierkamp-Voosen (1996)
{\em Predictive Models for the Breeder Genetic Algorithm I. Continuous Parameter Optimization.}
Evolutionary Computation, 1,  pp.25--49.

\item[]Sammon, J.\ W.\  (1969)
{\em A Nonlinear Mapping for Data Structure Analysis.}
IEEE Transactions on Computers. C-18(5), pp.401--408.

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

\item[]Shine, W.\ B.\ and C.\ F.\ Eick (1997)
{\em Visualizing the Evolution of Genetic Algorithm Search Processes.}
Proceedings of the IEEE International Conference on Evolutionary Computation, pp.367--372.

\item[]Syswerda, G. (1989)
{\em Uniform Crossover in Genetic Algorithms.}
Proceedings of the 3rd International Conference on Genetic Algorithms, pp.2--9.

\end{description}
\end{document}
