Accession Number:

ADA218916

Title:

Storage Capacity of the Linear Associator: Beginnings of a Theory of Computational Memory

Descriptive Note:

Technical rept.

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA ARTIFICIAL INTELLIGENCE AND PSYCHOLOGY PROJECT

Personal Author(s):

Report Date:

1988-04-27

Pagination or Media Count:

128.0

Abstract:

This thesis presents a characterization of a simple connectionist- system, the linear-associator, as both a memory and a classifier. Toward this end, a theory of memory based on information-theory is devised. The principles of the information-theory of memory are then used in conjunction with the dynamics of the linear-associator to discern its storage capacity and classification capabilities as they scale with system size. To determine storage capacity, a set of M vector-pairs called items are stored in an associator with N connection-weights. The number of bits of information stored by the system is then determined to be about N2log2M. THe maximum number of items storable is found to be half the number of weights so that the information capacity of the system is quantified to be N2log sub 2 N. Classification capability is determined by allowing vectors not stored by the associator to appear at its input. Conditions necessary for the associator to make a correct response are derived from constraints of information theory and the geometry of the space of input-vectors. Results include derivation of the information-throughput of the associator, the amount of information that must be present in an input vector and the number of vectors that can be classified by an associator of a given size with a given storage load. Figures of merit are obtained that allow comparison of capabilities of general memoryclassifier systems. kr

Subject Categories:

  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE