Lamarckian Evolution of Associative Memory

Akira Imada

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

Keijiro Araki

Graduate School of Information Science Nara Institute of Science and Technology

8916-5 Takayama, Ikoma, Nara, 630-01 Japan araki@is.aist-nara.ac.jp

Abstract— There have been a lot of researches which apply evolutionary techniques to layered neural networks. However, their applications to Hopfield neural networks remain few so far. We are applying genetic algorithms to fully connected associative memory model of Hopfield. In an earlier paper, we reported that random weight matrices were evolved to store some number of patterns only by means of a simple genetic algorithm. In this paper we present that the storage capacity can be enlarged by incorporating Lamarckian inheritance to the genetic algorithm.

I. Introduction

Associative memory is a process in which we can store information by distributing it among neurons. One of the most appealing features is its capability to tolerate noisy and/or partial input in recalling the information, though it has a limited capacity. We are thinking of using this as a memory organ of digital organisms of our Artificial Life research in the future. However, as a preliminary step, we are now investigating basic behavior of the function of associative memory under simple evolutionary processes.

In 1982 Hopfield [?] proposed a neural network model as an associative memory system. He used Hebbian rule [?] to make the network store a set of patterns. He estimated the storage capacity to be at most 15% of the number of neurons with computer simulations. Later the capacity was verified more analytically by Amit et al. [?] with spin-glass theory, and by Amari et al. [?] with statistical neuro-dynamical method. Since then, many researchers have been successfully trying to enlarge the capacity in various ways (see [?]). For example, Yanai et al. [?] made it by introducing sparse connectivity, Morita [?] by replacing the sigmoid function with a non-monotonic transfer function, and Willshow et al. [?], Palm [?] and Meunier et al. [?] by using sparsely coded patterns instead of random patterns. In this paper, we are exploring this by means of a genetic algorithm.

Genetic algorithms are a kind of searching techniques [?], [?]. Since the late 1980’s, genetic algorithms have been extensively used to search the optimal set of connection weights of neural networks and/or their optimal architectures (for reviews of this issue, see [?], [?] and references quoted therein). At first, they were used for determining connection weights, (see e.g., [?], [?]). However, it was pointed out that the genetic algorithms as a learning method were not so effective compared to other algorithms like Back Propagation [?]. So the interests were shifted toward the exploration of neural network architectures (see e.g., [?], [?]). However, to represent architectures effectively, more sophisticated genetic algorithms had to be considered. For example, grammatical representations of the architecture of neural networks were proposed [?], [?].

All of these researches were for layered neural networks, and there are only a few for Hopfield networks [?], [?], probably because the Hopfield network has a fixed architecture. However, sparse connectivity has a possibility to enhance the original associative memory capacity of Hopfield network [?]. Therefore, genetic algorithms are also valid for Hopfield neural networks to explore their architectures as well as to determine their connection weights.

In an earlier paper, we showed that a genetic algorithm enlarges the capacity of Hebb-rule associative memory by pruning some connections [?]. We also showed that randomly generated connection matrices can learn some patterns using a genetic algorithm without any learning rules [?].

In this paper, we redesigned the genetic algorithm so that we can test the effect of Lamarckian inheritance on the evolution. In this implementation, each individual in the population learn a set of pre-determined random patterns in its life time, and the learning result affects its chromosome. And we found that it can enlarge the storage capacity.

The overall goal for this research is twofold. One is to know if we can use the genetic algorithm as a more effective learning method than those proposed so far, and the other is to clarify the mechanism of this learning on an individual level during its life time as well as the learning on a population level of the genetic algorithm.

In the following section, we provide an outline of our experiment. Then the effects of Lamarckian inheritance on the evolution are described in Section III. Finally some conclusions are given.

II. Experiment

We applied a simple genetic algorithm to fully connected associative memory model of Hopfield. To be more specific, an auto-associative, discrete-time asynchronous-update, bipolar-state network.

The connection weights are chosen randomly either from −1 or 1 at the start of the genetic algorithm, therefore the network can not store any patterns initially. The objective of the experiment is to make this network store some number of patterns.

We set the size of the network to 49 neurons, in this paper, considering computational expense. This size of Hebb-rule associative memory would have a capacity of 7 patterns at most. In our previous simulation with the networks of the same size, we succeeded in evolving a random weight matrix eventually to store 9 patterns [?].

In this paper we incorporate Lamarckian inheritance to the genetic algorithm to see its effect on the storage capacity. (Later we will return to detailed description of this.)

In the following part of this section, we present a brief review of associative memory, and then describe the implementation of our genetic algorithm.

Associative Memory

