In this paper we analyze and extend the neural network based associative memory proposed by Gripon and Berrou. This associative memory resembles the celebrated Will- shaw model with an added partite cluster structure. In the literature, two retrieving schemes have been proposed for the network dynamics, namely SUM-OF-SUM and SUM-OF-MAX. They both offer considerably better performance than Willshaw and Hopfield networks, when comparable retrieval scenarios are considered. Former discussions and experiments concentrate on the erasure scenario, where a partial message is used as a probe to the network, in the hope of retrieving the full message. In this regard, SUM-OF-MAX outperforms SUM-OF-SUM in terms of retrieval rate by a large margin. However, we observe that when noise and errors are present and the network is queried by a corrupt probe, SUM-OF-MAX faces a severe limitation as its stringent activation rule prevents a neuron from reviving back into play once deactivated. In this manuscript, we categorize and analyze different error scenarios so that both the erasure and the corrupt scenarios can be treated consistently. We make an amendment to the network structure to improve the retrieval rate, at the cost of an extra scalar per neuron. Afterwards, five different approaches are proposed to deal with corrupt probes. As a result, we extend the network capability, and also increase the robustness of the retrieving procedure. We then experimentally compare all these proposals and discuss pros and cons of each approach under different types of errors. Simulation results show that if carefully designed, the network is able to preserve both a high retrieval rate and a low running time simultaneously, even when queried by a corrupt probe.
Gripon and Berrou propose the network structure in @cite_4 . @cite_8 , they show that using the same amount of storage, CSAMs outperform Hopfield networks in diversity (the number of patterns a network can store for a targeted performance), capacity (the maximum amount of stored information in bits for a targeted performance) and efficiency (the ratio between capacity and the amount of information in bits consumed by the network when capacity reaches its maximum) simultaneously. They later interpret CSAMs using the formalism of error correcting codes @cite_21 and propose a new decoding scheme called , which significantly decreases retrieval error. Jiang al @cite_20 modify CSAMs to store long sequences by incorporating directed links. Aboudib al @cite_11 extend the structure so that messages of different lengths can be stored in the same network. They also summarize criteria to build possible retrieving schemes and study the number of iterations required by each scheme. Yao al @cite_22 discover a previously overlooked problem that the network may converge to a bogus fixed point and propose heuristics to mitigate the issue. A novel post-processing algorithms is also developed, customized to the partite structure of CSAMs, which brings notably better retrieval rates than the standard scheme.
@cite_4 @cite_22 @cite_8 @cite_21 @cite_20 @cite_11
2106169150 1666036116 2121160181 2086523057 2611060325 2964027214
Associative memories are devices that are able to learn messages and to recall them in presence of errors or erasures. Their mechanics is similar to that of error correcting decoders. However, the role of correlation is opposed in the two devices, used as the essence of the retrieval process in the first one and avoided in the latter. In this paper, original codes are introduced to allow the effective combination of the two domains. The main idea is to associate a clique in a binary neural network with each message to learn. The obtained performance is dramatically better than that given by the state of the art, for instance Hopfield Neural Networks. Moreover, the model proposed is biologically plausible; it uses sparse binary connections between clusters of neurons provided with only two operations: sum and selection of maximum. The Gripon-Berrou neural network (GBNN) is a recently invented recurrent neural network embracing a LDPC-like sparse encoding setup which makes it extremely resilient to noise and errors. A natural use of GBNN is as an associative memory. There are two activation rules for the neuron dynamics, namely sum-of-sum and sum-of-max. The latter outperforms the former in terms of retrieval rate by a huge margin. In prior discussions and experiments, it is believed that although sum-of-sum may lead the network to oscillate, sum-of-max always converges to an ensemble of neuron cliques corresponding to previously stored patterns. However, this is not entirely correct. In fact, sum-of-max often converges to bogus fixed points where the ensemble only comprises a small subset of the converged state. By taking advantage of this overlooked fact, we can greatly improve the retrieval rate. We discuss this particular issue and propose a number of heuristics to push sum-of-max beyond these bogus fixed points. To tackle the problem directly and completely, a novel post-processing algorithm is also developed and customized to the structure of GBNN. Experimental results show that the new algorithm achieves a huge performance boost in terms of both retrieval rate and run-time, compared to the standard sum-of-max and all the other heuristics. 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. A new family of sparse neural networks achieving nearly optimal performance has been recently introduced. In these networks, messages are stored as cliques in clustered graphs. In this paper, we interpret these networks using the formalism of error correcting codes. To achieve this, we introduce two original codes, the thrifty code and the clique code, that are both sub-families of binary constant weight codes. We also provide the networks with an enhanced retrieving rule that enables a property of answer correctness and that improves performance. An original architecture of oriented sparse neural networks that enables the introduction of sequentiality in associative memories is proposed in this paper. This architecture can be regarded as a generalization of a recently proposed non oriented binary network based on cliques. Using a limited neuron resource, the network is able to learn very long sequences and to retrieve them only from the knowledge of some consecutive symbols. Associative memories are data structures addressed using part of the content rather than an index. They offer good fault reliability and biological plausibility. Among different families of associative memories, sparse ones are known to offer the best efficiency (ratio of the amount of bits stored to that of bits used by the network itself). Their retrieval process performance has been shown to benefit from the use of iterations. We introduce several families of algorithms to enhance the performance of the retrieval process inrecently proposed sparse associative memories based on binary neural networks. We show that these algorithms provide better performance than existing techniques and discuss their biological plausibility. We also analyze the required number of iterations and derive corresponding curves.