Kanerva's Sparse Distributed Memory: An Object-Oriented Implementation on the Connection Machine

1 Introduction

Uncertainty, vagueness and associativity have been a challenge for symbolic knowledge processing in AI. Apart from efforts to model these . properties inside symbol­ based AI, the development of hybrid systems by inte­ grating AI methods with connectionist memory mod­ els can be of certain benefit for e. g. inference or nat­ ural language processing. The advantages of both ap­ proaches should be combined: symbolic AI makes use of explicit methods and knowledge and thus leads to a certain amount of comprehensibility, whereas neural net­ works are capable of modeling knowledge which is diffi­ cult to express explicitly. In addition they offer an easy way to apply case-inherent statistics. The connectionist paradigm, in particular, could gain new significance by this confluence.

One of the most clear and sound connectionist mod­ els is the Sparse Distributed Memory, as introduced by Pentti Kanerva [1988; 1992]. SDM is rooted in a math­ ematical idea complying with a convenient deduction of quantitative properties. It has also been described as a general random access memory (cf. [Kanerva, 1988], ch. 2), such that an easy hardware realization could be Giinther Gorz Univ. of Erlangen-Niirnberg IMMD (Computer Science) VIII- A. I. Am Weichselgarten 9 D-9 10 58 Erlangen Germany expected. On this basis a further description of SDM could be developed, using formal neurons.

*Previously at Univ. of Erlangen-Niirnberg.

From results of physiologically motivated brain re­ search it has been argued that SDM models the physical structure of parts of the cerebellar cortex of mammals, as well as its functionality, the control of learned motor activity. SDM was designed to resemble some specific qualities of human cognition: dynamic recollection, dis­ tinct degrees of uncertainty in concept recognition, as­ sociativity in recalling memory contents, and the faculty for building abstractions.

SDM's technical properties, e. g. capacity, recognition rate, and convergence, have been investigated well. Now even the hardware restrictions, which for some time made the realization of SDM simulators of appropriate time efficiency impossible, have disappeared

We introduce a tool for experiments with SDM, run­ ning on a Connection Machine 2 [Hillis, 1985]. Compared to other simulators it has some specific advantages:

• There are in principle no hardware restrictions on the size of simulated SDMs, because data can be swapped between main and background memory of the CM 2.
• Data types are chosen in order to optimize execution time and reduce memory waste (sec. 3, 5) .
• The software is engineered: it is modular, adaptive and extensible.
• Modules for the most important architectures of SDM-like memory models are predefined.

Flexible investigation tools are required to compare the behavior of differently designed SDMs. We found some attempts to develop simulators for SDM of which the closest one to our approach is that of Rogers [1989]. The main reason for providing an implementation of our own has been that all of them are neither capable to simulate SDMs of an appropriate size nor in a tolerable time [Matz, 1993].

2 The Memory Model

The SDM memory model is based on a small subset of the space {0, l}n. Elements of this subset, the so-called hard locations, can be regarded as registers. The SDM is built up from three major parts concerning storage, the addressing mechanism and control (fig. 1): the address module, containing address matrix and Hamming reg­ ister the contents module (selection register, contents mat;ix and summation register) and external registers for address, input and output. All of them employ bi­ nary counters, except the contents matrix whic.h is built from integer counters. Counters can be con~tdered as (weighted) connections in a n:ural~net.wo~k-hke repre­ sentation of SDM. SDM's functtonahty ts gtven by three operations: the addressing of hard locations, and the writing and reading of data. Addressing serves ~o mark a subset of registers (rows) of the contents matnx as ac­ tive. The input register is added to the active memory locations by writing {"1"s cause the particular counters to increase "0" s to decrease by one) . The reading oper­ ation store~ the column-wise sums of active registers in the summation register which in turn is matched against an external threshold. Resulting values are stored in the output register ( "1" if greater than or equal to, "0" if less than the threshold).

With selected coordinate design, hyperplane design and several intermediate designs certain modifications of the original SDM have been accomplished [Jaeckel, 1989a; 1989b]. In principle these variants differ fr?m Kanerva's basic model only in the methods of selectmg sets of active registers. In Kanerva's SDM the address matrix is a uniform randomly initialized, constant binary matrix of dimensions m x n. During addressing for each row of the address matrix the Hamming distance {de­ fined below) to the address register has to be calculated. Locations that settle within a given radius are selected.

Choosing coordinates in {0, 1}n corresponds to these­ lection of columns from the address matrix. The selected coordinates SDM provides, for each row of the address matrix a different set of constant size containing ran­ domly 'selected coordinates. Activation is effected for those locations that have matching values in their selected coordinates, when compared to the address regis­ ter. This is to simulate a sparse matrix. The interme­ diate design also consists of sets of selected coordinates, but addressing is done as in basic SDM. Thus Kanerva's SDM and the selected coordinates SDM both can be specified from the more general intermediate design.

Another class of SDM is introduced by the hyperplane design. Addresses and data are assumed to contain "1s" with a probability of 0.1. This small proportion of ac­ tive connections is physiologically motivated. As before, a set of selected coordinates exists for each register, but now this set is meant to enumerate exactly all activated connections ( "1s" in the address-register). Thus all se­ lected coordinates of activated locations must reference a "1" in the corresponding coordinate of the address reg­ ister instead of matching "O"s and "l"s. This makes an explicit address matrix redundant .

The hyperplane design can be regarded as a counter­ part to the selected coordinates design. A corresponding variant of the basic SDM is easily defined: the adapted Kanerva design expects a probability of 0.1 for neural activity in address matrix and data. No further changes are made. Finally the intermediate hyperplane design functions as a counterpart to the intermediate design comprising hyperplane and adapted Kanerva.

To reduce complexity we have defined the generalized design, comprising all of the SDM variants men~ioned above. For this purpose it was necessary to formahze the different models in a uniform manner, so that all of them can be derived by an appropriate choice of parameters [Thrk, 1993] :

Addressing operations serve to activate a precisely predictable number of registers in a reproducible way. Close addresses must effect a larger intersection of ac­ tive registers than distant ones. Though Jaeckel [1989a; 1989b] based the measure on the logical and, we will here use measures 1 based on the logical nand, the zero distance

or based on the logical xor, the Hamming distance, as used in the original SDM

for the convenience of easy conversion. Arguments to these functions are memory items located in the space {0,1}n. .

A further modification has been applied: Smce the combinatorial deduction tends to become rather compli­ cated [Jaeckel, 1989a; 1989b], we preferred a statistical foundation . All probabilities are derived by application of the Binomial distribution or the Gaussian distribution as its approximation.

The new generalized design requires various param­ eters: n is the dimension of the address space, k the number of selected coordinates, p is the activation prob­ ability of a single register and h stands for the distance of activation. In addition, a probability Pone for the oc­ currence of connections ( "1s") in the address matrix has to be defined. All of them are mutually dependent and must be considered when the optimal probability of ac­ tivation Popt = 3b is approximated. m represents the v2mt number of hard locations and t the hypothetical size of the set of data to be stored. 2 In brief, the cumulative Binomial distribution is given by

1 These measures need not define a metric on the {0, l}n.

and the Binomial distribution can be defined as:

x(n) is meant to be a discrete random vector.

By choice of parameters we can specify various SDM designs from the most general one. Tab. 1 shows how the actual distance measure dist E {xor, nand} and the parameters k, h and Pone must be selected in order to obtain one of the models I<anerva (I<), selected coor­ dinates (SC), intermediate (!), adapted I<anerva (AI<), hyperplane (HP), and interm.ediate hyperplane (!H) . Ac­ tual activation probabilities are deduced. A combination of dist and Pone has to be considered to apply an ap­ propriate value for p to the Binomial distribution. In addition arbitrary intermediate models are possible. A complete quantitative comparison is presented in [Turk, 1993]. Jaeckel [1989b] stated that SC and HP designs show a better selectivity than the I< design and conse­ quently have a higher storage capacity (up to five times). On the other hand their capability for associating con­ cepts is, of ·course, reduced.

