TRs on reduced representations

[Alessandro Sperduti]

FTP-host: ftp.icsi.berkeley.edu (128.32.201.7)  
FTP-filename: pub/techreports/tr-93-029.ps.Z
FTP-filename: pub/techreports/tr-93-031.ps.Z

The following technical reports are available by public ftp from the
International Computer Science Institute. For hardcopies there is a small 
charge to cover postage and handling for each report (info at icsi.berkeley.edu).

Comments welcome.

Alessandro Sperduti
sperduti at icsi.berkeley.edu

____________________________________________________________________________

TR-93-029 (48 pages) 
                          Labeling RAAM

                       Alessandro Sperduti

            International Computer Science Institute
                 1947 Center Street, Suite 600
                   Berkeley, California 94704

                            TR-93-029

                             Abstract
In this report we propose an extension of the Recursive Auto-Associative 
Memory (RAAM) by Pollack. This extension, the Labeling RAAM (LRAAM), is 
able to encode labeled graphs with cycles by representing pointers explicitly.
A theoretical analysis of the constraints imposed on the weights by the 
learning task under the hypothesis of perfect learning and linear output 
units is presented. Cycles and confluent pointers result to be particularly 
effective in imposing constraints on the weights. Some technical problems 
encountered in the RAAM, such as the termination problem in the learning and 
decoding processes, are solved more naturally in the LRAAM framework. The 
representations developed for the pointers seem to be robust to recurrent 
decoding along a cycle. Data encoded in a LRAAM can be accessed by pointer 
as well as by content. The direct access by content can be achieved by 
transforming the encoder network of the LRAAM in a Bidirectional Associative 
Memory (BAM). Different access procedures can be defined according to the 
access key. The access procedures are not wholly reliable, however they seem 
to have a high likelihood of success.  A geometric interpretation of the 
decoding process is given and the representations developed in the pointer 
space of a two hidden units LRAAM are presented and discussed. In particular, 
the pointer space results to be partitioned in a fractal-like fashion.
Some effects on the representations induced by the Hopfield-like dynamics of 
the pointer decoding process are discussed and an encoding scheme able to 
retain the richness of representation devised by the decoding function is 
outlined. The application of the LRAAM model to the control of the dynamics 
of recurrent high-order networks is briefly sketched as well.


TR-93-031 (19 pages)

          On Some Stability Properties of the LRAAM Model

                       Alessandro Sperduti

            International Computer Science Institute
                 1947 Center Street, Suite 600
                   Berkeley, California 94704

                            TR-93-031

                             Abstract
In this report we discuss some mathematical properties of the LRAAM
model. The LRAAM model is an extension of the RAAM model by Pollack.
It allows one to obtain distributed reduced representations of
labeled graphs. In particular, we give sufficient conditions on the 
asymptotical stability of the decoding process along a cycle of the 
encoded structure. Data encoded in an LRAAM can also be accessed by 
content by transforming the LRAAM in an analog Hopfield network with 
hidden units and asymmetric connection matrix (CA network.)
Different access procedures can be defined according to the access key. 
Each access procedure corresponds to a particular constrained version 
of the CA network. We give sufficient conditions under which the property
of asymptotical stability of a fixed point in one particular constrained 
version of the CA network can be extended to related fixed points of 
different constrained versions of the CA network. An example of encoding 
of a labeled graph on which the theoretical results are applied is given 
as well.


To obtain electronic copies:
 
        ftp ftp.icsi.berkeley.edu
        login: anonymous
        password: <your email address>
        cd pub/techreports
        binary
        get tr-93-029.ps.Z  
        get tr-93-031.ps.Z 
        bye
 
Then at your system:
 
        uncompress tr-93-029.ps.Z  
        uncompress tr-93-031.ps.Z
        lpr -P<printer-name> tr-93-029.ps tr-93-031.ps