Neural Distributed Autoassociative Memories: A Survey <s> POTTS NAMs <s> We study the recognition and correction properties of a structured associative memory with a floating threshold which can be considered a modification of the Willshaw network and bears some resemblance to a network of Potts neurons. An analytical study is performed for the asymptotic case of large networks and single-step retrieval. The main informational characteristics of the network are obtained; the number of spurious stable states and the size of their attraction basins are calculated. A comparison is made with the Willshaw network considered earlier in this series of papers. <s> BIB001 </s> Neural Distributed Autoassociative Memories: A Survey <s> POTTS NAMs <s> Abstract We suggest an effective and simple algorithm providing a polynomial storage capacity of a network of the form M ~ N 2 s+1 , where N is the dimension of the stored binary patterns. In this problem the value of the free parameter s is restricted by the inequalities N >> s ln N 1 . The algorithm allows us to identify a large number of highly distorted similar patterns. The negative influence of correlations of the patterns is suppressed by choosing a sufficiently large value of the parameter s. We show the efficiency of the algorithm by the example of a perceptron identifier, but it also can be used to increase the storage capacity of full connected systems of associative memory. 1.Introduction Vector models of neural networks were investigated in a lot of papers [1-11]. Among them the most well-known is the Potts spin-glass model [4]. Its properties were investigated rather well by means of the statistical physics methods [5-9]. The characteristics of the memory of the Potts model were analyzed with the aid of computer simulations mainly. In [1-3], as well as in the series of the following papers [9-11], the so called parametrical neural network directed at realization in the form of an optical device, was investigated. In the last case rather simple analytical expressions describing its efficiency, storage capacity and noise immunity were obtained. The analysis of vector neural networks showed that they had an extremely large storage capacity, which was much higher than in the widely known binary models of the Hopfield type. In addition they have an extremely large noise immunity and the ability for recognition in the presence of very large distortions. At the present parametrical vector models of the associative memory are the best both with regard to the storage capacity and noise immunity. In the same time such high parameters of the aforementioned models were practically not used up to now, as well as other models of the associative memory. Moreover, for a lot of people the vector associative memory was related to the processing of the colored images only. The situation changed after the publication of the paper [3], where the algorithm of mapping of binary patterns into q-valued ones was proposed. It was also shown in [3] that such mapping allows one to use vector neural networks for storing and processing of signals of any type and any dimension. Moreover, the mapping brings to nothing the main difficulty of all the associative memory systems, which is the negative influence of correlations between the patterns. Thus, in the <s> BIB002 </s> Neural Distributed Autoassociative Memories: A Survey <s> POTTS NAMs <s> Coded recurrent neural networks with three levels of sparsity are introduced. The first level is related to the size of messages that are much smaller than the number of available neurons. The second one is provided by a particular coding rule, acting as a local constraint in the neural activity. The third one is a characteristic of the low final connection density of the network after the learning phase. Though the proposed network is very simple since it is based on binary neurons and binary connections, it is able to learn a large number of messages and recall them, even in presence of strong erasures. The performance of the network is assessed as a classifier and as an associative memory. <s> BIB003 </s> Neural Distributed Autoassociative Memories: A Survey <s> POTTS NAMs <s> An extension to a recently introduced binary neural network is proposed to allow the storage of sparse messages, in large numbers and with high memory efficiency. This new network is justified both in biological and informational terms. The storage and retrieval rules are detailed and illustrated by various simulation results. <s> BIB004 </s> Neural Distributed Autoassociative Memories: A Survey <s> POTTS 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> BIB005 </s> Neural Distributed Autoassociative Memories: A Survey <s> POTTS NAMs <s> This paper presents algorithms and hardware implementations of associative memories based on multiple-valued sparse clustered networks (MV-SCNs). SCNs are recently-introduced binary-weighted associative memories that significantly improve the storage and retrieval capabilities over the prior state-of-the art. However, deleting or updating the messages stored in binary-weighted connections result in a significant increase in the data retrieval error probability as the binary-weighted connections deleted may be shared for several data patterns. In order to address the problem, the proposed algorithm exploits multiple-valued weighted connections of the network for storing the messages while maintaining the number of computation nodes in a cluster. The use of the multiple-valued weighted connections reduces the probability of deleting the shared connections compared to the binary-weighted connections. As a result, the proposed algorithm lowers the error rate by an order of magnitude for our sample network with 60% deleted contents compared to the conventional algorithm when the same amount of memory is used. For performance comparisons in hardware, the proposed SCNs are designed using Verilog-HDL and synthesized on TSMC 65 nm CMOS technology. The synthesis results show that the proposed MV-SCNs are around 10% smaller than the conventional binary-weighted SCNs as the number of computation nodes in the proposed SCNs is smaller than that of the conventional SCNs with the comparable speed and memory size. <s> BIB006 </s> Neural Distributed Autoassociative Memories: A Survey <s> POTTS NAMs <s> Associative memories are data structures that allow retrieval of previously stored messages given part of their content. They, thus, behave similarly to the human brain’s memory that is capable, for instance, of retrieving the end of a song, given its beginning. Among different families of associative memories, sparse ones are known to provide the best efficiency (ratio of the number of bits stored to that of the bits used). Recently, a new family of sparse associative memories achieving almost optimal efficiency has been proposed. Their structure, relying on binary connections and neurons, induces a direct mapping between input messages and stored patterns. Nevertheless, it is well known that nonuniformity of the stored messages can lead to a dramatic decrease in performance. In this paper, we show the impact of nonuniformity on the performance of this recent model, and we exploit the structure of the model to improve its performance in practical applications, where data are not necessarily uniform. In order to approach the performance of networks with uniformly distributed messages presented in theoretical studies, twin neurons are introduced. To assess the adapted model, twin neurons are used with the real-world data to optimize power consumption of electronic circuits in practical test cases. <s> BIB007 </s> Neural Distributed Autoassociative Memories: A Survey <s> POTTS NAMs <s> The most efficient architectures of associative memories are based on binary neural networks. As example, Sparse Clustered Networks (SCNs) are able to achieve almost optimal memory efficiency while providing robust indexation of pieces of information through cliques in a neural network. In the canonical formulation of the associative memory problem, the unique stored message matching a given input probe is to be retrieved. In this paper, we focus on the more general problem of finding all messages matching the given probe. We consider real datasets from which many different messages can match given probes, which cannot be done with uniformly distributed messages due to their unlikelyhood of sharing large common parts with one another. Namely, we implement a crossword dictionary containing 8-letter english words, and a chess endgame dataset using associative memories based on binary neural networks. We explain how to adapt SCNs' architecture to this challenging dataset and introduce a backtracking procedure to retrieve all completions of the given input. We stress the performance of the proposed method using different measures and discuss the importance of parameters. <s> BIB008
Potts networks. The NAM from  can be considered as a network of neurons that are divided into non-overlapping parts ("columns"), with d neurons in each column and only one active neuron in the state 1 zd =-, for the remaining column neurons 1 z =-. That is, the sum of activations over all the neurons is zero in each column. The Hebb rule is used for learning. For the more convenient version of this model with the neurons having the states from {0,1} and single active neuron per column, the Hopfield rule is used. The connection matrix W for the entire network is constructed so that 0 ij w = for neurons i and j in the same column (this implies that 0 ii w = ). That is, the network is structured as a multipartite graph. Network dynamics (parallel or sequential) activates the one neuron in each column with the maximum input sum s (one of these neurons is randomly activated for neurons with equal s , but see the GB network below). For the number of columns D , the value of crit / ND of the Potts network was estimated by  to be (1)/2 ddtimes more than 0.14 (i.e., crit a for the Hopfield network with 1/2 p = ). However, to approximate the number of connections in the Hopfield network, the Potts network must have / Dd columns. Note also that one "Potts vector" contains only (/)log Ddd bits of information BIB001 . The Potts network with parallel and sequential dynamics, and with singlestep and multi-step retrieval was analytically explored in  . For exact retrieval (asymptotically, as D ®¥, with probability approaching 1), the upper and lower bounds of N were estimated both for the mode of querying with stable stored vectors and for the correction mode querying with distorted query vectors. In both cases, where the constant c increases quadratically in d , but with different c depending on the degree of distortion and the desired probability of state to be stable or vector to be retrieved. Willshaw-Potts network. For binary connections with the Willshaw learning rule, the Potts network becomes the Willshaw-Potts network BIB001 . When a vector is stored, a clique (a complete subgraph) is created in the connection graph. As for the Hopfield network, only static stable states or cycles of length 2 were experimentally observed for parallel dynamics. According to BIB001 , the information characteristics of this network are close to the Willshaw network at the same vector sparsity. Since the information content of Willshaw-Potts vectors is low, the crit N is higher than for the Willshaw network. This network was rediscovered as the GB network in BIB003 with various modifications BIB004 BIB005 and hardware implementations (for example, BIB006 with non-binary connections). The GB network is oriented for exact retrieval of vectors with distortion by deletion (columns without values activate all neurons). The peculiarities of the GB network include: connections of neurons with themselves; the possibility for several neurons in a column (with the maximum input sum) to be in the active state; the contribution from each column to the input sum of a neuron is not more than 1; various options for threshold management; the possibility of working with vectors having all zero components in some columns, etc. A theoretical GB analysis for single-step retrieval, as well as an experimental comparison with the Hopfield and the Willshaw networks for multi-step retrieval is given in BIB005 , see also Subsection "Willshaw networks with sparse vectors". Processing of realistic data. To represent arbitrary binary vectors in the Potts network, they are divided into segments of dimension log d and each segment is encoded by the activation of one neuron of its d -dimensional column BIB002 . Components of integer vectors can be represented in a similar way. Simulated data are typically generated as independent random samples. This ensures that the vectors to be stored are very nearly equally and maximally dissimilar. However, data generated from situations in the world is very unlikely to be so neatly distributed. When working with (unevenly distributed) real data, NAM is used non-optimally (many connections are not modified, others are "oversaturated"). To overcome this in the GB network, a free column neuron is allocated when the number of connections of a neuron (encoding some value) exceeds the threshold BIB007 . During retrieval, all column neurons that encode a certain value are activated. For better balancing the number of connections, in BIB008 the number of neurons in the column allocated to represent a vector component is proportional to the frequency of its 1-value in the vectors of the base. During storage, the various neurons representing the component are activated in turn. The authors of BIB008 also propose an algorithm for finding (with a high probability) all vectors of the base closest to the query vector distorted by deletion; the algorithm often significantly reduces the number of required queries.