Neural Distributed Autoassociative Memories: A Survey <s> INTRODUCTION <s> 1 Associative Memory, Content Addressing, and Associative Recall.- 1.1 Introduction.- 1.1.1 Various Motives for the Development of Content-Addressable Memories.- 1.1.2 Definitions and Explanations of Some Basic Concepts.- 1.2 The Two Basic Implementations of Content Addressing.- 1.2.1 Software Implementation: Hash Coding.- 1.2.2 Hardware Implementation: The CAM.- 1.3 Associations.- 1.3.1 Representation and Retrieval of Associated Items.- 1.3.2 Structures of Associations.- 1.4 Associative Recall: Extensions of Concepts.- 1.4.1 The Classical Laws of Association.- 1.4.2 Similarity Measures.- 1.4.3 The Problem of Infinite Memory.- 1.4.4 Distributed Memory and optimal Associative Mappings.- 1.4.5 Sequential Recollections.- 2 Content Addressing by Software.- 2.1 Hash Coding and Formatted Data Structures.- 2.2 Hashing Functions.- 2.3 Handling of Collisions.- 2.3.1 Some Basic Concepts.- 2.3.2 Open Addressing.- 2.3.3 Chaining (Coalesced).- 2.3.4 Chaining Through a Separate overflow Area.- 2.3.5 Rehashing.- 2.3.6 Shortcut Methods for Speedup of Searching.- 2.4 Organizational Features and Formats of Hash Tables.- 2.4.1 Direct and Indirect Addressing.- 2.4.2 Basic Formats of Hash Tables.- 2.4.3 An Example of Special Hash Table Organization.- 2.5 Evaluation of Different Schemes in Hash Coding.- 2.5.1 Average Length of Search with Different Collision Handling Methods.- 2.5.2 Effect of Hashing Function on the Length of Search.- 2.5.3 Special Considerations for the Case in Which the Search Is Unsuccessful.- 2.6 Multi-Key Search.- 2.6.1 Lists and List Structures.- 2.6.2 An Example of Implementation of Multi-Key Search by Hash Index Tables.- 2.6.3 The Use of Compound Keywords in Hashing.- 2.7 Implementation of Proximity Search by Hash Coding.- 2.8 The TRIE Memory.- 2.9 Survey of Literature on Hash Coding and Related Topics.- 3 Logic Principles of Content-Addressable Memories.- 3.1 Present-Day Needs for Hardware CAMs.- 3.2 The Logic of Comparison Operations.- 3.3 The All-Parallel CAM.- 3.3.1 Circuit Logic of a CAM Bit Cell.- 3.3.2 Handling of Responses from the CAM Array.- 3.3.3 The Complete CAM Organization.- 3.3.4 Magnitude Search with the All-Parallel CAM.- 3.4 The Word-Parallel, Bit-Serial CAM.- 3.4.1 Implementation of the CAM by the Linear-Select Memory Principle.- 3.4.2 Skew Addressing.- 3.4.3 Shift Register Implementation.- 3.4.4 The Results Storage.- 3.4.5 Searching on More Complex Specifications.- 3.5 The Word-Serial, Bit-Parallel CAM.- 3.6 Byte-Serial Content-Addressable Search.- 3.6.1 Coding by the Characters.- 3.6.2 Specifications Used in Document Retrieval.- 3.6.3 A Record-Parallel, Byte-Serial CAM for Document Retrieval.- 3.7 Functional Memories.- 3.7.1 The Logic of the Bit Cell in the FM.- 3.7.2 Functional Memory 1.- 3.7.3 Functional Memory 2.- 3.7.4 Read-only Functional Memory.- 3.8 A Formalism for the Description of Micro-Operations in the CAM.- 3.9 Survey of Literature on CAMs.- 4 CAM Hardware.- 4.1 The State-of-the-Art of the Electronic CAM Devices.- 4.2 Circuits for All-Parallel CAMs.- 4.2.1 Active Electronic Circuits for CAM Bit Cells.- 4.2.2 Cryotron-Element CAMs.- 4.2.3 Josephson Junctions and SQUIDs for Memories.- 4.3 Circuits for Bit-Serial and Word-Serial CAMs.- 4.3.1 Semiconductor RAM Modules for the CAM.- 4.3.2 Magnetic Memory Implementations of the CAM.- 4.3.3 Shift Registers for Content-Addressable Memory.- 4.3.4 The Charge-Coupled Device (CCD).- 4.3.5 The Magnetic-Bubble Memory (MBM).- 4.4 Optical Content-Addressable Memories.- 4.4.1 Magneto-Optical Memories.- 4.4.2 Holographic Content-Addressable Memories.- 5 The CAM as a System Part.- 5.1 The CAM in Virtual Memory Systems.- 5.1.1 The Memory Hierarchy.- 5.1.2 The Concept of Virtual Memory and the Cache.- 5.1.3 Memory Mappings for the Cache.- 5.1.4 Replacement Algorithms.- 5.1.5 Updating of Multilevel Memories.- 5.1.6 Automatic Control of the Cache Operations.- 5.1.7 Buffering in a Multiprocessor System.- 5.1.8 Additional Literature on Memory Organizations and Their Evaluation.- 5.2 Utilization of the CAM in Dynamic Memory Allocation.- 5.2.1 Memory Map and Address Conversion.- 5.2.2 Loading of a Program Segment.- 5.3 Content-Addressable Buffer.- 5.4 Programmable Logic.- 5.4.1 RAM Implementation.- 5.4.2 CAM Implementation.- 5.4.3 FM Implementation.- 5.4.4 Other Implementations of Programmable Logic.- 5.4.5 Applications of the CAM in Various Control Operations.- 6 Content-Addressable Processors.- 6.1. Some Trends in Content-Addressable Memory Functions.- 6.2 Distributed-Logic Memories (DLMs).- 6.3 The Augmented Content-Addressable Memory (ACAM).- 6.4 The Association-Storing Processor (ASP).- 6.5 Content-Addressable Processors with High-Level Processing Elements.- 6.5.1 The Basic Array Processor Architecture.- 6.5.2 The Associative Control Switch (ACS) Architecture.- 6.5.3 An Example of Control-Addressable Array Processors: RADCAP.- 6.5.4 An Example of Content-Addressable Ensemble Processors: PEPE.- 6.6 Bit-Slice Content-Addressable Processors.- 6.6.1 The STARAN Computer.- 6.6.2 Orthogonal Computers.- 6.7 An Overview of Parallel Processors.- 6.7.1 Categorizations of Computer Architectures.- 6.7.2 Survey of Additional Literature on Content-Addressable and Parallel Processing.- 7 Review of Research Since 1979.- 7.1 Research on Hash Coding.- 7.1.1 Review Articles.- 7.1.2 Hashing Functions.- 7.1.3 Handling of Collisions.- 7.1.4 Hash Table Organization.- 7.1.5 Linear Hashing.- 7.1.6 Dynamic, Extendible, and External Hashing.- 7.1.7 Multiple-Key and Partial-Match Hashing.- 7.1.8 Hash-Coding Applications.- 7.1.9 Hash-Coding Hardware.- 7.2 CAM Hardware.- 7.2.1 CAM Cells.- 7.2.2 CAM Arrays.- 7.2.3 Dynamic Memories.- 7.2.4 CAM Systems.- 7.3 CAM Applications.- 7.4 Content-Addressable Parallel Processors.- 7.4.1 Architectures for Content-Addressable Processors.- 7.4.2 Data Base Machines.- 7.4.3 Applications of Content-Addressable Processors.- 7.5 Optical Associative Memories.- 7.5.1 General.- 7.5.2 Holographic Content-Addressable Memories.- References. <s> BIB001 </s> Neural Distributed Autoassociative Memories: A Survey <s> INTRODUCTION <s> We discuss the thermodynamic phases and storage capacity of models which are extensions of the Hopfield-Little model of associative memory, generalized to allow for arbitrary polynomial Hamiltonians. The storage capacity increases as an exponential function of the highest power appearing in the polynomial Hamiltonian. We include the effects of replica symmetry breaking in our computations. <s> BIB002 </s> Neural Distributed Autoassociative Memories: A Survey <s> INTRODUCTION <s> The informational aspects of neural networks performing associative memory following Hebbian learning are analysed in detail. The recall process is decomposed into its recognition and error correction components, and the respective contributions are clarified and computed.The analysis identifies the principal sources of information loss. They are shown to be in the choice of the decoding procedure, in the indeterminacy introduced by zero modification states of the synapses and in the statistical dependences between different synaptic modification states.A wide range of storage schemes and decoding procedures are discussed and their optimal characteristics are compared and evaluated relative to the corresponding limits prescribed by Shannon's theorem. <s> BIB003
In this paper, we review some artificial neural network variants of distributed autoassociative memories (denoted by Neural Associative Memory, NAM) . Varieties of associative memory BIB001 (or content addressable memory) can be considered as index structures performing some types of similarity search. In autoassociative memory, the output is the word of memory, most similar to the key at the input. We restrict our initial attention to systems where the key and memory words are binary vectors. Therefore, autoassociative memory answers nearest neighbor queries for binary vectors. In distributed memory, different vectors (items to be stored) are stored in shared memory cells. That is, each item to be stored consists of a pattern of activation across (potentially) all the memory cells of the system and each memory cell of the system contributes to the storage and recall of many (potentially all) stored items. Some of types of distributed memory have attractive properties of parallelism, resistance to noise and malfunctions, etc. However, exactly correct answers to the nearest neighbor queries from such memories are not guaranteed, especially when too many vectors are stored in the memory. Neurobiologically plausible variants of distributed memory can be represented as artificial neural networks. These typically perform one-shot memorization of vectors by a local learning rule modifying connection weights and retrieve a memory vector in response to a query vector by an iterative procedure of activity propagation between neurons via their connections. In the first Section, we briefly introduce Hebb's theory of brain functioning based on cell assemblies because it has influenced many models of NAM. Then we introduce a generic scheme of NAMs and their characteristics (discussed in more details in the other sections). The following three Sections discuss the widespread matrix-type NAMs (where each pair of neurons is connected by two symmetric connections) of Hopfield, Willshaw, and Potts that work best with sparse binary vectors. The next Section is devoted to the function of generalization, which differs from the function of autoassociative memory and emerges in some NAMs. The following Section discusses NAMs with higherorder connections (more than two neurons have a connection) and NAMs without connections. Then some recent NAMs with a bipartite graph structure are considered. The last Section provides discussion and concludes the paper. In the retrieval mode, an input binary vector x (probe or key or query vector) is fed to the network by activation of its neurons: = zx . The input sum of the i -th neuron BIB002 is the value of the neuron threshold. For parallel (synchronous) network dynamics, the input sums and the states of all D neurons are calculated (updated) at each step t of iterative retrieval. For sequential (asynchronous) dynamics, i z is calculated for one neuron i , selected randomly. For simplicity, let us consider random selection without replacement, and one step of the asynchronous dynamics to consist of update of the states of all D neurons. The parameters W and T are set so that after a single, or several, steps of dynamics the state of the network (neurons) reaches a stable state (typically, the state vector does not change with t , but cyclic state changes are also considered as "stable"). At the stable state, z is the output of the network. The query vector x is usually a modified version of one of the stored vectors y . In the literature, this might be referred to as a noisy, corrupted, or distorted version of a vector. While the number of stored vectors is not too high, the output z is the stored y closest to x (in terms of dot product dot sim(,), ºáñ xyxy ). That is, z is the base vector y with the maximum value of , áñ xy . In this case, NAM returns the (exact) nearest neighbor in terms of dot sim . For binary vectors with the same number of unit (i.e. with value equal to 1) components, this is equivalent to the nearest neighbor by the Hamming distance ( Ham dist ). The time complexity (runtime) of one step of the network dynamics is 2 () OD . Thus, if a NAM can be constructed that stores a base of ND > vectors so that they can be successfully retrieved from their distorted versions, then the retrieval time via the NAM could be less than the () ODN time required for linear search (i.e. the sequential comparison of all base vectors y to x ). Since the memory complexity of this NAM type is 2 () OD , as D increases, one can expect an increasing in the size N of the bases that could be stored and retrieved by NAM. Unfortunately, the vector at the NAM output may not be the nearest neighbor of the query vector, and possibly not even a vector of the base. (Note that if one was not concerned with biological plausibility, one can quickly check whether the output vector is in the base set by using a hash table to store all base vectors.) In some NAMs, it is only possible to store many fewer vectors N than D , with high probability of accurate retrieval, especially if the query vectors are quite dissimilar to the base vectors. For NAM analysis, base vectors are typically selected randomly independently from some distribution of binary vectors (e.g., vectors with the probability p of 1-components equal to 1/2, or vector with pD 1-components, for some p from interval (0,1)). The assumption of independence simplifies analytical approaches, but is likely unrealistic for real applications of NAMs. The query vectors are typically generated by as modifications of the base vectors. Distortion by deletion randomly changes some of the 1s to 0s (the remaining components are guaranteed to agree). A more complex distortion by noise randomly changes some 1s to 0s, and some 0s to 1s while (exactly or approximately) preserving the total number of 1s. For a random binary vector of dimension D with the probability p of a component to be 1, the Shannon entropy For 1 D >> , a random vector with pD of 1s has approximately the same entropy. The entropy of N vectors is () NDhp. When N vectors are stored in NAM, the entropy per connection is  BIB003 . Knowing () hp, it is easy to determine N for a given a . When too many vectors are stored, NAM becomes overloaded and the probability of accurate retrieval drops (even to 0). The value of a for which a NAM still works reliably depends on the mode of its use (in addition to the NAM design and distributions of base and query vectors). The mode where the undistorted stored base vectors are still stable NAM states (or stable states differ by few components from the intended base vectors), has the largest value of a . (We denote the largest value of a for this mode as "critical", crit a , and the corresponding N as crit N .) For crit aa > the stored vectors become unstable. Note that checking if an input vector is stable does not allow one to extract information from the NAM, since vectors not stored can also be stable. The information (in the Shannon information-theoretic sense) that can be extracted from a NAM is determined by the information efficiency (per connection) E . This quantity is bounded above by some specific a (the entropy per connection that still permits information extraction), which in its turn is bounded above by crit a . A NAM may work in recognition or correction mode. In recognition mode, the NAM distinguishes whether the input (query) vector is from the base or not, yielding extracted information quantified by recog E . When NAM answers the nearest neighbor queries (correction mode), information quantified by corr E is extracted from the NAM by correction (completion) of the distorted query vectors. The more distorted the base vector used as the query at the NAM input, the more information corr E is extracted from the NAM (provided that the intended base vector is sufficiently accurately retrieved). However, more distorted input vectors lower the value of corr a at which the NAM is still able to retrieve the correct base vectors, and so lowers corr E (which is constrained to be less than corr a ). We refer to these information-theoretic properties of NAMs as their information characteristics. Let us now consider specific variants of the generic NAM. Hereafter we use the terms "NAM" and "(neural) network" interchangeably.