A storage problem which arises for overlapping se­ quences in the application of hetero-associative address­ ing is discussed by Kanerva [1988] (ch. 8). His solution assembles separate SDMs into a folded SDM of a defi­ nite depth performing an accurate indexing on those se­ quences. A k-folded SDM employs k inner SDMs, each one acting on individually delayed addresses. Sec. 5 gives an example.

2 Compare [Kanerva, 1992; Jaeckel, 1989a; Chou, 1988] for a deduction.

3 Algorithms and Data Types

The CM 2 hardware architecture is almost optimally well suited to the requirements of SDM calculations. A large number of processors can be connected efficiently in the form of a virtual grid of arbitrary dimensions. Each pro­ cessor is equipped with its own local storage. This allows for uniform operations on the elements of large matrices ( SIMD-parallelism).

We decided to use the programming language *lisp, a Common Lisp extension. *lisp supports the adaption of parallel algorithms to the CM 2 architecture by special functions derived from standard Common Lisp functions and macros. They are marked by a preceding ·, like ·set, or by the suffix ! ! , like in +! ! . Execution is restricted to all active CM 2 processors and takes place in paral­ lel. Input to *lisp functions is stored in so-called pvars (parallel variables) which are physically located in the storage of the particular CM 2 processors. Data transfer between a front-end computer and the CM 2 is provided.

Tab. 2 contains some variable declarations and sizes which are essential for a SDM simulator. 3 . Appropri­ ate geometries of processor grids are 1 and 2. All vari­ ables are realized as global pvars instead of permanent pvars which would be the usual pvar type, to permit their binding to local identifiers - necessary to avoid name conflicts when simultaneously maintaining multi­ ple SDMs. Type declarations are indispensable if time and space efficiency are to be increased by *lisp compi­ lation. The CM 2 requires the restriction of grid sizes to a power of two, also for reasons of efficiency.

The most important part of the code deals with ad­ dressing, writing, and reading, as pointed out in sec. 2. For addressing we distinguish two cases: 4

1. Hamming distance

with predefined one-dimensional processor grid of size m for each processor do in parallel 11 := logxor(address-register, address-matrix) 12 := logand(coordinates, 11) hamming-register := logcount(l2) selection-register := hamming register <= radius

Each CM 2 processor has a single part of a pvar in its local storage, for instance one single row of the address-matrix. Common Lisp variables like address-register must be demanded from the *lisp host machine.

2. Zero distance

Only the first assignment has to be replaced:

As pointed out before (sec. 2) no address matrix is required to compute the zero distance.

3 The maximum size of a SDM wrt . a specific CM 2 config­ uration is harder to find than expected: In *lisp the tempo­ rary allocation of stack memory- e. g. during the calculation of return values of function calls - occurs automatically and cannot be influenced. Compare sec. 5 for particular instances.

4 Instead of *lisp-code we use a form of intuitive pseudo­ code for clarity. Transfer to *lisp can easily be accomplished.

Addressing is executed row-wise in parallel. A differ­ ent column-wise parallel handling of the contents matrix occurs during a write operation:

with predefined two-dimensional processor grid of

size n x m

for each processor do in parallel when actual position in contents-matrix is selected case actual bit in input-register is 0: add-matrix := -1 1: add-matrix := 1

contents-matrix := contents-matrix+ add-matrix

Register overflow must be prevented.

Since reading from memory involves a column-wise ad­ dition of activated counters, an appropriate paralleliza­ tion is once more by columns:

with predefined two-dimensional processor grid of size n x m

for each processor do in parallel when actual position in contents-matrix is selected result := sum of all preceding values in contents-matrix wrt. second processor grid dimension summation-register := highest activated row of contents-matrix

This so-called spread sum can easily be modeled by a combination of two *lisp functions, scan! ! and +! ! .

*lisp embodies an ideal tool to encode the parallel al­ gorithms for the various memory models described in sec. 2. It functions as a mediator between abstract mem­ ory design and particular representations on the CM 2 hardware.

The appropriateness of *lisp and the CM 2 was re­ ported first by Rogers [1989), but our implementation differs from his in the choice of efficient data types (inte­ gers instead of floats), extended functionality (general­ ized design, cf. sec. 2) , and an object-oriented framework which allows for an elegant combination of several SDMs in order to gain a larger or more complex memory model.

4 Library Structure and Encapsulation

The SDM simulator we introduce has been implemented in a plain object-oriented programming style based on flavors . It employs simple object classes, direct in­ stances, and communication, but no further oo prop­ erties like multiple inheritance or sophisticated class hierarchies. Classes have been realized as generic func­ tions which return a specific instance depending on their actual parameters. The resulting object is represented by a closure which contains all necessary methods and variables. Thus any number of SDMs can coexist in the front-end storage without influencing each other. 5 We have defined a SDM class by the generic function create-sdm which accepts parameters for distance mea­ sure, individual name, and values m, h, k, and Pone among others. As the addressing operation suffices to specify different SDM variants (sec. 2), furthermore a class for addressing strategies corresponding to the par­ ticular model is needed as an argument. Two such classes exist: one for addressing with the generalized SDM and another one containing optimized methods for Kanerva's base model.

SDM objects are able to dispatch messages for ini­ tialization, addressing, writing, and reading, as well as for adjustment of the activation radius and access to computational results. The handling of SDMs of un­ restricted size is made possible by methods for swapping to and from the background memory. This includes file handling and memory allocation. Activation is initiated by the transfer of the simple messages :store and :load. Input, output, and address registers have to be handled externally. A typical session involves three steps: the creation of an SDM object by application of the corre­ sponding class, assignment of values to the external reg­ isters and communication in order to initiate the desired operations. We have grouped all definitions concerning the simulation of simple SDMs together into the Com­ mon Lisp package SDM.

SDM models are characterized by the compositional­ ity principle. It enables the division of a large SDM into parts in order to make a sequential processing possible. A vertical cut through the contents matrix and 1/0 reg­ isters could be carried out , if certain effect on common register selection were taken into account. Nevertheless we have decided to apply a horizontal cut through ad­ dress and contents matrices in order to obtain smaller complete SDMs as parts. Taking the desired simulation of folded SDMs into account this seems to be a more in­ tuitive partitioning. Fig. 1 can now be viewed as one (of many) inner SDM combined with the external registers (dashed box). The particular SDM partitions are inde­ pendent with one exception: reading out an overall sum requires one extra step to add up the inner summation registers.

5 In fact this was the reason why the use of an object­ oriented programming style was adopted. The employment of an elaborated oo development tool, for instance the Common Lisp Object System, would be of certain benefit in future releases.

In conjunction with the capability of swapping, mem­ ory partitioning allows for SDMs of arbitrary size. The package BIG contains functions necessary to handle sets of inner SDMs. Global load-operate-store cycles are built , managing step-by-step access to an array of sin­ gle SDM objects. Thus it is possible to simulate SDMs oLa size Kanerva [1988] stated as necessary to achieve c~rtain theoretical properties (orthogonality of memory contents, convergence of sequential reading, memory ca­ pacity). The collection of different SDM types into a large hybrid SDM is also provided. This permits a SDM which employs different addressing methods at the same time, collecting sets 6 of similarly addressed registers, only if these sets are of a relevant size. Experiments in the combination of the advantages of different SDM models still remain to be carried out.

One further package (FOLD) provides the simulation of folded SDMs (sec. 2) using similar means of combina­ tion as above.

