Context-Dependent Thinning 21
nesting level (with the input for each following perceptron provided by the hidden layer of the preceding
one, similarly to Sperduti & Starita, 1997), generalization in those schemes would improve.
In the APNN, chunks (thinned composite codevectors) of different nesting levels are memorized
in different auto-associative neural networks. It allows an easy similarity-based decoding of a chunk
through its subchunks of the previous nesting level and decreases memory load at each nesting level (see
also Rachkovskij, accepted).
9.2. Sparse binary schemes
Indicating unknown areas where useful representation schemes for nested compositional structures can
be found, Plate (1997) notes that known schemes poorly handle sparse binary patterns, because known
binding and superposition operations change the density of sparse patterns.
From the work known to us, only Sjodin (1998) expresses the idea of "thinning" in an effort to
avoid the low associative memory capacity for dense binary patterns. He defines the thinning operation
as preserving the 1s corresponding to the maximums of some function defined over the binary vector.
The values of that function can be determined at cyclic shifts of the codevector by the number of steps
equal to the ordering number of 1s in that codevector. However it is not clear from such a description
what are the properties of the maximums and, therefore, what is the character of similarity.
The CDT procedure considered in this paper allows the density of codevectors to be preserved
while binding them. Coupled with the techniques for encoding of the pattern ordering, this procedure
allows implementation of various representation schemes of complex structured data. Approximately the
same low density of binary codevectors at different nesting levels permits the use of identical procedures
for construction, recognition, comparison, and decoding of patterns at different hierarchical levels of the
Associative-Projective Neural Network architecture (Kussul 1988, 1992; Kussul, Rachkovskij, &
Baidyk, 1991).
The CDT procedure preserves the similarity of encoded descriptions allowing the similarity of
complex structures to be determined by the overlap of their codevectors. Also, in the codevectors of
complex structures formed using the CDT procedure, representation of the component codevectors
(subset of their 1s) is reduced. Therefore, the APNN-CDT scheme can be considered another
implementation of Hinton's (1990) reduced descriptions, Amosov's (1967) item coarsing, or compression
of Halford, Wilson, & Phillips (in press). Besides, the CDT scheme is biologically relevant since it uses
sparse representations and allows simple neural-network implementation.
10. Conclusion
Procedures of Context-Dependent Thinning described in the paper perform binding of items represented
as sparse binary codevectors. They allow a variable number of superimposed patterns to be bound on the
fly while preserving the density of bound codevectors. The result of the CDT is of the same
dimensionality as the component codevectors. Using of the auto-CDT procedures as analogs of brackets
in the bracketed symbolic representation of various complex data structures permits easy transformation
of these representations to the binary codevectors of fixed dimensionality with a small number of 1s.
Unlike other binding procedures, binding by the auto-CDT preserves the similarity of bound
codevector with each of the component codevectors. It makes possible both to determine the similarity of
complex items with each other by the overlap of their codevectors and to retrieve in full size the
codevectors of their components. Such operations are efficiently implementable by distributed
associative memories which provide high storage capacity for the codevectors with small number of 1s.
The APNN-CDT style representations have been already used by us in applications (an earlier
work is reviewed in Kussul, 1992, 1993; more recent developments are described in Lavrenyuk, 1995;
Rachkovskij, 1996; Kussul & Kasatkina, 1999; Rachkovskij, accepted). We hope that the CDT
procedures will find their application for distributed representation and manipulation of complex
compositional data structures, contributing to the progress of connectionist symbol processing
(Touretzky, 1995, 1990; Touretzky & Hinton, 1988; Hinton, 1990; Plate, 1995). Fast (parallel)