Sparse Distributed Memory
Retrieval & Ranking Systems DS practice problem on Onlearn.
Difficulty: medium.
Topics: Sparse Distributed Memory, Hamming Distance Thresholding, Superposition of Patterns, Focusing Mechanism, Hard Location Addressing, Write-Read Cycle Dynamics, Associative Memory Models, High-Dimensional Geometry, Information Retrieval Systems, Neural Network Architectures, Computational Neuroscience, Hyperdimensional Computing, Content-Addressable Storage, Sparse Vector Representations, Similarity-Based Retrieval, Distributed Representation Learning.
Implement a Sparse Distributed Memory (SDM) system, a content addressable memory model that operates on high dimensional binary vectors. SDM stores and retrieves binary patterns using a set of randomly placed 'hard locations' in the address space. When writing, all hard locations within a certain Hamming distance (the activation radius) of the target address have their integer counters updated. When reading, the counters of all activated locations are summed and thresholded to produce a binary output. Implement a class SparseDistributedMemory with the following: init (self, address length, word length, num hard locations, activation radius, seed=42): Initialize the memory. Use np.random.RandomState(seed) to generate num hard locations random binary address vectors (each of length address length). Initialize an integer counter matrix of shape (num hard locations, word length) to zeros. write(self, address, word): Given a binary address and a binary word (both as lists or arrays of 0s and 1s), find all hard locations within the activation radius (Hamming distance <= radius), and for each activated location, increment the counter by +1 for each bit that is 1 in the word and decrement by 1 for each bit that is 0. Return the number of activated locations as an integer. read(self, address): Given a binary address, find all activated hard locations, sum their counter vectors element wise, and threshold the result: non negative sums map to 1, negative sums map to 0. Return the result as a list of integers. If no locations are activated, return a list of zeros of length word length.