Storing and Generalizing Multiple Instances While Maintaining Knowledge-Level Parallelism

1 Introduction

One of the central problems in knowledge representation and learning is deciding how to represent and organize multiple instances in memory. Are people able to store and retrieve every instance of an event, such as walk­ ing somewhere? Since there are enormous numbers of walking events done by a given person, or done by oth­ ers and perceived by that person, retrieving every one is nearly impossible. Consequently, people must be orga­ nizing and generalizing multiple instances in some manner.

2 Previous Approaches

Previous approaches to knowledge organization and gen­ eralization can be divided into two levels, shown in Fig­ ure 1.

What follows is a review of symbolic and PDP ap­ proaches to the multiple instances problem.

*This research is supported in part under a contract to the second author by the JTF program of the DoD, monitored by JPL, and by a grant from the ITA Foundation.

1. Symbolic Systems: When a new event is encoun­ tered, a new token is created to represent it. For a lim­ ited number of events, storing every one does not pose a major problem. For large amounts of knowledge, simi­ lar events can be grouped together and discriminated by their differences, e.g. [Kolodner, 1984]. Unfortunately, this approach has a number of problems. First, it suffers from combinatorial explosion since there are many ways that shared features can be combined. Second, distinct tokens are needed as a final discriminant of each concept (i.e., the leaves of the tree). Third, an evaluative symbol processing mechanism is needed that decides (a) when to create a symbol, (b) how long to retain it and (c) where to index it. Finally, since each leaf is completely distinct, memory confusions do not naturally arise as a consequence of the representation. In human memory, however, confusions often do occur [Bower et a/., 1979j.
2. Parallel Distributed Processing: PDP Systems rep­ resent each concept over shared weights in a connection­ ist network [Rumelhart and McClelland, 1986]. A new instance is encoded by changing link weights. Some in­ stances will result in large weight changes and will therefore be remembered. Others, however, will change the weights only slightly and will be very difficult or impos­ sible to recall.

In general, distributed representations address the shortcomings of symbolic systems in handling multiple instances. They avoid the combinatoric problems by having the same unit participate in the representation of multiple concepts. They also naturally account for mem­ ory confusions because concepts that share a number of features will have a very similar representation. Thus, when an attempt is made to access a concept from its features, a similar pattern representing another concept may sometimes be recalled.

Unfortunately, distributed representations have not yet been successful at encoding structured knowledge while maintaining parallelism at the knowledge level. For example, Hinton [1981] has proposed a method for encoding semantic networks in a single PDP architecture (Figure 2) by representing all knowledge as triples of the form (Role1 Relation Role2).

Hinton's entire network is divided into four ensembles of units: one for each component of a triple and one which represents the entire proposition (PROP). When the patterns representing the components of a triple are placed into the appropriate ensembles shown above, a random pattern is generated on the units in PROP. This pattern, which represents a reduced description of the triple, is associated with the constituents that gave rise to it by adjusting the weights between the PROP units and the other three ensembles: By storing propositions in this manner, the network is able to perform simple inheritance and to complete a triple given two of its con­ stituents. Hinton [1988] proposes a generalization of this model, based on the reduced description principle, which can also store embedded structures.

Figure2

Systems using only a small set of ensembles (e.g. [Hinton, 1988, Touretzky, 1987]) for representing all of their knowledge, suffer from the Knowledge Parallelism Problem. That is, these systems are sequential at the knowledge level because only one triple can be stored or accessed at a time. Attempts to retrieve multiple triples in parallel will lead to enormous crosstalk prob­ lems. Some systems, such as [Dolan and Dyer, 1987, Touretzky and Hinton, 1985], can select a triple in par­ allel from the space of all available triples. However, they can only do this to the extent that their struc­ tures are represented locally (e.g. schema, their con­ stituent roles, and rules, each locally encoded as a sub­ set or node in a winner-take-all network). The loss of knowledge-level parallelism is particularly problematic in constraint-satisfaction inferencing, in which it is essential to pursue multiple paths simultaneously.

3 A Model for Storing Multiple Instances

We desire a knowledge representation system that: (1) represents structure, (2) is parallel at the knowledge level, (3) handles an enormous number of multiple in­ stances with graceful degradation and automatic gener­ alization, and ( 4) exhibits memory confusions only in the same situations that people do. Humans usually keep inferred bindings straight while confusing multiple in­ stances of a number of events. For example, if we learn that John shoots Fred, we would like the system to cor­ rectly infer and later recall that Fred (not John) bleeds. However, if we present a large number of propositions in rapid succession, (such as a list of different colored shirts different individuals wear) then we would like the system to become confused in the same way that people do.

3.1 General Approach: Parallel Distributed Semantic (PDS) Networks

Our approach is to maintain the locality of semantic net­ works for parallel manipulation and access of structure at the knowledge level, but to make each semantic network node an ensemble of PDP units to hold multiple patterns of instances. At the macro (localistfsemantic network)

level, the PDS network holds knowledge of structure with role relations. At the micro (PDP) level, the PDS net­ work holds multiple instances. For example, suppose that we wish to represent two particular humans named John and Mary. In a standard semantic network, the general concept human is represented by a single node, with nodes for John and Mary connected to it by in­ stance (is-a) links (Figure 3a).

In a PDS network (Figure 3b), humans are represented over a particular ensemble of units (e.g. ensemble 21) and John and Mary are represented as activation pat­ terns over that ensemble.

Ensemble 21 represents a single Semantic Network Node in a PDS Network, currently holding the ac­ tivity pattern for JOHN3, while also able to repre­ sent other instances, such as MARYS.

Figure 3b

The circled dots in the figure indicate the ensemble of units and the jagged lines are suggestive of the patterns of activity that represent John and Mary.

3.2 Issues: Symbol Processing and Knowledge-Level Encoding

Using PDS networks raises two important issues. The first is whether operations needed to handle processing and representation can be properly implemented. Mini­ mally, we need the equivalent of the following operations:

1. Create something like a new symbol. For example, in LISP a Gensym-like function is used to create INGEST.14.
2. Represent and manipulate schemas. erations include: binding roles in to another schema; traversing roles; schemas; etc. Schema op­ one schema binding new
3. Represent rules where variable bindings are propa­ gated between structures. For example, if we have

the rule: [X shoots Y] => [Y bleeds], and the bind­ ings X = John and Y = Fred, we would like to propagate the binding Y = Fred from the shoots structure to the bleeds structure.

The second issue involves encoding knowledge into the ensembles described earlier. At one extreme, creating a new ensemble for each instance defeats the purpose of using distributed representations and also raises the question (which plagues symbolic systems) of where the new nodes come from. At the other extreme, encod­ ing all schemas and roles into a small set of ensembles causes sequentiality at the knowledge level and massive crosstalk in retrieving concepts. The solution lies some­ where in between.

3.3 The PDS Network Approach

How are new instances added to a PDS network? Sup­ pose our model learns about a new human, John, who is male, tall and has red hair. In order to add John to memory, we will have to generate a new pattern in the human ensemble that will represent John. This is ac­ complished by placing the patterns for each of John's features into the appropriate ensembles and propagat­ ing activation into the human ensemble. The resulting pattern of activity over the human ensemble will then be used to represent John. This process is illustrated in Figure 4. In the figure, the conceptual ensembles (i.e., HUMAN, SEX, SIZE and COLOR) are labelled with capital letters and the role ensembles are indicated by lower-case labels placed inside the oval of units.

The pattern for the first feature, male, is placed into the ensemble of units representing SEX, loaded into the sex role ensemble, and propagated across links with fixed random values into the HUMAN ensemble by the path (dotted line) shown in the figure. The pattern for tall is then placed in the ensemble of units representing SIZE, propagated across random-valued links from the height role ensemble, and combined with the pattern of activ­ ity already on the human nodes. The pattern for red is placed into the COLOR and hair color role ensem­ bles and propagated in a similar fashion. The pattern that is generated from the combined activation of the three features is used to represent John in the HUMAN ensemble.

The process of adding John to memory is not yet com­ plete, because given the pattern for John, we also want to pe able to reconstruct his features. We must there­ fore associate the pattern for John with those for male, tall and red. Associating these patterns involves chang­ ing the variable weights along the path from the human ensemble to the sex, height and hair color role ensem­ bles, and can be accomplished using one of a number of generalized learning procedures. For instance, using backpropagation [Rumelhart and McClelland, 1986], the network of Figure 4 can be viewed as a conjunction of three 3-layer networks, with the HUMAN ensemble as the input layer and each of the role ensembles as the output layers (the hidden layers are indicated by the cir­ cles on the grey arrows in the figure).

As with Hinton's model, the units within a conceptual ensemble are interconnected by variable weights, which Black arrows = fixed random weighted links. Grey arrows = modifiable weighted links (single circle indicates hidden layer). Thick lines = links which propagate a pattern without changing it Dotted arrows indicate how activity patterns over ensembles are propagated.

generating a pattern for it in the COM units using the method described in the preceding section. Thus, the pattern for John is propagated from the actor ensemble (path 1); the pattern for the information from the object ensemble (path 2), and the Mary pattern from the to en­ semble (path 3). The resulting activity pattern, labelled COM.32, represents the proposition. COM.32 is now (a) associated with its constituents by weight changes between the COM units and the role ensembles, and (b) auto-associated with itself by weight changes within the COM units. Similarly, (Mary KNOWS info) is repre­ sented by propagating the pattern for Mary from the knower ensemble to KNOWS (path 4) and the pattern for the information from known to KNOWS (path 5). The resulting activity pattern, KNOWS.24, is also as­ sociated with itself and with the constituents that gave rise to it.

To represent the causality relationship between COM.32 and KNOWS.24, COM.32 is propagated from the antecedent ensemble ( c-ante) and KNOWS.24 from the consequent ensemble ( c-conseq) to generate a pat­ tern in CAUSES (paths 6 and 7). The new pattern, labelled CAUSES.13, is then associated with itself and

are trained by associating each pattern with itself (this process is referred to as auto-association [Rumelhart and McClelland, 1986]). Thus, when an ensemble is given an unfamiliar pattern that resembles a known one, it will tend to recreate the known pattern. This allows the net­ work to perform pattern completion from partial or noisy input. As an extension to Hinton's model, an interven­ ing hidden layer (not shown in the figure) is included in each conceptual ensemble and is used to interconnect the units within the ensemble. Adding these hidden units al­ lows the ensemble to store much more information, while using fewer units and connections.

3.4 Rules, Schemas, and Bindings in DCAIN

The network structure and operations described above are being used to implement DCA IN, a system designed to store instances of schemas and rules, and to implement static role bindings. For example, suppose DCAIN learns that John told Mary some information. From this, we would like DCAIN to infer both that John knew the information as a precondition to telling Mary, and that Mary now knows the information as a consequence of John's telling her. These inferences are summarized in Figure 5.

The first causal inference (CAUSES.13 in Figure 5) is stored in the architecture shown in Figure 6 1

Different ensembles of units (ovals in Figure 6) store the communicate (COM), know, causality and enable­ ment schemas, in the following manner: We first rep­ resent the proposition (John COM Info TO Mary) by with COM.32 and KNOWS.24. CAUSES.13 now com­ pletely represents the first causal relation. In exactly the same manner, (John KNOWS Info) is represented as KNOWS.25, and it and COM.32 are combined in the EN ABLES units (Figure 7) to yield a reduced descrip­ tion for ENABLES.16 from Figure 5.

1 For the sake ~f visual clarity, the black and grey arrows from Figure 4, that connect the conceptual and role ensem­ bles, are replaced by a single, thin line in Figure 6.

When the network is given (John COM Info TO Mary), it can now make the correct inferences. This proposition is presented by again propagating the pat­ terns for John, the information, and Mary through the COM units, resulting in COM.32. Propagating COM.32, we obtain a pattern over the CAUSES ensemble which is similar to CAUSES.13, and one over the ENABLES ensemble which is much like ENABLES.16. Since par­ tial (or noisy) patterns within an ensemble are trained to complete themselves, the CAUSES.13 and ENABLES.16 patterns will eventually emerge. The emergence of CAUSES.13 means that KNOWS.24 will appear in the c-conseq and KNOWS units, which in turn recreates the (Mary KNOWS Info) proposition. Similarly, EN­ ABLES.16 causes KNOWS.25 to emerge, which gener­ ates the inference (John KNOWS Info).

As a consequence, if we present [John told Mary Info] to DCAIN, it will reconstruct (1) what was told to Mary, (2) infer John already knew it, and (3) infer what Mary knows. DCAIN accomplishes these reconstructions with­ out having to create new nodes to represent each instance, as is required in standard semantic networks such as NETL [Fahlman, 1979].

4 Previous Work, Current Status, and Future Directions

To handle the problems of representing structured knowledge, dynamic role bindin~s and role propagation, we initially constructed CAIN lSumida et al., 1988], a marker passing system that uses a localist network and incorporates features of connectionist systems, specif. ically, link weights, activation values, and thresholds. CAIN propagates both markers and activation to do goaljplan analysis needed for interpretation of natural language input such as "the man hid the pot in the dish­ washer when the police came". Here, "pot" must be dis­ ambiguated to MARIJUANA by a goal/plan analysis, although "in dishwasher" suggests COOKING-POT.

Currently, we are constructing DCAIN, a distributed version of CAIN based on the principles described here. In DCAIN, patterns evoke other patterns, like [Hinton, 1981, Touretzky, 1987]. Unlike their systems, DCAIN uses many more ensembles to recreate many of the nodes normally existing in semantic networks, but without the instance nodes.

Future directions of research include methods for:

1. Propagating dynamic bindings along schema and

their roles. In this paper, we have demonstrated how PDS networks can store static role bindings, in which a previously encountered concept is bound to a role of a known proposition. In contrast, dynamic bindings in­ volve binding a novel concept and propagating it, unal­ tered, to the corresponding roles of related structures. We currently assume that the links which propagate dy­ namic bindings (e.g. the thick black lines in Figures 6 and 7) have exactly the right weight values so that pat­ terns can be passed on without being changed. Dynamic bindings in symbolic architectures are realized by prop­ agating bit patterns, unaltered, along various pathways. Our system needs a method for adjusting the weights so that such patterns are passed along unaltered.

(2) Forming semantic networks dynamically through modification of connectivity patterns between units, i.e., both within and across ensembles. One possibility that we are currently investigating involves conscripting new units to form additional ensembles.

5 Conclusions

A parallel distributed semantic (PDS) network called DCAIN, has been designed: (a) to handle the se­ vere combinatorics of storing and retrieving multiple in­ stances while maintaining parallelism at the knowledge level, and (b) to achieve graceful degradation and au­ tomatic generalization in the face of a vast number of instances. In DCAIN, ensembles of nodes are macroscop­ ically related like semantic networks and microscopically related like PDP networks. Structured objects such as schemas and .rules are represented at the macro-level, while at the micro-level, instances are reconstructed as patterns of activation over PDP ensembles.