The usefulness of a SDM simulation depends very much on a correct value for the actual activation ra­ dius. Even small deviations from the optimal value may result in pathological states with all or none of the regis­ ters activated. The package PROB contains a collection of functions for an approximative calculation of the cu­ mulative Binomial distribution of large numbers. They should be applied to calculate appropriate radii in ad­ vance.

A detailed description of functions as well as applica­ tion examples can be found in [Turk, 1993].

5 Simulation Examples

The intended system behavior can be demonstrated by two simple examples. A few intuitive patterns have been predefined such that similarity can be seen immediately. We have made no attempt to meet statistical properties, e.g. parity of "1"s and "O"s, or to maximize orthogo­ nality. The icons are called caterpillar, pine and the Roman numbers one to six.

The first experiment employs an SDM of type n = 1, 024 dimensions, m = 32, 768 hard locations, k = 102 selected coordinates, an activation radius of h = 85 and a probability of Pone = 0.3 for the appearance of "1"s in address matrix and data. The metric in use is defined by the zero distance. We added 20% of random noise to ten instances of the caterpillar icon. The resulting patterns are stored auto-associatively into the SDM:

-··.;,l~ ~···

.. ~ .... ;lt:JP,i lf];·~;;li. : ·...

Two gradual readings at a similarly noisy address:

results in the pattern:

What we obtained can be defined as the generation of an abstmction, since the original pattern caterpillar was in fact unknown.

The second experiment demonstrates the discrimina­ tion of sequences in a 4-folded SDM. The characteris­ tics are n = 1, 024 dimensions, m = 8, 192 hard loca­ tions per fold, k = 1, 024 selected coordinates, h = 480 as the activation radius and a probability for a single "1" of Pone = 0.5 in address matrix and data. We define the Hamming distance as the metric in use and hence are dealing with a SDM of type K. The hetero­ associative loading of both sequences [caterpillar, one, two, three, four] and [pine, one, two, three, five] to an unfolded SDM results in inseparable memory con­ tents. Reading four times gradually at the address caterpillar leads to nearly the same pattern as it does for the address pine: a combination of four and five . The 4-folded SDM we employ here, is capable of discrim­ inating the above sequences correctly. This can be seen from the results obtained:

address:~

output: [21

address: ~ output: M

[Turk, 1993] provides complete traces.

The CM 2 at our disposal was equipped with 16 K one­ bit processors, each with 32 K bit of local storage. Tab. 3 shows timing measurements of different SDM sizes wrt. allocation, addressing, write- and read-access . In the first row timing values for an SDM running on the *lisp simulator, a CM 2 simulator for Spare stations, can be found. Our experiences show that the *lisp simulator is inadequate even for development purposes. Sorted by SDM magnitude, compiled ("comp") and non-compiled code is compared . It can be seen that compilation results in shorter execution times (up to a factor of five). Execu­ tion times of the front-end which runs the Common Lisp process, decrease even more (not contained). Meticulous declarations are necessary to provide the *lisp compiler with sufficient information. 7

Rogers [1989] tested his simulator with a K-type SDM of size n = 256 and m = 8, 192. We obtained slightly

7 We would have liked to present a comparison to the CM 5, but unfortunately we could not manage to get access to a CM 5 running *lisp .

il better results than the reported three write-read-cycles per second.

6 Related Work

Palm [1980] described another associative memory model, the binary associative memory (BAM) . This model was designed to enable easy capacity estimations, but it also forms the basis of the PAN IV simulator (cf. [Palm, 1994]). 8 BAM can be compared directly with SDM, because its architecture is similar but simpler . BAMs consist of an initially empty binary contents ma­ trix the counters of which can be only activated. No address decoding is performed, the address register indi­ cates activation directly. Thus the number of hard loca­ tions is exactly the same as the dimension of the address space. BAM is an instance of SDM through definite ac­ tivation of a subset of registers in combination with a slightly modified write operation.

Instead of the distributed representations in SDM, BAM stores exactly one representation for each asso­ ciation. As a result BAM has a higher storage capacity (which has been proved to be optimal) at the price of less robustness: permanent noise on input leads to an almost completely filled contents matrix during training phases. SDM instead manages to generate an abstrac­ tion, as demonstrated in sec. 5. BAM requires sparse coding even in normal use, whereas SDM input may or may not be coded sparsely (Kanerva vs. hyperplane de­ signs). The performance of SDM subsumes BAM in the fields of e. g. pattern completion, pattern recogni­ tion, and the storage of sequences, but SDM possesses additional capabilities in building abstractions. The ap­ plication of SDM to concrete programming problems is consequently more adequate than the use of BAM. It is a matter for further research to compare storage capacities under sparse coding for SDM.

In this context the encoding problem should be men­ tioned: the convenience of metrics like the Hamming distance does not come for free. Applications of con­ nectionist memory models often involve an appropriate encoding of world knowledge. An isomorphic transition of relations of the conceptual domain into internal dis­ tances has to be found. The problem of variable binding that occurs, when neural processes are used to model logical inference, is an example as pointed out by Dorffner [1991] . Simple lexical coding has turned out to be insuffi­ cient. One can expect harder problems from the essential transfer of functional dependencies from world level to representational level, than from simple storage. This is caused by apparent incompatibilities between the neces­ sity of unambiguous representations in certain cases and the desire for involving vagueness. The role of knowl­ edge encoding will become a major research topic in the future . We suggest reducing similarity measurements to contexts to gain an extended comparability of data. Con­ texts are defined by subspaces in form of non-randomly selected coordinates. The effect is similiar to the use of different measures.

8 PAN IV is used in the WINA project - Wissensverar­ beitung in neuronaler Architektur - at the Univ. of Ulm.

Encoding may also serve as an alternative way to han­ dle overlapping sequences. Folding requires a set of sep­ arated SDMs, whereas an architecture-independent rep­ resentation of sequences of arbitrary length is desirable. Encoding of system history as in [Jordan, 1986] com­ bines the adequacy of one single unfolded SDM with a more plausible handling of overlapping sequences: long overlaps are harder to discriminate than short ones. Ex­ periments on encoding are currently in preparation.

7 Future Work on the Implementation of Symbolic Structures with SDM

One of the major challenges facing connectionist ap­ proaches in typical computer science and artificial intel­ ligence applications is the representation and processing of data structures, e. g. of (dynamic) sequences or sets. Fodor and Pylyshyn [1988] have argued that connection­ ist representations lack combinatorial syntactic and se­ mantic structure. As Kanerva ([1988], ch. 8) pointed out, SDM is suited to store and retrieve sequences which in turn provide a basis for the implementation of com­ plex data structures - as is common practice in Lisp programming. Therefore the next research step will be the specification and implementation of sequences, sets and temporal relations on top of the basic SDM stor­ age model. With these means it will be possible to realize devices like finite automata. A particular chal­ lenge will be to provide the basic structures and op­ erations for constraint-based natural language process­ ing which has been a traditional domain for symbolic representations. Whereas most of those do not pro­ vide appropriate facilities to deal with vagueness and under-specification, these issues are a particular strength of SDM. Slack showed in a series of papers [1986; 1990] how to represent the basic structures and opera­ tions of a chart parser and of constraint-based grammar formalisms in a distributed memory model which closely resembles SDM. He even argues that, in doing so, it is not only possible to explain certain linguistic phenom­ ena like unbounded dependency, but also that the use of distributed representations based on connectionist prin­ ciples might influence theories developed at the level of symbolic representation. The investigation of the pos­ sibility of implementing a chart parser for context free grammars or even an augmentation with a constraint­ based grammar formalism within SDM will not only pro­ vide valuable insights into bridging the gap between sub­ symbolic and symbolic representations, but also demon­ strate a close integration of both approaches.

Acknowledgments

We are grateful to the Gesellschaft fur Mathematik und Datenverarbeitung (GMD), Sankt Augustin, Germany, which provided access to the Connection Machine 2.