Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> Abstract ::: Computational properties of use of biological organisms or to the construction of computers can emerge as collective properties of systems having a large number of simple equivalent components (or neurons). The physical meaning of content-addressable memory is described by an appropriate phase space flow of the state of a system. A model of such a system is given, based on aspects of neurobiology but readily adapted to integrated circuits. The collective properties of this model produce a content-addressable memory which correctly yields an entire memory from any subpart of sufficient size. The algorithm for the time evolution of the state of the system is based on asynchronous parallel processing. Additional emergent collective properties include some capacity for generalization, familiarity recognition, categorization, error correction, and time sequence retention. The collective properties are only weakly sensitive to details of the modeling or the failure of individual devices. <s> BIB001 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> The Hopfield model of a neural network is studied near its saturation, i.e., when the number p of stored patterns increases with the size of the network N, as p = αN. The mean-field theory for this system is described in detail. The system possesses, at low α, both a spin-glass phase and 2p dynamically stable degenerate ferromagnetic phases. The latter have essentially full macroscopic overlaps with the memorized patterns, and provide effective associative memory, despite the spin-glass features. The network can retrieve patterns, at T = 0, with an error of less than 1.5% for α <αc = 0.14. At αc the ferromagnetic (FM) retrieval states disappear discontinuously. Numerical simulations show that even above αc the overlaps with the sored patterns are not zero, but the level of error precludes meaningful retrieval. The difference between the statistical mechanics and the simulations is discussed. As α decreases below 0.05 the FM retrieval states become ground states of the system, and for α < 0.03 mixture states appear. The level of storage creates noise, akin to temperature at finite p. Replica symmetry breaking is found to be salient in the spin-glass state, but in the retrieval states it appears at extremely low temperatures, and is argued to have a very weak effect. This is corroborated by simulations. The study is extended to survey the phase diagram of the system in the presence of stochastic synaptic noise (temperature), and the effect of external fields (neuronal thresholds) coupled to groups of patterns. It is found that a field coupled to many patterns has a very limited utility in enhancing their learning. Finally, we discuss the robustness of the network to the relaxation of various underlying assumptions, as well as some new trends in the study of neural networks. <s> BIB002 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> Spin glass models have a complex phase space which may be used to store information. By an asynchronous relaxational dynamics noisy patterns are recognized very fast. In particular the Hopfield model which may be a simple model for neural networks is analyzed in detail. By numerical simulations and analytical approximations the number of patterns to be stored and the amount of noise to be recognized is calculated. It is demonstrated that a random network can learn patterns by reducing frustrated bonds. <s> BIB003 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> Techniques from coding theory are applied to study rigorously the capacity of the Hopfield associative memory. Such a memory stores n -tuple of \pm 1 's. The components change depending on a hard-limited version of linear functions of all other components. With symmetric connections between components, a stable state is ultimately reached. By building up the connection matrix as a sum-of-outer products of m fundamental memories, one hopes to be able to recover a certain one of the m memories by using an initial n -tuple probe vector less than a Hamming distance n/2 away from the fundamental memory. If m fundamental memories are chosen at random, the maximum asympotic value of m in order that most of the m original memories are exactly recoverable is n/(2 \log n) . With the added restriction that every one of the m fundamental memories be recoverable exactly, m can be no more than n/(4 \log n) asymptotically as n approaches infinity. Extensions are also considered, in particular to capacity under quantization of the outer-product connection matrix. This quantized memory capacity problem is closely related to the capacity of the quantized Gaussian channel. <s> BIB004 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> We extend the analysis of asymmetric diluted networks to the case of low-activity level. The same learning algorithm which was used for the symmetric model turns out to be successful. The use of "V-variables" (V = 0; 1) leads to significant enhancing of the storage capacity. The overloading phase transition is found to be of the first order, which means good retrieval quality in all associative memory phases. The intensity of time-dependent nonthermal noise can be diminished considerably by the appropriate choice of the neural threshold. Some sort of "universality" of the performance of the networks with low-activity level can be noted. <s> BIB005 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> Approximate dynamic mean field equations for a generalized Hopfield model are derived, which allow to calculate transient properties of this model. These equations are exact for short times and yield the replica symmetric solution as a stationary solution. They allow reliable computation of retrieval trajectories and basins of attraction of retrieval states, as demonstrated by comparison with simulations. The equations are derived for networks with arbitrary mean activity and results are given for the standard model and for low activities. <s> BIB006 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> Abstract Characteristics of an autocorrelation or crosscorrelation associative memory largely depend on how items are encoded in pattern vectors to be stored. When most of the components of encoded patterns to be stored are 0 and only a small ratio of the components are 1, the encoding scheme is said to be sparse. The memory capacity and information capacity of a sparsely encoded associative memory are analyzed in detail, and are proved to be in proportion of n 2 log n 2 , n being the number of neurons, which is very large compared to the ordinary non-sparse encoding scheme of about 0.15n. Moreover, it is proved that the sparsely encoded associative memory has a large basin of attraction around each memorized pattern, when and only when an activity control mechanism is attached to it. <s> BIB007 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> We consider the Hopfield model with the most simple form of the Hebbian learning rule, when only simultaneous activity of pre- and post-synaptic neurons leads to modification of synapse. An extra inhibition proportional to full network activity is needed. Both symmetric nondiluted and asymmetric diluted networks are considered. The model performs well at extremely low level of activity p<K−1/2, where K is the mean number of synapses per neuron. <s> BIB008 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <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> BIB009 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> Considers a Hopfield associative memory consisting of n neurons, designed to store an m-set of n-dimensional /spl plusmn/1 statistically independent uniformly distributed random vectors (fundamental memories), using a connection matrix, constructed by the usual Hebbian rule. Previous results have indicated that the maximal value of m, such that almost all m vectors are stable points of the memory, in probability (i.e., with probability approaching one as n approaches infinity), is n/(2 log n)(n/(4 log n) if all m vectors must be stable simultaneously, in probability). Previous work further analyzed the direct convergence (i.e., convergence in one iteration) error-correcting power of the Hopfield memory. The present authors rigorously analyze the general case of nondirect convergence, and prove that in the m=n/(2 log n) case, independently of the operation mode used (synchronous or asynchronous), almost all memories have an attraction radius of size n/2 around them (in the n/(4 log n) case, all memories have such an attraction radius, in probability). This result, which was conjectured in the past but was never proved rigorously, combined with an old converse result that the network cannot store more than n/(2 log n)(n/(4 log n)) fundamental memories, gives a full picture of the error-correcting power of the Hebbian Hopfield network. The authors also upper bound the number of iterations required to achieve convergence. > <s> BIB010 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> Abstract We investigate the pattern completion performance of neural auto-associative memories composed of binary threshold neurons for sparsely coded binary memory patterns. By focussing on iterative retrieval, we are able to introduce effective threshold control strategies. These are investigated by means of computer simulation experiments and analytical treatment. To evaluate the systems performance we consider the completion capacity C and the mean retrieval errors. The asymptotic completion capacity values for the recall of sparsely coded binary patterns in one-step retrieval is known to be ln 2 4 ≈ 17.32% for binary Hebbian learning, and 1 (8 ln 2) ≈ 18% for additive Hebbian learning. These values are accomplished with vanishing error probability and yet are higher than those obtained in other known neural memory models. Recent investigations on binary Hebbian learning have proved that iterative retrieval as a more refined retrieval method does not improve the asymptotic completion capacity of one step retrieval. In a finite size auto-associative memory we show that iterative retrieval achieves higher capacity and better error correction than one-step retrieval. One-step retrieval produces high retrieval errors at optimal memory load. Iterative retrieval reduces the retrieval errors within a few iteration steps (t ⩽ 5). Experiments with additive Hebbian learning show that in the finite model, binary Hebbian learning exhibits much better performance. Thus the main concern of this paper is binary Hebbian learning. We examine iterative retrieval in experiments with up to n = 20,000 threshold neurons. With this system size one-step retrieval yields a completion capacity of about 16%, the second retrieval step increases this value to 17.9% and with iterative retrieval we obtain 19%. The first two retrieval steps in the finite system have also been treated analytically. For one-step retrieval the asymptotic capacity value is approximated from below with growing system size. In the second retrieval step (and as the experiments suggest also for iterative retrieval) the finite size behaviour is different. The capacity exceeds the asymptotic value, reaches an optimum for finite system size, and decreases to the asymptotic limit. <s> BIB011 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> Abstract A sparsely encoded Hopfield-like attractor neural network is investigated analytically and by computer simulation. Informational capacity and recall quality are evaluated. Three analytical approaches are used: replica method (RM); method of statistical neurodynamics (SN); and single-step approximation (SS). Computer simulation confirmed the good accuracy of RM and SN for all levels of network activity. SS is accurate only for large sparseness. It is shown that informational capacity monotonically increases when sparseness increases, while recall quality changes nonmonotonically: initially it decreases and then increases. Computer simulation revealed the main features of network behaviour near the saturation which are not predicted by the used analytical approaches. © 1997 Elsevier Science Ltd. <s> BIB012 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> We prove a sharp upper bound on the number of patterns that can be stored in the Hopfield model if the stored patterns are required to be fixed points of the gradient dynamics. We also show corresponding bounds on the one-step convergence of the sequential gradient dynamics. The bounds coincide with the known lower bounds and confirm the heuristic expectations. The proof is based on a crucial idea of Loukianova (1997) using the negative association properties of some random variables arising in the analysis. <s> BIB013 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> We consider re-learning ability of a Hopfield-type network after killing some neurons. Neurons were "killed" by means of nullification of corresponding rows and columns of the synaptic matrix. We show that one can restore recognition ability of this network using re-training with the vectors, which were memorized before. The number of vectors needed is equal to the number of deleted neurons. It does not depend on network's size and on volume of stored data. <s> BIB014 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> This note relates the storage capacity of the Hopfield model of neural networks with possibly correlated patterns to a moderate deviation upper bound for the empirical correlation of the patterns. Examples are, among others, independent patterns with spins that are correlated as in an Ising model or as in a Curie-Weiss model. <s> BIB015 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> Times of searching for similar binary vectors in neural-net and traditional associative memories are investigated and compared. The neural-net approach is demonstrated to surpass the traditional ones even if it is implemented on a serial computer when the entropy of a space of signals is of order of several hundreds and the number of stored vectors is vastly larger than the entropy. <s> BIB016 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> Abstract A fundamental question about brain function is why the connectivity in the cortex is diluted, in that neurons in a local region of the neocortex and in the CA3 part of the hippocampal cortex typically have a probability of having a synaptic connection between them that is less than 0.1. In both these types of cortex, there is evidence that the excitatory interconnections between neurons are associatively modifiable, and that the system supports attractor dynamics that enable memories to be stored, which are used in for example short-term memory and in episodic memory. The hypothesis proposed is that the diluted connectivity allows biological processes that set up synaptic connections between neurons to arrange for there to be only very rarely more than one synaptic connection between any pair of neurons. If probabilistically there were more than one connection between any two neurons, it is shown by simulation of an autoassociation attractor network that such connections would dominate the attractor states into which the network could enter and be stable, thus strongly reducing the memory capacity of the network (the number of memories that can be stored and correctly retrieved), below the normal large capacity for diluted connectivity. Diluted connectivity between neurons in the cortex thus has an important role in allowing high capacity of memory networks in the cortex, and helping to ensuring that the critical capacity is not reached at which overloading occurs leading to an impairment in the ability to retrieve any memories from the network. This intra-area diluted connectivity complements the diluted connectivity in the feedforward connections between cortical areas that helps the representations built by competitive learning to be stable. <s> BIB017 </s> Neural Distributed Autoassociative Memories: A Survey <s> HOPFIELD NAMs <s> Based on recent work by Gripon and Berrou (2011), we introduce a new model of an associative memory. We give upper and lower bounds on the memory capacity of the model. <s> BIB018
Hopfield networks with dense vectors. In the Hopfield NAM, "dense" random binary vectors (with the components from {0,1} with the probability 1/2 p = of 1) are used BIB001 . The learning procedure forms a symmetric matrix W of connection weights with positive and negative elements. The connection matrix is constructed by successively storing each of the base vectors y according to the Hopfield learning rule: (For brevity, we use the same name for generalization of this rule with 1/2 q < , though Hopfield did not propose it, Subsection "Hopfield networks with sparse vectors"). The dynamics in BIB001 is sequential (in many subsequent studies and implementations it is parallel) with the threshold 0 T = . It was shown BIB001 that each neuron state update decreases the energy function so that a (local) minimum of energy is eventually reached and such a network comes into a stable activation state. As D ®¥, various methods of analysis and approximation of experimental (modeling) data obtain crit 0.14 a » BIB001 BIB002  BIB006  which gives crit 0.14 Note that similar values of crit a are achieved at rather small finite D . For rigorous proofs of (smaller) crit a see refs in  . As for max corr E for distortion by noise, 0.092 was obtained by the method of approximate dynamical equations of the mean field BIB006 , and 0.095 by approximating the experiments to D ®¥  . By the coding theory methods in BIB004 it was shown that asymptotically (as D ®¥) it is possible to retrieve (with probability approaching 1) exact base vectors with query vectors distorted by noise (so that their Ham dist/2 D < from the base vectors), for /(2ln) NDD = stored base vectors if non-retrieval of some is permitted. If one requires the exact retrieval of all stored base vectors, the maximum number of vectors which can be stored decreases to /(4ln) NDD = . These values of N were shown to be the lower and upper bounds in BIB010 BIB013 . Note that in  crit 2 a = was obtained for "optimal" W (obtained by a non-Hebbian learning rule); a pseudoinverse rule (e.g.  BIB014 ) gives crit 1 a = . For correlated base vectors, the storage capacity crit N depends on the structure of the correlation. When the base vectors are generated by a onedimensional Markov chain  , crit N is somewhat higher than it is for independent vectors. This and other correlation models were considered in BIB015 . The same is valid for N corresponding to E . In the experiments BIB011 , for the Hebb rule and multi-step retrieval corr E values up to 0.09 were obtained. Detailed studies of the information characteristics of the finite-and infinite-dimensional networks with the Hopfield rule, can be found in BIB012  . Different degrees of distortion by noise for vectors with pD unit components were used. The dynamic threshold ensured pD active neurons at each step of the parallel dynamics. It was shown  that with this choice of threshold the stable states are static (some vector) or cycles of length 2 (two alternating vectors on adjacent steps of the dynamics). (This is the same behavior as for the fixed static threshold and is valid for all networks with symmetric connections.) It has been demonstrated experimentally  that even if after the first step of dynamics dotdot sim(,)sim(,) < yzyx (where y is the correct base vector, z is the network state, and x is the distorted input), the correct base vector can sometimes be retrieved by the subsequent steps of the dynamics. Conversely, increasing dot sim(,) yz at the first step of the dynamics does not guarantee correct retrieval  . These results apply to both the dense and sparse vector cases. The study  used analytical methods developed for the dense Hopfield network and adapted for sparse vectors, including the statistical neurodynamics (SN)  BIB012 , the replica method (RM) BIB002 , and the single step method (SS) BIB003 . All these analytical methods rather poorly predicted the behavior of finite networks for highly sparse vectors, at least for the parallel dynamics studied. (Note that all these methods (SN, RM, SS) provide accurate results for D ®¥ and 0 p ® , where retrieval by a single step of dynamics is enough.) Empirical experimentation avoids the shortcomings of these analytical methods by directly simulating the behavior of the networks. These simulations allow corr a and information efficiency, corr E , to be estimated as a functions of , pD and the level of noise in the input vectors. The value of corr E monotonically increases as D increases for a constant p . For p = 0.001 -0.01, which corresponds to the activity level of neurons in the brain, the maximum value of corr 0.205 E » was obtained by approximating experimental results to the case D ®¥  (higher than max corr 0.18 In BIB016 the time of retrieval in the Hopfield network was investigated (using the number of retrieval steps observed in simulation experiments; this number somewhat increases with D ). They conclude that for random vectors with small p , large D , and large N , Hopfield networks may be faster than some other algorithms (e.g., the inverted index) for approximate and exact nearest neighbor querying. An increase in the number crit N of stable states corresponding to the stored vectors proportional to 2 (/ln) DD for ~ln/ pDD is shown asymptotically in BIB007 (although non-rigorously, see also BIB012 ). Note, this result also follows from In BIB018 they give a rigorous analysis of a Hopfield network variant (neurons are divided into parts, see Section "Potts NAMs"), with the Hebb learning rule and p slightly less than ln/ DD , for retrieval by a single step of parallel dynamics with fixed T . The lower and upper bounds of N were obtained for which the memory vectors are stable states (with probability approaching 1 as D ®¥), and can also be exactly retrieved from query vectors distorted by noise. The lower and upper bounds of N found in BIB018 are of the same order as those found in BIB007 . For this mode of network operation, if we approximate the number of retrieval steps as ln D , we may estimate speed-up as 3 /(ln) DD relative to linear search (see Subsection "A generic scheme and characteristics of NAMs"). For both dense and sparse vectors, the NAM capacity max N grows with increasing D . Also, in order to maintain an adequate information content for a sparse vector ( () Dhp for ()1 hp<< ), it is necessary to have a sufficiently high D . The number of connections grows as D squared (because Hopfield networks are fully connected), which is unattainable even on modern computers at D of millions. Besides, the neurobiologically plausible number of connections per neuron is on the order of 10,000. Therefore, the development of "diluted" networks that perform NAM functions without being fully connected is attractive, e.g.  BIB005 BIB008 BIB009 BIB017 . This partial connectivity can be used to reduce the memory complexity of NAM from quadratic to linear in D   .