A Caltech Library Service

On the Uncertainty of Information Retrieval in Associative Memories

Yaakobi, Eitan and Bruck, Jehoshua (2019) On the Uncertainty of Information Retrieval in Associative Memories. IEEE Transactions on Information Theory, 65 (4). pp. 2155-2165. ISSN 0018-9448.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We (people) are memory machines. Our decision processes, emotions, and interactions with the world around us are based on and driven by associations to our memories. This natural association paradigm will become critical in future memory systems, namely, the key question will not be “How do I store more information?” but rather, “Do I have the relevant information? How do I retrieve it?” The focus of this paper is to make a first step in this direction. We define and solve a very basic problem in associative retrieval. Given a word W, the words in the memory that are t-associated with W are the words in the ball of radius t around W. In general, given a set of words, say W, X and Y, the words that are t-associated with {W, X, Y} are those in the memory that are within distance t from all the three words. Our main goal is to study the maximum size of the t-associated set as a function of the number of input words and the minimum distance of the words in memory - we call this value the uncertainty of an associative memory. In this work we consider the Hamming distance and derive the uncertainty of the associative memory that consists of all the binary vectors with an arbitrary number of input words. In addition, we study the retrieval problem, namely, how do we get the t-associated set given the inputs? We note that this paradigm is a generalization of the sequences reconstruction problem that was proposed by Levenshtein (2001). In this model, a word is transmitted over multiple channels. A decoder receives all the channel outputs and decodes the transmitted word. Levenshtein computed the minimum number of channels that guarantee a successful decoder - this value happens to be the uncertainty of an associative memory with two input words.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemConference Paper
Yaakobi, Eitan0000-0002-9851-5234
Additional Information:© 2018 IEEE. This research was supported in part by the ISEF Foundation, the Lester Deutsch Fellowship, the National Science Foundation under Grant CCF-1116739, and the NSF Expeditions in Computing Program under grant CCF-0832824. Part of the results in the paper were presented at the IEEE International Symposium on Information Theory, Cambridge, MA, July 1 – 6, 2012. The authors thank Tuvi Etzion for helpful discussions on anticodes. They also thank the three anonymous reviewers and the associate editor Joerg Kliewer for their valuable comments and suggestions, which have contributed for the clarity of the paper and its presentation.
Funding AgencyGrant Number
Lester Deutsch FoundationUNSPECIFIED
Subject Keywords:Associative memories, reconstruction of sequences, list decoding, anticodes
Record Number:CaltechAUTHORS:20181101-121348346
Persistent URL:
Official Citation:E. Yaakobi and J. Bruck, "On the Uncertainty of Information Retrieval in Associative Memories," in IEEE Transactions on Information Theory, vol. 65, no. 4, pp. 2155-2165, April 2019. doi: 10.1109/TIT.2018.2878750
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:90571
Deposited By: George Porter
Deposited On:01 Nov 2018 19:45
Last Modified:20 Mar 2019 17:14

Repository Staff Only: item control page