A Conceptual Associative Memory with Full Memory Capacity and Ability to Associate Arbitrary Patterns

Cheng-juei Wu

Department of Computer Science

New Mexico Tech.

Socorro, NM 87801

wu@titan.nmt.edu

Abstract

In this paper, a conceptual associative memory (CAM), which uses the conceptual layer(s) to associate input/output layers, is proposed to achieve the most important requirement for neural networks as memory devices, that is, the ability to store arbitrary patterns in networks and retrieve them correctly. The CAM has many advantages, such as the able to associate arbitrary patterns like the BP networks (Back Propagation networks), full memory capacity like the ART1 (Adaptive Resonance Theory 1) networks, fast construction of weights, easy update of the memory system, and capable of handling both spatial and temporal patterns. These features make the CAM very attractive as the building block of memory systems. Therefore, it is possible to build databases or expert systems based on CAM.

I. INTRODUCTION

Without memories, man is the creature of instant. All of our learning involves memories; therefore, the memory system plays a crucial role in an integrated artificial neural network. To evaluate various models, the following criteria for memory systems are adopted in this work.

1. Guaranteed recall of all trained patterns

2. High memory capacity

3. No spurious memories.

4. Easy to update the content of system, that is, the incremental ability

5. Short training time and fast retrieval

6. The ability to correct the input noise

7. Capable of handling both spatial and temporal patterns

For example, the analysis of bidirectional associative memory (BAM) [1], [2] shows that BAM can meet criteria 5-7; however, BAM usually has the disadvantages of no guaranteed recall of trained patterns and incremental ability, lots of spurious memories, and memory capacity of for non-homogeneous BAM [3].

Many models had been proposed since Kosko's BAM model, especially on retrieval correctness and memory capacity improvement [4-10]; however, none of above could achieve the goals of full memory capacity and association of two arbitrary patterns. In [11], a multilayer perception (MLP) like neural network was proposed to improve the capacity of Hopfield nets. Despite its significant improvement in capacity, some input patterns will be ruled out under this model; hence, there is no guarantee that you can store any patterns you want in the network. The other disadvantages are unidirectional association and lacking the ability to handle temporal patterns. The MBDS [12] can achieve guaranteed recall of trained patterns by adding two more layers and four more weights; however, it is only suitable for batch learning and lacks incremental ability since previous stored patterns need to be rechecked whenever a new pair of inputs is added into the system. The ARTMAP [13], which consists of two independent ART1 units and an unbalanced map field, can meet most of the criteria except bidirectional associations and temporal patterns. In [14], ARAM, an symmetrical ARTMAP like network, was proposed to handle the bidirectional association. However, the lack of temporal association ability remains.

In this work, a neural network conceptual associative memory (CAM), which is based on BAM and MAM [15], is proposed to achieve all the criteria mentioned above and be an possible ideal building block for future memory systems. In the following, section II introduces the architecture and learning algorithm of CAM which can handle spatial multi-directional associations. The temporal associative model, CTAM, is introduced in section III. At last, the features of CAM and conclusions are given in section IV and V, respectively.

II. CONCEPTUAL ASSOCIATIVE MEMORY (CAM)

The CAM , based on BAM and MAM, is a spatial multi-directional associative memory network with a conceptual layer in the middle of surrounding input/output layers to help the system escape from the restriction of real objects, such as shape and sound, in the physical world. A CAM consisting of 3 input/output layers is shown in Fig. 1.

A. The Encoding Algorithm of CAM (Unipolar Version)

We assume that there are no identical input vectors, that is, any two input vectors have at least one different component. In practice, the repeated vectors can be found by running the retrieval algorithm first. To encode P K-tuple of distinctive inputs , the CAM copies each tuple directly to the weights connected to an uncommitted node j in the conceptual layer as follows:

(1)

where is the number of nodes in the layer . Suppose we have 4 3-tuple of inputs as follows:

=(1, 0, 0, 1, 1), =(1, 1 , 0, 0), =(1, 0, 0),

=(0, 1, 1, 1, 1), =(1, 1 , 1, 0), =(1, 0, 1),

=(1, 1, 0, 1, 1), =(1, 0, 1, 0), =(1, 1, 1),

=(0, 0, 1, 1, 1), =(0, 0, 1, 1), =(1, 1, 0),

After encoding, the weight matrices are as follows:

where each column represents an input pattern. Clearly, the network can store up to pairs of patterns.

B. The Retrieval Algorithm of CAM (Unipolar Version)

For a K-tuple input , any component of the input can be used to retrieve the stored tuple.

Step 1. Present the unipolar input vector to and set up the thresholds as follows:

(2)

where is the threshold for the nodes in the rest of layers .

Step 2. Decide the output of each node in the conceptual layer as follows:

(3)

(4)

Step 3. For each node m in layer where , the output value is decided as follows:

(5)

(6)

where P and are the number of committed nodes and output value of node j in the conceptual layer respectively, is the weight matrix between the conceptual layer and , and is the output vector associated with .

Step 4. Read the next input. If no input, the operation terminates; otherwise, go back to Step 1.

III. CONCEPTUAL TEMPORAL ASSOCIATIVE MEMORY (CTAM)

The same assumption for CAM is applied to CTAM as well., whereas the retrieval algorithms of CAM needs to be slightly modified to handle the temporal patterns since the retrieval order of input component vectors must be adhered in CTAM. For a K-tuple CTAM, the network consists of K input layers and K-1 conceptual layers. A 3-tuple CTAM is shown in Fig. 2.

A. The Retrieval Algorithm of CTAM (Unipolar Version)

Assume P K-tuple of distinctive inputs have been stored in the networks, and then for a K-tuple input , any component can be used to retrieve the stored tuple as follows:

1. Present the unipolar input vector to and set up the thresholds as follows:

(7)

where is the threshold for the nodes in all input/output layers .

2. Whenever the retrieval process is from an input/output layer to its adjacent conceptual layer, that is, , the output of each node in is decided as follows:

(8)

(9)

where is the number of nodes in the .

3. Whenever the retrieval process is from the conceptual layer to its adjacent input/output layer, that is, , the output value of each node m in layer is decided as follows:

(10)

(11)

where P and are the number of committed nodes and output value of node j in respectively, is the weight matrix between the layer and , and is the output vector associated with .

VI. THE FEATURES OF CAM AND CTAM

The CAM has the following features:

1. It has the full memory capacity which is restricted by the number of nodes in the conceptual layer like ART networks.

2. It has the ability to associate arbitrary patterns. For a K-tuple pattern , all the components are associated with a node, say j, in the conceptual layer; therefore, the retrievals of pattern is certain through the node j in the conceptual layer.

3. It is easy to update the content of memory. Since the operations only involve the weights connected with a specific node in the conceptual layer at a time, each conceptual node with its connected weights can be treated as an independent unit. Thus, a new pair of patterns can be encoded any time we want, and an existed pair of patterns can be removed from the memory by simply resetting all the corresponding weights to their initial values.

4. The weight matrices can be constructed very fast. Since we copy the input patterns directly to the network, the time complexity is O(n) for encoding n pairs of inputs.

5. There are no spurious memories in the CAM. In contrast to the correlation matrices and energy functions used in the BAM, there are no local minima (or spurious memories) existed in this methodology since the CAM always responds with one of the stored patterns in the system.

6. It is capable of handling both spatial and temporal patterns.

7. The generalization (or noise elimination) can be achieved by using the threshold to pick up the most similar stored patterns in terms of Hamming distance.

V. CONCLUSIONS AND DISCUSSIONS

In this work, the conceptual associative memory (CAM) in which a conceptual layer is added in the middle of surrounding input/output layers has been studied. The CAM has the advantage of guaranteed association of arbitrary patterns. In addition, for a CAM with K input/output layers, the number of pairs that can be stored in the network is up to where is the dimension of layer i.

