What does the Landscape of a Hopfield Associative Memory Look Like?

Akira Imada^{1} and Keijiro Araki^{2}

1 Graduate School of Information Science Nara Institute of Science and Technology 8916-5 Takayama, Ikoma, Nara, 630-01 Japan akira-i@is.aist-nara.ac.jp

2 Department of Computer Science and Computer Engineering 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

Abstract. We apply evolutionary computations to the Hopfield’s neural network model of associative memory. In the model, some of the appropriate configurations of synaptic weights give the network a function of associative memory. One of our goals is to obtain the distribution of these configurations in the synaptic weight space. In other words, our aim is to learn a geometry of a fitness landscape defined on the space. For the purpose, we use evolutionary walks to explore the fitness landscape in this paper.

1 INTRODUCTION

Associative memory is a dynamical system which has a number of stable states with a domain of attraction around them (Komló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. The dynamical behavior of its neuron states strongly depends on synaptic strengths between neurons. The synaptic strengths are called weights and the weight from neuron j to neuron i is denoted as w_{ij} in this paper. Hopfield used the so-called Hebbian rule (Hebb 1949) to prescribe the synaptic weights. The prescription of the weights is usually called learning. Borrowing the expression from Kauffman (1993), learning is a walk in synaptic weight space seeking good attractors. We specify the synaptic weights using evolutionary walks.

For the fully connected neural networks with N neurons, all the possible combinations of w_{ij} construct an N^{2}-dimensional Euclidean space. Every configuration of w_{ij} is represented as a point in the weight space. A fitness value is associated with each point according to the pattern storing capability of the network that is determined by the configuration of w_{ij}. The task of our evolutionary walks is to locate the points of the highest fitness value. Our previous result (Imada and Araki 1997a) shows that the task to locate one of the optimum solutions becomes difficult as the number of patterns to be stored increases. We conjecture that this phenomenon is due to the increased ruggedness of the fitness landscape.

2 Fitness Landscape

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, Hagan and Perelson 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 and Schuster 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. 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 walk on the landscape. Macken et al. (1991) used random point mutation that changes a single letter in the string to specify neighbors of the string. Then, by sampling points along an evolutionary walk in which point moves to the firstly found fitter neighbor, they studied the statistical properties of the landscape of the chemical affinity of antibody for antigen in immune response. Weinberger (1990) used two different walks: “gradient walk” in which the walker steps to the best of its neighbors and “random adaptive walk” in which the next step is chosen 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 and Levin 1987).

The fitness landscapes described above are all constructed on the space of discrete configurations of string. What we are concerned, however, is a fitness landscape defined on the continuous weight space, following Gardner (1988) who discussed solutions in terms of the volume of the solutions in the space. However, the number and distribution of these solutions are still open problem. We explore the fitness landscape to obtain the information as to the number and distribution of the solutions in weight space. To explore the fitness landscape defined on this continuous weight space, we use a Gaussian random mutation, which is described later in detail.

3 Hopfield Model and Fitness Evaluation

The Hopfield model consists of N neurons and N^{2} synapses in which each neuron takes one of two states ±1. Then patterns

ξ^{ν} = (ξ_{1}^{ν}, ⋯, ξ_{N}^{ν}), ν = 1, ⋯, p

where ξ_{i}^{ν} takes the value of either 1 or −1, are to be memorized as equilibrium states. After one of these patterns is given to the network, neuron states are updated asynchronously, i.e., at most one neuron changes its state at a time, according to

s_{i} (t + 1) = sgn ( ∑_{j≠i}^{N} w_{ij}s_{j}(t) ) ,

where s_{i}(t) is a state of i-th neuron at time t. The behaviors of the collective states of individual neurons are characterized by synaptic weights w_{ij}. Provided the synaptic weights are determined appropriately, the network can store some number of patterns as attractors.

Fitness evaluation. When one of stored patterns ξ^{ν} is given to the network as an initial state, possibly including a few errors, the state of neurons varies from time to time afterwards. In order for the network to function as an associative memory, these instantaneous states s_{i}^{ν}(t) must be similar to the initial state. The similarity as a function of time is defined by,

m^{ν}(t) = \frac{1}{N} ∑_{i=1}^{N} ξ_{i}^{ν}s_{i}^{ν}(t).

This is conventionally called an overlap. The temporal average of m^{μ}(t) is calculated for each stored pattern. Then, the fitness function is obtained by further averaging these values over all the given patterns. That is, our fitness value f is calculated as:

f = \frac{1}{p · t_{0}} ∑_{ν=1}^{p} ∑_{t=1}^{t_{0}} m^{ν}(t).

Note that the fitness 1 implies all the p patterns are stored as fixed points (i.e., the initial state remains unchanged), while fitness less than 1 includes many other cases.

4 Experiment

Since experiments here were carried out on networks with 49 neurons, the fitness landscape is defined on the 49^{2}(= 2401) dimensional Euclidean space. Fitness of each point in the space is associated with the capability of the corresponding network to store a set of given patterns as associative memory. Note that p, the number of patterns to be stored, determines the ruggedness of the fitness landscape. To take a bird’s-eye view of the landscape for, say p = 6, we picked up 240,000 points^{3} randomly from the space. The observed fitness values were distributed only from 0.10 to 0.46. Peaks are too narrow to be viewed.

As a preliminary experiment to explore this fitness landscape, we use a simple random walk in which a point moves consecutively to one of its neighboring points at random by the Gaussian mutation. That is, we give small perturbation on each coordinate of the current point, x_{i} (i = 1, 2, ⋯, 2401), using the Gaussian random variables with mean 0 and standard deviation σ_{0}, i.e.,

x_{i}^{new} = x_{i}^{old} + σ_{0} · N_{i}(0, 1).

This mutation enables a point to make a random walk on the fitness landscape, where σ_{0} · N_{i}(0, 1) implies a step length. We already know the existence of some peaks on the fitness landscape. The weight configuration by the Hebbian rule:

w_{ij} = \frac{1}{N} ∑_{ν=1}^{p} ξ_{i}^{ν}ξ_{j}^{ν} (i ≠ j), w_{ii} = 0

is an example. We observed some down hill random walks from this Hebbian peak with several values of σ_{0}. Results are shown in Fig. ??a. From this experiment, we tentatively set σ_{0} to 0.002. We also made another experiment with this random walk, starting at a point chosen randomly from the space. A result is shown in Fig. ??b. We can see that a walker wanders around a comparatively flat region with low fitness values, not even being able to approach to local peaks.

Fig. 1. Examples of random walk: (a) downhill walks from a Hebbian peak; (b) random walk from a randomly chosen point.

Next, to reach the configurations of w_{ij} that gives the network a higher fitness value, we used two walks: simple hill climbing walk and evolutionary programming

3 The number of samples here is taken from the typical number of fitness evaluations in a run of our evolutionary algorithms.

walk. Evolutionary programming (EP) is a technique for optimization, proposed by L. Fogel, Owens and Walsh (1966) (see also D. Fogel 1995). Although the population in EP is usually randomized at the beginning of a run, we start it with all identical points. This allows us to call it a walk.

In simple hill climbing, the Gaussian mutation is given λ times to the current point. Then, the point which obtains the highest fitness value is selected as the next point. In EP-walk, on the other hand, μ points construct a population. Each of these μ points is mutated once, which produces μ mutants. Each point has additional variables σ_{i} for each coordinate, which are used as a standard deviation of a Gaussian random variable to be added to the i-th coordinate of the point. After the mutation, these σ_{i} are also modified as:

σ_{i}^{new} = σ_{i}^{old} + 0.01 · σ_{i}^{old} · N_{i}(0, 1).

All the σ_{i} are initialized to σ_{0} (= 0.002) at the beginning of a walk. Now, we have the original μ points and their μ mutants. The fitness value of each of the 2μ points are compared to those of q points which are chosen randomly at every time of the comparison from the whole 2μ points. Then the 2μ points are ranked according to the number of wins, and the best μ points survive (q-tournament selection). The cycle of reconstructing the new population with better fitness points and restarting the search is repeated until one of the global optima is found or a set maximum number of generation has been reached. In this paper, both λ and μ are set to 200 and q is chosen to be 10.

Thus, a walker will be able to walk toward higher point in the fitness landscape. However, as will be described in the next section, walkers are often trapped at one of many local hills. When we use the Gaussian mutation to move a point, the probability to escape from local optimum is not zero, at least theoretically. In practice, however, the distribution of step sizes by the Gaussian mutation is like the one shown in Fig. ??a. In our experiments on the condition described above, the distribution of these step lengths ranges from 0.0102 to 0.0250. We can control the range by tuning σ_{0} so that the step lengths remain small, and this allows us to estimate the basin size of global/local peaks when our walkers walk in the landscape.

Note that if, for example, we use discrete crossover, or equivalently continuous version of uniform crossover, instead, step lengths from one of the parents also shows Gaussian-like distribution, but step lengths take larger values, and in addition, we cannot control the distribution in this case. In our experiment, the lengths range from 25.8 to 30.8 as shown in Fig. ??b. This is rather a long jump, or another version of random sampling, much more effective though. Since our aim is to learn the geometry of the fitness landscape, rather than to locate the global optimum efficiently, we use the above two walks expecting to obtain the quasi-continuous information of the landscape along a walk of small step length.