Hopfield network which has N neurons can store some number of N-bit bipolar patterns, if all the connection weights are determined adequately. The patterns are ndimensional random vectors whose elements take the values ±1 randomly with equal probability. The μ-th pattern is denoted as

ξ^{μ} = (ξ_{1}^{μ}, ξ_{2}^{μ}, ⋯, ξ_{i}^{μ}, ⋯, ξ_{N}^{μ}),

where ξ_{i}^{μ} is the i-th bit of the μ-th pattern which takes the value of either −1 or 1. To store these patterns, each connection weight has to be adequately adjusted. If we use Hebbian rule, for example, the weight w_{ij} is determined as follows:

w_{ij} = ∑_{μ=1}^{p} ξ_{i}^{μ}ξ_{j}^{μ},

where p is the number of patterns to be stored. This process of determining w_{ij} is referred to as learning.

These w_{ij}’s define a so called energy function on an Ndimensional bipolar state space, i.e.,

E(S) = \frac{1}{2} ∑_{i,j(i≠j)} w_{ij}S_{i}S_{j},

where S moves over all possible combinations of Ndimensional vector {−1, 1}^{N} and S_{i} is the i-th component of the state S. If the number of stored patterns is small enough, this function takes a local minimum where S corresponds to one of stored patterns. In this sense the stored patterns are said to be attractors and the size of this local minimum are referred to as basin of attraction. As the number of stored patterns p increases, spurious minima become non-negligible, and finally these local minima are randomized.

The retrieval of one of stored memories is as follows. The state of each neuron is asynchronously updated by

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

where s_{i}^{μ}(t) is the state of the i-th neuron at time t when the μ-th pattern is given to the network. For each neuron, the weighted sum of its inputs is computed, and if this is greater than or equal to zero, the state of the neuron takes the value of 1, and −1 otherwise. In this paper, a neuron is chosen according to pre-assigned order (once in a cycle) at each step of updating, instead of chosen randomly.

When input is one of the stored patterns which is given small noise within the size of basin of attraction, this input pattern relaxes to the original stored pattern after several steps of the update. If we do not give any noise to the input, on the other hand, i.e., one of stored patterns is given to the network, all the states remain unchanged from the start, and the patterns are said to be memorized as fixed points. We evaluate the ability of weight matrix by the upper bound of the number of patterns stored as fixed points.

To know more about associative memory, see for example [?].

Our Genetic Algorithm

In this subsection we describe the implementation of our genetic algorithm briefly. As in Figure ??, our genetic algorithm proceeds as follows:

Fig. 1. Overview of our GA

(1) At first, 256 weight matrices(49x49), W^{ν}, are produced randomly so that each component of the matrices w_{ij}^{ν} are chosen from {−1, 1}. Hence the matrix does not store any patterns at this moment. We must note that the larger the population number, the higher the performances. In these experiments, however, we set it to 256 just because of our computer resources. (2) Each weight matrix learns a set of pre-determined random patterns ξ^{μ} by Hebbian learning rule as follows.

w_{ij} = w_{ij} + λ ∑_{μ=1}^{p} ξ_{i}^{μ}ξ_{j≠i}^{μ}.

We set the value of λ to 0.02 here. These components of Hebbian learned weight matrices are incorporated directly to their chromosomes in procedure(4) below. Hence we call this evolution as Lamarckian. (3) Fitness value f for each individual weight matrix is evaluated with the predetermined random patterns ξ^{μ}. First we calculate the average of all the inner products (overlap) of initial states and states at each time of update not more than certain time t_{0}. And then these are averaged over all sets of initial patterns, i.e.,

f = \frac{1}{p · (t_{0} − 1) · 49} ∑_{μ=1}^{p} ∑_{t=2}^{t_{0}} ∑_{j=1}^{49} ξ_{j}^{μ}s_{j}^{μ}(t).

In this paper, t_{0} is set to 98 i.e., twice the number of neurons, and we observed that was enough. Note that fitness 1.000 implies that all the initial patterns are stored as fixed points, while fitness less than 1.000 includes many possible cases. If we evaluated the fitness at one point of updating time instead, some solutions might be limit cycle. We adopted the above time-consuming fitness evaluation in order to avoid these oscillated solutions. (4) Each chromosome is simply produced from corresponding weight matrix by unfolding the components i.e., each allele of the chromosome is:

c^{ν}(i + N · j) = w_{ij}^{ν}, i, j = 0, 1, 2, ⋯, (N − 1).

Therefore the chromosome has a fixed length of 2401 (=49x49) alleles which take the value of either −1, 0, or 1. Note that we use integer variables to express alleles instead of the usual bit-expressions of chromosome. (5) Two parent chromosomes are chosen uniformly at random from the upper 40% of the population which is ranked by fitness. Then these are recombined to make one child chromosome, and an individual in the lower 60% of the population is replaced with it. This process is repeated until all the individuals in the lower subpopulation are replaced.

