Holographic Reduced Representations: Convolution Algebra for Compositional Distributed Representations

1 Introduction

Distributed representations [Hinton, 1984] are attractive for a number of reasons. They offer the possibility of rep­ resenting concepts in a continuous space, they degrade gracefully with noise, and they can be processed in a parallel network of simple processing elements. How­ ever, the problem of representing compositional struc­ ture in distributed representations has been for some time a prominent concern of both followers and critics of the connectionist faith [Fodor and Pylyshyn, 1988; Hinton, 1990] .

Using connectionist networks, e.g., back propagation nets, Hopfield nets, Boltzmann machines, or Willshaw nets, it is easy to represent associations of a fixed num­ ber of items. The difficulty with representing composi­ tional structure in all of these networks is that items and associations are represented in different spaces. Hinton [1990] discusses this problem and proposes a framework in which "reduced descriptions" are used. This frame­ work requires that a number of vectors be compressed (reduced) into a single vector of the same size as each of the original vectors. This vector acts as a reduced description of the set of vectors and itself can be a mem­ ber of another set of vectors. The reduction must be reversible so that one can move in both directions in a part-whole hierarchy. In this way, compositional struc­ ture is represented. However, Hinton does not suggest any concrete way of performing this reducing mapping.

Some researchers have built models or designed frameencoding operation takes two item vectors and produces a memory trace (a vector or a matrix). The decoding operation takes a memory trace and a single item (the cue), and produces a noisy version of the item that was originally associated with the cue. Memory traces can be composed (by addition or superposition) and the de­ coding operation will work with this sum of individual traces, but the retrieved item will be noisier. In some models encoding and decoding are linear, e.g., Murdock [1983], in others decoding is non-linear, e.g., Hopfield [1982], in others all the operations are non-linear, e.g., Willshaw [1981].

To illustrate this, let I be the space of vectors repre­ senting items 1 , and T be the space of vectors or matrices representing memory traces. Let 181 : I x I -4 T be the encoding operation, 1>: I x T -4 I be the decoding op­ eration, and HI : T x T -4 T be the trace composition operation. Let a, b, c, d, e, and f be item vectors, and let T; be memory traces.

The association of two items a and b is represented by the trace T1 = a181b. We can recover a from T1 by using the decoding operation on T1 and the cue b: b !> T1 is a degraded, or noisy, version of a. Noisy versions of b can also be used as cues. Depending on the properties of the particular scheme, the retrieved vector will be more or less similar · to a.

A trace can represent a number of associations, e.g., T2 = (a181 b) EH (c 181d) EH (e 181f). An item from any pair can be used as a cue to recover the other item of the pair, e.g., c !> T2 gives a noisy version of d. The noisiness of the recovered vector increases with the number of asso­ ciations stored in a single memory trace. The number of associations that can be represented usefully in a single trace is usually referred to as the capacity of the memory model .

In matrix memories the encoding operation is the outer product, and in convolution memories the encod­ ing operation is convolution. Addition and superposition have both been used as the trace composition operation in matrix and convolution memories.

2.1 Convolutipn-correlation memories

In nearly all convolution memory models the ape­ riodic convolution operation has been used to form associations. 2 The aperiodic convolution of two vectors with n elements each results in a vector with 2n - 1 elements. This result can be convolved with another vector (recursive convolution); and if that vector has n elements, the result has 3n-2 elements. Thus the result­ ing vectors grow with recursive convolution. This same growing property is exhibited in a much more dramatic form by both matrix memories and Smolensky's [1990] tensor product representations.

Researchers have used three solutions to this problem of growth with recursive associations- (a) limit the depth of composition (Smolensky [1990]), (b) discard elements outside the n central ones (Metcalfe [1982]), and (c) use infinite vectors (Murdock [1982]).

1 There are usually distributional constraints on the ele­ ments of the vectors, e.g., the elements should be drawn from independent distributions.

2 The exception is the non-linear correlograph of Willshaw [1981], first published in 1969.

The growth problem can be avoided entirely by the use of circular convolution, an operation well known in signal processing. The result of the circular convolution of two vectors of n elements has just n elements. Since circular convolution does not have the growth property, it can be used recursively in connectionist systems with fixed width vectors.

There is a close relationship between matrix and convolution memories. A convolution of two vectors (whether circular or aperiodic) can be regarded as a com­ pression of the outer product of those two vectors. The compression is achieved by summing along the trans­ diagonals of the outer product.

Circular convolution, denoted by the symbol®, is illus­ trated in Figure 1. Each of the small circles represents the product of a pair of elements from a and b, and these are summed along the indicated diagonals. While the circular convolution operation is straightforward, what is remarkable is that circular correlation, lot, (illustrated in Figure 2) is its approximate inverse. 3 If a pair of vectors is convolved together to give a "memory trace", then one of the pair, the "cue", can be used to retrieve the other from the trace. Suppose we have a trace which is the con­ volution of the cue with another vector, t = c®x. Then correlation allows the reconstruction of a noisy version of x from t and c: y = clott where y ~ x . The correlation operation also has aperiodic and circular versions.

