Part of Neural Information Processing Systems 0 (NIPS 1987)
Philip Chou
The capacity of an associative memory is defined as the maximum
number of vords that can be stored and retrieved reliably by an address vithin a given sphere of attraction. It is shown by sphere packing arguments that as the address length increases. the capacity of any associati ve memory is limited to an exponential grovth rate of 1 - h2 ( 0). vhere h2(0) is the binary entropy function in bits. and 0 is the radius of the sphere of attraction. This exponential grovth in capacity can actually be achieved by the Kanerva associative memory. if its parameters are optimally set . Formulas for these op.timal values are provided. The exponential grovth in capacity for the Kanerva associative memory contrasts sharply vith the sub-linear grovth in capacity for the Hopfield associative memory.
ASSOCIATIVE MEMORY AND ITS CAPACITY
Our model of an associative memory is the folloving. Let ()(,Y) be
an (address. datum) pair. vhere )( is a vector of n ±ls and Y is a vector of m ±ls. and let ()(l),y(I)), ... ,()(M) , y(M)). be M (address, datum) pairs stored in an associative memory. is presented at the input vith an address )( that is close to some stored address )(W. then it should produce at the output a vord Y that is close to the corresponding contents y(j). To be specific, let us say that an associative memory can correct fraction 0 errors if an )( vi thin Hamming distance no of )((j) retrieves Y equal to y(j). The Hamming sphere around each )(W vill be called the sphere of attraction, and 0 viII be called the radius of attraction.
If the associative memory
One notion of the capacity of this associative memory is the
maximum number of vords that it can store vhile correcting fraction 0 errors . Unfortunately. this notion of capacity is ill-defined. because it depends on exactly vhich (address. datum) pairs have been stored. Clearly. no associative memory can correct fraction 0 errors for every sequence of stored (address, datum) pairs. Consider. for example, a sequence in vhich several different vords are vritten to the same address . No memory can reliably retrieve the contents of the overvritten vords. At the other extreme. any associative memory ' can store an unlimited number of vords and retrieve them all reliably. if their contents are identical.
A useful definition of capacity must lie somevhere betveen these
tvo extremes. that for most sequences of addresses XU), .. . , X(M) and most sequences of data y(l), ... , y(M). the memory can correct fraction 0 errors. We define
In this paper. ve are interested in the largest M such
IThis vork vas supported by the National Science Foundation under NSF
grant IST-8509860 and by an IBM Doctoral Fellovship.
© American Institute of Physics 1988
185
I most sequences' in a probabilistic sense, as some set of sequences yi th total probability greater than say, .99. When all sequences are equiprobab1e, this reduces to the deterministic version: sequences.