High Order Neural Networks for Efficient Associative Memory Design

Gérard Dreyfus, Isabelle Guyon, Jean-Pierre Nadal, Léon PersonnazNeurIPS 1987

This foundational 1988 paper by Guyon et al. explores how to make associative memories—systems designed to "complete" a pattern or sequence from a partial or noisy input—more powerful and efficient. By introducing multi-neuron interactions, the authors demonstrate a dramatic increase in storage capacity and the ability to process complex temporal sequences.

The Problem with Standard Associative Memory

In the late 1980s, the Hopfield model was the gold standard for associative memory. However, it suffered from three major limitations:

  1. Low Capacity: The network could only store a small number of patterns relative to the number of neurons ($n$). Attempting to store too many patterns caused the memory landscape to become "blurry," leading to retrieval failures.
  2. Linear Limitations: Standard networks struggled to classify data that was not linearly separable, famously failing on the classic XOR problem.
  3. Sequence Struggles (Bifurcations): They could not handle complex temporal sequences where the same state might lead to two different outcomes depending on the context. For example, in a sequence like A -> B -> C and D -> B -> E, a standard network gets "stuck" at B because it lacks the historical context to know whether to proceed to C or E.

The authors sought a method to circumvent these limitations without triggering the explosive growth of synaptic coefficients that typically accompanies added network complexity.

Methods: High-Order Interactions

The core innovation of this paper is the introduction of high-order interactions.

  • Standard Model: A neuron's state is determined by the weighted sum of its individual neighbors: $v_i = \sum C_{ij} \sigma_j$.
  • High-Order Model: A neuron's state is determined by pairs, triplets, or larger combinations of other neurons: $v_i = \sum C_{ij} \sigma_j + \sum C_{i,jl} \sigma_j \sigma_l$.

By treating these products of states as a new, higher-dimensional vector, the authors apply a pseudoinverse learning rule (the projection matrix method). This ensures that the desired patterns become stable "attractors" in the network's energy landscape.

To handle temporal sequences and bifurcations, they introduce a "memory span." Instead of the network only looking at its current state ($t$) to decide the next state ($t+\tau$), it evaluates a concatenation of its current state and its previous state ($t-\tau$). This historical context disambiguates overlapping paths in a sequence.

Key Insights

  • Capacity Scaling: By moving to three-neuron interactions, the storage capacity jumps from being proportional to the number of neurons ($O(n)$) to the square of the neurons ($O(n^2)$).
  • The "Squaring" Trick: The authors identify a clever mathematical shortcut: if all possible second-order interactions are used, the potential can be calculated simply by squaring matrix coefficients. This is highly computationally efficient and was particularly well-suited for optical computing hardware being researched at the time.
  • Local Learning: While the pseudoinverse is a global calculation, the authors demonstrate that a local, iterative Widrow-Hoff (Delta) rule can achieve the same results, making the model more biologically plausible.

Experimental Results

The paper evaluates the model using two primary datasets: synthetic random binary patterns ($n=30$ neurons) to measure the "basins of attraction," and a "Poem" dataset ($n=48$ neurons) to test complex temporal sequences.

Enhanced Attractivity and Capacity

In simulations with $n=30$ neurons, a standard projection network failed to recall patterns accurately once the number of stored patterns ($p$) reached the number of neurons ($n$). However, by utilizing high-order interactions, the network maintained nearly perfect recall even when the number of patterns was double the number of neurons ($p/n \approx 2$).

Recall performance as a function of network capacity

Sequence Retrieval

To test temporal sequences, the authors stored a large number of poems, including the French nursery rhyme "Alouette." This involved 424 elementary transitions, with each state representing 8 letters encoded in 6-bit codes.

Even when initialized with a heavily corrupted version of the first two lines, the network's high-order memory span allowed it to "snap" back to the correct stored sequence and recite the poem perfectly.

The network successfully retrieves the 'Alouette' poem sequence, correcting a heavily corrupted initial input.

Limitations and Future Work

While groundbreaking, the authors acknowledged several limitations:

  • Combinatorial Explosion: Using all possible high-order interactions creates a massive number of synapses. While they suggest using "subsets" of interactions, they do not provide a definitive algorithm for selecting the optimal subsets for a given problem.
  • Hardware Constraints: Simulating these networks on 1988-era conventional computers was slow. The authors pointed toward optical implementations as a more promising avenue for high-order neural hardware.
  • Scaling: The examples provided (random bits and short text) are relatively small-scale, leaving the full derivation for larger, structured problems to future research.

Summary updated

BibTeX
@inproceedings{dreyfus1987high,
  author = {Gérard Dreyfus and Isabelle Guyon and Jean-Pierre Nadal and Léon Personnaz},
  title = {{High Order Neural Networks for Efficient Associative Memory Design}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1987},
}
Figure