Circular convolution is defined as: ®: Rn x Rn -4 Rn, such that t = c®xwheret; = L:j~~CjXi-i · Subscripts are interpreted modulo n, which gives the operation its circular nature.

Circular correlation is defined as: lot : Rn x Rn -4 Rn, such that y = c~ott where y; = L:j~~ citi+;.

Convolution can be computed in 0( n log n) time using Fast Fourier Transforms (FFTs). The method is simple and well known: a® b = J- 1 (!a 0 fb), where f is a dis­ crete Fourier transform (its range is a vector of complex numbers), J- 1 is its inverse, and 0 is the component­ wise multiplication of two vectors.

3 Under certain conditions on the distribution of elements in the vectors.

2.2 Distributional constraints on vectors

For correlation to decode convolution the elements of each vector must be independently distributed with mean zero and variance 1/n so that the euclidean length of each vector has a mean of one. Examples of suit­ able distributions are the normal distribution and the discrete distribution with values equiprobably ±1/ Vfi. The analysis of signal strength and capacity depends on elements of vectors being independently distributed.

The tension between these constraints and the need for vectors to have meaningful features is discussed in Plate [1991].

2.3 How much information is stored

Since a convolution trace only has n numbers in it, it may seem strange that several pairs of vectors can be stored "in" it, since each of those vectors also has n numbers. The reason is that the vectors are stored with very poor fidelity; to successfully store a vector we only need to store enough information to discriminate it from the other vectors. If M vectors are used to represent M different (equiprobable) items, then about 2k logM bits of information are needed to represent k pairs of those items. 4 The size of the vectors does not enter into this calculation, only the number of vectors matters.

3 Addition Memories

One of the simplest ways to store a set of vectors is to add them together. Such storage does not allow for recall or reconstruction of the stored items, but it does allow for recognition, i.e., determining whether a particular item has been stored or not.

The principle of addition memory can be stated as "adding together two high dimensional vectors gives something which is similar to each and not very similar to anything else." 5 This principle underlies both convo­ lution and matrix memories and the same sort of analysis can be applied to the linear versions of each. Addition memories are discussed at greater length in Plate [1991]

4 Slightly less than 2k log M bits are required since the pairs are unordered

5 This applies to the degree that the elements of the vectors are randomly and independently distributed.

4 The need for reconstructive item memories

If a system using convolution representations is to do some sort of recall (as opposed to recognition), then it must have an additional error correcting associative item memory. This is needed to clean up the noisy vectors re­ trieved from the convolution traces. This reconstructive memory must store all the items that the system could produce. When given as input a noisy version of one of those items it must either output the closest item or indicate that the input is not close enough to any of the stored items.

For example, suppose the system is to store pairs of letters, and suppose each one of the 26 letters is repre­ sented by the random vectors a, b, ... , z. The item mem­ ory must store these 26 vectors and must be able to out­ put the closest item for any input vector (the "clean" op­ eration). Such a system is shown in Figure 3. The trace is a sum of convolved pairs, e.g., t = a®b + c®d + e®f . When the system is given one item as an input cue its task is to output the item that cue was associated with in the trace. It should also output a scalar value (the strength) which is high when the input cue was a mem­ ber of a pair, and low when the input cue was not a member of a pair. When given a as a cue it should pro­ duce b and a high strength. When given g as a cue it should give a low strength. The item it outputs is unimportant when the strength is low.

The convolution trace stores only a few associations or items, and the item memory stores many items. The item memory acts as an auto-associator to clean up the noisy items retrieved from the convolution trace.

The exact method of implementation of the item mem­ ory is unimportant. Hopfield networks are probably not a good candidate because of their low capacity. Kanerva networks [Kanerva, 1988] have sufficient capacity, but can only store binary vectors. 6 For experiments I have been using a nearest neighbor matching memory.

5 Representing more complex structure

Pairs of items are easy to represent in any type of asso­ ciative memory, but convolution memory is also suited to the representation of more complex structure.

5.1 Sequences

Sequences can be represented in a number of ways using convolution encoding. An entire sequence can be represented in one memory trace (providing the soft capacity limits are not exceeded), or chunking can be used to rep­ resent a sequence of any length in a number of memory traces.

6 Although most of this paper assumes items are repre­ sented as real vectors, convolution memories also work with binary vectors [Willshaw, 1981].

Murdock [1983; 1987] proposes a chaining method of representing sequences in a single memory trace, and models a large number of psychological phenomena with it. The technique used stores both item and pair infor­ mation in the memory trace, for example, if the sequence of vectors to be stored is abc, then the trace is

