Improving the computational effciency, accuracy, and applicability of clustered sparse associative memories

An associative memory, unlike conventional memory systems, is a device or data structure that maps input-output patterns directly, without the need to construct an explicit address before retrieving the information content. The retrieval complexity grows in the data dimension, independent of the amount of data stored. Recently Gripon and Berrou propose a new type called clustered sparse associative memory (CSAM), which adopts a particular sparse encoding and non-linear iterative retrieval algorithms. The construct, extremely resilient to noise and errors, is able to store and reliably retrieve considerably more messages than other models.This thesis comprises three main parts. First, we implement the CSAM network on a graphic processing unit (GPU), together with two existing retrieval algorithms. We study the convergence properties of both algorithms, tailoring a novel retrieval process to take full advantage of the GPU's massive parallelism, which results in an 880 times acceleration improvement without any loss of accuracy. Second, we discover a previously overlooked problem that the state-of-the-art retrieval algorithm in the literature leads the network to premature local minima called bogus fixed points. Heuristic solutions are proposed. A novel post-processing algorithm, which involves identifying the maximal cliques in a graph, is also developed. By applying these, we manage to reduce the retrieval error significantly. Last, we develop five different approaches, extending the use of the CSAM network so that not only completing the partial messages as in previous studies but also correcting erroneous probes are both supported. The applicability and feasibility of the CSAM network are greatly enhanced.Une mémoire associative, contrairement aux systèmes de mémoire conventionnels, est un dispositif ou une structure de données qui associe des motifs d'entrée et de sortie directement sans avoir besoin de construire une adresse explicite avant de récupérer le contenu de l'information mémorisée. La complexité de récupération augmente avec la dimension des données et indépendante de la quantité de données mémorisées. Récemment Gripon et Berrou ont proposé un nouveau type de mémoire associative dénommé mémoire associative parcimonieuse groupée, en anglais clustered sparse associative memory (CSAM), qui tire parti d'un encodage parcimonieux et d'algorithmes de récupération non-linéaires itératifs. Ce modèle, extrêmement résilient aux bruits et erreurs, est capable de mémoriser et récupérer fidèlement significativement plus de messages que les modèles alternatifs.Cette thèse comprend trois parties principales. D'abord nous implémentons le réseau CSAM sur une carte graphique (GPU) avec deux autres algorithmes de récupération préexistants. Nous étudions les propriétés de convergence des deux algorithmes et adaptons un nouveau procédé de récupération afin de tirer parti de l'important parallélisme du GPU ce qui culmine en une accélération de la performance par un facteur de 880 sans perte de précision. Deuxièmement, nous découvrons un problème auparavant ignoré: l'algorithme de récupération qui est l'état de l'art dans la littérature mène le réseau à des minimums locaux prématurés dénommés points fixes erronés. Des solutions heuristiques sont proposées. Un nouvel algorithme de post-traitement qui inclut la découverte des cliques maximales d'un graphe est aussi entièrement conçu. En appliquant ces solutions et cet algorithme, nous réduisons avec succès les erreurs de récupération par une énorme marge. Finalement, nous développons cinq approches différentes qui étendent l'utilisation du réseau CSAM de telle sorte que compléter des messages partiels, comme dans certaines études précédentes, et corriger des sondes erronées sont supportés. L'applicabilité et la faisabilité du réseau CSAM s'en voient fortement améliorées