Associative Memory using Dictionary Learning and Expander Decoding
This work addresses the challenge of robust content-addressable memory for neural networks, offering a solution with high capacity and error tolerance, though it appears incremental in its approach.
The paper tackles the problem of designing neural associative memories that can store exponentially many message vectors and correct a large number of adversarial errors, achieving storage of exp(n) n-length vectors with O(n) nodes and tolerance of Ω(n/polylog n) errors.
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 $Ω(\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.