(6) Recombinations are made with uniform crossover. We tested several types of crossover including one- and twopoint-crossover, and observed that uniform crossover outperformed the others. Furthermore, mutation rotates the value of randomly chosen bit in chromosome c^{(n)}(i) cyclically i.e.,

(1) → (−1), (−1) → (0), (0) → (1).

We must note that zero components of weight matrices are introduced only by this mutation operation in the implementation of this paper. The mutation rate is set to 0.01 here. (7) The chromosomes are again mapped to weight matrices with reverse process of (2). (8) Unless highest fitness value reaches the value of 1.000 nor generation exceeds 12000, individuals in upper subpopulation (40%) survive to constitute the next generation with their offspring (60%), then the processes from (2) to (8) are repeated.

These operations and parameter values were determined mainly on the basis of trial and error.

III. Results and Discussions

In this section, we present the effect of Lamarckian inheritance on the evolution of fully connected associative memory model of Hopfield, comparing it to the no-learning counterpart. All simulations were carried out on networks with 49 neurons in this paper.

To see the effect of Lamarckian inheritance on the evolution, first we ran the simulation without Hebbian learning procedure (by skipping the process (2) mentioned in the preceding section). In this case, some networks eventually evolved to store up to 9 patterns as fixed points. For 10 patterns, however, we repeated 30 runs with different random number seed at the start, nevertheless we did not obtain the weight matrix which stored all these 10 patterns. In Figure ??, we show representative sample of best-so-far-fitness vs generation for 9 and 10 patterns in this experiment.

On the other hand, under the Lamarckian inheritance, the weight matrices emerge which can store a maximum of 17 patterns. An example for 17 patterns from Lamarckian evolutions is also shown in the figure. In this case, perfect solution was obtained at generation 2147, while the no-learning version for 9 patterns mentioned above converged at generation 6931. Hence, we can conclude that the Lamarckian inheritance improves the convergence speed as well as the storage capacity.

Fig. 2. Fitness vs Generation

To see the difference between these two versions, we investigated the zero density in the weight matrices and their degree of symmetry as evolution proceeds. Here we define the degree of symmetry η of the matrix w_{ij} by

η = ∑_{i=1}^{N} ∑_{j=1}^{N} w_{ij}w_{ji}/ ∑_{i=1}^{N} ∑_{j=1}^{N} w_{ij}^{2}.

The results of the best-so-far-individual (from the same run as in Figure ??) are shown in Figure ??, with the fitness

Fig. 3. Degree of symmetry and Zero density

curve for convenience. The behaviors of both ratios are totally different from each other. In the case of no-learning version (upper in the figure), both ratios increase from zero and asymptotically approach to the value of 0.2 approximately. In Lamarckian evolution (lower in the figure), on the other hand, the zero density in the weight matrices remains almost zero, and the degree of symmetry keeps the value around 0.6. Both ratios do not change throughout the evolution. Consequently, there must be other parameters which increase with fitness value, though we have not found to date.

The weight matrix of the original Hebb-rule associative memory is symmetric and includes no zero components except for diagonal elements. (Note that in the case of even number of patterns to be stored, some weight values could be zero due to Hebbian learning). And its storage capacity is 15% of the number of neurons at most. This corresponds to 7 patterns in our simulation with 49 neurons. Hence the genetic algorithm, especially Lamarckian version, might be said to work quite successfully. We conjecture that the enhancement in storage capacity is due to these differences in architecture of weight matrix.

In an earlier experiment with different implementation of genetic algorithm [?], we conjectured that both asymmetry of weight matrix and pruned connections introduced by the genetic algorithm enlarge the capacity. Around 60% asymmetry of weight matrix observed in this paper also supports this conjecture, while the weight matrix has only a few zero components here.

Furthermore, these differences in architecture in different implementations seem to suggest that there are many solutions in the entire search space. Therefore it might be interesting to search these solutions as a multi-modal function optimization, though this includes difficult issues and as yet unexplored.

IV. Conclusions

In this paper, we have described an application of a genetic algorithm to fully connected neural network model of associative memory. The objective of these experiments is to see whether Lamarckian inheritance enhances the performance of the genetic algorithm.

The simulations in this paper were made with 49 neurons. This size of Hebb-rule associative memory would store at most 7 patterns as fixed points. The no-learning version of our genetic algorithm evolved the network to store 9 patterns starting from random matrix. On the other hand, individuals’ Hebbian learning in their life time and its effect on their chromosomes, i.e., Lamarckian inheritance, result in the weight matrix which store 17 patterns eventually. In addition, Lamarckian evolution also enhances the convergence speed drastically.

