FOUL-UP: A Program that Figures Out Meanings of Words from Context

1. Nouns

The FOUL-UP program works solely on the basis of intra- and inter- sentence expectations, built into the parser and the script applier, respectively. Thus any conceptualization which can be "expected" in this sense by SAM should be able to be figured out from context by the FOUL-UP program, and FOUL-uP should be able to use the available expectations to construct a context-specific definition for the word, re­ gardless of its syntactic or semantic class. However, the examples so far given have dealt only with nouns. In this section, Foul-Ups of other parts of speech will be demonstrated, and it will be shown why each different syntactic class presents its own unique difficulties to the FOUL-UP program.

2. Anaphoric References

Consider the simple story:

"A car swerved off Route 69. struck a tree." The flivver

Again, we assume all the words are defined but "flivver", and we assume a run of the SAM system with this story as input. Once again, the first sentence presents no difficulty, and serves to invoke the script context which is necessary for setting up the inter-sentence expectations that FOUL-UP uses to figure out the meaning of the word. The flow of control of the SAM run of this sentence would be practically identical to that of the previous example. ELI's expectations are also similar. However, the inter-sentence ex­ pectations from APPLY are of a different form than those in the previous examples. APPLY still matches the CD for the second sentence into the $Vehaccident script, and still notes the attrib­ utes of the slot in the script conceptualization corresponding to the place-holder slot in the CD. Those attributes, however, are no longer in the form of a scriptrole specification. Instead, associated with that slot is a pointer, saying that the object in this slot is the same object as that which appeared in the ACTOR slot of the previous sentence. This is obvious when we note that (1) the script must know that the object that "swerves off the road" in an accident is the same as the object that later is said to "strike" something, and (2) SAM as a whole has the capa­ bility to resolve general anaphoric references. Thus the second sentence in the story might have read simply "It struck a tree", and the anaphoric reference to "it" would be resolved as "the car" that appeared earlier.

When such a situation occurs, FOUL-UP takes advantage of the pointer to the referent, and constructs a definition based on this pointer. Such a definition will simply duplicate the def­ inition of the word that filled the pointed-to slot, since the unknown word is presumably just another reference to the same object. Thus, the definition for an unknown word in this circum­ stance will be better than the "FUNCTION" defi­ nition of "elm" in the previous example. The definition will not simply give the function of the word in this script context, but rather will give as complete a definition as exists for the already defined word "car" which the unknown word is an anaphoric reference to. Thus in this ex­ ample, the definition created for "flivver" will be identical to that for "car":

