Source-linked AI summary
Associative Long Short-Term Memory
Ivo Danihelka, Greg Wayne, Benigno Uria, Nal Kalchbrenner, Alex Graves
TL;DR
LSTM is limited by parameter growth with memory size and lacks indexed writing and reading for associative data structures. The paper combines LSTM with complex-valued holographic key-value memory and redundant copies, reporting faster learning on multiple memorization tasks while acknowledging capacity-flexibility and noise trade-offs.
Problem
LSTM memory size is tied to recurrent matrix size and lacks a mechanism to index memory while writing and reading.
Method
Associative LSTM combines LSTM with complex-valued holographic key-value storage, using randomly permuted redundant copies and associative read-write operations.
Results
Associative LSTM learned memorization tasks faster than LSTM in the reported copy-task comparison and solved the variable-length copy task quickly.
Takeaways & Limitations
The architecture provides flexible associative storage and retrieval with larger capacity than LSTM without larger weight matrices, and its updates can exactly emulate LSTM.
Takeaways & Limitations
Multiple copies performed poorly on the addition task because the architecture read only one value at a time, creating a capacity-flexibility trade-off.
Abstract
from arXiv · showhide
We investigate a new method to augment recurrent neural networks with extra memory without increasing the number of network parameters. The system has an associative memory based on complex-valued vectors and is closely related to Holographic Reduced Representations and Long Short-Term Memory networks. Holographic Reduced Representations have limited capacity: as they store more information, each retrieval becomes noisier due to interference. Our system in contrast creates redundant copies of stored information, which enables retrieval with reduced noise. Experiments demonstrate faster learning on multiple memorization tasks.
1. Introduction
Associative LSTM addresses LSTM’s parameter-scaling and memory-indexing limitations by combining LSTM with holographic key-value storage and redundant representations. The resulting associative memory stores data without discrete locations and supports larger memory without increasing network parameters.
- LSTM memory size is tied to recurrent weight matrices and scales as O(N_h^2) for N_h memory cells.
- LSTM lacks a mechanism to index memory while writing and reading, limiting its suitability for common data structures such as arrays.
- Associative LSTM combines LSTM with Holographic Reduced Representations to store key-value pairs in distributed vectors without locations.
- Redundant storage copies increase memory capacity and reduce retrieval noise compared with direct holographic storage.
- The system provides large memory without increasing network parameters, and experiments evaluate learning speed and accuracy.
2. Background
Holographic Reduced Representations encode key-value pairs by binding vectors into a fixed-size memory trace and retrieving values with inverse-like key operations. Retrieval is exact for the target value apart from interference noise from other stored items.
- Holographic Reduced Representations represent an associative array as the sum of bound key-value pairs in a fixed-size vector.
- Complex-space binding multiplies vector moduli element-wise and adds their phases.
- To retrieve a value, the memory trace is multiplied element-wise by the associated key inverse.
- Retrieval returns the target value plus a noise term whose mean is zero when key phases are randomly distributed.
- Using the complex conjugate instead of the exact inverse avoids magnifying the noise term through inverse key moduli.
3. Redundant Associative Memory
Redundant associative memory reduces holographic retrieval noise by storing multiple randomly permuted copies and averaging restored copies. Its retrieval error rises with stored items but falls with copies, while copies can be adjusted to trade capacity against noise.
- Retrieval noise grows as the number of stored items increases, motivating redundancy whose copy count scales with item count.
- The memory stores multiple transformed copies of each input and averages the restored copies during retrieval.
- Random permutations decorrelate retrieval noise across copies, enabling incoherent noise averaging.
- More copies reduce noise in retrieved ImageNet image sequences, as illustrated by comparisons using 1, 4, and 20 copies.
- 50 copies with stored-image counts from 1 to 100 produce mean squared error that grows linearly, while scaling copies with items keeps error almost constant after 50 copies.
- Increasing copies enlarges capacity, whereas reducing copies increases retrieval noise; more items than copies remain possible at higher noise.
- The memory supports partially known keys and does not require searching for free locations when writing.
4. Long Short-Term Memory
LSTM maintains a hidden state and cell state, updating them at each time step through gated recurrent computations.
- LSTM represents its hidden state with two parts, ht and ct, both in R^Nh.
- The network updates its state from the current input xt and the previous hidden state through recurrent transformations.The update uses input-to-hidden and hidden-to-hidden weight matrices plus a bias vector.
- The forget, input, and output gates are logistic-sigmoid variables controlling cell-state updating and hidden-state output.The proposed cell-state update is denoted u, and ⊙ indicates element-wise multiplication.
5. Associative Long Short-Term Memory
Associative LSTM augments LSTM with complex-valued associative keys and redundant memory copies, while retaining parallelizable updates and averaged retrieval.
- The model bounds the modulus of each complex number between 0 and 1 before constructing the update and two keys.The hard modulus bound performed slightly better than applying tanh to the modulus.
- The input key ri stores information in the associative array, the output key ro retrieves it, and the gated update supplies the stored value.The update u is multiplied by the input gate gi before storage.
- Each redundant copy receives the same key-value pair using a copy-specific permuted input key and element-wise complex multiplication.Each permutation matrix is constant, random, and specific to one copy.
- The output key for each copy is permuted consistently with that copy’s input key, and memory traces are read out by averaging copies.Permutation costs O(Nh) computations, and all copies can be updated in parallel.
- On selected tasks, setting Whu to zero improved learning speed by making the update u serve as an embedding of xt.This modification was used for episodic copy, XML modeling, and variable assignment tasks.
6. Experiments
Experiments compare Associative LSTM with LSTM, Permutation RNN, Unitary RNN, and related baselines across memorization and sequence tasks. Associative LSTM generally learned quickly, with redundant copies improving XML performance while preserving parameter efficiency.
- Experimental setup: Associative LSTM uses an associative memory integrated with LSTM, while the compared baselines include LSTM, Permutation RNN, Unitary RNN, and a multiplicative Unitary RNN.The experiments also compare network sizes on the episodic copy task.
- Episodic copy: The fixed-length copy task requires storing 10 random characters across 100 blanks before reproducing them after a delimiter.Associative LSTM solved it much faster than LSTM, although Permutation RNN and Unitary RNN were fastest; redundancy provided no benefit because few symbols were stored.
- Episodic copy: Associative LSTM solved the variable-length copy task quickly, whereas Unitary RNN performance was compromised relative to the fixed-length task.The sequence length was uniformly variable from 1 to 10 characters, and Associative LSTM learned almost as quickly as on fixed-length copy.
- XML modeling: Associative LSTM’s XML advantage increased with redundant copies, and four copies learned significantly faster than a 512-cell LSTM with the same number of cells.A single-copy 128-unit Associative LSTM also greatly outperformed a 128-unit LSTM, which appeared unable to store enough characters.
- Additional comparisons: Associative LSTM performed comparably to LSTM, and its update can exactly reproduce a conventional LSTM cell update under a specified input-key setting.The authors therefore describe Associative LSTM as at least as general as LSTM.
7. Why use complex numbers?
Complex-valued keys offer a flexible representation, while matrix-valued keys are possible but can make retrieval slow and numerically unstable.
- The system uses complex-valued vectors as associative-memory keys.A matrix-valued key is an alternative, with complex multiplication replaced by matrix multiplication.
- Matrix-valued keys require premultiplication by A−1 during retrieval, which is generally slow and potentially numerically unstable.
8. Conclusion
The conclusion presents redundant associative memory with multiple read-write heads as a high-capacity, flexible recurrent-memory component that does not require larger weight matrices.
- Redundant associative memory provides flexible associative storage and retrieval, high capacity, and parallel memory access.
- Associative LSTM has greater capacity than LSTM without introducing larger weight matrices.
- Its update equations can exactly emulate LSTM, making the architecture more general and usable wherever LSTM is.
A. Comparison with a Neural Turing Machine
On XML, variable assignment, and arithmetic tasks, Associative LSTM and the Neural Turing Machine both achieved good performance, while Associative LSTM learned more stably.
- The comparison used the same network architecture for Associative LSTM and the Neural Turing Machine across XML, variable assignment, and arithmetic tasks.Network sizes are reported in Table 3.
- Both Associative LSTM and the Neural Turing Machine achieved good performance on the three tasks.
- Associative LSTM showed more stable learning progress than the Neural Turing Machine.Training used minibatches of size 1 for comparison with the original Neural Turing Machine; other minibatch sizes produced similar learning curves.
- The Neural Turing Machine had previously shown better generalization to longer sequences on algorithmic tasks.
- The learning curves for the XML, variable assignment, and arithmetic tasks are shown in Figures 11–13.The figures plot training cost against minibatch number, with cost measured per character in bits.