The architectures of the weight matrices in these three cases above are different from each other. This suggests that there are other alternative architectures which can store the same set of patterns as fixed points in the fitness landscape.

The results and analysis reported here are only the beginning of our continuing research project, and many other tasks, such as the size of basin of attraction or multimodality mentioned above, are still waiting for exploration.

Acknowledgments

We thank Peter Davis at Advanced Telecommunication Research Institute (ATR). The ideas in this paper were originally derived from discussions with him. Thanks also go to two anonymous reviewers both for comments on a draft version of this manuscript and for encouragements on this work.

References

[1] J. J. Hopfield, “Neural Networks and Physical Systems with Emergent Collective Computational Abilities”, Proceedings of the National Academy of Sciences, USA, vol.79, pp.2554–2558, 1982

[2] D. O. Hebb, The Organization of Behavior, Wiley, 1949

[3] D. J. Amit, H. Gutfreund, and H. Sompolinsky, “Statistical Mechanics of Neural Networks near Saturation”, Annals. of Physics, vol.173, pp.30–67, 1987

[4] S. Amari, and K. Maginu, “ Statistical Neurodynamics of Associative Memory”, Neural Networks, vol.1, pp.63–73, 1987

[5] M. H. Hassoun (Ed.), Associative Neural Memories: Theory and Implementation, Oxford University Press, 1993

[6] H. Yanai, Y. Sawada, and S. Yoshizawa, “Dynamics of an Auto-Associative Neural Network Model with Arbitrary Connectivity and Noise in the Threshold”, Network, vol.2(3), pp.295–314, 1991

[7] M. Morita, “Associative Memory with Nonmonotone Dynamics”, Neural Networks, vol.6, pp.115–126, 1993

[8] D. J. Willshow, O. P. Buneman, and H. C. Longuett-Higgins, “Nonholographic Associative Memory”, Nature, vol.222, pp.960–962, 1969

[9] G. Palm, “On Associative Memory”, Biological Cybernetics, vol.36, pp.19–31, 1980

[10] C. Meunier, H. Yanai, and S. Amari, “Sparsely Coded Associative Memories: Capacity and Dynamical Properties”, Network, vol.2, pp.469–487, 1991

[11] J. Holland, Adaptation in Natural and Artificial Systems, The University of Michigan Press, 1975

[12] D. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989

[13] J. D. Schaffer, D. Whitley, and L. J. Eshelman, “Combinations of Genetic Algorithms and Neural Networks: A Survey of the State of the Art”, Proceedings of the Workshop on Combinations of Genetic Algorithms and Neural Networks, pp.1–37, 1992

[14] X. Yao, “A Review of Evolutionary Artificial Neural Networks”, International Journal of Intelligent Systems, vol.8, pp.539–567, 1993

[15] D. Montana, and L. Davis, “Training Feedforward Neural Networks using Genetic Algorithms”, Proceedings of 3rd International Conference on Genetic Algorithms, pp.762–767, 1989

[16] D. Whitley, and T. Hanson, “Optimizing Neural Network using Faster More Accurate Genetic Search”, Proceedings of 3rd International Conference on Genetic Algorithms, pp.391–396, 1989

[17] H. Kitano, “Designing Neural Networks using Genetic Algorithm with Graph Generation System”, Complex Systems, vol.4, pp.461–476, 1990

[18] G. Miller, P. Todd, and S. Hegde, “Designing Neural Networks using Genetic Algorithm”, Proceedings of 3rd International Conference on Genetic Algorithms, pp379–384, 1989 [19] S. Harp, T. Samad, and A. Guha, “Towards the Genetic Synthesis of Neural Networks”, Proceedings of 3rd International Conference on Genetic Algorithms, pp.360–369, 1989

[20] F. Gruau, and D. Whitley, “Adding Learning to the Cellular Development of Neural Networks: Evolution and Baldwin Effect”, Evolutionary Computation, vol.1(3), pp.213–233, 1993

[21] A. Imada, and K. Araki, “Genetic Algorithm Enlarges the Capacity of Associative Memory”, Proceedings of 6th International Conference on Genetic Algorithms, pp.413–420, 1995

[22] A. Imada, and K. Araki, “Mutually Connected Neural Network Can Learn Some Patterns by Means of GA”, Proceedings of the World Congress on Neural Networks, vol.1, pp.803–806, 1995

[23] A. Imada, and K. Araki, “A Simple Genetic Algorithm as a Learning Method for Associative Memory”, Nara Institute of Science and Technology Technical Report, No.95036, 1995