How Real-valued Random Synapses Evolve toward Symmetry with Diploid Chromosomes?

Akira Imada

Graduate School of Information Science Nara Institute of Science and Technology

1-11-13-604 Abeno, Hannan, Osaka, 545-0021 Japan akira-i@is.aist-nara.ac.jp

Keijiro Araki 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 genetic algorithms to the Hopfield’s neural network model of associative memory. Previously, we observed that random synaptic weights of a network evolved to create the fixed point attractors in pattern space exactly at the locations corresponding to a set of given patterns to be stored. In that simulation, a weight configuration was represented as a sequence of genes which might be called a haploid chromosome. Then, a population of these haploid chromosomes underwent evolution. In this paper, we employ diploid chromosomes, a pair of chromosomes. We have reported elsewhere two different versions of this evolution. One is the evolution of the Hebbian synapses in which some of the synapses are adaptively pruned according to information in diploid chromosomes. The other is the evolution of random synaptic weights whose values are restricted to ±1, and are encoded directly into diploid chromosomes. Here, we describe the evolution of real-valued random synaptic weights.

keywords

Hopfield model of associative memory, genetic algorithm, diploid chromosome.

1 Introduction

Associative memory is a dynamical system which has a number of stable states with a domain of attraction around them (Komló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 is retrieved from dynamically relaxed neuron states.

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 bipolar pattern, a sequence of +1 and −1, is given to the network as an initial state, the network changes its state dynamically afterwards. The dynamical behaviors are determined by the strengths of the N^{2} synapses which are referred to as weights. Here, the weight from neuron j to neuron i is denoted as w_{ij}. These w_{ij}’s construct a weight matrix. If these w_{ij}’s are prescribed appropriately, then the network can store a number of patterns as attractors, and hence works as an associative memory. The prescription of w_{ij}’s is called a learning. Hopfield employed the so called Hebbian rule^{1} for the learning, while we explore it by genetic algorithms (GA). The GA was proposed by Holland (1975) to solve combinatorial optimization problems by borrowing the idea of natural selection. In GAs, a problem is usually represented using one-dimensional array, which might be called a haploid chromosome from an analogy of biological evolution. In our problem, N^{2} synaptic weights of a network can also be represented as a string of genes of a haploid chromosome. In this way, we have already observed a random configuration of w_{ij}’s evolves to store a number of patterns as fixed point attractors (Imada et al. 1997a).

On the other hand, there is an alternative way to represent a configuration of weights using two onedimensional arrays as a pair of chromosomes, which are called diploid chromosomes in the field of GAs. The GAs using diploid chromosomes are said to be more biologically realistic than those using haploid chromosomes. At the same time, the associative memory taking advantage of dynamical behaviors of fully connected neurons might be regarded as a model of human memory. This is one of the reasons of our interest in exploiting diploid chromosomes to evolve the associative memory network, though this is too simple to be compared to our memory mechanisms. Here, w_{ij} and w_{ji}, which occupy two symmetric positions in the weight matrix, are mapped onto the same position in each pair of diploid chromosome. If two genes at the same position of a chromosome pair take a same value as an allele, the position is said to be homozygous, and heterozygous otherwise. Hillis (1991) used diploid chromosomes in his GA to optimize a sorting network. He expected an evolutionary pressure to decrease the number of heterozygous positions in the chromosome pairs, which would minimize the number of comparisons of sorting entries. He showed that the number of heterozygous sites decreases as generation proceeds. In our problem, homozygous site means that the two symmetric elements in the weight matrix, w_{ij} and w_{ji}, are identical. Our previous results show that when random synaptic weights, which are entirely asymmetric at the beginning, become somehow symmetric after evolving to be able to store some patterns (Imada et al. 1997a). Hence, we expect a more efficient evolution from an entirely asymmetric weight configuration to somehow a symmetric weight configuration by exploiting diploid chromosomes than exploiting usual haploid chromosomes.

1The rule was at first advocated by Hebb (1949) and later formalized by Cooper (1973).

Thus far, we have reported elsewhere two versions of the GA that employs diploid chromosomes. One is the evolution in which an over-loaded Hebbian network is diluted using information in diploid chromosome (Imada et al. 1997c). The other is the evolution of random synaptic weights clipped into two values, 1 and −1 which are encoded directly into the diploid chromosomes (Imada et al. 1998). In this paper, we evolve real-valued random synaptic weights in the same way as the latter scheme.

2 The Hopfield Model

The Hopfield model consists of fully connected neurons. The network with N neurons has N^{2} synapses. An instantaneous state of a neuron is determined by the sign of the weighted sum of all the other neuron’s state, i.e.,

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. Thus, neurons are updated asynchronously (one neuron at a time) in certain pre-fixed order^{2}. In general, when a bipolar pattern is given to the network as an initial state, states of neurons vary from time to time afterwards. To store p bipolar patterns ξ^{ν}:

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

as fixed point attractors, Hopfield prescribed the weight values by the Hebbian rule:

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

Then, giving one of the stored patterns to the network keeps all the states unchanged (fixed points), unless the number of patterns exceeds the capacity, and an input of the stored patterns including a few noise possibly converges to the pattern in its perfect form.

Fitness evaluation is made as follows. Since we start with a random configuration of synaptic weights, the network state diverges in early stages of the evolution. In order for the network to be improved to function as an associative memory, instantaneous state s_{i}^{ν}(t) should become similar to the input pattern ξ^{ν}. 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, our fitness function is obtained by further averaging these temporal averages of overlap over all the given patterns. That is, our fitness value f is defined as:

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

In this paper, t_{0} is set to 2N, twice the number of neurons. Note that the fitness 1 implies all the p patterns are stored as fixed points, while fitness less than 1 includes many other cases.

3 Experiment

The GA Implemented in this paper is as follows. A set of p random bipolar patterns ξ^{ν} (ν = 1, 2, ⋯, p) is generated before each run. The goal of the GA is to evolve networks to store all these patterns as fixed point attractors. In each generation, the networks are estimated fitness value using these patterns as a target. In this paper, weight values assume any real value taken from [−1, 1]. A configuration of weights of a network (phenotype) is represented by a pair of chromosomes (genotype) in which each gene takes this real weight value. At the 1st generation, weight values are assigned at random.

2One neuron is updated only once per cycle in which all the N neurons must be updated. Hopfield chose neuron to be updated in random order, while we updated them in a pre-fixed order. It was verified that the both cause essentially the same results.

Previously, we employed haploid chromosomes to solve the same problem (Imada et al. 1997a), where weights were represented as:

(c_{1}, ⋯, c_{k}, ⋯, c_{N^{2}}).

That is, w_{ij} = c_{k}, k = j + (i − 1)N.

Here, instead, we employ diploid chromosomes. Two genes of the same position in a pair of chromosomes correspond to the two symmetric sites of the weight matrix. Namely, two components in the upper right triangle and lower left triangle of the matrix. To be more specific, assume that the diploid chromosome pair is denoted as

\{ \begin{matrix}chromosome 1: (c_{1}^{1}, c_{2}^{1}, ⋯, c_{N(N−1)/2}^{1}) \\ chromosome 2: (c_{1}^{2}, c_{2}^{2}, ⋯, c_{N(N−1)/2}^{2}). \end{matrix}

Then, weights in the upper right triangle of the matrix are

w_{ij} = c_{k}^{1} for i = 1, ⋯, N − 1 and j = i + 1, ⋯, N;

and weights in the lower left triangle are

w_{ji} = c_{k}^{2} for j = 1, ⋯, N − 1 and i = j + 1, ⋯, N,

where

k = \frac{(2N − i)(i + 1)}{2} − 2N + j.

Note that we assume diagonal elements are all zero.

Two genes of a heterozygous position in the diploid chromosome remain the corresponding components of the phenotype asymmetric, while two genes of a homozygous position introduce symmetry in the weight matrix. The more homozygous positions, the more symmetric. A completely homozygous genotype will produce a symmetric phenotype.

The fitness of each network is measured in the way mentioned earlier. All the diploid chromosomes in the population are ranked according to the fitness value. In the usual genetic algorithms, the mating processes of selecting two parents to be recombined to produce offspring are iterated at this stage. Here, on the other hand, all the diploid chromosomes, before being mated, are operated uniform crossover within each pair to produce a single chromosome called gamete, such that each gene of the gamete is chosen from either of the pairs at random. Thus, each pair of diploid chromosomes produces a single gamete. The length of the gamete is same as the chromosome (= N(N − 1)/2). It is these gametes that are recombined in this implementation.

Two diploid chromosomes are chosen randomly from the best T % of the population, prohibiting self-mating. Two gametes from these two parent diploid chromosomes are combined. This forms a new child diploid chromosome. This particular mating process is repeated until the worst (100 − T)% of the population are replaced with these new children. The offspring is mutated with the probability p_{m} by replacing a gene with another random real number taken from [−1, 1].

The cycle of reconstructing the new population with better individuals and restarting the search is repeated until a perfect solution is found or a maximum number of generation has been reached.

All the simulations are carried out on networks with 49 (=N) neurons. Hence, the length of a chromosome is 1176. The parameters we used in the GA are as follows. The population number is 256. This is just because of our limited computer resources. The mutation rate p_{m} is set to 0.01. In selecting two parents, T is chosen to be 40%. Searching procedure is iterated until 12000 generations unless perfect solution is found. These values were determined mainly on the basis of trial and error.

4 Results and Discussion

Since we started the GA with a population of networks with weights chosen randomly from [1, −1], any patterns given to these networks at early stages of evolution, will result in chaotic behavior of neurons’ states. This is due to the asymmetry of their weight matrices. The behaviors are visualized, for example, by observing trajectories of the Hamming distance between the initial state given to the network and the instantaneous states afterwards. In Figure ??, we show an example of a sequence of snapshots of the trajectories^{3}. The Hamming distances are plotted against updating time steps. The goal of the GA is to find a solution which makes all trajectories for the given input patterns coincide with the x-axis (fixed point attractors).

Now, let’s look at the evolutions using diploid chromosomes. The effect on evolution of varying p, the number of given patterns, is studied. We repeat each simulation 30 times with different random number seed for the fixed p. If we find the perfect solution(s) then Figure 1: An example of trajectories of the Hamming distance of instantaneous state from the initial input state (seven snapshots during an evolution). we increment p.

3This is an example taken from our previous experiment with a GA using haploid chromosomes (Imada 1997b).

It was found that a network that stores two patterns as fixed points emerges. In Figure ??, we show the representative sample of the best fitness versus generation of the evolution. A maximum storage obtained here were unfortunately very small.

The degree of symmetry of the weight matrices varies as generation proceeds. We investigated the time expansion of the ratio of the best fit weights in each generation. The degree of symmetry is defined by

σ = ∑_{i=1}^{N} ∑_{j=1}^{N} w_{ij}w_{ji} · (∑_{i=1}^{N} ∑_{j=1}^{N} w_{ij}^{2})^{−1} ,

following after Krauth et al. (1988). The results are shown in Figure ??. Here, the data were taken from the evolution presented in the Figure ??.

Figure 2: The best fitness versus generation.

To see how the affect of diploid chromosomes to the evolution is different from the one using haploid chromosomes, the best fitness versus generation and degree of symmetry under haploid chromosomes are plotted in Figure ??. The experiments were made with the same condition as in Figure ?? and ?? above. As Hertz (1987) suggested, asymmetry of the synaptic weights is relevant to the number of spurious attractors, and therefore, the function of associative memory. We can

Figure 3: Degree of symmetry during evolution.

observe significant difference in the degree of symmetry. The degree of symmetry when the fitness reaches 1 is around 0.6 with diploid chromosome, while the one with haploid chromosome is 0.3. We conclude that the difference is due to the pressure to homozygosity of diploid chromosomes. This is in contrast to our previous experiment that evolved symmetric Hebbian weights, where we were not able to observe such difference.

To say a network an associative memory system, the tolerance for certain amount of noises should be shown. Namely, each memorized pattern must have a certain domain of basin of attraction. We studied elsewhere the basin size of attractors created by our genetic algorithm (Imada et al. 1996), and found that the basin of attraction of the created memory by evolutionary process is generally small. Probably, this is because of the remaining spurious attractors around the created memories. Here, using diploid chromosomes, we were not able to enlarge the size of basins of attraction of the stored patterns either.

5 Conclusion

We have described how diploid chromosomes affects the evolution of fully connected neural networks which are to be used as an associative memory. Experiments were carried out on networks with 49 neurons, and Figure 4: Fitness and degree of symmetry versus generation with haploid chromosomes.

evolved here were real-valued random weights. The GA using diploid chromosomes succeeded in emerging a network that can store a maximum of two random bipolar patterns as fixed points. If we employ the Hebbian algorithm to prescribe weights of a network with the same size, the network will store around eight patterns. So, it might be argued that since the capacity obtained are too small to say the experiment is worthwhile to test. However, it is important to note that the Hebbian weight matrices are totally symmetric. Here, we have started with totally asymmetric weights on the contrary (≈ 0% symmetry), and observed that they evolved to be considerably symmetric (≈ 60%). The degree of symmetry was much higher than the one when we employed haploid chromosomes (≈ 30%).

This phenomenon was also observed in our previous experiment of evolving weights of random clipped value (±1). In addition, the storage capacity obtained in that experiment were a maximum of five patterns. The GA was also applied to the Hebbian weights that had learned patterns exceeding the capacity where we found that the weights evolved to perform better by reducing the degree of symmetry. In that case, however, we did not observe the difference between diploid and haploid chromosomes.

The Hopfield associative memory has an upper bound in capacity to store patterns. A network stores a maximum of only 2N patterns, as Gardner (1988) discussed. However, it is not so difficult to extend the model to the one with a higher (λ-th) order synapses, where storage capacity scales N^{λ} (Baldi and Venkatesh, 1987). We think we can employ multi-ploidy chromosomes also to represent the network with this higher order synapses.

Acknowledgments

We thank Peter Davis at Advanced Telecommunication Research Institute (ATR) for providing us great insight into the dynamics of the Hopfield neural networks, in the early stage of this research.

References

Baldi, P., and S. S. Venkatesh (1987) Number of Stable Points for Spin-Glasses and Neural Networks of Higher Orders. Physical Review Letters, 58(9), pp913–915.

Cooper, L. N. (1973) A Possible Organization of Animal Memory and Learning. Proceedings of the 24th Nobel Symposium on Collective Properties of Physical Systems, pp252–264.

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. Hertz, J. A., G. Grinstein, and S. A. Solla (1987). Irre-

versible Spin Glasses an Neural Networks. in L. N. van Hemmen and I. Morgenstern eds. Heidelberg Colloquium on Glassy Dynamics. Lecture Notes in Physics, No.275, Springer-Verlag, pp538–546.

Hillis, W. D. (1991) Co-Evolving Parasites Improve Simulated Evolution as an Optimization Procedure. C. G. Langton, C. Taylar, J. D. Farmer, and S. Rasmussen eds. Artificial Life II. SFI Studies in the Science of Complexity, vol. X, Addison-Wesley, pp295–312.

Holland, J. (1975) Adaptation in Natural and Artificial

Systems. The University of Michigan Press. Hopfield, J. J. (1982) Neural Networks and Physical Sys-

tems with Emergent Collective Computational Abilities. Proceedings of the National Academy of Sciences, USA, 79, pp2554–2558.

Imada, A., and K. Araki (1996) Basin of Attraction of Associative Memory as it Evolves from Random Weights. Proceedings of the 1st Asia-Pacific Conference on Simulated Evolution and Learning, pp271–278.

Imada, A., and K. Araki (1997a) Evolved Asymmetry and Dilution of Random Synaptic Weights in Hopfield Network Turn a Spin-glass Phase into Associative Memory. The 2nd International Conference on Computational Intelligence and Neuroscience, Proceedings of Joint Conference of Computer Science, vol. 2, pp223– Imada, A., and K. Araki (1997b) Evolution of Random Synaptic Weights of the Hopfield Associative Memory : How Chaotic Trajectories Turn into Fixed Point Attractors? Proceedings of the 4th International Conference on Neural Information Processing and Intelligent Information Systems, vol. 1, Springer Verlag, pp452– 455.

Imada, A., and K. Araki (1997c) Evolution of Associative Memory using Diploid Chromosomes. The 10th Australian Joint Conference on Artificial Intelligence. Proceedings of the Workshop on Evolutionary Computation, pp24–36.

Imada, A., and K. Araki (1998) Does Diploidy Affect Evolutions of Hopfield Associative Memory? The 7th Turkish Symposium on Artificial Intelligence and Neural Networks (to appear).

Komlós, J., and R. Paturi (1988) Convergence Results in an Associative Memory Model. Neural Networks 1, pp239–250.

Krauth, W., J.-P. Nadal, and M.Mezard (1988) The Roles of Stability and Symmetry in the Dynamics of Neural Networks. Journal of Physics A: Math. Gen. 21, pp2995–3011.