An Adaptive Natural Language System That Listens, Asks, And Learns

1 . INTRODUCTION

A nu.ber of syst .. s are being developed Which co.aunicate with users in a natural language such as English. The ultiute purpose of such syst .. s is to provide easy coaputer access to a technically unsophisticated person. When such a person interacts with a natural language syst·, however, he is quite likely to use words and expressions which were not anticipated. To provide truly natural interaction, the syst .. should be able to respond intelligently when this happens.

Nost current syst .. s, such as those of Winograd [10] and Woods [11], are not designed to cope with such "linguistic input uncertainty.· Their parsers fail coapletely if an input sentence does not use a specific, built-in syntax and vocabulary. At the other extr ... , syst ... like ELIZA [9] and PARRY [2] allow the user to type anything, but uke no atteapt to fully understand the sentence. The present work explores the ·iddle ground between these extr ... s: developing a syst .. which has a great deal of knowledge about 1 particular subject area, and which can use this knowledge to uke language interaction a flexible, adaptive, learning ·ediua.

In pursuing this goal, the present work is aost closely related to work being done in the various speech recognition efforts [5, 7, I, 12] which are studying how linguistic and seaantic constraints can help deal with the ACOUSTIC error and uncertainty of speech. The adaptive syst·, however, is designed to dell with a auch aore LINGUISTIC type of uncertainty.

When people use unf .. iliar words or expressions in conversation, we can usually deduce froa context what is Hant, and if not, we can at least ask intelligent clarifying questions. To allow the .. chine to do the s .. e, there aust be a very flexible interaction of syntax and s.-antics in the parsing/understanding process. There aust be a different parser organization, and a aore flexible use of linguistic and s ... ntic constraints, than is present in current natural language syst ....

The adaptive syst .. is a step towards this goal. The current iapl ... ntation is a prototyPe,

Perry L. ·uner Rlssachusetts Institute of Technology C.-bridge, Nassachusetts

designed to illustrate aany of these ideas, and to tie th .. together in a restricted syst .. that is coaplete but not too coaplex. The syst·'s do.ain of discourse is TIC-TAC-TOE: it plays a g ... and discusses the g ... in progress. It has a (currently liaited) set of s ... ntic concepts, and atteapts to interpret the user's sentences in teras of these. The set of s .. antic concepts is FIXED. The syst .. does not att .. pt to learn new concepts , aerely new ways of describing concepts that are already f .. iuar.

When the syst.. encounters a new word or a new phrasing, it uses contextual inforution to deteraine the possible .. aning, and to ask clarifying questions which are as intelligent as possible. It then r-...bers the .. aning of the new expression, and will usi it itself when it talks.

2. SAftPLE IES§IQN

The best way to introduce the syst .. is to show it in operation. In the s .. ple session that follows, user input is preceded by ·u:·, .. chine output by "ft:·, and caa.ents added by the author are in ... 11 type, enclosed in brackets.

(NACHINE: I PLACE AN X IN THE TOP LEFT IIQUARE)

(X · -) (- - -) (- - -) [The .. chine .. kes its opening aove . ] (USER: PLAY A ZERO IN THE CI.NTER IQUA!ll) (N: IS ZERO A NOUN NEANING 0) (U: YES) (N: ~) (X - ·) (- 0 -) (- --) [The new word ·zero· is added to the .. chine's vocabulary.] · (N: I PLACE AH X IN THE BOTTOII RIGHT IQUARI) (X - ·) (- 0 -) (- - X)

(U: SLAP AN 0 IN THE BOTTOII LEFT CORNER)

(PI: IS (TO SLAP SOPIETHING SOPIEWHERE) A WAY OF lAYING (TO PLACE 'SOliE THING SOIIEWHERE))

(U: YES)

(PI: Ol)

(X - -)

(- 0 -)

(0 - X)

[A new surface rr ... (as described in section 4) is added to the set or surface rr ... s which express the concept or -.king a .ove.]

(PI: I SLAP AN X IN THE TOP RIGHT 8QliARE)

(X - X) (- 0 -)

(0 - X)

[In this s .. ple session, the .. chine uses ita newly acquired vocabulary at every opportunity.]

(U: HOW conE YOU PLACED AN X IN THE TOP RIGHT RIM£)

(PI: I§ (IDI COPIE 80fiEONE DOES IOIIETHING) AN EXPRE§§ION PIEANING (WHY DOEI DIEONE DO IOIIETHING))

(U: YES)

(PI: Ol)

(PI: TO BEAT YOU)

[A new surface rr ... is added to those expressing the concept 'WHY'. Syntactic features are associated with each such rr ... indicating such things as whether subject-verb inversion is to be perforMd.]

( U: CAN YOU CURRENTLY BEAT liE)

(PI: I§ CURRENTLY AN ADVERB REFERRING TO THE TIPIE OF A PIOVE)

[These are the only adverbs the syst .. knows about. In fact, at present, the systea ignores adverbs in ita seaantic processing. It asks the question because it wants to account for all the words in the sentence.]

(U: YES)

(PI: Ol)

(PI: YES)

( U: AFTER YOU PLAYED AN X IN THE TOP \fEST SQUARE COULD I BEAT YOU IF I PLAYED AN 0 IN THE B0TT011 RIGHT SQUARE)

(PI: IS WEST AN ADJECTIVE PIEANING) EITHER

(1: CORNER)

(Z: LEFT)

(U: 2)

(PI: Ol)

(PI: NO)

[Notice that two top squares contain an x. However, only the left one was played while the botto. right square was free. Therefore the syst .. concluded that the top left square was being described. This ex .. ple illustrates how contextual inforaation can be used to ask as intelligent a clarifying question as possible.]

( U: HOW conE YOU PLACED AN X IN THE TOP WT SQUARE)

(PI: IS WT AN ADJECTIVE PIEANING)

EITHER

(1: RIGHT)

(2: WEST)

(U: 1)

(PI: Ol)

(PI : TO BEAT YOU)

[Here, either top square aight have been referred to.]

(U: WHEN I PLAYED AN 0 IN THE BOTTOII LEFT SQUARE COULD YOU BEAT PIE)

(PI: IS (WHEN SOfiEONE DOES SOPIETHING) AN EXPREIIION PIEANING (AFTER 80fiEONE DOE3 SOPIETHING))

(U: YES)

(PI: Ol)

(PI: YES)

[In the do.ain of this TIC-TAC-TOE discussion, ·when· and ·after· have the ...... aning.)

[The next two sentences each contain two probl ... for the ayat .. to resolve.]

(U: WHEN YOU PLAYEQ AN X IN DIE TOP RIGHT CELL CQULD I PEP YOU FROB BQTIMj ftE)

(PI: IS CELL A NOUN PIEANING SQUARE)

(U: YES)

(PI: Ol)

(PI: IS (TO lEEP SOPIEONE FROPI DOING SOPIETHING) A WAY OF SAYING) EITHER

(1: (TO PREVENT SOMEONE FROPI DOING SOMETHING))

(2: (TO ALLOW SOPIEONE TO DO SOMETHING))

( 3: (TO FORCE SOPIEONE TO DO SOMETHING))

(U: 1)

(PI: Ol)

(U: If I LAY AN 0 ON THE RIGHT SIDE sguME HOW CAN YOU POLISH fiE Off)

(PI: IS (TO LAY SOPIETHING IOPIEWHERE) A WAY Of SAYING (TO SLAP SOPIETHING 30PIEWHERE) )

(U: YES)

(PI: Ol)

(PI: IS (TO POLISH SOPIEONE OFF) A WAY OF SAYING) EITHER

(1 : (TO BEAT SOPIEONE) )

( Z: (TO LOBE TO SOMEONE) )

(3: (TO TIE SOPIEONE))

(U: 1)

(PI: Ol)

(PI: BY LAYING AN X ON THE TOP CENTER CELL)

[If this s ... session were subsequently repeated, of course, the system would not need to ask any questions of the user.]

2.1 C9111nts on Current Ltlitations

There are a nulber or ltaitations to the adaptive syst .. as it now stands. &o.e of these .. Y be apparent in the saaple session, but an introduction to the systea is not co.plete without discussing th .. explicitly.

1. The nu.ber of concepts available to the syst .. at present is very ... 11. This, in fact, is why the systea' s first guess is usually the correct one. If the sentence is at all within the syst .. ·s co.prehension, the options as to its .. aning are currently quite liaited.
2. (Z) The range of expressive devices presently recognized is quite liaited as well. for instance, the syst .. does not recognize relative clauses, conjunctions, or pronouns (except for I and you).
3. ' (l) The systea currently deals only with TOTALLY UNFAMILIAR words and expressions in this aHaptive fashion. It will not correctly handle f .. iliar words which are used in new ways (such as a noun used as a verb, as in ·zero the center square·).
4. The systea tries to aap the aeaning or new words and expressions into its specified set of underlying concepts. It then displays its hypotheses to the user, giving hia only the option of saying yes or no. The user cannot say ·no, not quite, it .. ans ··. ·. (Thus concepts like "the 'northeast' square· or "the 'topmost' square· would be confusing and not correctly understood.)

The present siaple systea has been developed with two goals in aind: (1) to explore the techniques required to achieve adaptive behavior, and (Z) to help formulate the issues which will have to be faced when incorporating these techniques into a auch broader natural language syst... ·

fig. 1 shows the various stages that the Adaptive Syst .. goes through in understanding a sentence. In this section, we shall watch while the systea processes the sentence "How co.. you placed an x in the top right square.· ·

(1) Local Syntactic Processing: In this first stage, the systea $Cans the entire sentence looking for local constituents. These include "simple" noun phrases (NPs) and prepositional phrases (PPs), ("simple" aaaning ·up to the head noun but not including any aodifying clauses or phrases·), and verb groups (VGs) consisting or verbs together with any adjoining aodals, auxilliaries, and adverbs. In this instance, the systea finds the two NPs, ·you· and ·an x·, the PP "in the top right square·, and the VG "placed".

(Z) S...ntic Clustering: At· this stage, the clause-level processing starts.

Unlike aost systems, this clause-level processing is driven by SEftANTIC relationships, rather than by syntactic form. It uses a semantics-first ·clustering·, with a secondary use or syntax for comments and confirmation. In this example, all the local constituents round can be clustered into a description or a single concept: that or .. king a move. Section 4 describes the aachanics or this stage in more detail.

(3) Cluster Expansion and Connection:

• During this stage, an atteapt is made to account for each word in the sentence by expanding the concept clusters, and if there is aore than one, by joining them together to form an entire aulticlausal sentence. In this case, the concept cluster aight be expanded in two ways.
• One possibility might be that it is a "HOW" type question, and that ·come· is soae sort or adverb. However this possibility violates a semantic constraint, since the systea is not set up to answer how a move is made; only how to win, how to prevent someone from winning, etc. Therefore this possibility is ignored.
• The other possibility is that "how coae· is a new way or describing some other clause function.

(4) Contextual Inference; Clarification; and Response:

During this final stage, any contextual infonaation available is brought to bear on areas or uncertainty, any necessary clarifying questions are asked, and the systea responds to the sentence. In this example, the only uncertainty is the meaning or ·how come·. Since this is the aain clause or the sentence, the possibility or its being an "if" or ·arter· clause are discarded. The reaaining possibilities are "iaperative·, "how·, "why", and ·can·. The system does not answer "how" and ·can· questions in relation to aaking moves. Similarly, "imperative· does not make sense since the action described is a previously aade move. tbarefore the system asks if ·How come someone does something· means "Why does someone do something·. The user answers ·yes·, so the systea stores this new way or asking ·why·, and proceeds to answer the question.

4. SEftANTICS-FIRST CLAUSE-LEVEL PRQCESSIHG

One or the major differences between this approach to parsing and that or a top-down, syntax­ driven system (such as Woods' or Winograd's) is the order in which syntactic and s .. antic processing is done at the clause level.

In a top-down systea, a sentence must exactly match the built-in syntax before semantics can even be called and given the various constituents or a clause. This is clearly undesirable when one is dealing with input uncertainty, since one cannot be sure exactly how the user will phrase his sentence. One would prefer to let semantics operate first on any local consituents present, so that it can make a reasonable guess as to what is being discussed.

As semantically-related clusters or local constituents are round, syntax can be consulted and asked to comment on the relative grammaticality or the various clusters. If there are two competing semantic interpretations or one part or a sentence, and syntax likes one much oetter than the other, then the ·syntactically pleasing· interpretation can be pursued first. Later, if this does not pan out, the syntactically irregular possibility can be looked at as well. In this way, syntax can help guide the system, but is not placed in a totally controlling position.

A by-product advantage or this semantics­ first approach is that the system can handle aildly ungrammatical input without any extra work. In addition, the semantics-first clustering approach lends itself quite naturally to handling sentence fragments.

In the remainder or this section, we describe how the adaptive system organizes its linguistic knowledge to implement this semantics­ first approach. As we shall see, there are three components or this knowledge.

(a) The local recognizers which initially find local constituents. These recognizers are represented in Augmented Transition Network [11] fora, are quite simple, and are not described further in this paper. (b) Clause-laval knowledge of how actions and clause-functions are described. This knowledge is expressed in a descriptive fashion which makes it easily manipulable, and easy to add to. (c) Clause-level syntactic knowledge which is expressed in a domain-independent fora.

4.1 Knowledge of how Actions are Qescribad

Figure Z illustrates how the systea stores its knowledge or how actions (or events) are described. This knowledge is stored at two levels: the conceptual level, and the surface (or · expressive) level.

CONCEPT: #PLACE

CONCEPTUAL SLOTS:

P: player

ft: mark

S: square

SURFACE FRAftES:

VERB: place

AGENT: P

OBJ: ft

in: S

VERB: play

AGENT: P

OBJ: ft

in: S

VERB: play

AGENT: P

(as in:

I place an x in the center)

(as in:

I play an x in the center)

(as in:

I play the center)

OBJ: S

Fig. Z: Linguistic Knowledge about Actions

As shown in Fig. 2, the concept IPLACE represents the act or making a TIC-TAC-TOE move. (a) On the CONCEPTUAL level, there are three ·conceptual slots· indicating the actors which are involved in the action: a player, a mark, and a square.

(b) On the SURFACE, or expressive, level there is a list or surface frames each indicating one possible way that the concept can be expressed. Each surface rr .. e consists or a verb plus a set or syntactic case rr ... s to be filled by the actors. (Notice that neither the conceptual slots nor the surface rr ... s indicate explicitly the order in which the various constituents are to appear in a sentence.)

When the system processes a sentence, it fills the conceptual slots with local constituents found in the sentence. If it has found a f .. iliar verb, then it also gets any surface fr ... (s) associated with that verb. At this point it calls syntax, asking for comments.

For instance, if the input sentence is "I place an x in the corner·, then all the conceptual slots of #PLACE would be filled, and the syst .. would pass the following string to syntax ·agent verb obj pp·. As a result, clause-level syntax does not see the actual constituents of the sentence, only the labels specified in the surface case fr ... , plus infonaation indicating nu~er, tense, etc .

An interesting aspect of this approach is that the clause-level syntax is entirely da.ain­ independent. It knows nothing about TIC-TAC-TOE, or even about the words used to talk about TIC-TAC-TOE. The surface fr .. es allow semantics to talk to syntax purely in teras of syntactic labels. As a result, one could write a single syntactic .adule, and then insert it unchanged into .. ny da..ins.

4.1.1 Using this Infonaation

In this section, we describe in more detail how this knowledge can be used when precessing a sentence.

(1) If the verb and constituents are f .. iliar: If there is no uncertainty in a clause, then each constituent can be put into one of the conceptual slots, and any surface fr ... s associated with the verb can be ex .. ined. The rr ... indicates the case (agent, object, etc.) associated with each constituent when that verb is used. The rr ... is used to create a string of case labels that are sent to syntax for comments.

For instance, if the sentence is "I place an x in the center square·, the string passed to syntax is ·agent verb obj pp·. Syntax replies that the sentence follows normal order. Had the string been ·verb obj pp·, syntax would reply that the subject had been deleted. If the string was "do agent verb obj pp·, syntax would reply that subject-verb inversion had taken place. Given ·agent obj verb pp·, syntax would reply that the object was out of position.

Thus syntax is set up to notice both grammatical and ungrammatical per.utations in constituent order, and to co.aent appropriately. The systea aust then decide how to interpret these ca.ents.

For instance, if syntax replies that the object is out of position in the clause, or that there is incorrect agreeaent in nu~er between subject and verb, the systea .. y decide that the user has .. de a ainor grammatical error, and allow the sentence to be processed anyway, especially if there is no better interpretation of the sentence. In this way, clause-level syntax plays an assisting role rather than a controlling role in the analysis or a sentence.

(2) If a constituent is unknown:

If an unknown constituent is present, then both the rr ... and slot infonaation can be used to help resolve its .. aning. For instance, suppose the sentence is "I place a cross in the center square·, and the word ·cross· is unf .. iliar.

Here, during the semantic clusterina, the conceptual slots for a player and a square can be filled by ·J· and "in the center square·, but the slot for a mark is unfilled. In addition, there is the unknown constituent ·a cross·.

A natural hypothesis, therefore, is that the unknown constituent refers to a type of .. rk. Since the verb is faailiar, a surface rr .. e is available. Next, assuming the unknown constituent is a .. rk, the string ·agent verb obj pp· can be passed to syntax. When syntax approves, this offers additional confirmation that the hypothesis is probably right.

Subsequent evaluation or this hypothesis indicates that the sentence .. kes sense only if tbe mar·k referred to is an x, so the syst· asks 1f ·cross· is a noun .. aning ·x·.

(3) If the verb is unknown:

If an unfamiliar verb is used, then there is no surface frame available to help guide the analysis. Instead, syntax aust be used in a different mode to propose what the surface fr ... should be.

Suppose the sentence is ·J plunk an x in the center square·. Here, all the constituents can be clustered into the concept #PLACE, but-there is an unknown word, and no verb. The logical hypothesis is that the new word is a verb. A special· syntactic module is therefore passed the following string "NP(P) verb(plunk) NP(") PP(in,S)". This aodule ex..ines the string and produces a new fr ... :

VERB: plunk AGENT: P OBJ: ft in: S

The system can then ask if ·to plunk something somewhere· .. ana ·to place soaethint somewhere·, and upon getting an affinaative re,ly, can add the new fr ... to those associated with the concept #PLACE.

Since the syst .. uses the surface fr ... s to generate its own replies, it can now use this new fr ... itself when it talka. When the syst· wants to generate I clause, it PISSIS a selected fr ... , the constituents, and a list of syntactic features to a clause generator which outputs the specified fora. (Thus, clause-level syntax can be used by the system in three different modes: (1) to ca..ent on the gramaaticality of a string of case .. rkers, (2) to construct a new surface fr ... , and (3) to generate clauses when the systea itself re,lies.)

4.2 Knowledge of how Clause-Functions are Described

As illustrated in Fig. 3, knowledge of hew clause-function concepts are described is also expressed as two levels.

Each clause function has a conceptual slot indicating what types of action can be used with that clause type (in this case, the action #PLACE), and a list of surface fr .. es indicating different ways in wh.ich the concept can be expressed.

A clause-type fr ... currently includes any special words which introduce the clause (ie. "why" or "how come"), together with e list of syntactic properties which should be present in the clause.

This list of syntactic properties ·ight include SVINV, ·subject-verb inversion· (as in ·why does someone do something·), or ·subject deletion·, ·ING fora·, and ·use or a particular preposition· (as in ·rroa doing something·).

CONCEPT: IWHY

CONCEPTUAL SLOTS:

ACTION: #PLACE

SURFACE FIWIES:

Why ACTION(SVINV)

How coma ACTION()

(as in: ·Why does soaeone do soaathing·)

(as in:

·How coae someone does soaething·)

Fig. 3: (nowledga about Clause Functions

These syntactic features, however, need not be inflexible rules. Sentence understanding can still proceed even if the syntactic features round by syntax do not exactly aatch those specified by the clause-function rraae. Thus, an inadvertent ungramaaticality can readily be recognized as such, and processing can continua.

4 .· 2.1 Usina the Clause Function (nowladaa

In this section we axaaine how this clause function knowledge can be used.

(1) With no uncertainty:

If the input sentence is ·Why did you place an x in the center square·, than during the saaantic clustering the string ·do agent verb obj pp· is passed to syntax, which replies that subject-verb inversion has taken place.

When examining the whole clause, the syst .. sees that it exactly matches one of the surface fraaes for a IWHY-type question, since it starts with the word ·why· and contains subject-verb inversion.

Suppose, however, the sentence had bean ·Why you place an x in the center square·, or ·How cODa did you place an x in the center square·. Each of these sentences matches a surface frame for a #WHY­ type question, except that in both cases subject­ verb inversion is incorrect. In such a case, the system can, if it chooses, decide that the user has made a minor error, and allow the sentence to be processed anyway. The locally-driven seaantics­ first approach lets this happen in a natural way.

(2) A new surface frame:

Another problem arises when a new clause introducer is encountered, as in: ·Wherefore did you place an~ in the center square·. Here, as described in section 3, the system hypothesizes that this may be a new way of asking a IWHY-type quest~on. Since syntax reports that subject-verb inversion has taken place, the system can therefore create a new surface fraae:

Wherefore ACTION(SVINV)

to be added to the fraaas associated with #WHY.

4.3 Cowents

In summary, the adaptive systaa stores its linguistic knowledge in a very accessible fora. It is not embedded in the parsing logic. (nowladge or how actions and clause-functions are described is represented in a descriptive, manipulable format. Syntax is domain independent, and is used only to make co .. ants, with seaantics playing the guiding role. This organization allows the parsing/understanding procais to proceed in a flexible fashion.

5. FLEXIBLE ORGANIZATION OF SEPIANTIC CONSTRAINTS

In an adaptive parsing system, semantic constraints must also be in a flexible, aanipulable form so that they can assist in the infaranca-aaking process. This contrasts with a non-adaptive syst .. (a system where the syntax and vocabulary is assumed to be fixed). In a non-adaptive syst .. , se..ntic constraints can often be included in an ad-hoc fashion, without really being explicit about how they interrelate.

To illustrate this difference, let us consider the following sentences.

(1) After you played the top WEST square could I beat you if I played the bottom right square.

(Z) After you played the top right square could I beat you if I played the bottom WEST square. [We shall assume that the word ·west· is not known to the syst ... ]

First let us see how a non-adaptive syst .. would handle such aentencas, assuaing no unknown worda. (Sea Fig. 4)

(a) When it encounters the ·after· clause, it looks in ita liat or past moves to see if one .. tchas the description given. If so, the resulting board position is used as context for the rest of the aentence. If not, the systaa aborts, giving an error mess,age such as ·You have referred to a non­ existent past aove·.

(b) When processing the ·if· clause, the syate· takes the board position produced by the ·arter· clause, and sees if the move referred to is legal in that context. If so, it produces a new board position. If not it aborts with an error message such as ·You have proposed an illegal move·. (c) Finally, when processing the main clause, the aystem takes the board position produced by the ·ir· clause and examines it to answer the question.

Thus, the following seaantic constraints are progr ... ed in: (a) that the move described in an ·after· clause must refer to a previous move, and (b) the move described in an "if" clause must be legal in its board position context.

In an adaptive syste·, these constraints can be used in an active fashion to help infer the meaning of new words. For instance, if sentence (1) is to aake sense, then "the top west square· must refer to a square played while the botto. right square was free (ie. was still a legal move). Thus, as illustrated in the s .. ple session, if two top squares contain an x, but only one was played before the bottom right square was filled, then that must be the square being described. Si·ilarly, in sentence (2), "the botto. west square· must refer to some square that was free when the top·right square was played.

Thus the semantic constraints which ar~ added almost as after-thoughts in a non-adaptive system to handle the unlikely event of a user typing NONSENSICAL input, beco.e a central part of the inferential .. chanis. in an adaptive syste·, for the very reason that they allow the syste· to discard NONSENSICAL INTERPRETATIONS of the .. anings of new words.

These two sentences also illustrate that such constraints can operate globally between widely separated parts of the sentence. Furthen10re, they can operate equally effectively in two (or more) "directions·. In other words, certainty in the "if· clause can help resolve uncertainty in the ·after· clause, or alternately, certainty in the ·after· clause can help resolve uncertainty in the "if" clause.

Notice that there is also a third "direction· in which these constraints can be used. Consider the following sentence.

(3) WHEN you played in the center square could I beat you if I played the top right square.

If "when· is an unknown word, then the system must try to infer what clause-function it might refer to. In so doing, the system checks whether the "when· clause describes a previous .ave whose subsequent board position allows the move described by the "if" clause. If so then "when· might mean ·after·. If not, then "when· presuaably means something else. Here we see certainty inside the two clauses helping resolve uncertainty as to the function of one of the clauses.

The clear implication of these ex .. ples is that these semantic constraints lUSt be incorporated in a much more systematic and flexible fashion than is necessary in a non-adaptive syst ...

5.1 l·pleaentina these Constraints

The adaptive syste· handles this probl .. as follows:

(a) · If there is uncertainty in the ·after· clause, then it produces not ONE, but rather a LIST of board positions (corresponding to different possible interpretations of what the clause ·eans). Associated with each is the uncertain constituent (in this case, the NP "the top west square·) and the referent of that constituent that corresponds to that board position possibility (ie. the actual square which the NP might be describing). Each of these board positions are fed in turn to any "if"

clauses in the sentence. During this process, the semantic constraints might invalidate some of these board positions. This leaves the syste· with a more selective group of referents that the NP ·ight be describing. In this way, the user can be asked a clarifying question that is as "intelligent· as possible. ·

(b) A similar process takes place if the "if" clause contains uncertainty. A list of possibilities is co.piled by the "if" clause, tested in further ·tf· clauses (if any), and only then is the user asked for clarification.

This method is ONE way of allowing such semantic constraints to help the inference process, and thereby let the syst .. ask as intelligent questions as possible. There are a great aany intra-utterance constraints of this sort, whose nature and implications have never been systematically explored. The develop.ant of adaptive parsing techniques will provide motivation to explore these more fully.

This example, in fact, illustrates a much more general phenoaenon. In natural language, there are aany levels of syntactic and s ... ntic knowledge which contribute to the understanding of a sentence. These all interact, and therefore constrain each other in complex ways. In a fully adaptive syste·, one must be prepared to help resolve uncertainty on ANY of these levels by 'taking advantage of certainty on many other levels. To allow this, one is forced to think out fully and syst ... tically exactly how all this knowledge interacts. This could be one of the greatest contributions of studying language fra. an adaptive standpoint.

6. SENTENCE CLABifiCATION AND EVALUATION

In this section, we describe how semantic constraints can ba used to resolve input uncertainty. After the semantic clusters have been formed, cluster expansion and connection groups these into one or more sentence hypotheses. Each sentence hypothesis is a set of clauses which span the entire sentence . The system must then "evaluate" these clauses (ie. determine their meaning).

The clauses are evaluated in the following order . first any "after" clause is evaluated. Then any "if" cl~uses are evaluated left to right. finally the main clause is evaluated. Thus if the sentence is

"[if A][after B][could C][if D]" the clauses would be evaluated in order B, A, D, C.

In the process of this evaluation, any uncertainty present is resolved . The un.certainty might be that a constituent contains an unknown word, or it might be due to the use of a new action or clause-function surface frame.

Constituent Uncertainty:

Sometimes constituent uncertainty can be resolved from information available in a stngle clause. Sometimes information from several clauses

is used. For exanple , consijbr the clause "After I placed a circle in the center square". If the word "circle" is unknown, then as described in section 4, previous processing indicates that this is an "after" clause describing a move, and that ·a circle" probably refers to some mark . To evaluate this clause, the system examines the previous moves and presumably finds that "I" indeed did play in the center square and that the mark involved was an ·o·. Thus the likely meaning of "circle" is resolved from information available entirely within this clause.

On the other hand, as described in section 5, with the clause "After I placed an o in the top WEST square", if "west" is unknown then several squares may be being described. Section 5 describes how the system allows information from other clauses to constrain the square being described. When as restricted as possible a list of squares is finally determined, it is passed to a routine whose job is to resolve noun phrase uncertainty. In this case, the routine will examine the different adjective­ concepts (such as #RHiiH, #LEFT, #CORNER, I BOTTOM, etc.) to see which might describe possible squares, and then ask. the user which was meant.

New Surface Frame Uncertainty:

If a new surface frame is used to express a familiar action (ie. a new verb and/or prepositions marking the NPs), the different possible meanings are automatically considered when the system attempts to fill the conceptual slots of different action concepts. Even if only one concept has the a'ppropriate slots, the system asks to be sure . Sometimes, however, several actions have the same conceptual slots (such as "I beat you·, "I tie you", and "I lose to you"). In this case, of course, the system must ask which was meant.

If a new surface frame is used to express a familiar clause function, the system currently uses the following simple constraints to delimit its possible meaning . Each sentence is assumed to have one and .only one main clause. "After· clauses must describe a previous move. "If" clauses must describe some possible move (either in the current game context, or in the context of any "after· clause in the sentence) . "Why" clauses must refer to a previous move. "Can" and "How can" clauses must refer to the action of beating, tieing, losing, preventing, allowing, or forcing. Imperative clauses must refer to a possible current move. In our simple domain, these constraints usually delimit the meaning ~f a new surface clause-function frame to a single possibility.

This section has described how the adaptive system can constrain input uncertainty. Clearly, in a more complex domain, one would want to use much more sophisticated constraints. The important point is that the locally-driven, semantics-first design provides a very natural framework for incorporating such constaints. The purpose of the present work is to take a first step in exploring the design of such a system.

7. CONCLUSION

Language communication is an inherently adaptive medium. One sees this clearly if one takes a problem to a lawyer and spends time trying to assimilate the related "legalese·. One also sees it in any conversation where a person is trying to convey a complicated idea, expressed in his own mental terms, to someone else. The listener must try to relate the words he hears to his own set of concepts. Language has, presumably, evolved to facilitate this sort of interaction. Therefore it is reasonable to expect that a good deal of the structure of language is in some sense set up to assist in this adaptive process. By the same token, studying lariguilge from an adaptive standpoint should provide a fresh perspective on how the various levels of linguistic structure interact.