Conceptual Overlays: A Mechanism for the Interpretation of Sentence Meaning in Context

Introduction

The goal of this research is to synthesize a domain-independent theory of how context, specifically expectancy, influences perception and interpretation of natural language meaning stimuli. I 1~ant here to examine the specific problem of interpreting actions in context, and to describe a general theoretical approach to its solution, because I believe many of the iss­ ues of this specific problem overlap with the issues of most other problems of context.

The statement of the task of interpreting actions in context can be formulated as follows: Given a "meaningful" sequence, T1 , ... ,Ti, of syntactically, referentially and conceptually unambiguous sentences (actually, the sequence of thoughts underl~ing them, expressed in some meaning formalism) , assign a meanin~ interore-

*There will be many interesting interrelation­ ships between the present theory and the pro­ cesses by which meaning is extracted from real1·1orld sentences and perceptions which contain syntactic, referential and conceptual ambigui­ ties. The assumption made here that sentences are unambiguous helps separate the influence of context from the influences of the various other processes.

CONCEPTUAL OVERLAYS: A MECHANISM FOR THE INTERPRETATION OF SENTENCE MEANING IN CONTEXT

Chuck Rieger Department of Computer Science University of Maryland College Park, Maryland 20742

tation to the i+lSt similarly unambiguous sen­ tence in a way which elucidates its relationshi~ to the context, or situation, established by T1, ... ,Ti.

This task engages four issues: (1) What is a reasonable definition of C(Tl , ... ,Ti), the context established by Tl, . .. ,Ti? (2) What is a meaningful definition of I(T,K), the interpre­ tation of sentence T in context K? (3) What is the role of inference in the contextual inter­ pretive process (and at what point and to what richness are inferences made)? (4) How do con­ texts begin , switch, end and interact? This paper concentrates on (1) and (2), describing a method and a prototype s¥stem, EX-SPECTRE-1, for obtaining I(T2,C(T1)), where T2 describes some volitional action by an actor who is act­ in~ in the context established by T1 .

Specific Goals and Examples

There have been four goals in the first phase of building this theory and model:

GOAL 1: To elucidate the relationship of action T2 to the context C(Tl).

Example : T1: Pete stole Jake's cattle. T2: Jake saddled his (Jake's) horse.

GOAL 2: To account for how different contexts prescribe different interpretations of the same thought.

Example: T1a: John saw the thunder clouds and felt the first drops of rain.

T1b: John dived under his jeep.

T2a: John heard a thud and saw the precious water leaking from his jeep's radiator.

T2b: John dived under his jeep.

T3a: John didn't want the cops to see him.

T3b: John dived under his jeep.

GOAL 3: To alter T1's influence on T2 by pre­ ceding T1 with some To.

