Storing sequences in binary tournament-based neural networks

Xiaoran Jiang, Vincent Gripon, Claude Berrou, Michael G. Rabbat

Abstract

An extension to a recently introduced architecture of clique-based neural networks is presented. This extension makes it possible to store sequences with high efficiency. To obtain this property, network connections are provided with orientation and with flexible redundancy carried by both spatial and temporal redundancy, a mechanism of anticipation being introduced in the model. In addition to the sequence storage with high efficiency, this new scheme also offers biological plausibility. In order to achieve accurate sequence retrieval, a double layered structure combining hetero-association and auto-association is also proposed.

Introduction

Traditional neural network architectures, such as Hopfield networks, frequently encounter the problem of "catastrophic interference," where learning new information leads to the rapid degradation of previously stored memories. While sparse binary "clique-based" networks have successfully addressed this issue for static patterns, they lack an inherent mechanism to manage temporal data. This paper introduces an extension to the clique-based model designed for the highly efficient storage and retrieval of sequential information. By incorporating directed connections and a dual-layer architecture, the proposed system achieves high memory capacity while maintaining biological plausibility.

Methods

The proposed model builds upon the clique-based neural network architecture, where information is represented as fully connected sets of nodes within clusters. The primary innovation is the transition from undirected edges to directed "tournaments." In graph theory, a tournament is a directed graph in which every pair of distinct nodes is connected by exactly one directed edge. By organizing these tournaments into chains, the network gains the ability to represent temporal order.

Comparison of undirected clique (left) and directed tournament (right) structures for sequence encoding.

To improve robustness against noise and prevent error propagation, the authors implement an "anticipation mechanism" with a degree $r$. During sequence retrieval, the network considers the $r$ previous items to predict the next step, providing significant temporal redundancy. Furthermore, a double-layered architecture is employed to halt the "avalanche of errors." The lower layer utilizes tournament-based hetero-association to predict subsequent states, while the upper layer uses clique-based auto-association to clean and complete the current pattern. This structure functionally mirrors the interaction between the dentate gyrus and the CA3 region of the hippocampus.

Results

The network's performance was evaluated using synthetically generated random sparse sequences to measure capacity and the Message Retrieval Error Rate (MRER). Simulations demonstrate that the architecture possesses high storage capacity; for example, a network with 6,400 nodes can store approximately 700 sequences of length 100, representing roughly 13.2 Mbits of information.

Message Retrieval Error Rate (MRER) as a function of stored messages for various graph topologies.

The dual-layer approach significantly outperformed single-layer configurations in terms of Pattern Error Rate (PER). The authors also derived a formula for optimal clustering ($\chi_{opt} \approx n^2 / eSL$), which serves as a design guideline for balancing memory load and network size. Despite the added complexity of directed edges required for biological plausibility, the network remains efficient, achieving 20-30% efficiency in practical scenarios.

Discussion and Future Work

The study demonstrates that adding orientation to connections allows clique-based networks to inherit high-capacity properties for sequential data. However, the system's retrieval performance is sensitive to the choice of activation threshold ($\theta$). Future research could explore "intelligent training" methods for self-adjusting thresholds and mechanisms for associating or switching between different stored sequences. Additionally, the authors propose a four-level hierarchical structure to scale the system for more complex data processing tasks.

Summary updated

Abstract

An extension to a recently introduced architecture of clique-based neural networks is presented. This extension makes it possible to store sequences with high efficiency. To obtain this property, network connections are provided with orientation and with flexible redundancy carried by both spatial and temporal redundancy, a mechanism of anticipation being introduced in the model. In addition to the sequence storage with high efficiency, this new scheme also offers biological plausibility. In order to achieve accurate sequence retrieval, a double layered structure combining hetero-association and auto-association is also proposed.
BibTeX
@article{jiang2016storing,
  author = {Xiaoran Jiang and Vincent Gripon and Claude Berrou and Michael G. Rabbat},
  title = {{Storing sequences in binary tournament-based neural networks}},
  journal = {IEEE Trans. Neural Networks Learn. Syst.},
  year = {2016},
  url = {https://openreview.net/forum?id=cYMCrxtbWJx},
}

Loading related content...

Figure