Visual Analog Representations for Natural Languages Understanding

('1<-,d,t·) Tht · man wa s

{

VTSlJAl. ANAl.OC IU: I'RI·:SENTATTONS l"llR NATURA f. I AN< :lJ/1< ;E liNilERSTANil IN< ;:,

David 1.. Walt z and l.ois 1\oggess ·'"'' Advanced Automation Croup Coordinated Science laborator y University of Illinois at llrhana-Champaign Urbana, illinois 6lHOl

In order i'or a natural language system to trul y "know what it is talking ahoul ,"it must havt· a ··oniH'<" tion to th·· r ea l-world correlates of language. l'or lan gua ge desc rihin )', physical ohjects and their relations in a scene, a visual analog representation of the scene can provide a useful target struct ure to he shared by a language understanding syst em and a computer vi.sion system.

This papt> r discusses the ge neration of visual analog repre s e ntations from input l·:nglish sen­ L<'IH't'S. IL also dt·scrihes the ope ration of a I.TS I' program whi ch generate-s suc h a r e pre senta ­ ti'"' [rom s imple l·:nglish sentences de scrihing a scene. A seque nce of sentences ca n r esult in a lairly e Laborate model. The program can the n answer questions ahottt r e lationships betwee n the ohje c ts, even though the relationships in que stion may not have been explicit in the ori­ )~ illal s cPnP des c ription. R<·sults suggest that the direc t testing of visual analog r e presenta1 ion s ma y he an important way to bypass long chains of reasoning and t.o thus avoid the combill ­ ; ll i'"'''' prohl<'ms inlwn·nt in suc h reasoning methods.

1. liNili·:RSTANiliN!: I.ANt:liAt:l·: All!lUT Till·: I'IIYS ICAI. WlliU .ll

Suppos<' that W<' are g iven a sentence such as

( I ) :

• (I) A dog hit a mailman.

llow do we under s tand such a sentence ? What inferences do we make and what inferences can we make? To help answer these questions, sup­ pose that we are asked:

1. Whe r e on his body did the dog probably bite the mailman ?

We s uggest that most pe ople would answer (2) with: "on the leg," and that as a first guess, s uch an answer could plausibly he part of a IIITIN1 ; s<·ript or dt·fault slots of a frame for Il l TINt:. llowe ver, suppose that we inse rt one or more· of tlw followin g sentences aft e r (l) be­ Co_!:_'::. asking (2 ):

l da chshund.

('la,h) Th t· dog was a Jdoherman.

"itt in g .

l y in .1~ down ,

l fec·t tall.

('li' ,g) .11ll' dog wa sfs~an~in~ on its hind

sttttng.

• ·:.-·111 is work i s sttpport<·d hy the office of Naval Rl·search unde r Contract N00014-75-C-0612
• ·:.--:.-current add r ess: llr . l.ois lloggess, Computer Sc i e nce lle pt. ,Mississippi State University Mississippi State, Mi ss issippi ]9762

In these cases the answer to (2) cottld he quite different parts of the body ("arm" he­ comes most likely if bitten hy a doberman) or one cottld he much more def init e ahottt the an­ swer ("l eg" becomes ove rwhelmin g ly I ikely if one is bitten hy a da ch shund whil e standing up).

How could we successfully model in a program the understanding proce ss a pe rson goes through in this example? We suggest that the simplest and most natural way to mode l this unde rstand­ ing is to build up a visual analog knowledge base (representing "person," "dog ," etc. a s 3-D spatial entities) and to writ e programs which can manipulate and integrate these visual analog representations . For the example given (l) - (3), fiA"re I i llustratcs some of the information that wottld have to he inc luded. As anothe r exampl e , suppose we were g iven t h e following set of sent e nces:

• ( 4) A goldfish i s in a go I d fi s h how I .
• The gold[ish bowl i s on a stand .
• The she![ is on a d<'sk .
• The desk is in a room.

Now suppose that we are asked:

1. Is the goldfish in the room ·? or
2. Is the goldfi s h on the desk?

The answer to (8) should of cour se he "yes" and the answe r t o (9) should he something like "Not direc tly on, hut on is still an appropriate de­ s c ription." How could W£' mechani ze the answer ­ ing of s u ch questions?

leg"

We suggest that these questions can be easily answered if we use (4) - (7) to build an inte­ grated visual analog structure which represents (4) - (7). Then given procedural definitions of prepositions like in and on, with the "aub­ ject" and "object"* that the prepositions re­ late viewed as arguments to the procedures, we can apply the procedures to the structure dir­ ect ly to answer the questions. Boggess [2] hM written a program, described later in this paper, which works exactly in this manner. Given (4) - (7), the program constructs an analog model like that shown in figure 2.

In constructing the model, the program uses prop­ erties of the subject and object to decide what the preposition means in each given case. For example, on would be interpreted quite differ­ ently in "the shelf on the wall," and "the shadow on the wall." "The shelf" is assumed to touch the wall, be supported by it, and to have a preferred orientation and position (height) with respect to the wall, whereas none of these are true o.f "shadow. " The differences in treat­ ment are the result of noting in the lexicon that "shelf" is an ordinary physical object (re­ quiring support) with preferred orientation-~ts free surface should be horizontal--whereas a "shadow" is 2-D and weightless and thus does not require support. Each object has default di­ mensions as well as weight, and these dimenskos (actually a rectangular parallelepiped which encloses the object) can be used to construct the visual analog model.

i< Given the phrase "the cat on the mat," or the sentence, "The cat is on the mat, we call cat the subject and mat the object.

To illustrate the interpretation of this model, consider the preposition in. If in's object is a 3-D enclosure, then all-;e nee~to do to see whether the subject is in the object is tocheck whether the coordinates of all the corners of the subject are within the intervals of the co­ ordinates of the corners of the object. The answer can be found with one set of tests, re­ gardless of how many chained statements were re­ quired to relate the subject and object in the scene description. Thus, given a model like figure 2, it is very easy to answer (8) because all the dimensions of "goldfish" are within the dimensions of "room."

• +Knowledge about dt' da' d 1 , etc.
• "bite" means put (x, around (mouth (x), part-of (y))) & apply-force (x, mouth-joint (x))
• "x feet tall" => h=x, etc.

Default dog

Figure 1. Some of the information needed to understand (1) - (3).

~ Dachshund: Doberman:

d

d w h

3 1 1

4 1 3

2. USING DEDUCTIVE RULES ON ~ DATA BASE OF ASSERTIONS.

Starting with Black [1), there have been pro­ grams which dealt with similar questions. Most of these programs have "understood" sentences like (4) - (7) by adding something equivalent to an assertion of the form (ON GOLDFISH-BOWLl STANDl) to a data base . Answering questions about the scene described has then involved ap­ plying deductions rules such as:

1. (ON ?A ?B) AND (ON ?B ?C) =>(ON ?A ?C) to verify that a given relationship doesor does not hold between two given objects . In general, the set of assertions in the data base will de­ fine a network, i.e. any two items in the data base may be connected by an arbitrary number of deductive chains or direct assertions. For ex­ ample, a chair can at the same time be at a desk, under the desk and touching the desk . There are at least two serious difficultieswith using a method like deductive chaining to under­ stand the spatial domain, represented as a data

base of assertions:

1. If there are many rules and many objects, the search for a deductive chain which can prove or disprove a given relation between two objects can involve combinational explosion . Often there will be insufficient information to decide whether a relationship holds between two objects; in such a case, all relevant paths between the objects will have to be explored before a system can decide that the problem cannot be decided.
2. Even more serious is the difficulty in formulating deduction rules properly to begin wi.th. For example, rule (10) allows us to de­ duce correctly that a leaf is on a tree if the leaf is on a branch and the branch is on a tree, but it is not correct to deduce that a cow has wings if we know that a wing is on a fly and the fly is on a cow!

One obvious solution to this difficulty has been to create a number of definitions for ON--ONl, ON2, ON3, and so on, where ONl might mean "is a part of" as in "the wing on a fly," ON2 might mean "above, touching and supported by" as in "the pencil on the desk," etc. Deduction rules can then be formulated with greater precision, but we have added an additional problem: when ~ is asserted to hold between two objects or used in a question a program must now decide whether ONl, ON2, ON3, or ONn is intended. More rules delimiting the classes of objects which can he related by each meaning of on must then be formulated and somehow utilized~o decide which meaning(s) are appropriate.

But even a large number of such rules =annot easily substitute for the visual analog model . Suppose that (4)-(6) were followed by

(11) The desk is in a box.

In this case the goldfish may or may not be in­ side the box, depending on the dimensions of the box, desk, and stand (see figure 3). But how could a deduction-rule-based system give a dif­ ferent answer to these two cases, unless it im­ plicitly coded metric information? And if it coded metric information, why bother with the potentially long deductive chains?

3. OPERATION OF A PROGRAM FOR UNDERSTANDING -- -- SIMPLE lANGUAGE ABOUT SPACE.

A MACLISP program has been written by Boggess [2) which can build a spatial model of sentences involving in and on relations, and answer ques­ tions about its model. Input to the program consists of normal English sentences, which are parsed with the aid of a LINGOL [ 9 ) preproces - sor. LINGOL is an MIT-originated program pack­ age which accepts grammatical rules of the type s~NP+VP and produces LISP programs which can then parse input sentences according to the rules of the specified grammar . For this im­ plementation, UNGOL was used to single out prepositions and their semantic subject and object. For example, in the sentence, "On the bed was a box," the LINGOL portion passes the preposition on, the semantic object the-bed and the semantic subject the-box to the rest of the program. Let's follow and extended example. Input: A glass is in a box.

Resulting model: figure 4.

Figure 4 .

Comments: The glass has weight, so it ends up not only in the box, but at the bottom of it.

Input: The box is on a table. Resulting model: figure 5.

-----·-·····-----------

Comments: There is only one individual box known to the system, so the "the box" can be interpreted with no difficulty. Notice that the surface of the table is taken as the basic plane for the discussion so far, rather than putting the origin at, say, a point at the bottom of the table.

Inputs: The table is on a floor.

The floor is in a room.

Re sulting model: figure 6.

Comments: "A floor" sounds strange, but the system doesn't know for the present that tables are almost always on floors, so mentioning a particular table does not allow it to presuppose a particular floor that it could reference as the floor. As is probably becoming obvious, the model does not choose locations randomly. Rathe~ it tends toward a particular corner. This choice was made in hopes of avoiding the "findspace" problem [11] when several objects must be lo­ cated on one surface.

The current model doesn't know that a floor is part of a room . Naturally, a default-sized floor exactly fits a default-sized room, but the model has to know that a floor belongs at "ground level" or it would try to put the floor at a more or less arbitrary level in the room. While this particular sentence sounds unusual, it is natural to speak, say, of "the floor in Jonathan's room."

Suppose after all this the user types: Is the box on the table? The response from the system is YES.

To the input : Is the box on the floor? The

system responds NO.

Is the box in the room? YES Is the glass on the table? NOT DIRECTLY, BUT

ON IS STILL AN ACCEPTABLE DESCRIPTION.

The program answers these questions by directly interrogating the three-dimensional model, not by knowing that, say, if A is on B and B is in C then A is probably in C. At no time did we say that the box was in the room. But thanks to the sizes of boxes and tables and the loca­ tions of floors relative to the rest of a room, there is no question but that the box must be in the room in the most rigorous sense of the word.

It is also possible to handle situations which would be difficult for systems based on chained inference rules. For example, this program can distinguish between a glass on a tall object in a box and a glass on a small object in the box. If the tall object were large enough that the glass was exterior to the box, then this sort of model could reasonably balk at calling the glass in the box--or at least hedge, as a per­ son might . A system built on the sort of in­ ference rules mentioned above could have trouble distinguishing between these cases.

3.1 Use of Other Knowledge

If the preceding dialog were continued with "The room is in a house," the room would be placed within the volume of the house several feet off the ground, since rooms are weightless. While this seems odd (and could obviously be "fixed"), it is reasonable gi ven that houses can have more than one story. In contrast, given "The house is in a field," the model puts the house on the ground, even though houses have no weight either, as far as the model is concerned. This is because a field is a 2-D object, and the in relation implies contiguity under those circum­ stances.

Given "A shelf is on a wall," the model uses(l) Knowledge about the free surface of a wall, (2) Knowledge that a shelf's free surface is horizontal, and (3) Knowledge about typical heights of shelves to place the shelf appropri­ ately. The free-surface of a ceiling is down­ ward, so after "A light is on a ceiling," the light ends up on the correct side of the ceiling surface.

4. PROGRAM IMPLEMENTATION-REPRESENTATION OF PREPOSITIONS AND OBJECTS

The examples give~n the preceding section were from a session with a small program, written in MACLISP and run on the DEC-10 system at the Co­ ordinated Science Lah. The program consists of ab~ut 45 functions, most of them fairly short. Data for the implementation consisted of twenty­ two "definitions" of objects and the definitions of the prepositions themselves. Input to the program consists of English sentences--either statements or questions. Statements are ex­ pected to be either "naming" statements ( Tweety is a " or "Volume-1 is a book") or locative statements ("A book is on a table," "In the room is a bed"). Output is either a set of coordi­ nates for each object in the ''mental model" or a response to the question.

4.1 Object Definitions

Some sample definitions of visually perceptible objects follow (units of measurement are meters and kilograms):

(TA~LE PROTOTYPE (INSTANCE-OF FURNITURE) (TYPICAL-SHAPE ((HEIGHT 0. 75) (CROSS-SEC 1.2 0.9))) (FREE-SURFACE (((PLANE HORIZONTAL) (FREE-DIRECTION /+Z) (HEIC:HT 0.75) (DIMENSIONS 1/2 0.9)))) (WEICHT 25.0)) (!lOX PROTOTYPE (TYPfCAT.-SHAPE ((HEICHT 0.3) (CROSS-SEC 0.3 0 . 3))) (FI~ATURES (CONTAINER OPEN-TOP)) (WE r ( :HT 1. 0) ) (FLY PROTOTYPE (TYPICAL- SHAPE ((HE rc:HT 3. OE- 3) (CROSS-SEC 3.0E-3 S.OE-3))))

(CEILING PROTOTYPE (TYPICAL-SHAPE ((CROSS-SEC 3.6 4.))) (FREE-SURFACE (((PLANE HORIZONTAL) (FREE-DIRECTION /-Z) (DIMENSIONS 3/6 4.0)))) (FEATURES ((TYPICAL-HEIGHT 2.5)))) (SHELF PROTOTYPE (INSTANCE-OF FURNITURE) (FEATURES ((TYPICAL-HEIGHT 1.0))) (WEIGHT 1. 5) (TYPICAL-SHAPE ((HEIGHT 0.025) (CROSS-SEC 0.2 1. 2))) (FREE-SURFACE (((PLANE HORIZONTAL) (HEIGHT 0.025) (DIMENSIONS 0.2 1.2) (FREE-DIRECTION /+Z)))))

At initialization, the components of the typical­ shapes are used to create a simple "mental pic­ ture" of the object, in the form of coordinates of an enclosing right parallelepiped. This permanent mental picture is kept under a "local coordinates" property, with the bottom right front taken as local origin .

The definitions specifically single out planar free surfaces on a free-surface list, since it is impossible to judge from the representation whether a planar surface is a characteristic of the object itself.

Also included in the definitions is an indica­ tion of whether the object is essentially hollow as opposed to essentially "solid" throughout. The surfaces of the latter are the boundariesof matter; the surfaces of the former enclose space. The feature CONTAINER is used to indicate an ob­ ject whose interior is canonically empty. An­ other feature applied to CONTAINERs only and is used to indicate whether they are OPEN-TOPped or not.

TYPICAL-HEIGHT as part of a feature list indi­ cates that an object normally would be found at a given height above the default ground-level (either the floor or the actual ground). Other­ wise a clock placed randomly on a wall might end up very close to the floor. After using the program for a while, it became obvious that we needed to have such default heights for a num­ ber of items--clocks, windows, shelves, counters, cabinets, and so forth.

4. 2 Pre posit ion De f ini tiona

Each preposition is defined as a LISP function with the subject and object as arguments . The LISP functions are based on the results of an extensive analysis of about 20 spatial locative prepositions (see [2]). In this analysis, a num­ ber of primitives were identified, such as CON­ TIGuous, SUPPORTed, INTERIOR (2-D and 3-D), CROSS-SECTION (of objects), PROJECTION (ofCROS~ SECTIONs), TRAJECTORY, UP/DOWN, HORIZONTAL, VERTICAL, and various coordinate systems. These primitives constitute a major result of this re­ search. They will allow us to express neatly the meanings of the approximately 20 locative prepositions analyzed but not yet programmed, and seem on preliminary analysis to be an ade­ quate set for the spatial use of most of the rest of the prepositions as well (prepositions form a closed set).

Each preposition seems to have a default inter­ pretation if its subject and object are unknown, as in "the thingamajig on the whatchamacallit." The default interpretation represents a "pure" case of the prepositional relation--however the preposition can be used to describe a range of physical situations which vary from the "pure" instance by having one or more components of the default case missing or modified. For ex­ ample, the pure case of above is that in which the SUBJECT is INTERIOR (3-D) but not CONTIG­ uous to the bottom of a volume defined by pro­ j ecting the HORIZONTAL CROSS-SECTION of the OB­ J ECT upward VERTICALly in space for a distance of on the order of 3 times the object's diam­ eter. However, above can also be used to de­ scribe a variety of "impure" relationships in a scene, in~luding cases where the subject is merely at a higher level than the object (as in "there are clouds above us") and cases where the 2-D projected image of the SUBJECT is INTERIOR (2 - D) to the region defined by projecting the HORIZONTAL extreme of the 2-D projection of the OBJECT upward VERTICALLY (as in "the moon above Miami").

To give a better idea of what each prepositional definition is like, let us look at what the functions for on and in do. On is faced with - - - two decisions: it must decide which surface of the object the subject is continguous to, and it must decide which side of the subject is contiguous to the object.

If the subject does not behave normally with re­ spect to gravity (shadows, visual patterns, thin films of liquids and many insects exhibit grav­ ity-defying behavior) then any available sur­ face of the object will do.

If the subject is under gravitational con· straints, then the routine looks for one of four possibilities: in order of preference, 1) a horizontal plane in the object, 2) if the object is three-dimensional and is not an open-topped container, then the top of the object 3) fail­ ing either of these, then any planar free-sur­ face, and finally 4) any available surface. In any of these cases, the object requires support and by supposition the semantic object fur­ nishes it.

Having found the surface of the object, on looks for a probable surface of the subject. A check is made to see if the subject has a marked fre~ surface (actually a back-handed way to see if the subject has a preferred orientation). [ f it has, the preferred orientation is presumed to he the canonical one, and on passes to a function called CONTIG, not a surface of the subject hut the entire subject, thereby instructing CONTTC to translate the subject in whatever direction necessary to bring it into contact with the ob­ ject-surface indicated. On the other hand. If the subject has no preferred orientation, on se lects the canonical bottom of the subject .

The definition of the preposition in has to de­ cide if it is dealing with a container, whether the container is open-topped, and whether the subject behaves normally with respect to gravi ­ tational constraints. It then calls one of the INTERIOR functions and, sometimes, CONTIG (when the subject is assumed to be in the bottom of a container, for instance). At present, the sys­ tem has 2- and 3- dimensional interior functions, which restrict the location of their subject with respect to a plane of their object or the volume delineated by the object, respectively.

5. ~Sl>ESSMENT OF THE PROGRAM.

5.1 [nferencing Problems

One of the nice features of this "analog model" is that it holds out hope for doing inferencing and deduction by direct reference to the model, under optimum conditions, and by reference to the model plus the location restrictions under other circumstances; the construction of chains of rules can be avoided.

Two cautions are in order, however. In inter­ preting a description (building the model in the first place), it suffices to place objects in simplest possible relationships. rf a descrip­ tion mentions a book on a desk, we probably visu­ alize the book as being directly on the desk. The reverse process--judging from a mental model whether a particular preposition is an appropri­ ate description of the relation between two ob­ jects--is not always so simple. In deciding whether "above" is an acceptable description, for instance, there is little question when one ob­ ject is directly above the other, but clearly the word is acceptable even when the direct case is not applicable, and deciding these more mar­ ginal cases often leads to a lot of hedging, even from native speakers.

The second caution is best put by describing a session with the implementation: as it happe~, the particular mental model produced after "a shelf is on a wall" and "a fly is on bhe wall" was the equivalent of figure 7.

Now suppose we were to ask if the fly is under the she 1 f. The program wi 11 say "yes" . The correct answer, of course, if "I don't know," since on the basis of the description the fly might be under the shelf, but it might be else­ where too. Clearly, then, the simple expedient of directly consulting the constructed model is a little too simple. The more freedom a model allows in choosing the location of an object, the more incidental any relations between var­ ious objects may be. In the end what we know are the location restrictions and it is based on them that we need to make judgments.

5.2 Regularities

For all the hedges and caveats of the preceding paragraphs, it was evident from the implementa­ tion that paying attention to a very small set of attributes of objects yields an astonishing amount of descriptive power. The attributes in­ cluded a very rudimentary surface description, the concept of a free-surface with associated free-direction, the essential "emptiness" of containers, some notion of gravity, of contigu­ ity,of the interior relation in two or three dimensions, of part ia 1 axes of symmetry, some awareness of scale, and a coordinate system with marked vertical direction . Clearly, these concepts do not handle all cases ofdescriptions using place locatives. It might even be said that they do not handle some of the most common cases (we will come back to this in a moment). But they do handle the most typical cases--the regular uses of in, on, and the other preposi­ tions--the uses we are most likely to think of as standard. In so doing, they capture much of the descriptive power of the prepositions.

Why then could it be said that they do not handle some of the most common cases? It is well known that the most frequently occurring verbs in Eng­ lish are also the most irregular. Something of the same sort seems to apply to uses of the pre­ positions with common objects. Tables, for in­ stance, have a tendency to be treated as if they were essentially the table top- - "under the table'' for most objects means under the table top but definitely not under the legs . Rugs are an ex­ ception, of course, as are floors, and there are undoubtedly other exceptions to the mini-rule of treating the table as top only .

5.3 Is on Transitive?

As another example ot the irregularity oftables, consider a scene like that in figure 8, which can be described by ( 12a - h ) :

(12a) Volume 8 is on volume 7

(12b) Volume 7 is on volume 6

(12i) VolUIIIe 2 is on volume 1.

( 12j) Volume 1 is on the table.

Since all volumes, 1 - 8 can be said to be "on the desk" we would like some kind of tran­ sitive rule to apply, but it would not be proper (or at least it would be very-odd) to say that "Volume 8 is on volume 2 . " The hid­ den regularity here is that tables (and other furniture: desks, shelves, counters, etc.)have on relations with everything they support, dir­ ectly or indirectly. Most other objects do not have on relations with everything they support, so that, for example the top book on a stack of books on the ground is not normally said to be "on the ground . "

Fortunately, even the most common objects (in ­ cluding tables) appear to be regular most of the time, with most of the prepositions . It is in ­ teresting that some of the irregularities fall into classes, like classes of irregular verbs (sing, sang, sung; drink, drank, drunk; sink, sank, sunk). For example, "the people on the bus" are actually in the bus--they aren't on the bus in the same sense that "the people on the car" would be on the car. On has the sa~ inter­ pretation in "on the plane," "on the subway," or "on the boat"--indeed for anything that can be boarded or alternatively that one can stand up in. So at least potentially there may he classes of irregular objects .

After all is said and done, though, it is still the case that the system seems to work, andwork well, for the great majority of re~ular ob j ects , and even for the irregular ones most of the time.. It seems clear that basic understanding of the use of the prepositions is ours if only we pay attention to a small set of perceptually salient characteristics of the objects related.

6. PROBLEMS REMAINING

Clearly there will be surprises in programming the r est of the prepositions, and we have only begun to scratch the surface of the problems in implementing programs to deal with sentences like ( 1)-(3) (the "dog bites mailman" example) . However, we are already aware of some problems and exceptions to the general picture presented in t his paper.

One major problem was alluded to in the example in sec tion 5 of the fly which was (arbitrarily) placed under a shelf in the mental model and could thereafter not be differentiated from a fly s pecifically asserted to be under the shelf. Wha t seems to be needed is some way of keeping track of the range of possible positions avail­ able to objects described; we have debated sev­ eral schemes (e.g. a probability distribution for pos i tion, a tag on objects explicitly ne­ gating accidental relationships between objects, deferring the creation of a mental model until a question is raised, etc.) but are still un­ dec i ded about the best way to proceed.

Anot her difficulty (initially pointed out to us by Ph i l Johnson-Laird) is that the preposition at seems to have the function of specifying a canon i cal relation between subject and object. Thus "the chair is at the desk" describes a speci fic relationship--if the chair is upside down or facing away from the desk, it can no longer be naturally said to be at the desk. Simi larly at picks out canonical relations in "I stood at the window," "John was at the door," "I am at my desk,"etc. At seems to require specia l scenarios for each object, and is othe~ wise r egular only in that most scenarios re­ qui r e proximi ty of subject and object .

Many prepositions require that the positions of the speaker and/or listener with respect to the subjec t and object be known. For example, I could say to a listener in Japan that "Urbana is near Chicago," (it is about 130 miles away) but I would not say this to a listener 10 miles from Urbana (see [5] ).

Most difficult (and most exciting) of the pro­ blems we are aware of are the transfers ofmean­ ings f rom the spatial domain to abstrac t do­ mains. A representation of physical ob j ects . event s , and their relations should be able to be used in constructing effective representa ­ tions for abstract phenomena . An important pare of understanding the abstract use of prepo­ sitions involves identifying the "covert cate­ gories" [14] to which words belong. As an ex­ ample, cons i der the phrases below:

t out of a car We suggest that both trouble and car belong to a covert category whi ch could be called "spatia 1 enclosures," but that mischief does not belong to this category, even though its meaning is closer to trouble's than is car's meaning . This example seems to us to be similar to the mass/ count distinction in English--words like house, ~son, and book are count nouns (we can say"a house" or "two houses") whereas sand, butter, and water are mass nouns (we cannot sa~and" OR "two sands," but must add a measure phrase, e.g . "a ton of sand," or "a lot of sand") Mass nouns with common measures associated with them can sometimes be used as count nouns, as in ''Waiter, bring me two waters," and some nouns , like ~. seem to fit equally well in either category . (Such categories are extensively dis­ cussed in [12] and [14]. For those interested in this topic, Jackendoff [7] is a fascinating source of ideas; also see Waltz [13] and Pylyshyn [ 10].)

7. RELATED WORK

This research has been influenced by a number of other pieces of work; three items stand our pa~ ticularly : a thesis by N. Goguen [6], a report by G. S . Cooper [4], and a paper by H.H. Clark [3] . Cooper's work developed a set of primi­ tives and paper definitions for a number of pre­ positions . While the primitives proved to be inadequate when we began programming, this paper was an inspiration for the overall approach . Goguen wrote a program in many ways similar to this, but did not address the problems of mul­ tiple interpretations of prepositions . Clark 's paper provided valuable insights into the coor­ dinate systems underlying spatial language, and into the types of mental models people create from scene descriptions .

D. V. McDermott's TOPLE [8] dealt interesting aspects of building a of a scene from natural language. given the sentence: with some very "menta 1 mode 1" For example,

(13) The banana is under the table,bytheball. there are two interpretations: (1) the ball can be under the table, or (2) the ball can be near the table, but not under it . If we were given

(14) The banana is under the table, by the

floor lamp .

then the interpretation where the floor lamp i s near but not under the table becomes more likel~ based on the typical size of a floor lamp. Mc ­ Dermott's program is able to use size to make this type of distinction . However , the "mental model" in this work is a data base of assert i ons, e .g.

(UNDER TABLE 1 BANANA 1 ) .

Winograd's SHRDLU [15] is probably the most c losely related program, though i ts tasks were r a ther different--its "mental model" was known completely to the language understander,not con­ structed by descriptive natural language input .

• [1) Black, F., "A Deductive Question-Answering System," in Minsky (ed . ) Semantic Information Processing, Cambridge, MA:--MIT Press, 1968.
• (21 Boggess, L. Computational interpretation of English spatial prepositions. Ph . D. thesis, Univ. of Illinois, Urbana, 1978.
• (31 Clark, H. H "Space, Time, Semantics, and the Child," in T. E. Moore (Ed . ), Cognitive Development and the Acquisition of Language, New York : Academic Press, 1973.
• [4) Cooper, G. S. "A Semantic Analysis of English Locative Expressions . " (Techr.ical Re­ port No.l587), Cambridge, MA: Bolt, Beranek & Newman, Inc., 1968 .
• [5) Denofsky, M. E. "How Near is Near? A Near Specialist." Memo No. 344, MIT AI Lab. 1976.
• [6) Goguen, N. A procedural description of spatial prepositions. M.S . thesis, Moore School of Electrical Engineering, Univ.of Pennsylvania, 1973 .
• [7) Jackendoff, R. "A System of Semantic Pri­ mitives," in Schank and Nash-Webber (eds.), Theoretical Issues in Natural Language Proces­ sing, ACL, Arlington, VA, 1975.
• McDermott, D. Assimilation of New Infor­ mation by a Natural Language-Understanding System. TR-241, MIT AI Lab, 1973.
• [91 Pratt, V. R. "A Linguistics-Oriented Pro­ gramming Language," Memo No. 277 ,MIT AI Lab, 1973.
• Pylyshyn, Z. W. "Children's Internal Description," in Language, Learning, and Thought. New York: Academic Press, 1977.
• [111 Sussman, C. J. "The FINDSPACE Problem," Memo No . 286, MIT AI Lab, 1973.
• [ 121 Talmy, L. "The Relation of Grammar to Cogn ition--A Synopsis," in TINLAP-2, New York : ACM, 1978, 14-24 .
• (13] Waltz, D. L. "On the Interdependence of Language and Perception," in TINLAP-2: Theoretical Issues in Natural Language Pro­ cessing-2, New York: ACM, 1978, 149-156.
• Whorf, B. L. "A Linguistic Consideration of Thinking in Primitive Communities," in J. B. Carroll (Ed.), Language, Thought and Reality, Cambridge MA: MIT Press, 1956.
• [ 15] Winograd, 'f. Understanding Natural Lan­ ~. New York: Academic Press, 1972.
• [1) Cresswell, M. J., "Prepositions and Points of View," Linguistics and Philosophy, 1978, 2, 1-41.
• Fillmore, C. J. , "The Case for Case Reopened," in J. P. Kimba 11 (Ed.), . Syntax and Semantics, New York: Academic Press, in press .
• [3) Johnson-Laird, P., "Mental Models of Meaning." Paper presented at Sloan Workshop on Computational Aspects of Linguistic Struc­ ture and Discourse Setting, University of Pennsylvania, May 1978. To appear in a book A. Joshi (Ed . ) Cambridge University Press, 1980.
• [4) Kosslyn, s . M. and Schwartz, s . P., "A Similation of Vis1,1al Imagery," Cognitive Science 1. 3, July 1977, 265-95 .
• [5) Miller, G. A. and Johnson-Laird, P., Language and Perception, Cambridge, MA: Harvard University Press, 1976 .
• [6) Piaget, J . and Inhelder, B., The Child's Conception of ~. translated by F. J . Langdon and J. L. Lunzer, New York : w. w. Norton & Co., 1967.
• [ 7) Sondheimer, N. K. , "Spatia 1 Reference and Semantic Nets," American Journal of Computa­ tional Linguistics, 1977, 71, 1-67.
• (8] Wilks, Y., Grammar, Meaning and the Machine Analysis of Language, London: Routledge, 1972.