The Capacity of Sparsely Encoded Associative Memories


IEICE TRANSACTIONS on Information and Systems   Vol.E76-D    No.3    pp.360-367
Publication Date: 1993/03/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Bio-Cybernetics
associative memory,  capacity,  sparse encoding,  exchangeable random variables,  

Full Text: PDF>>
Buy this Article

We consider an asymptotically sparsely encoded associative memory. Patterns are encoded by n-dimensional vectors of 1 and 1 generated randomly by a sequence of biased Bernoulli trials and stored in the network according to Hebbian rule. Using a heuristic argument we derive the following capacities:c(n)ne/4k log n'C(n)ne/4k(1e)log n'where, 0e1 controls the degree of sparsity of the encoding scheme and k is a constant. Here c(n) is the capacity of the network such that any stored pattern is a fixed point with high probability, whereas C(n) is the capacity of the network such that all stored patterns are fixed points with high probability. The main contribution of this technical paper is a theoretical verification of the above results using the Poisson limit theorems of exchangeable events.