where a; and ,8; are suitable weighting constants less than 1, generated from a two or three underlying param­ eters, with a; > ai+l· The retrieval of the sequence begins with retrieving the strongest component of the trace which will be a. From there the retrieval is by chain,ing - correlating the trace with the current item to retrieve the next item. The end of the sequence is de­ tected when the correlation of the trace with the current item is not similar to any item in the item memory.

Another way to represent sequences is to use the entire previous sequence as context rather than just the previ­ ous item [Murdock, 1987]. This makes it possible to store sequences with repetitions of items. To store abc, the trace is: a+ a®b + a®b®c. This type of sequence can be retrieved in a similar way to the previous, except that the retrieval cue must be built up using convolutions.

The retrieval of later items in both these representa­ tions could be improved by subtracting off prefix com­ ponents as the items in the sequence are retrieved.

Yet another way to represent sequences is to use a fixed cue for each position of the sequence, so to store abc, the trace is: p 1®a + P2®b + p3®c. The retrieval (and storage) cues p; can be arbitrary or gener?-ted in some manner from a single vector, e.g., p; = (p )'.

5,2 Chunking of sequences

All of the above methods have soft limits on the length of sequences that can be stored. As the sequences get longer the noise in the retrieved items increases until the items are impossible to identify. This limit can be overcome by chunking - creating new "non terminal" items representing subsequences [Murdock, 1987].

The second sequence representation method is the most suitable one to do chunking with. Suppose we want to represent the sequence abcdefgh. We can cre­ ate three new items representing subsequences:

These new items must be added to the item memory and marked in some way as non-terminals. The representa­ tion for the whole sequence is:

Decoding this chunked sequence is slightly more dif­ ficult, requiring the use of a stack and decisions on whether an item is a non terminal that should be further decoded. A machine to decode such representations is described in section 7.2.

5.3 Variable binding

It is simple to implement variable binding with convolu­ tion: convolve the variable representation with the value representation. If it is desired that the representation of a variable binding should be somewhat similar to both the variable and the value, the vectors for those can be added in. This gives ax®a + ,Bx + 1a as the represen­ tation of a variable binding.

This type of variable binding can also be implemented in other types of associative memory, e.g., the triple­ space of BoltzCONS [Touretzky and Hinton 1985], or the outer product ofroles and fillers in DUCS [Touretzky and Geva, 1987]. However, in those systems the variable and value objects were of a different dimension than the binding object. Thus it was not possible add components of the variable and the value to the representation of the binding, nor use the binding itself as an item in another association.

5.4 Frame-slot representations

Frames can be represented using convolution encoding in an analogous manner to cross products of roles and fillers in [Hinton, 1981] or the frames of DUCS [Touret­ zky and Geva, 1987]. A frame consists of a frame label and a set of roles, each represented by a vector. An in­ stantiated frame is the sum of the frame label and the roles (slots) convolved with their respective fillers. For example, suppose we have a (very simplified) frame for "seeing". The vector for the frame label is l,ee and the vectors for the roles are ragent and robject· This frame could be instantiated with the fillers fjane and f,pot, to represent "Jane saw Spot" :

Fillers (or roles) can be retrieved from the instantiated frame by correlating with the role (or filler) . The vectors representing roles could be frame specific, i.e., ragent-·ee could be different from ragent-run 1 or they could be the same (or just similar). Uninstantiated frames can also be stored as the sums of the vectors representing their com­ ponents, e.g., U1 eeing = l.ee+ragent+robject· Section 7.1 describes one way of manipulating uninstantiated frames and selecting appropriate roles to fill.

The frame representation can be made similar to any vector by adding some of that vector to it. For example, we could add afjane to the above instantiated frame to make the representation for Jane doing something have some similarity to the representation for Jane.

6 Reduced Representations

Using the types of representations described in the last section, it is a trivial step to building reduced represen­ tations which can represent complex hierarchical struc­ ture in a fixed width vector. We can use an instantiated frame 7 as a filler instead of f,pot in the frame built in the previous section. For example, "Spot ran.":

7 Normalization of lengths of vectors becomes an issue, but I do not consider this for lack of space.

could be used in a "seeing" frame "Dick saw Spot run.":

This representation can be manipulated with or with­ out chunking. Without chunking, we could extract the agent of the object by correlating with robject ® ragent· Using chunking, we could extract the object by correlat­ ing with robject, clean it up, and then extract its agent, giving a less noisy vector than without chunking.

This implements Hinton's idea [1990] of a system being able to focus attention on constituents as well as being able to have the whole meaning present at once. It also suggests the possibility of sacrificing accuracy for speed - if chunks are not cleaned up the retrievals are less accurate.

7 Simple Machines that use HRRs