Example: To: Jake asked Pete to steal his (Jake's) cattle to teach Sara a lesson.

T1: Pete stole Jake 's cattle.

T2: Jake saddled his horse.

GOAL 4: To account for how a "peculiar" T2 can be detected and how it can change the influ­ ence nominally exerted by T1. ·

Example: T1: Pete stole Jake's cattle.

T2 : Jake smirked.

It is felt that the specific mechanisms under­ lying these four varieties of binary and ter­ nary interaction will prove to be characteristic of many other context-related mechanisms. At the time of writing, EX-SPECTRE-1 has met the first

and second goals for restricted examples.

Background

The present theory of conceptual overlays is the next step in the development of the model of memory and inference described in (Rl) and (R2), which proposed that a spontaneous, non­ goal-directed substratum of language-indepen­ dent inference is requisite to even the simplest forms of language comprehension. As will be evident, the present theory of overlays is in accord with the philosophy verbalized by Abelson in (Al) and by Minsky in (Ml) that perceptions and events can be interpreted only within rel­ atively large "themes" (Abelson) or "frameworks" (Minsky). The theory also relates to the idea of a "demon", used by Charniak in (Cl), and ties in closely with the goals of Schmidt's model of per· sonal causation (S3), which deals with some of the same issues from the point of view of soc­ ial psychology.

Conceptual Overlays

For the sake of concreteness, acknowledgin9 the potential loss of generality, it will be useful to thread the discussion through the de­ tails of one particular example. At least this will connote the main ideas of the theory. The example will be the one used earlier:

T1: Pete stole Jake's cattle.

T2: Jake saddled his (Jake's) horse.

The voal in this example will be to explain how Jakes saddling his horse might relate to Pete's act of theft. The theoretical setting is a con­ ceptual memory of the sort described in (Rl) and (R2), which receives as its input meaning graphs which have been constructed from input sentences by an autonomous parser of the sort described by Riesbeck in (R4), and which contains the low1 eve 1 inference reflex mentioned above. In order to communicate some representation-independent ideas, most problems of meaning representation will be unabashedly ignored by using English­ like notation. It is assumed that a suitably ex­ pressive system of representation (such as Schank's Conceptual Dependency (S2)) is used throughout.

To begin with, we would expect reasonable interpretations of this example to follow the lines: "Jake is going after Pete to get his cat­ tle back," or "Jake is going into town to see the sheriff." These interpretations relate to this specific T2. Of course, there could have been a limitless range of other T2's in place of this particular one: "Jake sat down and wept'! "Jake took out his rifle," "Jake smirked," "Pete was arrested next day," "Jake lingered over his morning coffee in deep thought," "Pete celebrat­ ed," and so forth. The important test of the theory is that it be able to relate these as well. The requirement of the theory is therefore that it provide a format wherein general expect­ ancies can be maintained, providing enough imp­ licit slots so that very diverse subsequent in­ put can fit later. Hence the term "overlay" has been used to suggest a superimposable piece of cellulose with boxes drawn on it which say: "If you see such-and-so occur, here is where it fits into the laroer scneme of things at the moment."

Action Overlays

. Entities called action overlays are the veh1cles for storing and organizing bundles of expectancies. An action overlay, A, · is a data structure consisting of five components: (1) a set of interceptors, lA, (2) a universe of QQ!.­ ential expe~tancies, E 4 , (3) an expectancy~­ ector funct1on, SA, (4J a set of overlay switch­ ~. WA, and (5) a set of termination handlers, HA. Fig. 1 shows an action overlay which relates to acts of theft. Fig. 2 is the correspondin9 LISP data structure in use by EX-SPECTRE-1. (Re­ call that, in principle, the English-like nota­ tion now in use will eventually be replaced by a forma 1 sys tern.)

Interceptors

The set of interceptors, lA, specifies con­ ceptual patterns which can trigger the action overlay, A, of which they are a part. As each new input, T, arrives in the system (either from the sentence analyzer directly, or as an infer­ ence from the inference component of the overlay sys tern), the interceptors of every inactive ac·· tion overlay in the system are compared toT. If at least one interceptor is satisfied, the over­ lay becomes active. The process of action over­ lay activation in EX-SPECTRE-1 is therefore a pattern-directed invocation scheme.

There will be quite a large number of ac­ tion overlays in a full-scale system, each deal­ Jng with some relatively narrow situation and 1ts related expectancies. Because of this, and since situation descriptions will frequently overlap, more than one action overlay will gen­ eral~y be found applicable to a given input, m~an1ng that several situations are in progress s1multaneously. As will be seen, multiple over­ lays exert their influence concurrently on subsequent inputs. ·

In the overlay of Fig. 2, only one inter­ ce~tor has been included. When the input

(PETE STEAL CATTLE FROM JAKE)

arrives, this overlay is activated in EX-SPECTRE· 1. Activation begins by binding X to PETE, Y to CATTLE, Z to JAKE, and H to the entire pattern for later reference in the selector function.

Potential Expectancies

EA, the universe of potential expectancies is a set of "what next" describers which en urn- ' erates at a high descriptive level the universe of activities which might possible follow the triggering input without "violating the spirit" of the overlay (and hence cause a switch to a·n­ other action overlay). The information in Fig. 2 associated with the feature UNIVERSE comprises the set of potential expectancies for this theft overlay. By "violates the spirit" I mean some subsequent activity which would cause the com­ prehender to be surprised - something which some· how deviates from what is normally expected af­ ter a theft.

Within this paradigm there are many specific fac· tors which can assist in the prediction of the relevance of each potential expectancy in EA. For example, if Z already knows X's identity, then his future activities should not be expect­ ed to include the determination of X's identity. Likewise, such factors as X and Z's relationship (student-teacher, husband-wife, jailer-inmate, neighbor-neighbor, etc.), 7's belief about X's motivation for the theft (if ascertainable), and the relative value of Y to Z, will all be good clues for der.iding, say, whether Z can be ex­ pected to attempt a physical get-back of Y from X or a psychological retaliation against X, or both. If some sort of retali~tion seems in order some notions of degree and kind will be of im­ portance - Jake is less likely to stick his ton­ gue out at Pete than to break down his fence! Fig. 1 contains a partial list of relevant fac­ tors for t~e theft overlay which might be reason· able to include in a larger system. EX-PECTRE-1 contains only a subset of these tests, as shown in Fig. 3.

The tests of Fig. 3 are made by the expec­ tancy selector function, SA. SA is currently im­ plemented as a "ternary transition network", serving a~ a discrimination network. "Ternary" refers to the characteristic that each node in the net branches three ways: "yes", "no" and "don't know" . Nodes in the net are memory quer­ ies and each arc has associated with it a set of saliency setters - assignment statements which specify estimations of the saliency of various elements of EA when the arc is followed. All sal· iency estimations are preset to 0.5 out of 1.0; the net changes only those for which definite clues are present one way or another.

SA is intended to model the phenomenon wherein a human comprehender seems to acquire some very cursory, rough gestalt of. the situa­ tion, or in other words, which expectancies in EA are salient and which are not. SA therefore imposes only a rough ordering on EA so that those e 1 ements presumed most sa 1 i ent can receive more attention in subsequent PARTOF searching to be described. An "incorrect" judgement of saliency will in principle never preclude com­ prehension; it will simply increase the processina time required to discover relationships lat­ P: ' on, and perhaps cause an i nab i1 i ty to prefer one interpretation over another in a case where there are several competing interpretations. In a sample run, EX-SPECTRE-1 produced the ·saliency vector indicated by the dashed lines in Fig. 3 for the theft example.

The Expectancy Cloud

Having been roughly assessed for saliency, all members of EA are thrown into a central ex­ pectancy cloud, EC. Each expectancy in EC is backlinked to its contributinq overlay, since the cloud will generally contain expectancies from numerous concurrent overlays, and since fin a 1 i nternretati ons ~dll need to reference the contributin9 overlay.

A person is never fully aware at each mom­ ent exactly what his expectancies are. Apparent­ ly, an expectancy is a subliminal thing. The cloud, EC, therefore, although explicit and com­ posed of discrete and isolatable expectancies, is intended to model a component in the human which is not part of his immediate awareness from moment to moment, but which in retrospect generally seems to have contained most of the necessary information for contextual interpre­ tation.

The expectancies in this cloud define the context at each moment in the model.

Stepwise Indexed Aloorithms

An active expectancy in EC describes some activity which is anticipated to have some chance of occurring at some future point. Such an activity can be characterized by a common­ sense algorithm, or set of algorithms, where an algorithm is some temporally sequenced, hier­ archical collection of subgoals, or steps. As one penertates deeper into the hierarchy, steps become more specific and the alternatives more numerous. As a basic data structure, the AtiD/OR graph provides an effective declarative (as opp­ osed to procedural) method of specifying common­ sense algorithms. (See (Nl) for instance).*

Since an expectancy is an anticipated act­ ivity, and since activities can be represented by alqorithms, each expectancy in EC is in fact no more than a pointer to one or more common­ sense algorithms; hence each expectancy implic­ i!!r references all possible steps in those algorithms. If a subsequent input, T, can be id­ entified as a step in the algorithms referenced by some expectancy in EC, this identification will.relate T to the current context, K (repre­ sented by EC) thereby providing an interpreta­ tion, I(T,K). This relating of an input as a step in some activity which has been anticipated via an action overlay is the central idea of the theory.

------------------ ----- *'IOTE: Since the time of first submittal of this paper, a new formalism for representino commonsense algorithms has heen developed and partially i111plemented. The neo·1 formalism ren­ laces the AND/OR graph, which lacks thP struct­ ural constraints needed for representinq gen­ eral commonsense algorithms. See (R3).

The collection of commonsense algorithms, the algorithm base, used for the contextual in­ terpretation process is the very same collection of algorithms the comprehender would use in ac­ tually getting about in the world (first-hand problem solving). This is a crucial point in my opinion, since it directly brings the world model to bear on the process of comprehending language.

However, the interpretive task is the in­ verse of the executory task; rather than "trans­ late a goal into some plan of action," the task is "ascribe a ~oal to sor.~e at-served plan of ac­ tion," or More specifically, ''characterize some observed action as a step in tne attainMent of some inferred goal ." Because of this difference in use, the data structure used in EX-SPECTRE-I for storinq commonsense algorithms is an aug­ mented AND/OR graph which I have called a step­ wise indexed_!l]Qf_ithm. {SIA). In an SIA, each specific step in the alaorithm is represented by {1) a pointer to a step schema, and {2) rel­ evant binding information relating the instance of the schema to the schema. For instance, in­ stead of writing {P GOTO DRUGSTORE) as a step in some algorithm for getting rid of a headache, this GOTO step, as well as all other GOTO steps in the entire algorithm base, is represented by a pointer to the step schema {X GOTO Y), with the appropriate bindings, i~ this case, X:P and Y:DRUGSTORE. In addition, each step in the SIA is "father-linked" to its parent step. This will permit traversing an SIA bottom-up, from a step to higher level goals of which it is a part.

Each step schema is backlinked to each of its occurrences in the algorithm base through its occurrence set . This provides an index into the algorithm base to all points where the sch­ ema is referenced. For the {X GOTO Y) schema, this occurrence set would probably br quite large in a full-scale system. Hence, finer dis­ tinctions among the various types of GOTO {as one example), based on the specific conceptual features of X andY, would probably have to be made by the indexinq scheMe to improve on the search efficiency of the PARTOF function, about to be described.

Fig. 4 shows the SIA and related steo schema for oart of a physical get-back goal, referenced by one of the expectancies in the cattle theft examole .

PARTOF Searching Upward Throuoh SIA's

SIA's and st~p sche~as are out to use as fo 11 ows. In addition to hei nn scanned t-v th:-· in­ terceptors nf all inactive action overlays, each input to the ovPrlay system is matched to some step schema . If the input is unambiguous, and if a suitably formal system of representational priMitives is used to represent the meaning of each input, then at most one schema will match each input. In the cattle theft example, "Jake saddled his horse," represented in EX-SPECTRE-I as {JAKE PUT SADDLE ON HORSE), matches the step schema {X PUT YON Z) . This schema represents the more general concept of an actor putting some object on top of another.

Having matched the input to some schema, the task then becomes one of locating occurren­ ces of that schema in some active expectancy in EC by upward searches from each of the schema's occurrences in the algorithm base. This opera­ tion is performed in EX-SPECTRE-I by calling the function {PARTOF <step><algorithm>) for <step>= {X PUT Y ON Z) and <algorithm> varying over the members of EC, in the order of highest saliency first. Identifications of the schema in some member, E, of the cloud define upward paths from the schema to E through SIA's. Such a path, from a step to an expectancy, is defined to be the contextual interpretation of the sentence, lJLIT.

Fig. 4 shows by dotted lines one path of length 3 which EX-SPECTRE-I discovers as an in­ terpretation of "Jake saddled his horse" in C{"Pete stole Jake's cattle"): Jake is going directly after Pete to get his cattle back. Ano­ ther interpretation not shown, but which is also discovered, is in the "Jake will inform the sheriff" expectancy: Jake is going to see the sheriff.

As a point of engineering, the motivation for searching upward through SIA's {from the step schema to the element of EC), rather than downward {from the members of EC to all possible step schema) has to do with the phenomenon that the typical commonsense algorithm teQds to be­ come quite specific after just a few levels. That is, even though the top few levels of an expectancy describe general subgoals, the lower levels begin quickly to deal with the particular details of the objects and people involved. Put another way, the infinity of detail in a common­ sense algorithm is a phenomenon of breadth ra­ ther than depth. Because of this, if the occur­ rence set indexing is refined enough, the number of relevant occurrences of a schema referenced by a particul~r input can be made quite small . This means that the branching factor in an ~P­ ward search will be small in comparison with the branching factor coming downward frOm the expec­ tancy to the step. To illustrate, even though the full occurrence set for the schema {X GOTO Y might be large, the subset of occurrences index­ ed by the particular form (X GOTO STORE) would only be 2 or 3 in number (e.g. it occurs in an algorithm for buying something, or returning something, and perhaps one or two others).

Multiple Interpretations

In any given context C(TJ , ... ,Ti). there will generally be several competing interpre­ tations . A human comprehender seems usually to be able to prefer one over the rest. Although it is too early in the research to prescribe exact­ ly how such a preference should be made by the model, two obvious factors are (1) saliencies of expectancies and (2) interpretation path length. That is, a fit of a step into an expectancy of high saliency should be preferred over a fit of that step into one of low saliency. In conjunc­ tion with this, it would seem reasonable to pre­ fer shorter interpretation paths over longer, more remote ones. In fact, in a full-scale sys­ tem, it would probably ue necessary to have PARTOF give up its scanning after, say, 10 lev­ els of some SIA; after that point, even if some interpretation could be found, it would almost certainly be obscure.

Related to these ideas is the conjecture that sequences of purposively-constructed com­ munication, say as found in children's stories, are organized so that the average contextual in­ terpretation path length will be relatively con­ stant across all cultures, relative to a typi­ cal algorithm bas~ within each culture . Per~aps the constant is 3, perhaps 8; it would be inter- . esting to ascertain whether or not such a metric exists, and if so, to discover its range. That is, on the average, how far do we have to search· to connect each thouqht in with the context? Too short and we become bored, too long and we be­ come lost.

Uses of I(T,K)

An interpretation is a useful thing in it­ self. However, once an interpretation path is discovered, two other context-related operations become possible. First, all steps "to the left" of the identified step, S, in algorithm A - those steps which must logically have preceded S in A - can be generated as inferences. That is, if we know that Jake has already saddled his horse, and this has been interpreted as part of a physical get-back, then Jake must already know who and what X andY were, have decided on some plan of action, perhaps gotten his gun, and gone to the barn. Such inferences relate to the

- ...

class of conceptual inference tenned "enablement inference" in the model of (Rl).

The second use is that the original high­ level expectancy in EC can be replaced by the set of remaining subgoals in A - those "to the right" of S in A. At that point, the system has begun to "track" a particular algorithm, and can descend from general to more specific expectan­ cies which are the subgoals remaining to be ful­ filled in the original expectancy. This narrow­ ing of expectancies is perhaps a rough approx­ imation of the way expectancies evolve from the general to the specific during the course of a human's comprehension of a story or sequence of events.

Overlay Switchers

In a system which relies upon expectancy as its primary mechanism, it seems to be as import­ ant to specify negative expectancies as well as positive ones. That is, to make explicit what classes of behavior would be "anomalous" in the current context, and to specify what the system should do when it detects an anomaly.

The switchers, WA· specify these negative expectancies by making explicit a set of patterns which are overtly anomalous in the context the overlay represents. These patterns become active at the time A is initially activated, and serve as interceptors for subsequent input which "vio­ lates the spirit" of the overlay. Associated with each negative expectancy is a pointer to another overlay to which the system should switch in case that negative expectancy is realized.

In the prototype system, there are just two switchers for the theft overlay; one of them is: {Z BE HAPPY): OVERLAY2, where OVERLAY2 represents the bundle of expectancies relevant to classes of practical jokes. At the time of writing, this negative expectancy can intercept anomalous input and prepare to switch, but no switching actually occurs yet. Details of how accumulated informa­ tion can be transfered from one overlay to ano­ ther have not been considered yet.

Related Issues

There is not room here to discuss all the related topics and questions raised by the con­ ceptual overlay approach to context. For a ful­ ler discussion, the reader is referred to the unedited version of this paper and to the new formalism for commonsense alqorithms (R3), both available upon request.

Conclusions

While the task of interpreting actions in context is only one aspect of "the context pro­ blem", its applicability is broad; even thouoh much of what we perceive is static information about the world, it usually relates, via rel­ atively low-level inference, to some action or another. In this sense, nearly everythin~ relates one way or another to algorithmic knowledge. And within this domain, one basic mechanism is as applicable to understanding why the president summoned the tape-erasing technician as it is to understanding why Mary wanted the car keys when she was hungry.

Specific conclusions are not yet in order. However, a general conclusion to be drawn is that algorithms play a central role in the in­ terpretation of volitional actions in context. Since algorithms presumably account for a large portion of a person's belief system, the theory is actually one of how interpretation of percep­ tions is influenced by beliefs. Although the is­ sues discussed have of necessity been limited in scope, I believe that the basic idea will prove to be fundamental to most other context phenom­ ena.

Current plans are to continue the develop· ment of EX-SPECTRE along the lines of the new commonsense algorithm formalism. Then, after seven more prototype version numbers, it will be time to rename the system!

Acknowledgments

My thanks to Dave Levy and Bob Abelson, who taught me about cattle thefts last summer.