Neural Distributed Autoassociative Memories: A Survey <s> Wy <s> The task of a neural associative memory is to retrieve a set of previously memorized patterns from their noisy versions by using a network of neurons. Hence, an ideal network should be able to 1) gradually learn a set of patterns, 2) retrieve the correct pattern from noisy queries and 3) maximize the number of memorized patterns while maintaining the reliability in responding to queries. We show that by considering the inherent redundancy in the memorized patterns, one can obtain all the mentioned properties at once. This is in sharp contrast with previous work that could only improve one or two aspects at the expense of the others. More specifically, we devise an iterative algorithm that learns the redundancy among the patterns. The resulting network has a retrieval capacity that is exponential in the size of the network. Lastly, by considering the local structures of the network, the asymptotic error correction performance can be made linear in the size of the network. <s> BIB001 </s> Neural Distributed Autoassociative Memories: A Survey <s> Wy <s> We consider the problem of neural association for a network of nonbinary neurons. Here, the task is to first memorize a set of patterns using a network of neurons whose states assume values from a finite number of integer levels. Later, the same network should be able to recall the previously memorized patterns from their noisy versions. Prior work in this area consider storing a finite number of purely random patterns, and have shown that the pattern retrieval capacities (maximum number of patterns that can be memorized) scale only linearly with the number of neurons in the network. In our formulation of the problem, we concentrate on exploiting redundancy and internal structure of the patterns to improve the pattern retrieval capacity. Our first result shows that if the given patterns have a suitable linear-algebraic structure, i.e., comprise a subspace of the set of all possible patterns, then the pattern retrieval capacity is exponential in terms of the number of neurons. The second result extends the previous finding to cases where the patterns have weak minor components, i.e., the smallest eigenvalues of the correlation matrix tend toward zero. We will use these minor components (or the basis vectors of the pattern null space) to increase both the pattern retrieval capacity and error correction capabilities. An iterative algorithm is proposed for the learning phase, and two simple algorithms are presented for the recall phase. Using analytical methods and simulations, we show that the proposed methods can tolerate a fair amount of errors in the input while being able to memorize an exponentially large number of patterns. <s> BIB002 </s> Neural Distributed Autoassociative Memories: A Survey <s> Wy <s> An associative memory is a structure learned from a dataset M of vectors (signals) in a way such that, given a noisy version of one of the vectors as input, the nearest valid vector from M (nearest neighbor) is provided as output, preferably via a fast iterative algorithm. Traditionally, binary (or q-ary) Hopfield neural networks are used to model the above structure. In this paper, for the first time, we propose a model of associative memory based on sparse recovery of signals. Our basic premise is simple. For a dataset, we learn a set of linear constraints that every vector in the dataset must satisfy. Provided these linear constraints possess some special properties, it is possible to cast the task of finding nearest neighbor as a sparse recovery problem. Assuming generic random models for the dataset, we show that it is possible to store super-polynomial or exponential number of n-length vectors in a neural network of size O(n). Furthermore, given a noisy version of one of the stored vectors corrupted in near-linear number of coordinates, the vector can be correctly recalled using a neurally feasible algorithm. <s> BIB003 </s> Neural Distributed Autoassociative Memories: A Survey <s> Wy <s> An associative memory is a framework of content-addressable memory that stores a collection of message vectors (or a dataset) over a neural network while enabling a neurally feasible mechanism to recover any message in the dataset from its noisy version. Designing an associative memory requires addressing two main tasks: 1) learning phase: given a dataset, learn a concise representation of the dataset in the form of a graphical model (or a neural network), 2) recall phase: given a noisy version of a message vector from the dataset, output the correct message vector via a neurally feasible algorithm over the network learnt during the learning phase. This paper studies the problem of designing a class of neural associative memories which learns a network representation for a large dataset that ensures correction against a large number of adversarial errors during the recall phase. Specifically, the associative memories designed in this paper can store dataset containing $\exp(n)$ $n$-length message vectors over a network with $O(n)$ nodes and can tolerate $\Omega(\frac{n}{{\rm polylog} n})$ adversarial errors. This paper carries out this memory design by mapping the learning phase and recall phase to the tasks of dictionary learning with a square dictionary and iterative error correction in an expander code, respectively. <s> BIB004
, where k is the part number. To do this, the objective function is formulated and optimized with a stochastic gradient descent (several times for each part). During retrieval, they first independently correct errors in each part by performing several steps of the network dynamics. The correction is based on the fact that Then, exploiting intersection of the parts, the parts without errors are used to correct the parts with errors. In BIB002 , y from a subspace of dimension dD < are considered. Training forms a matrix W of Dd -non-zero linearly independent vectors orthogonal to the vectors y of the base: 0 = Wy for all y of the base. An iterative algorithm of activity propagation in the network retrieves y . Algorithms BIB001 BIB002 , described above, are claimed to store the number N of vectors (generated from their respective data models) exponential in D ( () D Oa , 1 a > ) with the possibility of correcting a number of random errors that is linear in the vector dimension, D . However, to ensure a high probability of retrieval, a graph with a certain structure must be obtained, which is not guaranteed by the learning algorithms used. NAMs based on sparse recovery algorithms. To create autoassociative memory on the basis of a bipartite graph, in BIB003 BIB004 they use connection matrices W which allow them to reconstruct a sparse noise vector e which additively distorts the vector y of the base to form the query vector x . Then the required base vector is obtained as =-yxe . The noise vector is calculated using sparse recovery methods (that is, methods that find the solution vector with the least number of non-zero components). These methods require knowledge of the linear constraints matrix W such that 0 = Wy for all vectors y of the base. For some models of vectors (i.e. constraints or generative processes for the base vectors), such W can be obtained in polynomial time from the base of vectors generated by the model. In contrast to BIB001 BIB002 , finding W is guaranteed with high probability, and adversarial rather than random errors are used as noise. In BIB003 ££ . Both models allow for accurate recovery from vectors with significant noise. In BIB004 , as in BIB002 , the vectors of the base are from a subspace defined by sparse linear constraints. They consider both real-valued vectors and binary vectors from {1,1} D -+ satisfying W models of a certain type (sparse-subGaussian model). Learning is based on solving the dictionary learning problem with a square dictionary BIB004 . An iterative retrieval algorithm uses the fact that W is an expander graph with good properties BIB004 . The memory capacity and resistance to distortion is increased relative to BIB003 . Note the drawback of the methods considered in this section is that bases of real data may not correspond to the data models used.