In this section two simple machines that operate on com­ plex convolution representations are described. Both of these machines have been successfully simulated on a convolution calculator using vectors with 1024 elements.

7.1 Role/filler selector

To manipulate frames with roles and fillers one must be able to select the appropriate roles and fillers before convolving them. I describe here a way of extracting the most appropriate role from an uninstantiated frame. The most appropriate role for a particular filler might be either the "first" role in the frame, or the role that combines best with the given filler. Both of these selec­ tion criteria can be combined in a single mechanism. An uninstantiated frame is stored as the sum of the roles and a frame label. Each role and filler also must be stored separately in item memory.

Let the uninstantiated frame be .fll+a1r 1 +a2r2+aara. The task is to select the role that combines best with f, the filler. Suppose there is some item r 2®f' in the item memory, such that f' is quite similar to f. The presence of a similar binding in the item memory defines r 2 as the "best fitting" role for f. 8

If the roles in the frame should be selected according to best fit, then the a; should be approximately equal, but if r1 should be selected first, then a 1 should be greater.

The selection of the role is done by convolving the uninstantiated frame with the potential filler, i.e., f® (,81 + a1r1 + a2r2 + aara). This is cleaned up in item memory to give r 2®f', which is then correlated with f to give a vector which can be written as 1r2 +vnoi·e where 1 and the noise depend on the similarity off to f'.

This result is added to the uninstantiated frame to give .Bl+a1r1 +(a2+1)r2+aara+vnoi·e· The strongest role can be selected by cleaning up in item memory. Which is strongest will depend on the relative strengths of a 1 , (a2 + 1), and aa, and the value of 1 in turn depends on the similarity off' to f.

8 This form of generalization by similarity can be used extensively.

The machine that accomplishes this operation 1s shown in Figure 4.

7.2 Chunked sequence readout machine

A machine that reads out the chunked sequences de­ scribed in section 5.2 can be built using two buffers, a stack, a classifier, a correlator, a clean up memory, and three gating paths. The classifier tells whether the item most prominent in the trace is a terminal, a non-terminal (chunk) or nothing. At each iteration the machine ex­ ecutes one of three action sequences depending on the output of the classifier. The stack could be implemented in any of a number of ways; including the way suggested in [Plate, 1991] , or in a network with fast weights. The machine is shown in Figure 5.

The control loop for the chunked sequence readout machine is:

Loop: (until stack gives END signal)

Clean up the trace to recover most prominent item: x = Clean(t).

Classify x as a terminal, non-terminal, or nothing (in which case "pop" is the appropriate action) and do the appropriate of the following action sequences.

Terminal:

• 1 Item x is on output. T1 gates path to replace trace by its follower: t +- x*(t- x).

Non-terminal:

• 1 Signal N1 tells stack to push the follower of the non terminal: s +- push(s,x*(t- x)).
• 2 Signal N2 gates path to replace trace by the non-terminal: t +- x.

Pop:

• 1 Signal P1 gates path to replace trace by top of stack: t +- top(s) .
• 2 Signal P2 tells stack to discard top of stack: s +- pop(s). Stack gives END signal if empty.

This machine is an example of a system that can have the whole meaning present and that can also focus at­ tention on constituents.

8 Mathematical properties

Mathematical properties of circular convolution and cor­ relation are discussed in Plate [1991], including: alge­ braic properties; the reason convolution is an approx­ imate inverse for correlation; the existence and useful­ ness of exact inverses of convolutions; and the variances of dot products of various convolution products.

9 Discussion

Circular convolution is a bilinear operation, and one con­ sequence of the linearity is low storage efficiency. How­ ever, the storage efficiency is high enough to be usable and scales linearly. Convolution is endowed with several positive features by virtue of its linear properties. One is that it can be computed very quickly using FFTs. An­ other is that analysis of the capacity, scaling, and gener­ alization properties is straightforward. Another is that there is a possibility that a system using HRRs could retain ambiguity while processing ambiguous input.

Convolution could be used as a fixed mapping in a con­ nectionist network to replace one or more of the usual weight-matrix by vector mappings. Activations could be propagated forward very quickly using FFTs, and gra­ dients could be propagated backward very quickly us­ ing FFTs as well. Such a network could learn to take advantage of the convolution mapping and could learn distributed representations for its inputs.

Memory models using circular convolution provide a way of representing compositional structure in dis­ tributed representations. The operations involved are linear and the properties of the scheme are relatively easy to analyze. There is no learning involved and the scheme works with a wide range of vectors. Systems employ­ ing this representation need to have an error-correcting auto-associative memory.

Acknowledgements

Conversations with Jordan Pollack, Janet Metcalfe, and Geoff Hinton have been essential to the development of the ideas expressed in this paper. This research has been supported in part by the Canadian Natural Sciences and Engineering Research Council.