The other advantages of CAM ( and CTAM) are easy to update the memory content, capable of handling both spatial and temporal patterns, no spurious memories, and fast weight construction. These features make the CAM very attractive as the building block of memory system. The neural-based database or expert systems based on CAM or CTAM are the directions of ongoing researches.

ACKNOWLEDGMENT

The author would like to thank A.H. Sung for his valuable suggestions.

REFERENCES

[1] B. Kosko, "Adaptive Bidirectional Associative Memories," Applied Optics, vol. 26, no. 23, pp. 4947-4960, Dec. 1987.

[2] B. Kosko, "Bidirectional Associative Memories," IEEE Trans. on System, Man, and Cybern., vol. 18, no. 1, pp. 49-60, Jan./Feb. 1988.

[3] H. Karen and R. Hecht-Nielsen, "A BAM with Increased Information Storage Capacity," in Proceedings of IEEE/INNS International Joint Conference on Neural Networks, 1988, pp. 181-190.

[4] Y. F. Wang, J. B. Cruz, and J. H. Mulligan, "Two Coding Strategies for Bidirectional Associative Memory," IEEE Trans. on Neural Networks, vol. 1, no. 1, pp. 81-91, March 1990.

[5] Y. F. Wang, J. B. Cruz, and J. H. Mulligan, "Guaranteed Recall of All Training Pairs for Bidirectional Associative Memory," IEEE Trans. on Neural Networks, vol. 2, no. 6, pp. 559-567, Nov. 1991.

[6] P. K. Simpson, "Higher-Ordered and Intraconnected Bidirectional Associative Memories," IEEE Trans. on Systems, Man, Cybernetics, vol. 20, no. 3, pp. 637-653, 1990.

[7] B. L. Zhang, B. Z. Xu, and C. P. Kwong, "Stability and Attractivity Analysis of Bidirectional Associative Memory from the Matched-Filtering Viewpoint," in Proc. IEEE/INNS International Joint Conference on Neural Networks, 1991, pp. 2277-2281.

[8] J. Sun, and T. Nagata, "Associative Memory on the Basis of High Correlation," in Proc. IEEE/INNS International Joint Conference on Neural Networks, vol. 1, 1992, pp. 482-486.

[9] C. C. Wang, and H. S. Don, "High-Capacity Discrete Exponential BAM," in Proc. IEEE/INNS International Joint Conference on Neural Networks, vol. 2, 1992, pp. 178-183.

[10] H. Oh, and S. C. Kothari, "A Pseudo-Relaxation Learning Algorithm for Bidirectional Associative Memory," in Proc. IEEE/INNS International Joint Conference on Neural Networks, vol. 2, 1992, pp. 208-213.

[11] J. Hao, and J. Vandewalle, "A New Model of Neural Associative Memories," in Proc. IEEE/INNS International Joint Conference on Neural Networks, vol. 2, 1992, pp. 116-171.

[12] W.-J. Wang and D.-L. Lee, "A Modified Bidirectional Decoding Strategy Based on the BAM Structure," IEEE Trans. on Neural Networks, vol. 4, no. 4, pp. 710-717, Jul. 1993.

[13] G. A. Carpenter, S. Grossberg, and J. H. Reynolds, "ARTMAP: Supervised Real-Time Learning and Classification of Nonstationary Data by a Self-Organizing Neural Network," Neural Networks, vol. 4, no. 5, 1991, pp. 565-588.

[14] A. H. Tan, "Adaptive Resonance Associative Map: A Hierarchical ART System for Fast Stable Associative Learning," in Proc. IEEE/INNS International Joint Conference on Neural Networks, vol. 1, 1992, pp. 860-865.

[15] M. Hagiwara, "Multidimensional Associative Memory," in Proc. of 1990 IEEE Joint Conf. on Neural Networks, vol. I, 1990, pp. 3-6.


C.J. Wu, "A Conceptual Associative Memory with Full Memory Capacity and Ability to Associate Arbitrary Patterns," Proc. of IEEE Int. Symposium on Circuits and Systems, pp. 339-342, May 1994.