Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW 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> BIB001 </s> Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW 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> BIB002 </s> Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW NAMs <s> From the Publisher: ::: Substantial progress in understanding memory, the learning process, and self-organization by studying the properties of models of neural networks have resulted in discoveries of important parallels between the properties of statistical, nonlinear cooperative systems in physics and neural networks. <s> BIB003 </s> Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW NAMs <s> The simple learning algorithm in the neural network with binary synapses, which take one step for storing one pattern is considered. The resulting model turns out to be palimpsestic, and the number of patterns which can be effectively retrieved is L~N1/2. <s> BIB004 </s> Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW NAMs <s> The Willshaw model of associative memory, implemented in a fully connected network with stochastic asynchronous dynamics, is studied. In addition to Willshaw's learning rule, the network contains uniform synaptic inhibition, of relative strength K, and negative neural threshold -\ensuremath{\theta},\ensuremath{\theta}g0. The P stored memories are sparsely coded. The total number of on bits in each memory is Nf, where f is much smaller than 1 but much larger than lnN/N. Mean-field theory of the system is solved in the limit where C==exp(-${f}^{2}$P) is finite. Memory states are stable (at zero temperature), as long as Cg${h}_{0}$==K-1+\ensuremath{\theta} and ${h}_{0}$g0. When C${h}_{0}$ or ${h}_{0}$0, P retrieval phases, highly correlated with the memory states, exist. These phases are only partially frozen at low temperature, so that the full memories can be retrieved from them by averaging over the dynamic fluctuations of the neural activity. In particular, when ${h}_{0}$0 the retrieval phases at low temperatures correspond to freezing of most of the population in a quiescent state while the rest are active with a time average that can be significantly smaller than the saturation level. These features resemble, to some extent, the observed patterns of neural activity in the cortex, in experiments of short-term memory tasks. The maximal value of P for which stable retrieval phases exist, scales as ${f}^{\mathrm{\ensuremath{-}}3}$/\ensuremath{\Vert}lnf\ensuremath{\Vert} for f\ensuremath{\gg}1/lnN, and as ${f}^{\mathrm{\ensuremath{-}}2}$ln(Nf/\ensuremath{\Vert}lnf\ensuremath{\Vert}) for f\ensuremath{\ll}1/lnN. Numerical simulations of the model with N=1000 and f=0.04 are presented. We also discuss the possible realization of the model in a biologically plausible architecture, where the inhibition is provided by special inhibitory neurons. <s> BIB005 </s> Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW NAMs <s> Recent studies of the information capacity in a sparsely coded memory net has led to some contradictory results. In the Willshaw model, where the couplings are binary (0 or 1), the maximal quantity of information that can be stored is 1n 2 approximately=0.69 bits per synapse. On the other hand a calculation a la Gardner (1988) for (0,1) couplings gives an upper bound for the maximal capacity of about 0.29 bits per synapse. In this study, the author considers two possible sources for this discrepancy. The first one is that the criteria for defining the maximal capacity are different (with or without a constraint of perfect errorless storage). The second one is a difference in the choice of the probability distribution of the random patterns used to compute this capacity. This analysis shows in particular that for the Willshaw model the maximal information capacity is much larger when the number of active neurons is exactly the same in every stored pattern, than when it is given only in average. In addition he gives an argument showing that this result may be generic, e.g., valid for any activity level and independent of the learning rule. <s> BIB006 </s> Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW NAMs <s> A new access to the asymptotic analysis of autoassociation properties in recurrent McCulloch-Pitts networks in the range of low activity is proposed. Using information theory, this method examines the static structure of stable states imprinted by a Hebbian storing process. In addition to the definition of critical pattern capacity usually considered in the analysis of the Hopfield model, the authors introduce the definition of information capacity which guarantees content addressability and is a stricter upper bound of the information really accessible in an autoassociation process. They calculate these two types of capacities for two types of local learning rules which are very effective for sparsely coded patterns: the Hebb rule and the clipped Hebb rule. It turns out that for both rules the information capacity is exactly half the pattern capacity. <s> BIB007 </s> Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW NAMs <s> The associative net is a mahix model of associative memory whichhas ah efficiency of recall approaching that of a random access memory with no associative capability. This is a fully connected netwoIk, which m&es it possible to use a simple strategy for setting ,the thresholds of the units in recall. However, most brain structures that a!e thought to underlie leaming and memory have only partial interconnectivity. We deicribe five different strategies for setting the thresholds of units in piilially connected nets. The simprest is a, meZhaniSm of the winners-lake-all type. The most sophisticated strategy employs information about the density of modified synapses and their dishiburion on each output unit. The action Of this mechanism is shown to be equivalent to minimiration of output ermr but without re&ring numerical solution of a selof equations, which would 6e biolo&cally implausible. Simulation results demonstrare the superiority of this mechanism in a typical case. Paramew sensitivity analysis of this mechanism shows~its robusuless and that performance improves as mnnectivity becomes more complete. <s> BIB008 </s> Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW 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> WILLSHAW NAMs <s> We study the recognition properties of a modification of the Willshaw associative memory with a floating threshold analytically for the asymptotic case of large networks and single-step retrieval. The number of spurious stable states and the size of their attraction basins are calculated. Comparison is made with simulations for single- and multistep dynamics. The appropriateness of the recognition procedure based on the remanent overlap is demonstrated. <s> BIB010 </s> Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW 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> WILLSHAW NAMs <s> The information storing capacity of certain associative and auto-associative memories is calculated. For example, in a 100×100 matrix of 1 bit storage elements more than 6,500 bits can be stored associatively, and more than 688,000 bits in a 1,000×1,000 matrix. Asymptotically, the storage capacity of an associative memory increases proportionally to the number of storage elements. The usefulness of associative memories, as opposed to conventional listing memories, is discussed — especially in connection with brain modelling. <s> BIB012 </s> Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW NAMs <s> Neural associative networks with plastic synapses have been proposed as computational models of brain functions and also for applications such as pattern recognition and information retrieval. To guide biological models and optimize technical applications, several definitions of memory capacity have been used to measure the efficiency of associative memory. Here we explain why the currently used performance measures bias the comparison between models and cannot serve as a theoretical benchmark. We introduce fair measures for information-theoretic capacity in associative memory that also provide a theoretical benchmark. In neural networks, two types of manipulating synapses can be discerned: synaptic plasticity, the change in strength of existing synapses, and structural plasticity, the creation and pruning of synapses. One of the new types of memory capacity we introduce permits quantifying how structural plasticity can increase the network efficiency by compressing the network structure, for example, by pruning unused synapses. Specifically, we analyze operating regimes in the Willshaw model in which structural plasticity can compress the network structure and push performance to the theoretical benchmark. The amount C of information stored in each synapse can scale with the logarithm of the network size rather than being constant, as in classical Willshaw and Hopfield nets (< or = ln 2 approximately 0.7). Further, the review contains novel technical material: a capacity analysis of the Willshaw model that rigorously controls for the level of retrieval quality, an analysis for memories with a nonconstant number of active units (where C < or = 1/e ln 2 approximately 0.53), and the analysis of the computational complexity of associative memories with and without network compression. <s> BIB013 </s> Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW NAMs <s> We study various models of associative memories with sparse information, i.e. a pattern to be stored is a random string of 0s and 1s with about \(\log N\) 1s, only. We compare different synaptic weights, architectures and retrieval mechanisms to shed light on the influence of the various parameters on the storage capacity. <s> BIB014 </s> Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW NAMs <s> Associative memories aim at matching an input noisy vector with a stored one. The matched vector satisfies a minimum distance criterion with respect to the inner metric of the device. This problem of finding nearest neighbors in terms of Euclidean or Hamming distances is a very common operation in machine learning and pattern recognition. However, the inner metrics of associative memories are often misfitted to handle practical scenarios. In this paper, we adapt Willshaw networks in order to use them for accelerating nearest neighbor search with limited impact on accuracy. We provide a theoretical analysis of our method for binary sparse vectors. We also test our method using the MNIST handwritten digits database. Both our analysis for synthetic data and experiments with real-data evidence a significant gain in complexity with negligible loss in performance compared to exhaustive search. <s> BIB015 </s> Neural Distributed Autoassociative Memories: A Survey <s> WILLSHAW NAMs <s> Nearest neighbor search is a very active field in machine learning for it appears in many application cases, including classification and object retrieval. In its canonical version, the complexity of the search is linear with both the dimension and the cardinal of the collection of vectors the search is performed in. Recently many works have focused on reducing the dimension of vectors using quantization techniques or hashing, while providing an approximate result. In this paper we focus instead on tackling the cardinal of the collection of vectors. Namely, we introduce a technique that partitions the collection of vectors and stores each part in its own associative memory. When a query vector is given to the system, associative memories are polled to identify which one contain the closest match. Then an exhaustive search is conducted only on the part of vectors stored in the selected associative memory. We study the effectiveness of the system when messages to store are generated from i.i.d. uniform $\pm$1 random variables or 0-1 sparse i.i.d. random variables. We also conduct experiment on both synthetic data and real data and show it is possible to achieve interesting trade-offs between complexity and accuracy. <s> BIB016
Willshaw networks with sparse vectors. NAMs with binary connections from {0,1} are promising since they require only one bit per connection. Such networks were proposed both in heteroassociative  and autoassociative versions (e.g. BIB012   BIB004 BIB005 BIB006  BIB007 BIB008  BIB009  BIB010  BIB013 ). The learning rule (let's call it the Willshaw rule) becomes: where Ú is disjunction, Ù is conjunction. Various strategies for threshold setting can be used, e.g., setting threshold T to ensure pD active neurons, as in Subsection "Hopfield networks with sparse vectors". Note that this NAM can not work with dense vectors, since storing only a small number of dense vectors will set almost all the connection weights to 1. Moreover, for the same reason, the Willshaw networks (unlike the Hopfield networks) cease to work at any constant p and a as D ®¥. The number N of random binary vectors able to be stored and retrieved in the Willshaw NAM grows with decreasing vector density. Even for not very large networks and not very sparse vectors (~/ pDD ), N can exceed D (e.g. D = 4096 allowed storage and retrieval of up to N = 7000 vectors distorted by noise in the experiments of  ). The particular N values reached (for D and p fixed) vary depending on the degree of the query vector distortion and on the desired probability of retrieval. The maximum theoretical crit ln20.69 a =» is reached as D ®¥ for ~ln/ pDD   BIB009 . In BIB007 was theoretically shown for single-step (as well as multi-step) retrieval and distortion by deletion. For multi-step retrieval in finite Willshaw NAMs (with distortion by deletion) corr E up to 0.19 (at D = 20000) was obtained experimentally in BIB011 . Experiments in BIB011  show that in the Willshaw NAM (unlike the Hopfield NAM), the values corr a and corr E for not too large D are higher than for D ®¥ (see also  ). Note that the quality of retrieval in the Willshaw NAM is higher than in the Hopfield NAM; the retrieved vectors more often coincide exactly with the stored vectors of the base. From the detailed analytical and experimental study of the values of corr a in  (at various levels of sparsely, parameterized as b , degrees of distortion by noise, and D up to 100000), it was found that corr 0.13 E » per connection can be reached in the experiments (for small networks, N = 640, pD = 20, 0.25 b = ). It was also shown that the results of the analytical methods SS BIB001 and GR  are far from the experimental results (in most cases, worse than them). Due to the connections being binary, the efficiency per bit of connection implemented in computer memory is higher than that for the Hopfield network (where corr 0.205 E » per connection BIB009 ). A review of NAM studies in BIB013 concludes that for Willshaw networks having connection matrix W with probability of a nonzero element close to 0 or 1, compression of W improves information characteristics compared with the usual uncompressed Willshaw NAM. Such compressed W are obtained when the base vectors have the number of 1s sublogarithmic or superlogarithmic in D . Their comparison of the retrieval time in compressed Willshaw networks and the inverted index has shown the advantage of the inverted index for most parameters. An analytical and experimental comparison of the Willshaw, the GB (Subsection "Willshaw-Potts network"), and the Hopfield networks (with the Hebb rule BIB002 ) for vectors with p of the order of ln/ DD and distortion by deletion was carried out in BIB014 . They investigate single-step retrieval theoretically (asymptotically, for D ®¥ with probability approaching 1). For all models, the lower bound of N of the order 2 (/ln) DD is obtained, and for the Willshaw network the matching upper bound is shown. In experiments, the results are worse for a fixed threshold than for a variable threshold. The Hopfield network performed worse, in terms of empirical probability of retrieval versus N , compared with the other NAMs, probably because of the non-optimal Hebb learning rule and non-optimal threshold selection. For the diluted Willshaw networks BIB008 BIB003 BIB009  ] the optimal pD (providing approximately the same capacity N ) is higher than for the fully connected networks. Willshaw networks in the index structures for nearest neighbor search. In BIB015 the base of binary sparse vectors is divided into disjoint sets (of the same cardinality) and each is stored in a Willshaw NAM with its own W . When the query vector x is input, dot sim(,) xWx is calculated for the matrices W of all sets, and the vectors of sets with the maximum similarity are used as the nearest neighbor candidates (verified by linear search). Analysis and experiments for bases of random vectors with small random distortions of query vectors showed that up to a certain number of vectors in each network the nearest neighbor is found with a high probability (in experiments, without error) and faster than by linear search only. If this number of vectors per network is exceeded, both the probability of finding an incorrect nearest neighbor and its distance to the correct vector increase. A somewhat lower speedup relative to linear search is shown for real, nonrandom data, versus synthetic, random data. In BIB016 similar results were obtained analytically (asymptotically for D ®¥ and error probability approaching zero) and experimentally for bases of sparse and dense random vectors (for the Hopfield rule).