Tech. Report Available

[MUMME%IDCSVAX.BITNET@CUNYVM.CUNY.EDU]

The following tech. report is available from the University of Illinois
Dept. of Computer Science:


UIUCDCS-R-88-1485

STORAGE CAPACITY OF THE LINEAR ASSOCIATOR:  BEGINNINGS OF A THEORY
                   OF COMPUTATIONAL MEMORY

                             by

                        Dean C. Mumme
                          May, 1988

                           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 (N/2)logM.  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
(N/2)logN.

Classification capability is determined by allowing vectors not stored by
the associator to appear 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
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 memory/classifier systems.  For an associator with a simple
non-linarity on its output, the merit figures are evaluated and shown to be
suboptimal.  Constant attention is devoted to relative parameter size required
to obtain the derived performance characteristics.  Large systems are shown
to perform nearest the optimum performance limits and suggestions are made
concerning system architecture needed for best results.  Finally, avenues for
extension of the theory to more general systems are indicated.



This tech. report is essentially my Ph.D. thesis completed last May and can
be obtained by sending e-mail to:

                erna at a.cs.uiuc.edu

Please do not send requests to me since I now live in Idaho and don't have
access to the tech. reports.

When replying to this notice, please do not use REPLY or send a note to
"CONNECTIONISTS...".   Send your request directly to Erna.

Comments, questions and suggestions about the work can be sent directly to
me at the address below.

Thank You!

Dean C. Mumme                         bitnet:  mumme at idcsvax
Dept. of Computer Science
University of Idaho
Moscow, ID 83843