Although we have thus far used the term hill or peak for the optimal configuration of w_{ij}, we must note here the following feature of our fitness landscape. Since each 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 κ, κw_{ij} works exactly in the same way as w_{ij} in updating neuron states. Therefore, our landscape of the Hopfield network, if defined on the weight space, is made up of infinitely extended straight ridges emanating from the origin. The height of each ridge remains constant, but different from each other.

Fig. 2. Distribution of step lengths. (a) Gaussian mutation; (b) Discrete crossover.

5 Results and Discussion

Walk by Evolutionary Programming. We run EP-walks with p, the number of patterns to be stored, incremented from 1 to 7. For each p, we repeated a walk 30 times with different random number seed at the start. Typical results for p = 6 are shown in Fig. ??. Some walks reach the global optimum (Fig. ??a), some of the others are trapped at one of the local optima (Fig. ??b) and the rest are still searching for the optima even at 60,000 generations (Fig. ??c).

In Table 1, we show statistics of the results. All the runs for p = 1 locate the global optimum. Then, as p increases, the number of runs that reached the global optimum (within 12000 generations) decreases, and the average walklength to the global optimum increases significantly, and finally for p = 7, no run can locate the global optimum any more. The short walk-length to the global peak on the landscape for p = 1 suggests the existence of many global peaks. Then the number decreases as p increases. However, as we reported elsewhere, we had found the global optimum even for p = 90 with another evolutionary technique (Imada and Araki 1997b). Therefore, other possible interpretations for the decrease in number of runs that locate the global optimum are: (1) the basin size of the global optimum becomes narrower and (2) the number of local optima increases. As will be described in the next subsection, the heights of the local optima which trap some EP-walks are quite high if we compared them to the hill-climbing walks by Gaussian mutation alone. Hence, we surmise that the

Fig. 3. Fitness along a EP-walk. (a) Reach the global optimum; (b) Trapped at a local optimum; (c) Still searching for the optima.

increase in walk-length for the runs which success in locating the global optimum is due to the decrease of the basin size of the global optima.

Table 1. Statistics of EP-walks (up to 12,000 generations). Runs are repeated 30 times for each p.

#-of- reached the global optimum trapped or still searching
patterns #-of-runs avg-length  #-of-of-runs avg-fitness
1  30  161  0  —
2  28  1085  2  .983590
3  23  2458  7  .988458
4  12  4948  18  .990322
5  6  6938  24  .987976
6  2  9648  28  .984423
7  0  —  30  .973128

Gaussian Random Mutation Hill Climbing Walk. Then, we run hill climbing walks by the Gaussian mutation, in the same way as the above EPwalks. Typical examples are shown in Fig. ??. As expected, the runs are less efficient than EP-walks. It is only among the runs for p = 1 that were able to locate the global optimum (Fig. ??a). Other runs are trapped at local optimum (Fig. ??b) or keep searching for the optima (Fig. ??c).

As shown in Fig. ??b, some runs struggle in the basin of local hill for quite a long time (more than 50,000 generations). Hence, we can guess that the capability to escape from a local trap is much higher in an EP walk than a Gaussian mutation hill-climber. We take a run to be stuck at local optimum if it stays there for more than 50,000 generations, otherwise we take it that the run keeps

Fig. 4. Fitness along a hill-climbing-walk. (a) Reach the global optimum; (b) Trapped at a local optimum; (c) Still searching for the optima.

searching for the optima.

The statistics of the results are shown in Table 2. Comparing to the above EP walks, the heights of local optima which trap a run become significantly lower as p increases. Both the decrease in height and increase in number of these local peaks make a walk difficult to reach the global peaks.

Table 2. Statistics of the Gaussian mutation hill-climbing walk (up to 60,000 generations). Runs are repeated 30 times for each p.

#-of- reached the global optimum trapped at the local optima still searching
patterns #-of-runs avg-length  #-of-runs avg-fitness  #-of-runs
1  10  1945  20  .950300  0
2  0  —  22  .934692  8
3  0  —  7  .882200  23
4  0  —  3  .870902  27
5  0  —  1  .826972  29
6  0  —  1  .663160  29

Are Searches Easier in the Region near the Origin? As already described, the fitness landscape of the Hopfield network, when the landscape is defined on the weight space, is made up of continuous ridges emanating from the origin of the space, instead of discrete peaks. It is intuitively clear that these ridges are more densely packed in the region near the origin than the region far from the origin.

In the EP-walk described in this paper, each w_{ij} is perturbed by adding the Gaussian random variables δw_{k} at every step of the walk. When the walk is terminated, each initial weight value increases by ∑ δw_{k}. Hence, a different value of σ_{0} affects only by the scaling factor on the cumulatively added term ∑ δw_{k} for a different sequence of random numbers which generates the walk. Therefore, as far as when we start the walk with w_{ij} being all zero, a same set of the initial random number seeds results in an equivalent set of solutions for an arbitrary set σ_{0}. The difference is only a scaling factor.

However, if we start with non-zero matrix, this does not hold. The initial difference in w_{ij} prevents the walk from yielding the equivalent solution despite only difference by a scaling factor of the cumulatively added terms ∑ δw_{k}. We observed that the region where a walk starts affects the results dramatically. Here, we test it using two Hebbian peaks which are equivalent except for scaling. That is, the two Hebbian weight configurations are on the same ridge, but one is near the origin and the other is far from the origin. The Hebbian weights have learned 10 patterns (p = 10), therefore two peaks are not the global optima due to its being overloaded^{4}. Then, two EP-walks start from these two local optima searching for higher fitness point. We observed that the EP-walk which started at the peak near the origin can easily reach the global optimum, while when started at the peak far from the origin it keeps searching even at generation 60,000. Probably, the lower density of ridges in the region far from the origin makes it difficult to search for another higher ridges.

6 CONCLUSION

We have analyzed evolutionary walks through the fitness landscape defined on the weight space of fully connected neural networks. The fitness landscape of the Hopfield model of associative memory, when defined on weight space, is made up of many ridges emanating from the origin of the space. The geometry is determined by p, the number of patterns to be stored. We conjecture that, as p increases,

• the number of the global ridges increases

• the width of the global ridges decreases

• the height of the local ridges becomes lower

• the width of the local ridges becomes smaller

• the number of the local ridges increases Furthermore, the region between ridges are rugged lowland and naturally its area becomes wider as the region becomes far from the origin.

The next step is to analyze the fitness value of the points along a walk in more detail, which will allow us to obtain a more precise geometry of the landscape.

Acknowledgments

We thank anonymous reviewers for useful comments and encouragements on this work. The final version of the paper has been significantly improved by

4 The capacity of the network with 49 neurons to store patterns as fixed points is around eight (see e.g., Amit (1989)).

suggestions sent by David Fogel, to whom we are very grateful.

References

Amit, D. J. (1989) Modeling Brain Function: The World of Attractor Neural

Networks. Cambridge University Press. Bray, A., and M. Moore (1980) Metastable States in Spin Glasses. Journal of

Physics C: Solid State Physics 13, ppL469–L476. Fogel, D. B. (1995) Evolutionary Computation: Toward a New Philosophy of

Machine Intelligence. IEEE Press. Fogel, L. J., A. J. Owens, and M. J. Walsh (1966) Artificial Intelligence through

Simulated Evolution. Wiley. Fontana, W., and P. Schuster (1987) A Computer Model of Evolutionary Opti-

mization. Biophysical Chemistry 26, pp123–147. Gardner, E. (1988) The Phase Space of Interactions in Neural Network Models.

Journal of Physics 21A, pp257-270. Hebb, D. O. (1949) The Organization of Behavior. Wiley. Hopfield, J. J. (1982) Neural Networks and Physical Systems with Emergent

Collective Computational Abilities. Proceedings of the National Academy of Sciences, USA 79, pp2554-2558.

Imada, A., and K. Araki (1997a), Random Perturbations to Hebbian Synapses of Associative Memory using a Genetic Algorithm. J. Mira, R. Moreno-Díaz, and J. Cabestany (Eds.) Proceedings of International Work-Conference on Artificial and Natural Neural Networks. Springer Verlag, Lecture Notes in Computer Science No.1240, pp398–407.

Imada, A., and K. Araki (1997b) Evolution of Hopfield Model of Associative Memory by the Breeder Genetic Algorithm. T. Bäck (Ed.) Proceedings of the 7th International Conference on Genetic Algorithms, Morgan Kaufmann, pp784–791.

Kauffman, S. A., and S. Levin (1987) Towards a General Theory of Adaptive

Walks on Rugged Landscapes. Journal of Theoretical Biology 128, pp11–45. Kauffman, S. A. (1993) The origin of Order: Self-organization and Selection in

Evolution. Oxford University Press. Komlós, J., and R. Paturi (1988) Convergence Results in an Associative Mem-

ory Model. Neural Networks 1, pp239–250. Macken, C., P. Hagan, and A. Perelson (1991) Evolutionary Walks on Rugged

Landscapes. SIAM Journal of Applied Mathematics 51, pp799–827. Maynard Smith, J. (1970) Natural Selection and the Concept of a Protein Space.

Nature 225. pp563–564. Weinberger, E. D. (1990) Correlated and Uncorrelated Fitness Landscapes and

How to Tell the Difference. Biological Cybernetics 63, pp325–336. Wright, S. (1932) The Roles of Mutation, Inbreeding, Crossbreeding and Selec-

tion in Evolution. Proceedings of the 6th International Congress of Genetics, pp356–366.

This article was processed using the L^{A}TEX macro package with LLNCS style