Generalized Connectionist Associative Memory

Nigel P. Duffy, Arun K. JagotaIJCAI 1999

Abstract

This paper presents an evolution of the classic Hopfield network designed to store "gtuples"—tuples where each component is a set of values. This generalization provides a mathematical framework to ensure stable storage of complex patterns found in bioinformatics and computer vision. By recoding data into "k-uniform" gtuples, the model guarantees that stored patterns are stable fixed points. The system excels at novelty detection in protein sequences and noise removal in handwritten digits, offering improved representation efficiency over standard binary models.

Introduction

Standard associative memories, such as the original Hopfield network, are typically restricted to storing vectors of binary or real-valued scalars. While effective for simple pattern completion, these models struggle with the multi-modal data often found in fields like bioinformatics. For instance, a protein consensus sequence might specify that multiple different amino acids are valid at a single position. Representing this ambiguity as a simple scalar leads to information loss. Duffy and Jagota address this by introducing a connectionist model that handles "gtuples" (tuples of sets) while maintaining the "stable storage property," ensuring that saved patterns are not immediately forgotten or warped by the network's dynamics.

Methodology

The authors propose a graph-based recurrent network where vertices represent unique (symbol, position) pairs. For example, a vertex might represent the presence of "Leucine at position 10."

Storage and the Multipartite Structure

To store a gtuple, the model adds edges between all symbols within that gtuple across different positions, creating a multipartite clique structure. This structure allows the network to represent complex relationships between sets of symbols natively.

Graph-based representation of a gtuple associative memory illustrating the multipartite structure and connections between symbol-position pairs.

Ensuring Stability

A significant challenge in neural associative memory is the emergence of unstable patterns. To solve this, the authors employ a "k-uniform" trick: arbitrary data is recoded into gtuples where every position has exactly $k$ symbols (using "dummy" symbols for padding where necessary). This mathematical constraint ensures that every stored pattern becomes a guaranteed fixed point in the network. This graph is then mapped to a Hopfield-type network where missing edges are assigned high negative weights to inhibit invalid states.

Experimental Evaluation

The model was tested on two distinct tasks:

  1. Bioinformatics: A dataset of 3,202 protein blocks converted into generalized consensus sequences over a 20-letter amino acid alphabet.
  2. Image Processing: 60,000 binary images of handwritten digits ($28 \times 28$ pixels). Each image was treated as a gtuple where each column represented a position, and the black pixels in that column formed the set for that position.

Results and Discussion

Novelty Detection

In the protein sequence task, the model was used to identify sequences that did not match the stored biological patterns. When sequences were distorted by replacing amino acids with random symbols (with probability $p$), the model effectively flagged them as "novel." As shown in the experimental results, the novelty score increased linearly with the amount of distortion, providing a reliable metric for biological plausibility.

The average novelty score increases linearly as the distortion probability p increases, demonstrating the model's reliability in detecting non-biological sequences.

Noise Removal and Efficiency

On the handwritten digit task, the model's noise-removal algorithm successfully cleaned up approximately 50% of added random noise. Furthermore, the authors noted that the model is highly efficient; only about 1/6th of the neurons are active for any given memory, making the network less crowded and more scalable than standard binary Hopfield nets.

Limitations

The primary limitation identified is the emergence of "spurious memories"—ghost fixed points that are combinations of real memories. While the model is excellent for novelty detection and noise removal, these spurious states make full pattern reconstruction difficult on very large datasets.

Conclusion

The generalized connectionist associative memory offers a robust framework for handling complex, set-based data. By moving from scalars to gtuples, the model provides a more natural representation for bioinformatics and image data while maintaining mathematical guarantees for stability. Future work will focus on more sophisticated distance metrics to better separate real memories from spurious ones.

Summary updated

BibTeX
@inproceedings{duffy1999generalized,
  author = {Nigel P. Duffy and Arun K. Jagota},
  title = {{Generalized Connectionist Associative Memory}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure