Neural Distributed Autoassociative Memories: A Survey <s> NAMs WITH A BIPARTITE GRAPH STRUCTURE FOR NONBINARY DATA WITH CONSTRAINTS <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> NAMs WITH A BIPARTITE GRAPH STRUCTURE FOR NONBINARY DATA WITH CONSTRAINTS <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> NAMs WITH A BIPARTITE GRAPH STRUCTURE FOR NONBINARY DATA WITH CONSTRAINTS <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> NAMs WITH A BIPARTITE GRAPH STRUCTURE FOR NONBINARY DATA WITH CONSTRAINTS <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
In some recent papers (e.g., BIB001 BIB002 BIB003 BIB004 ), in order to create NAMs which can store and retrieve (from rather noisy input vectors) the number N of (not always binary) vectors with N near exponential in D , the vectors considered are not arbitrary random but satisfy (linear) constraints. The neural network has the structure of a bipartite graph. One set of neurons (not connected with each other) is used to represent the vectors of the base, neurons of the other set represent constraints. A rectangular matrix of connections between these two sets is learned on the vectors of the base. The connection vector of each constraint neuron represents the vector of that particular constraint. Iterative algorithms with local neuron computations are used for retrieval. Iterative algorithms for learning constraint matrix and vector recovery . In BIB001 BIB002 , they consider the problem of the exact retrieval (with high probability) of vectors that belong to a subspace of dimension less than D . The graded weights of the bipartite graph connections representing linear constraints are learned from the vectors of the base (which have only non-negative integer components). Iterative algorithms are used for learning. The weights are constrained to be sparse, which is required for analyzing the retrieval algorithm. The input (query) vectors x are obtained from the vectors y of the base by additive noise: =+ xye , where e are random sparse vectors with (bipolar) integer components. During retrieval, activity propagates first from the data neurons to the constraint neurons and then in the opposite direction, and so on for multistep retrieval. Non-linear transformations are used in neurons. In a stable state, the data neurons represent a base vector, and all constraint neurons obtain a total weighted zero input from the associated data neurons. In BIB001 the vectors are divided into intersecting parts. Any part of the vector belongs to a subspace of smaller dimension than the vector dimension of that part. А subset of the constraint neurons corresponds to each part. They are not looking for an orthogonal basis of constraints, but for vectors orthogonal to the corresponding parts of the data vectors from the base: