Information Processing Using a Model of Associative Memory
Proceedings of the Second International Joint Conference on Artificial Intelligence. Pages 101-109.
© 1971 International Joint Conferences on Artificial Intelligence
Abstract
Association mechanisms are consid ered to play important roles in thinking in the human brain. Such mechanisms should be analysed and utilized in machine intelligence in order to further work in the field. This paper describes a model of a neural network named 'Associatron', and considers its applications for information processing. The Associatron sto re s a lot of entities in the same region of i ts structure, and recalls the whole of any entity from a part of it without any sequential search. From its structu re, some properties are derived that are expected to be useful for humanlike information processing. Analysis of these properties is b riefly described. An As~oci atr on with 180 neurons has been simulated by a compute r and has been applied to simple examples of concept formation and game playing. Hardware realization of an Associatron with 25 neurons made f o r trial purposes, is outlined, too.
- E. R. Caianiello, ~outline of a Theo- ry of Thought Processes and Thinkin~ Machines,~ Journal of Theoretical Biology, vol. 1, n o . 2, pp. 2 0 ~-235, April 19 61.
- F. Rosenblatt, ~The Perceptron--A Probabilistic Model for Information Storage and Organization in the Brain,~ Psychol. Rev., vol. 65, pp. 386-407, 1958.
- B. Widraw, ~Generalization and Infor- mation Storage in Networks of Adaline 'Neurons•,~ Self-organizing Systems, pp. 435-461, Spartan Books, Washing- ton, D. C., 1962.
- P. B. Post, "A Lifelike Model for Association Relevance,~ Proc. Int. Joint Computer Conf. on Artificial Intelligence, pp. 271-280, May 1969.
- K. Nakano and J. Nagumo, "Studies on Associative Memory Using a Model of Neural Network,~ Conf. on Medical Electronics of Institute of' Ele.c.tr.on- Session No. 4 Associative and Adaptive Models ics and Communication Engineers of Japan, JunP 1Q70.
- K. Nakano, "Learning Process in a Model of Associative Memory,~ Japan, U. S. Seminar on Learning Process in Control systems, August 18-20, 1970, Nagoya, Japan.
- A. Samuel, ~some Studies in Machine Learning Using the Game of Checkers,~ IBM J. Res. Develop, vol. 3, no. 3, pp. 210-229, July 1950.
- A. Samuel, "Some Studies in Machine Learning Using the Game of Checkers II--Recent Progress,"IBM J. Res. De- velop, vol.ll, no. 6, p. 601, Kovem- ber 1967.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
Introduction
The purpose of this paper is to out line an approach t o simulating certain functions of a human brain from the view point of association. The first aspect of this work is to design an associative memory device that is considered to be reasonable as a mode~ for association mechanisms . The second is to distinguish tte characteristics of informatlon pro cessing using the device, from that of conventional information processing.
Association in the human brain has been studied mainly in the field of psy chology , and some semantic models for association have been presented in the last few years . On the other hand, bio logical s tudies are beginning gradually to reveal the structure of the nervous system .. But Knowlege about it is still not enough to construct the structure arti ficially, although models of nerve cells have been presentedl,
In this situation, it will be impor tant to try to construct a machine with homogeneous structure, where the micro scopic behavior of i ts components combines to form the macroscopic behavior, such as' pattern recognition, concept formation, game playing and so on. Perceptron2, device extract automatically, from anum ber of entities, the essence useful for a certain job.
(3) Since information is accessed associatively without sequential search, the speed of access or information re trieval is very high.
These properties differentiate infor mation processing using the associative memory from that of conventional com puters.
Recently, the thinking process has been studied in detail using so-called heuristic programs. For example, the learning pBogram for the game of checkers7, is well known. The model in this paper is related to such heuristics in game playing, general problem solving and possibly to the thinking process it self.
A Model of Associative Memory
A model of associative memory real ized in the following way is named an 'Associatron':
Presume that an entity is represented by a row vector
where xi = -1, 0, 1. An entity is com posed of several patterns and of neutral areas. Each pattern is composed of -l's, O's and l's, while the neutral area is composed only of O's. Each pattern has a simple or complex meaning, and the en tity represents the association of these patterns.
Now the memorizing process is con sidered. Let xt denote the transposed vector of x. The inner state of the memory, after k entities x(1l, x'Z), ~!)have been stored, is defined as an n x n matrix
To recall entities, first we define the quantizing function,
Suppose that it also can be applied to a vector u = (uj) and a matrix A = (ai.j), as
From an input y = (y 1 , y:J., ··· , Y~~.l, the same kind of vector as x, the memory device can recall a row vector z as the output, where
If y is composed of a neutral area and a few patterns which are also the com ponents of a stored entity x, then it is possible that y is nearly equal to x, even when a lot of entities are memorized. This would enable recalling the whole of a stored entity from a part of it. Con sequently, a few patterns previously pro cessed can be associated with the rest of the patterns of entity x.
Figure 1 depicts the behavior of the Associatron as a neural net"ork. Any pair of neurons X<. and Xj is connected through a memory unit m·L· which corre sponds to the synapse. ~his model dif fers from general neural networks in the following points,
- {1) All neurons are mutually con nected.
- Each neuron has three possible states.
- For any pair of neurons, the values of synaptic conductance are as sumed to be equal for. both directions. The value of the memory unit m" · is multi valued and is modified during ~ memoriz ing process by adding the product XL· Xj to the previous value. However, in propa gation of a stimulus, the quantized value is used.
- Refractory time is not con sidered.
From these items, it can be said that the Associatron is at best a considerably simplified model of a neural network. This simplification might cause a situ ation where separation of patterns is not very good, revers~d patterns cannot be separated and the direction of recall is out of control. The first problem will be solved by increasing neurons, and the other problems by modifying the model. But the modification is not always neces sary, because the results turn out pre dictably when the model is applied appro priately.
Properties of the Model of Associative Memory
In this section, properties of memo rizing and recalling entities are dis cussed. It was previously mentioned that an entity is composed of patterns, each of which has a meaning. Here we consider it in a little more detail. Figure 2 illustrates the relation of an entity and its component patterns; that is Fig. 2 (a) shows the array of compo nents of vector x and {b) shows an ex ample of entities. The entity is com posed of patterns 1, 2, 3 and a neutral area, where, pattern 1 has the meaning of 'red', pattern 2 the meaning 'spherical', etc .. Now it is reasonable to consider that a pattern or a few patterns establish a concept. In the present ex ample, pattern 1 has the concept of 'red', pattern 2 the concept of 'spherical', the set of patterns 1 and 2 has the complex concept of 'red and spherical', the set of patterns 1, 2 and 3 has the concept of 'apple' and so on. In the Associatron, when entities or associations of patterns are stored, not only can patterns be re called , but also various concepts are gradually formed.
The following discussion considers the properties of memorizing and recall ing.
Presume that Q denotes the set of all n-dimentional vectors
where x ~ = -1, 0, 1. Now, we consider the recalling function
If X E Q, and ~ is defined as
then z is also a member of Q. Now let us introduce the index vector
where v~ is equal to 0 or 1. This vector represents a certain area of the neural network. Defining elementwise multipli cation * as
we call v * x the concept of x at the area v. Presume that both x and y are members of Q. If
then x and y are said to have the same concept at area v . The measure of area v is defined by

Now it is presumed that the entity x or the association of patterns A and B is stored in the memory device, as in Fig. 3 (a), whose representati on is the same as Fig. 2. If the order of the elements of x is changed to put together the elements constructing the same pattern, the entity x is represented by a row vector as
where A and B are row vectors, and 0 de notes zero- vector. Then the matrix M which stores only x will be If the index vectors of A and B are v~ and v 8 , respectively, the concept at area · v& of the recalled pattern from v,. * x is This means that the pattern of concept B is completely recalled from A.


Where associations A-B and C-D are stored independently, as shown in Fig. 3 (b), in the same way it can be seen that a pattern of each pair is completely re called from another.
In the case of Fig. 3 (c), two asso ciations, A-B and C-B', are stored in such a way that pattern B and B' are over lapped. Stored vectors are
The matrix is

The re cal ling process is as follows,


In the case of Fig. 3 (d), where two associations, A-B and C-D , are stored, A and C, Band D partially overlap , respec tively. This is rewitten as Fig. 3 (e), where the overlapping areas are delt with as new patterns. From the previous re- sult, it is clear that E and F are indif ferent to the recal ling AB ~CD , where AB means the complex concept of A and B et~. so they are eliminated. Therefore, stored vectors can be considered as
The recalling process from AB to CD i s as follows,

Thus, CD can be completely recalled from AB, because only two patterr.s are over lapped at vi . When this number is arbi trary, the following argument will hold.
Let k pairs of Aj -Bj be stored as shown in Fig. 3 (f). For simplicity of calculation, k is presumed to be an odd number. Besides, it is presumed that t<vA) ~ s is odd and that the entities are random patterns at areas v~ and vB. These assumptions do not necessarily hold in actual use of the associative memory. But it matters little, because this only causes a small error in estimation of accuracy of recalling. In any recalling process, the probability that a memory unit votes for the right state of a neu ron for the specific entity stored in the memory device is
The probability that the state of a neu ron decided by majority is right , is re presented by the sum of the first (stl)/2 terms of the binomial expansion o f


where J C ~ is the number of combination. As this summation cannot be written as a simple form, to determi ne the behavior of this equation, the graphical expression is taken by calculating the values of P for various values of k and s. This is shown in Fig. ~. From the graph, it is found that completely accurate recalling can be done when the number of stored en tities is very small or when the number of elements constructing the input pat tern is very large. But it is important that the capability of an associative memory is not judged only by the accuracy of memory. Characteristics of information processing using an associative memory are shown in the following sections.
Computer Simulation and Some Experimental Results
An Associatron composed of 180 neu rons has been simulated by a digital com puter. Using this simulated model, sev eral experiments were performed. To evaluate the results, the correlation co efficient between a stored pattern and the recalled pattern is used. Presume that both patterns A and B consist of n elements, and that corresponding elements of patterns are a" and b~, respectively. The correlation coefficient is defined as r = 1 means that A and B are the same. When r equals zero, they are indifferent, and when r equals -1, one is the reversed pattern of the other. Although input patterns for recalling should also be memorized, for convenience of evaluati on of the behavior of the memory, they are not memorized in these experiments.

Example 1 Three areas A, E and C, each of which consists of ~0 neurons are taken on the neural plane. Each of the names of 6 things, 3 colors and 3 shapes is coded into a ~0 bit pattern of l's and -l's. A thing, its color and its shape are stored at areas A, B and C, respec tively. After 6 triplets are stored, the memory device is made to recall the color and the shape from a thing, and vice ver sa. The results are shown in Fig. 5. The device recalls the color and the shape completely from the thing, but the accuracy of reverse recalling is about 92 %.
Example 2 An experiment concerning simple concept formation was accomplished. In this case, for example, red things a nd the word 'red' such as Apple-red-sPheri cal-word 'red', brick-red-boxlike-word 'red' are shown one by one t o the memory device. At first, the memory device might take the word 'red' for 'spherical', but as it is trained, it forms the con cept 'red' as shown in Fig. 6, where sym bols are used instead of things, shapes colors etc .. Thus, the pattern of 'red' is associated with the pattern of the word 'red ', and the memory device recalls one from another. Besides, if entities apple-red and apple-spherical are stored at other times, the device recall s 'red' and 'spherical' from 'apple' and vice ver sa. That is, although the triplet apple red-spherical is not a stored entity, it is formed in the memory device.
Example 3 When the associative memory device is applied to games, a set of pat terns effective for winning the game is expected to be extracted aut omatically. The f o llowing game is used for a demon stration o f t he learning process in the associative memory. There are n chips on the board initially. Two players take any number of one to three chips alter nately. The player who is forced to take the last chip loses the game. The re striction is that a player must not take the number which his opponent took at his previous move. For simplicity, presume that there are onl y six chips on the ini tial board. To play the game using the Associatron, firs t the components of vec tor x are assigned as shown in Fig. 7 t o four patterns of the board position, the move, the mutual effect of the board position and the move, and the image of the result. Learning is performed in such a way that, all sets of patterns of board position, strategy, mutual effect and the result, which have appeared in the game, are memorized one by one. The player with the associative memory (Player A), at every move, recalls the image of the result from the board position, a possible strategy and the mutual effect. The strategy, from which the image of 'win' is recalled, is taken. If the images are the same through possible strategies, one strategy is chosen at ran dom. In this simple way, Player A is ex pected to make progress in developing his skill in the game, utilizing the property of the associative memory. In this ex periment, it is assumed that the opponent (Player R) chooses one of possible strate gies at random. In training after each game, for the opponent's move, the image of the result is reversed from 'win' to 'lose' and vice versa, and is used. Therefore, Player A makes progress using his opponent's strategies, too. Eighteen games have been played. As the result, the winners are R, A, A, A, A, A, A, A, A, R, A, A, A, R, R, A, R, A. Examination of the game tree yields the best player's strategy at every board position. Strate gies of Player A are examined after a certain number of games, as shown below. At every possible board position, a check is made 2s to which image of 'win' or 'lose' Player A recalls from the set of board position, possi b le strategy at the board and their mutual effect. The re sult of the examination is shown in Fig. B. The winning rate of Player A to Player R is shown, too. Figure 9 shows it graphically . From the graph, it is found that the assoc iative memory can learn how to play the game well.
Hardware Realization
The hardware can be constructed as an iterative circuit as shown in Fig. 10 ( a ) . Since the matrix in Eq. (2) is sym metrical, only half of the n X n memory units are required. The memory unit is represented by a simple automaton operat ing synchronously. Presume that the notation is assigned as in Fig. 10 (b). The automaton is described as
s ( t + 1) Y 1 ( t + 1) y2 ( t + 1) YJ ( t + 1) Y,._ ( t + 1 ) S ( t ) + X 1 ( t ) Xz ( t) ; < s < t ) l X2 < t l + x.~ ( t) ~ (S( t )) X, ( t) + X'~~-(t) (24) x, (t) XJ ( t ) ,
where S s orresponds to the value o f the memo ry unit and t is time. For the value of the unit , few levels are enough to operate the device specifically.
In this way, a memory device with 25 neurons, that is, 325 memory units, has been constructed for trial. Figure 11 shows the appearance of the device. The levels of the memory unit previously men tioned are taken to be seven. Each memo ry unit is composed of 20 integrated cir cuit elements. A block diagram of this device is shown in Fig. 12. For conve nience, input and output parts are clear ly separated in this device, and if the 'Memory Hold' is used, the device will recall entities without changing its in ner state. Any entity can be set in the input register with the input switches. The output can be transferred to the in put register manually or automatically. If some of the selecting switches are turned on, corresponding states of the input register are obtained from the in put switches instead of the output register. Thus, the recalled pattern can be immediately modified and be used as the next input. Although this device is very small in number of neurons, it is effec tive for some experiments concerning se quential recalling. The importance of this kind of experiment is shown in the next section.
Thinking by the Sequence of Associations
If the recalling process is repeated in the method where recalled pattern is used as the next input, a chain of asso ciations may be traced. The process is considered as one o f the thinking pro cesses, rather than one of reca l ling t he stored entities, because the structure of the associations was not directly memo rized but has been formed in the memory through experience from a set of associ ations.
Though the real thinking process may be far more complicated, here we consider the simplest loop A.-.B .... C~A by setting
where l <vA) =).(v 9 ) =t)ve ) = 60. After a number of such loops have been st ored, an initial input of u = (A', 0, 0) is used to recall patterns sequentially, where A' is an arbitrary pattern. In case the stored loop number is less than six, the loops can be separated complete ly. That coincides with the result o f theoretical evaluation. When the number of loops is larger, various kinds of con fusion take place. The behavior of the associative memory in sequential recall ing is being studied, but no particularly interesting results have been obtained yet.
Conclusions
Information processing based on as ssociative memory was studied. The model, named an Associatron, memorizes entities distributively and recalls them associ atively. Consequently, it has different properties from conventional memory de vices. Those properties were analyzed and found useful for realizing machine intelligence. The ability of an Associ atron increases as the number of neurons increases. A few examples, using the model as simulated by a digital computer, show that concept formation and game play ing with learning are possiQle. In the Example of game playing, it is found that the application of the method is not re stricted t o a special game, because it fully utilizes the properties of associ ative memory and the method itself is very primitive and simple . Hardware of the Associatron with 25 neurons, made for trial purposes, uses integrated circuit elements. Although consideration is lim ited to 'static' properties, or the pro perties of singl e recalling, it is sug gested that 'dyna~ic' behavior, or the sequence of ass oc iations, is more impor tant.
Acknowledgement
This work was supported by a grant from the Science and Technology Agency of Japan .
@inproceedings{ijcai1971p11,
title = {Information Processing Using a Model of Associative Memory},
author = {Nakano, Kaoru and Nagumo, Jin-ichi},
booktitle = {Proceedings of the Second International Joint Conference on
Artificial Intelligence, {IJCAI-71}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {D.C. Cooper},
pages = {101--109},
year = {1971},
url = {https://ijcai.org/proceedings/1971/11},
}
TY - CPAPER TI - Information Processing Using a Model of Associative Memory AU - Nakano, Kaoru AU - Nagumo, Jin-ichi T2 - Proceedings of the Second International Joint Conference on Artificial Intelligence, IJCAI-71 PB - International Joint Conferences on Artificial Intelligence PY - 1971 SP - 101 EP - 109 UR - https://ijcai.org/proceedings/1971/11 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: