Organization and Retrieval in a Conceptual Memory for Events or CON 54, Where Are You?

1. · Introduction

How can a large memory be searched efficiently? This is one of the biggest problems facing the designers of large systems, yet one which has been sorely neglected. While there has been a lot of work done on problems of knowledge representation and inference processes, the assump­ tion of most research projects has been that the necessary information would be available when needed without search. Without a well-structured memory organization, however, this will not always be true. This paper addresses the problem of organizing and retrieving events from a computer memory. There are three major questions to answer:

1. What are the processes for retrieving
2. events from memory?
3. What memory organization do the retrieval processes imply?
4. What are the processes for adding new events to memory, and how does memory organization change as new events are
5. added?

These questions cannot be independently ans­ wered. The organization of memory constrains the types of retrieval and updating processes the memory can have. On the other hand, memory organization, and therefore procedures for adding information to memory, must be based on retrieval

requirements.

In considering these problems, I will present CYRUS, a computer system that retrieves events from memory and automatically reorganizes itself as new events are added to it. CYRUS (Computerized Yale Retrieval and Updating System) stores and retrieves episodes in the lives of former U. S. Secretaries of State Cyrus Vance and Edmund Huskie. CYRUS can answer questions posed to it in English about the

events it stores.

CYRUS can be seen as both a model of human i ng up r equired generalized information.

Since people seem to be good at remembering, we have turned to people to try to find efficient al gor i t hms for retrieval and organization. In pr evious research ((9], (7]), it has been proposed t hat people remember by reconstructing what must have happened. The retrieval process can be seen as a process of specifying and elaborating contexts for search. In terms of the computer implementation, to retrieve any particular target event, it is necessary to (1) specify a memory category that the event might be found in, and (2) compute differentiating features of the event wi th i n that category. In order to explain this process in more detail, it is first necessary to gi ve an overview of the memory organization.

3. An overview of the meaory organization

The memory organization we are assuming is based on conceptual categories for events. These categories index similar episodes according to thei r differences and keep track of their similar ities. These categories will be referred to as Episodic Memory Organization Packets (E-MOPs), or generically as "MOPs". These structures are relat ed to Schank's [6] MOPs and to Lebowitz's (4] S-HOPs, but the concerns in defining MOPs and S-HOPs were different than those in defining E-MOPs .

An E-MOP is a net in which each node is either an E-MOP or an event. Each E-MOP has two important aspects-- (1) generalized information characteriz­ i ng its episodes, and (2) tree-like structures that index those episodes by their differences. An E-MOP' s norms include information describing its event s , such as their usual participants, l ocations , and topics, and their usual relat i onships to other events.

An E-MOP's indices can index either individual episodes or specialized E-MOPs. When an E-MOP hold s only one episode with a particular index, t hat i ndex will point to the individual episode. When t wo or more episodes in an E-MOP share the same feature, its corresponding index will point to a spec ialized sub-MOP (with the structure just described) which organizes the events with that feature . In this way, MOP/sub-MOP hierarchies are formed. The MOP below is part of CYRUS' "diplomat ic meetings" E-MOP. "Diplomatic meetings" holds generalized information about "diplomatic meetings", while MOP2 and MOP3 index "meetings with Begin" and "meetings about the Camp David Accords" respectively.

Indexing is two-tiered, where the first tier indexes~ of features, and the second indexes values for the features themselves. Thus, by fol­ lowing t~index for "participants", and from there followi ng the index for Begin, the sub-MOP organiz­ ing "meet ings with Begin" can be found. Following indices for "topic" and from there the index for "SALT", one arrives at the individual event EV2, the only meeting about SALT indexed in this MOP.

Thi s organization provides rich cross-indexing of events in memory. Specification of any discriminating set of event features within an E-MOP al l ows retrieval of the corresponding event. Using a richly indexed organization such as this, enumerat ion of a memory category should never be necessary for retrieval. Instead, retrieval strategies can be used to expand on question com­ ponents, thereby inferring relevant paths through the memory structures. In this way, search is directed only to categories and sub-categories whose events are relevant.

'diplomatic meetings'

4. Retrieving an event from an E-MOP

Given appropriate features of an event, its retrieval from an E-MOP is rather trivial. Consider, for example the following question:

(Q1): Have you ever attended a diploaatic meeting about the Camp David Accords with Dayan?

The answer to (QO) can be found either by travers­ ing the indices for "has Dayan as a participant" or by first following the indices for "has topic the Camp David Accords", and then from there traversing those for "has Dayan as a participant". Either way, EV4 would be found.

This retrieval process can be characterized as a traversal process, a process of following appropriate indices down a tree until an event is found. An event to be retrieved from an E-MOP is called a target event.

Rich cross-indexing of events in E-MOPs enables directed search of memory. To ensure directed search, the first step of traversal must be specification of paths to traverse, or selection of indices for traversal,

Index selection is based on features specified in the target event, Indices chosen for traversal to find any target event should be features that would have been chosen as indices for that event if it had previously been indexed in the E-MOP. Thus, the same index selection process is used both when adding an event to memory and during retrieval. Index selection will be discussed in section 5.1.

Traversal is a recursive process involving choice of indices and traversal of those indices. It stops when an event is found, or when there are no additional specified indices to be traversed. Thus, if there are multiple paths to a target event, it will be retrieved from the shortest path with all of its indices specified in the target event. We can think of traversal as a breadth­ first search which implements parallel traversal of all appropriate indices.

4.1 The need for elaboration

Retrieval of a target concept which specifies an event feature or combination of features which are both indexed and unique can be done easily through traversal. When a target concept specifies an unindexed feature or does not specify a unique combination of features, the traversal algorithm presented above will fail, as in the example below:

(Q2): Have you ever attended a meeting in Jerusalem?

Answering this question requires that a meeting in Jerusalem be found. Using the algorithm and MOP above to answer (Q2) , there are no features specified .by the question that can be used directly to find an event. The traversal process described must abort, even though there are events in the E-MOP which might have occurred in Jerusalem. Although we have outlawed enumeration in the normal case, there must be a way of retrieving events from an E-MOP even when indexed features are not specified in the question.

The traversal process can be continued if plausible indices can be computed. Since MOP1 indexes events by "topic" and "participants", if either of those could be inferred for a meeting in Jerusalem, then actual meetings could be retrieved from the MOP. We call the process of specifying additional features of a target event elaboration.

The processes CYRUS uses for elaborating on a retrieval specification are called instantiation strategies. They use information specified in a target concept and information associated with the E-MOPs the target concept fits into to better specify target concept features. The following is one of CYRUS' instantiation rules:

Infer-Participants

Infer participating people by retrieving representatives of specified organizations, members of known · groups, representatives of known countries, or persons associated with known organizations, groups, or countries.

Since a "diplomatic meeting" is a political event whose participants are political dignitaries, this rule can be used to infer that possible participants in a "meeting in Jerusalem" would have been important Israeli dignitaries. A similar strategy associated with "topics" would allow the

"COOtp David Accords" to be inferred as a possible topic for such a meeting.

CYRUS uses these strategies to elaborate "a meeting in Jerusalem" in the following way:

"a meeting in Jerusalem with Begin, Dayan, or Weizmann, with probable topic the Camp David Accords"

It then attenpts traversal of the appropriate indices. EV4 would be found in this way and would then be checked to make sure it had happened in Jerusalem. MOP4 would also be reached during traversal, and additional elaboration would be done to traverse its indices. We can envision the entire process as follows:

Traversal/Elaboration

4.2 Context construction

In order to search memory, a category for search must first be chosen -- in CYRUS, an E-MOP. Strategies in CYRUS which choose initial categories for search are called component-to-context instantiation strategies. These strategies use event information associated with question com­ ponents to infer plausible E-MOPs. Consider, for ex001ple, the following question:

(Q3): Who have you talked to about SALT?

In answering this question, CYRUS uses information about SALT to infer the context of a "political meeting", and searches memory for "political meetings with topic SALT". It is able to make this inference because "SALT" is an "international contract" and "international contracts" are known to be the topics of "political meetings". In this case, the strategy "Infer-from-Topic" does that work:

In fer- from-Topic

If the event is an MTRANS, and its topic (MOBJECT) is specified, then predict communicatory contexts associated with the topic.

4.3 Alternate-context search

In using elaboration to answer (Q2), we stated that 'EV4 would be found, and that MOP4 would be found, but additional elaboration would be needed to traverse its indices. Suppose that there was not enough information available to do the additional elaboration necessary for traversal of MOP4, or alternatively, that the only meeting which had taken place in Jerusalem was the one indexed in "diplomatic meetings" as a "meeting about Jerusalem". In either of those cases, elaboration would not suffice to answer the question.

Events, however, occur in the contexts of other events and refer to those related events. An event can be foun~finding an episode it was related to. When a related event is found, its context can be searched for the target. Thus, to search for a meeting in Jerusalem, it might be appropriate to recall a trip to Israel or negotiations involving Israel which might have included such a meeting in its sequence of events. Since trips and negotiations are less common than diplomatic meetings, they might be easier to retrieve [7].

Context-to-context instantiation strategies are used to construct alternate contexts for search. In order for possible related contexts to be inferred from a target event, E-MOPs must specify both the types of episodes (other E-MOPs) they are often related to, and how those episodes are related, i.e., how their roles correspond to those of the related E-MOP. A diplomatic trip related to a meeting in Jerusalem, for example, can be inferred to have been to Israel.

Search strategies direct search for alternate contexts. They have the following steps:

1. choose a context to be searched for, and call appropriate instantiation strategies to construct and elaborate that context
2. retrieve corresponding events from memory
3. search for surrounding retrieved the target event in the contexts of the events

In searching for "diplomatic meetings in Jerusalem", a search strategy which searches for episodes an event could have been part of would (1) construct contexts for "diplomatic trips to Israel," and "negotiations concerning an Israeli issue," (2) traverse memory searching for each of those, and (3) search the sequence of events of each episode found for an appropriate diplomatic meeting. The following is an example from CYRUS which illustrates the retrieval process:

--------------------------------------------------

>Who have you discussed SALT with? inferring political meeting -- sM-MEETING searching memory for question concept additional information needed meeting could have occurred in USSR or USA searching for meeting in USSR searching for meeting in USA searching memory for episodes meeting could have occurred in searching for -I-NEGOTIATE searching I-NEGOTIATE for meeting searching for conferences about SALT searching for diplomatic trips to USSR searching memory for standard types of ·meetings searching for diplomatic meetings about SALT searching for briefings about SALT searching for public relations meetings CARTER, BREZHNEV, GROMYKO, OTHER AMERICAN AND RUSSIAN DIPLOMATS, ·AND MUSTAFA KHALIL.

4.4 S~D~ary

The following chart illustrates the entire retrieval process:

The Retrieval Process

This retrieval process trades speed of retrieval for memory space. It is faster than enumeration would be, but needs more memory. It is also less accurate than enumeration would be. If cues necessary to choose an appropriate context are not available at the time of retrieval, then retrieval will fail. Similarly, if the knowledge necessary to do appropriate elaboration is not available, then retrieval will fail. What this scheme does allow is (1) retrieval in most cases that is faster than enumeration and (2) retrieval of generalized information in exactly the same way actual events are found.

5. Maintaining aeaory organization

In order for retrieval to work consistently as new events are added to memory, memory's organiza­ tion must be maintained. When a new event is added to an E-HOP, it must be indexed so that it can later be retrieved. New E-MOPs must be created as necessary, and generalized information necessary to aid retrieval must be built up.

The first step in adding a new event to an E-HOP is to choose appropriate features of the event for indexing. Each feature chosen can have one of four relationships to the E-MOP [2]:

1. There is nothing yet indexed in the E-HOP with that feature

1. There i3 one other item with that feature indexed in the E-MOP
2. There is an E-MOP indexed by that feature
3. It is on of the E-MOP's norms.

When there is not already an index for a feature (1), a new index is built and the event is indexed at that point. When the;e is one other event with a particular feature (2), a new E-MOP is formed ba3ed on the similarities between the new event and the previous one with that feature and the two events are indexed in that E-MOP.' When there is already an E-MOP indexed by a particular feature (3), the new event is integrated into that E-MOP. That integration includes refining the E-MOP's generalized information and indexing the event. If the feature is one of the E-MOP's norms (4 ) , no indexing is done, The remainder of this section will describe index 3election, and building up generalized information during processes associated with (2) and (3) above.

5.1 Index selection

Index selection is part of both retrieval and memory update. It takes an event and an E-MOP as input, and produces a subset of the event's features to be used for indexing the event in the MOP (during update) or for traversal (during retrieval).

Index selection in a particular E-MOP depends on the MOP's norms. In general, to maintain discriminibility between events, normal aspects of a situation should not be indexed, while weird and different aspects of a situation should. Indexing by a norm would supply memory with unneeded redun­ dancy, and violate economy of storage. Differences between events, on the other hand, differentiate them from each other, providing discriminability. Organizing events according to differences allows events to be recognized individually. If a unique difference from a norm is 3pecified in a retrieval key, the event that corresponds to that specifica­ tion can be retrieved.

Another important property indices should have is predictive power, A feature which is predictive often co-occurs with some other event feature. The nationality of participants in a diplomatic meeting, for example, is usually the same as one party to the contract being discussed. Thus, in a "diplomatic meetings" MOP, the nationality of participants can help predict the meeting's topic, and is a good predictive feature for indexing.

Predictions that a particular feature or set of features can make are used during retrieval for elaboration. During retrieval, specification of the value of a predictive property will allow inference of the properties it predicts. If the feature "participants are Russian" co-occurs with "topic is usually arms limitations", then knowing a meeting was with a Russian will allow inference of the meeting's topic.

Of course, we can't tell for sure, the first time we see a particular feature, whether or not it will later be predictive. Predictiveness of features, however, can be judged by previous experience, If a~ of index (e.g., nationality of participants, sides of a contract) has been useful previously for similar events, then there is a good chance it will be useful for the current event. This implies that as new events are added to memory, the relative predictive power of different types of indices must be tracked.

The predictive power of a feature depends on the context in which it is found. Thus, E-MOP indices must lmake--context-rel~ predictions, i.e., predictions about MOP-specific features. These criteria suggest the following algorithm for index selection:

Index Selection

+---------------------------------------------+ : Select the types of features from the event : : that have been predictive previously.

+---------------------------------------------+

+-------------------------------------------+

Get rid of

:

(1) features known to be non-predictive :

(2) E-MOP norms

+-------------------------------------------+

Following is the information CYRUS uses to choose indices when adding events to its "diplomatic meetings" MOP.

'diplomatic meetings'

norms:

participants: diplomats of countries involved in contract being discussed

location: conference room in capital city of

country of an important participant

topic: international contract

duration: one to two hours

predictive:

political roles of the participants classes those roles fit into nationalities of the participants occupations of the participants political leanings of participants topic, place, participants sides of the topic

issue underlying the topic (e.g., peace)

non-predictive features:

participants' occupation is for. min .

participants' occupation is head of state

Using this knowledge, the first step of the index selection process would choose the following as potentially predictive features of EV1:

EV1: Cyrus Vance has a meeting with An­ drei Gromyko in Ru33ia about SALT.

1. the meeting is with a foreign minister

2. the meeting is with a diplomat

3. the meeting is with a Russian

4. the meeting is with a Communist

5. the meeting is about SALT

6. the topic concerns the U.S. and Russia

1. the underlying topic is arms limitations

8. the meeting is with Gromyko

9. the meeting is in Russia

Taking into account the norms and non­ predictive aspects of the "diplomatic meetings" MOP above, only features 3 through 9 would remain as plausible indices for EV1 after the second step.

5.2 Generalization

Generalization is important to both the retrieval and updating processes. It is the process which builds up an E-MOP's norms. Retrieval strategies are guided by generalized knowledge. During memory update, a MOP's norms contrain later indexing and creation of new E-MOPs, thus preventing combinatorial explosion of indices.

5.2.1 Initial generalization

Initial generalization happens when the second event with a particular feature is added to an E-MOP. At that point, there are two events available for comparison -- the current one and the one already in memory. A new E-MOP is created, and the common features of the two events are added to the norms of the new E-MOP.

Consider two trips that Vance might have gone on to the Middle East: one to Israel, and one to Egypt, both to negotiate Arab-Israeli peace. Sup­ pose that in both he talked to the head of state of the country he was visiting and was treated to a state dinner. If both of those events were indexed as "trips to the Middle East" in the "diplomatic trips" MOP, their similarities and differences would be reflected in the norms and indices of the newly-created MOP as follows:

'diplomatic trips to the Middle East'

norms: destination is the Middle East purpose is to negotiate Arab-Israeli peace includes meeting with head of state includes state dinner

specialization of "diplomatic trip"

differences:

destination

I

\

Israel Egypt

--------------------------------------------------

5.2.2 Adjusting the certainty of a generalization

The first two events added to an E-MOP are special. They initiate the set of generalizations that will be used in future indexing and retrieval. Some initial generalizations are more reasonable than others, however. All meetings indexed in the E-MOP above, for example, will have the feature "destination is the Middle East" since that is the index for this sub-MOP in "diplomatic trip". Probably, these trips will continue to have the purpose of negotiating Arab-Israeli peace, at least as long as there is no peace there. We would not, however, expect that every trip to the Middle East will include a state dinner. There may also be attributes·of trips to the Middle East not common to both of these trips. As additional meetings are added to the E-MOP, the unreasonable generalizations must be discovered and removed from the MOP. In addition, new events must be monitored to see if additional generalized information can be extracted from them.

5.2.3 Making additional generalizations

Because the first two events indexed in an E-MOP might fail to imply a particular generalization, MOP norms and indices must be monitored after initial generalization. In CYRUS, after an E-MOP reaches a reasonable size (6), CYRUS checks each sub-MOP referred to by incoming events to see if any of them index a large majority of the events in the E-MOP. If one does, CYRUS collapses it and merges its generalizations with those of the parent E-MOP, thus adding to the generalized information associated with that MOP.

5.2.4 Recovery fra. bad generalizations

Recovery from bad generalizations is more com­ plex. When new information and events contradict a previously made generalization, that generalization must be removed as one of the E-MOP's norms.

This raises a special problem. While a feature is a norm of an E-MOP, events can never be indexed by that feature. In addition, if a feature is one of an E-MOP's norms, then some events ought to have it as a feature. Because events were not indexed by that feature, however, it would be impossible to go back and find all events support­ ing the generalization.

Generalization removal, then, can have grave implications in retrieval. If a retrieval specification specified a feature that had been removed as a generalization, but which had· not yet been indexed, then the retrieval processes would not be able to find any trace in memory that an event with that feature had ever been processed. It would have to conclude that there had never been such an event in memory.

The solution to this is to create an index to an empty sub-MOP each time a feature is removed from a MOP's generalized information, and in addition, to mark the feature as having been "once generalized". That way, the retrieval functions will be able to come back with the message "there may be events with this description, but I can ' t find particular ones", instead of failing com­ pletely if no distinct event could be found. Dur­ ing later indexing, that sub-MOP will be treated like any other.

We caw now point out an important need for search strategies as part of the retrieval process. Although false generalization on one E-MOP might keep a particular event from being well-indexed, related events might have been more richly indexed. If that is the case, they will be easier to retrieve than the event whose features had been falsely generalized. Finding a "once-generalized" E-MOP during traversal, then, should signal that search strategies will be particularly appropriate.

6. CYRUS itself

CYRUS has two data bases one each for former U.S. Secretaries of State Cyrus Vance and Edmund Muskie. CYRUS takes conceptual representations of episodes as input. Thus, representations of episodes must be built before sending them to CYRUS. CYRUS has two modes of receiving representations of stories. In one mode, the stories are analyzed and the representations encoded by the human reader before being integrated into CYRUS' memory. In its second mode of operation, CYRUS is connected to FRUMP [1] to form a complete information retrieval system called CyFr [3]. FRUMP reads stories from the UPI news wire, and sends conceptual summaries of stories about Muskie and Vance to CYRUS. CYRUS then adds the new events to its memory and answers questions about them. CYRUS' Muskie memory has been built up entirely from FRUMP-processed stories. Its Vance memory is built partially of FRUMP-processed stories and partially of stories encoded by hand.

The following is a story CyFr has processed about Muskie. FRUMP produced the summary, and sent its conceptual representation to CYRUS. After adding the events to its memory, CYRUS answered the questions:

Carter begins going from the United States to Italy and Yugoslavia to talk. Secretary of State Edmund Muskie will go from the United States to Asia this month to have talks with ASEAN. Mu~kie will have talks with NATO in Ankara in June.

··························

>Have you been to Europe recently? YES, MOST RECENTLY LAST MONTH. >Why did you go there? TO TALK TO ANDREI GROMYKO. >Are you going to Asia? YES, THIS MONTH. >Who will you talk to? WITH NATO IN ANKARA, TURKEY.

The Vance and the Muskie memories start out the same, but after adding events to the two data bases, their organizations differ in four ways: (1) The indices are different. (2) The types of indices are different. While the Vance E-MOP has topic indices and larger episode indices, the Muskie E-MOP has neither of those. (3) The norms of their corresponding E-MOPs are different, (i.e., different generalizations have been made). (q) The Vance E-MOP indexes mostly sub-MOPs, and the Muskie E-MOP indexes mostly individual events.

Three factors contribute to these differences. First, the experiences the two men have had are different. This is the reason for differences between indices in corresponding E-MOPs. Second, the data entered into the Vance data base is much more detailed than that entered into the Muskie memory. This factor accounts for the differences in the types of indices in the two memories. Because the Muskie memory is not usually aware of the topics of Muskie's meetings, for example, it cannot index them by aspects of their topics.

The third factor which accounts for differences between the two memories is the degree of similarity between the events. The first ten events added to the Vance E-MOP, for example, were very similar to each other. Eight of them were meetings about the Camp David Accords. On the other hand, except for three meetings with Gromyko the meetings entered into the Huskie data base had very different participants and locations.

This factor accounts for differences (3) and (q) above. The more similarities between events in an E-MOP, the more filled out the MOP's generalized information can be. In addition, the more similar events in an E-MOP are, the more sub-MOPs will be indexed in the MOP than individual events. The extent of new category creation, then, is a func­ tion of the degree of similarity between items added to an E-MOP, and not on the number of items it organizes.

CYRUS itself is no longer being developed as a computer system. Many of the problems illuminated by work on CYRUS are being investigated in the context of other research projects. The generality of CYRUS' retrieval and organizational strategies is being examined in two new areas a world ~ffairs expert and a medical diagnosis program. We are investigating more sophisticated methods for index selection and new category creation, and memory reorganization based on retrieval. The behavior of reconstructive memory as a memory or~anization for expert domains is also being explored.

7. References

1. DeJong, G. F. (1979). Prediction stantiation: a new language processing. Vol. 3, pp. 251-273. approach Cognitive and subto natural Science,
2. Kolodner, J. L. (1980a). Organizing memory and keeping it organized. In Proceedings of the First Annual National Conference on Artificial Intelligence, Stanford, CA.
3. Kolodner, J.·L. (1980b). Retrieval and organizational strategies in conceptual memory: A computer model. Research Report #187. Dept. of Computer Science, Yale University, New Haven, CT.
4. (q] Lebowitz, M. (1980) Generalization and memory in an integrated understanding system. Research Report #186. Dept. of Computer Science. Yale University, New Haven, CT.
5. Norman, D. A. and Bobrow, D. G. (1977). Descriptions: a basis for memory acquisition and retrieval. Report #7703. Center for Human Information Processing, La Jolla, California.
6. Schank, R. C. (1980). Language and memory. Cognitive Science. Vol. q, No. 3.
7. Schank, R. C. and Kolodner, J. L. (1979). Retrieving Information from an Episodic Memory Research Report #159. Department of Computer Science, Yale University. also in IJCAI-79.
8. Smith, E. E., Adams, N., and Schorr, D. (1978). Fact Retrieval and the Paradox of Interference, Cognitive Psychology, Vol 10, pp.q38-q6q.
9. Williams, M. D. (1978). The process of retrieval from very long term memory. Center for Human Information Processing Memo CHIP-75, L~ Jolla, California.