(PROG NIL

(DEFPROP FLIVVER T PP)

(DEFPROP FLIVVER *PHYSOBJ* ISA)

(DEFPROP FLIVVER T NOUN)

(DEC FLIVVER (T (NIL ((SHAPE NP)) NIL

{QUOTE (NOUNGROUP))

{QUOTE (STARTNOUNGR)))))

(DENG FLIVVER (VAL (#PHYSOBJ TYPE (*CAR*)))

(MARKER NOUN)))

The "TYPE" specification in this definition is a reference to the entry "*CAR*" in a general dic­ tionary which defines attributes of generic ob­ jects such as cars, and their uses in certain contexts. Thus anything that SAM knows about cars it now also knows about flivvers. Further­ more, it is likely that the term "flivver" refers to a specific subset of all cars, (e.g. "sedan", "jeep"). Therefore, the term is saved, and FOUL-UP gives the term to SAM's generator program (see Goldman, 1975) to use when referring to the car in this story.

3. Verbs

1. Structure-builders vs. Slot-fillers

Consider the story

"A car swerved off Route 69. . The car hied

into a tree."

The unknown word in the sentence, ("hied"), is recognized as being a verb by ELI expectations and by the .fact that it ends in a regular verb ending. A simple place-holder cannot be straightforwardly constructed for the word, as was the case for nouns. This is because the verb in a sentence determines most of the structure of the Conceptual Dependency representation for that sentence. (see Schank, 197.5, and Riesbeck & Schank, 1976) Essentially, the verb builds the framework outline for the CD, and sets up most of the expectations as to what will come next. Then the nouns build structures which fill slots in that verb-frame. This can be illustrated by looking at a parse of a sample sentence, "John went to New York". Partially "kernelized" CD representations for sentences will be used for convenience, to facilitate references to specific pieces of the conceptualization. The internal representations of CDs in ELI are entirely "ker­ nelized" in this fashion. A partially kernelized CD for the above sentence follows:

K1: ((ACTOR (K2) <=> (PTRANS) OBJECT (K2) TO (K3)))

K2: (#PERSON FIRSTNAME (JOHN))

K3: (#LOCALE STATE (*NY*))

The word "went" builds the structure K1, with empty slots in the ACTOR, OBJECT and TO posi­ tions. The word "John" builds the structure K2, which simply fills in the ACTOR and OBJECT slots in K1, and "New York" builds K3, which fills the TO slot in K1. Although these constructs may look about the same size and complexity, it is in fact K1, the verb-frame, which drives the parse of the rest of the sentence. The verb itself sets up the expectations that a #PERSON should fill the ACTOR and OBJECT slots, and that a #LOCALE should fill the TO slot. Then when the words "John" and "New York" build such struc­ tures, those expectations dictate how they are incorporated into the CD. By contrast, the CD representation for the sentence "John hied to New York", assuming the unknown word "hied" is ig­ nored, would simply be:

K1: (//PERSON FIRSTNAME (JOHN))

K2: (//LOCALE STATE (*NY*))

This representation is simply an unordered bag of noun groups, lacking the structure usually im­ posed upon it by the verb. Assuming that this kind of structure was built in the event of a verb foul-up, the later stages of processing would be quite difficult. This unstructured bag of noun groups cannot be matched into a script, at least not by the usual methods. The FOUL-uP program performs a four-step process to enable undefined verbs to be correctly defined in terms of the context in which they appear.

b. Step 1: A "Catch-All" Verb Frame

In the event that the unknown word in a sentence is a verb, FOUL-UP must create a verb­ frame which is capable of expecting all the sub­ sequent noun groups or other slot-fillers that may occur. Such a "catch-all" verb frame looks like the following:

((ACTOR (NIL) <=> (NIL) OBJECT (NIL) TO (NIL) FROM (NIL)) TIME (NIL))

Furthe'rmore, each of the slots in this CD-frame has associated with it a set of expectations that will accept virtually any conceptual class of noun that may appear. This ensures that all words in the sentence will at least be assigned some position in the CD. Note that the resulting CD, built by ELI and FOUL-uP, will become input to APPLY's pattern-matcher, when it attempts to match the CD into the script. Thus, it is cru­ cial that the noun groups are put into the cor­ rect slots within the conceptualization, i-f--the en--is to be recognized correctly by APPLY's pattern-matcher.

c. Step 2: Preposition Matching

This step consists of using knowledge of prepositions to tentatively place nouns into their appropriate slots. Thus the prepositions TO, TOWARDS, INTO, AT expect to fill the TO slot in the CD, while FROM, OFF, OUT expect to fill the FROM slot. Finally, if no preposition is present, the OBJECT slot is assumed. This heur­ istic is dependable up to a point, but difficul­ ties arise when idiomatic uses of prepositions occur. As an example, assume the second sentence in the above story had read "The car caromed off a tree", where "caromed" is unknown to SAM. Then the conceptualization for "tree" would be put into the FROM slot in the CD, by the heuristic just stated for the preposition "off". However, the script pattern will be looking for the ob­ struction "tree" in the OBJECT slot, correspon­ ding to the normal construction "The car struck a tree". Thus the position of the nouns in the CD must be thought of as tentative, and APPLY will often have to search more than one conceptual­ ization before it finds the appropriate match.

d. Step 3: ACT Preference

The APPLY search can be limited to those conceptualizations in the script which contain at least the same noun groups as the input concep­ tualization, even if they're not in the correct slots. There are still likely to be two or more such potential matches in the script, which APPLY can not dependably decide between. Thus FOUL-uP uses an additional heuristic to aid the search, that of "ACT Preference". Based on the preposi­ tional phrase that appears in the sentence, there is quite often a unique primitive ACT implied, along with a set of expectations for the slot­ fillers. Thus if we see a sentence like "John hied to New York", we easily infer, even in the absence of a script or other large context, that the ACT in the CD for this sentence will probably be a PTRANS, because of the preposition "to" followed by a location. The prepositional phrases considered are those which contain a preposition followed by a noun group. The SAM system is able to classify noun groups into conceptual classes, such as #PHYSOBJ (physical object), #PERSON (human being), #CONCEPT (sub­ clause), #LOCALE (place), etc. When certain prepositions occur in a prepositional phrase combined with certain conceptual classes of nouns, the primitive ACT in the sentence can of­ ten be predicted simply from this information. The following table is a segment of a table of such correlations, used in FOUL-UP to help pre­ dict what the ACT in the sentence will be. Given in the table are common prepositions on one axis, and common conceptual classes of nouns along the other axis. For each possible combination of preposition and noun in a prepositional phrase (e.g. "to" and "IIPERSON" in "He gave the book to Marr"), the corresponding preferred ACT is looked up in the table (e.g. ATRANS), as well as the predicted slot in the CD for the noun to fill (the TO slot).

For each of these pairs of categories (preposi­ tion I noun class), sample sentences are abun­ dant. For example, the pair (OFF I 1/LOCALE) could arise from the sentence "The man jumped off the building", and the pair (INTO I iiCONCEPT) occur in the sentence "He looked into the inc!­ dent". The idea of "preferring" a certain set of attributes when in the presence of partial in­ formation has been used in other systems (see Wilks, 1975). Note that the table is incomplete, and thus can not always provide enough informa­ tion to allow the correct conceptualization to be chosen from the script. Further work is being done in this a~ea.

e. Step 4: Matching

Recall the story that began this section. Based on the above table, the second sentence, "The car hied into a tree", would be represented as follows:

Kl: ((ACTOR (K2) <z> (BOGUS-ACT LEXVAL (HIED)

PREFER (PROPEL)) TO (K3))

K2: (#PHYSOBJ TYPE (*CAR*))

K3: (#PHYSOBJ TYPE (*TREE*))

Note that the ACT "PROPEL" is preferred, and the conceptualization for the noun "tree" is put in the "TO" slot. When APPLY attempts to match this conceptualization into the script, it discovers one tentative match, which has the same noun conceptualizations, corresponding to "car" and "tree", but the one for "tree" is in the OBJECT slot in the script conceptualization, and in the TO slot in the CD, so the match can only be con­ sidered tentative. (This is an example of the idiomatic usage of verb-preposition pairs men­ tioned earlier.) APPLY now looks at the informa­ tion in the PREFER slot of the "BOGUS-ACT" place-holder, which says that the ACT should be a PROPEL. Since this is in fact the ACT in the script conceptualization, the match is considered successful, and the word "hied" is defined as building a PROPEL in this context. The defini­ tion that FOUL-UP creates for "hied" looks like the following: (PROG NIL

(DC HIED

ACTORSUGG BYSUGG TOSUGG (OBJECT CONREQ) TIMESUGG MODESUGG (FROM CONREQ) (TO CONREQ))

• (NIL (THREEFRAME (QUOTE HIED)) NIL (3) SUBJSUGG (OBJ SYNREQ) RECIPSUGG)))

Again, the definition is in three parts: part (1) puts the appropriate internal properties "verb" and "concept" on the word; part (2) de­ fines the conceptual (semantic) structure­ builders and the expectations for the subsequent slot-fillers; and (3) defines the syntactic ex­ pectations and slot-fillers (see Riesbeck and Schank, 1976). Note that all the information provided by the first three steps (verb-frame, preposition match and ACT preference) was in fact required by the matching process before the con­ ceptualization could be recognized as a form of

the pattern in the script.

f. Notes on how hard this all is

The process just described depends on the current state of knowledge of (1) prepositions and (2) conceptual classes of nouns. The theo­ ries behind each of these are quite primitive (no pun intended), and the above process for foul-ups of verbs is at a correspondingly early stage of development. The problem of resolving the case ambiguity of text prepositions has proved in­ tractable in many natural language systems. General rules for prepositions are riddled with exceptions and special cases, and every preposi­ tion seems to have a myriad different uses. For an example of the diversity of uses of a single preposition ("for"), see (Hemphill, 1973). Sim­ ilarly, the theory behind conceptual classes in SAM is considerably less developed than that of primitive ACTs. Other sets of conceptual classes and object primitives have been proposed in the past, and perhaps the SAM system (and FOUL-uP) would benefit from a re-examination of the cur­ rent classification system for nouns. (See

Weber, 1971, and Lehnert, 1977).

4. Adjectives

Consider the story:

"Friday, a car swerved off Route 69. The flibby vehicle struck a tree."

The meaning of the word "flibby" in the second sentence is not at all clear, nor can it be easily figured out from the context. In fact, it is not clear whether or not the adjective even changes the meaning of the sentence at all, since the sentence can be understood in this case by ignoring the unknown word. In fact, FOUL-UP at­ tempts to ignore unknown adjectives wherever possible, and cannot guess meanings for them in general. The methods used for nouns and verbs totally break down when applied to adjectives. There are three closely related reasons for this: (1) Adjectives are not expected in a sentence, in the sense of expectation we have been dealing with. Rather an adjective appears as a modifier, affecting the meaning of the noun following it. (2) There exist no primitives for adjectives corresponding to the relatively comprehensive sets of primitives within the realms of nouns and

• verbs in CD representation.
• The conceptualization built by an adjective usually occupies an "extra" slot in a CD, at­ tached to the slot filled by the noun which the adjective modifies. Thus there is no purely "top-down" way to guess a meaning for an unknown adjective, since it is inherently unexpected.

Note that the ideas of expectation, conceptual classes, and slot-filling are all closely related. The expectations in both ELI and APPLY are based on differentiation between various conceptual classes of objects, and the slots are filled on the basis of the expecta­ tions. Thus the lack of conceptual classes of adjectives causes the other difficulties, and they should notlb; viewed as independent prob­ lems.

CONCLUSION: LIMITING CASES

It was stated earlier that there might be no theoretical limitation on the classes of words that FOUL-UP could figure out from context, as long as there existed ELI and APPLY expectations for the conceptualizations built by a word. We have now seen, however, that different syntactic classes of words present varying degrees of dif­ ficulty to the FOUL-UP program. The difficulties arise depending on (1) the consistency and com­ pleteness of the existing representational schemes for a given syntactic class, and (2) the amount of information contained in the structures typically built by words in that syntactic class. Furthermore, · we have seen that the issues of ex­ pectation on the one hand, and conceptual class on the other, cannot be easily separated. Thus the expectations for the members of certain syn­ tactic classes are stronger than for others, de­ pending on the relative thoroughness of the rep­ resentation schemes for those classes. Thus strength of expectation is also a (dependent) factor contributing to the ease or difficulty of

the FOUL-UP task within a given syntactic class.

Nouns are typically slot-fillers, builders of small structures containing relatively little of the overall information present in a given conceptualization. They also have a reasonably consistent and complete representation in terms of conceptual classes. Thus the process for figuring out unknown nouns from context is rela­ tively straightforward. Verbs are builders of large structures which contain most of the ex­ pectations for a given sentence, and which supply most of the structure to conceptualizations. They also have a consistent and complete repre­ sentation in terms of primitive ACTs. Thus they are more difficult to figure out from context than nouns. Adjectives are not well defined or consistently represented in CD, and they build structures of varying size and complexity. Fur­ thermore, being conceptual modifiers, they lack pre-defined slots to fill in a conceptualization. Thus it is natural that they should be most dif­ ficult, if not impossible, to figure out from context.

Assuming that all words can eventually have their meanings represented in something akin to Conceptual Dependency representation, then there would still be limitations on FOUL-UP's ability to figure out words from context. To perform the process, a strong top-down context, like a script, is needed to provide the expected at­ tributes of unknown words. Other large top-down frameworks, such as plans (see Schank & Abelson, 1977) or belief systems (see Abelson, 1973), should theoretically provide enough context to enab'le words to be figured out from those con­ texts. For example, consider the following "planny" story:

"John saw a menacing figure approaching his store. He reached into the desk drawer and pulled out a magnum."

The word "magnum" in this story is highly ex­ pected to be some kind of weapon or other pro­ tective device. That expectation could be set up by a plan-applier mechanism (PAM) (see Wilensky, 1976), and a version of FOUL-UP could theoreti­ cally use such expectations to guess the meaning of the unknown word. However, scripts are very explicitly defined sequences of actions, while plans are much less explicitly sequenced, and belief systems still less so. It is to be ex­ pected that the ability to figure out words from context will diminish as the strictly episodic nature (and thus the strength of the expecta­ tions) of the knowledge database diminishes. Thus scripty stories are ideally constructed for figuring out words from context, plans are less so, and belief systems still less. It is worth­ while to reiterate that the representations being discussed are intended as models of the human understanding process, and thus that the abili­ ties and limitations of the programs are modelled after analogous processes in people. The FOUL-uP program was designed to simulate a known human ability, and to add this ability to the already existing SAM system. Since SAM is intended to model the human understanding process within the realm of script-based stories, it is encouraging to note that the limitations of the FOUL-UF seem to closely parallel the limitations of people's ability to perform the same task. Certainly a program intended to model humans will not be able to out-perform them, but rather should show the same sorts of abilities and shortcomings that people show. In that sense, the FOUL-UP program has demonstrated some psychological validity for the SAM system, and for Conceptual Dependency representation itself.